Hi Michael,
Good points! See comments inlines.
On 8/10/2017 3:20 PM, Michael StJohns wrote:
Hi Xuelei -
Great analysis.
Some comments in line.
On 8/10/2017 3:10 PM, Xuelei Fan wrote:
Hi,
I want to extend the comment a little bit.
1. The background
A elliptic curve is determined by either an equation of form
y^2 = x^3 + ax + b (1) [Weierstrass form]
or
y^2 + xy = x^3 + ax^2 + b. (2)
However, some other forms may also be used. For example:
y^2 = x(x-1)(x-r) (3)
or
By^2 = x^3 + Ax^2 + x (4) [RFC 7748, Montgomery curve]
x^2 + y^2 = 1 + dx^2y^2 (5) [RFC 7748, Edwards curve]
In general, any elliptic curve can be written in Weierstrass form (1)
or (2). That's, Montgomery curve and Edwards curve can be expressed
in Weierstrass form.
2. Where we are now?
In JDK, an elliptic curve is defined in the Weierstrass form
((1)/(2)). See java.security.spec.EllipticCurve:
EllipticCurve(ECField field, BigInteger a, BigInteger b)
In theory, the existing APIs can be used for RFC 7748, by converting
the Montgomery curve and Edwards curve to the Weierstrass form.
However, the conversion can be misleading and complicate the
implementation significantly. For example, before using a point
Weierstrass form (x, y), the implementation need to convert it to
Montgomery curve (x', -) so as to use the fully potential of RFC
7748. The curves returned in public APIs need to use (x, y), while
the implementation need to use (x', y'). It's very confusing and the
compatibility impact could be significant. For example:
public something(ECPublicKey ecPublicKey) {
// Problem: If no other information, it is unclear
// whether the ecPublicKey can be used for a particular
// signature verification or not when the RFC 7748/8032
// get supported.
// Problem: an old application may use ecPublicKey for
// the old style operation, even the ecPublicKey is supposed
// to be x25519. It's not easy to control the behavior in
// legacy application code, and may introduce unexpected
// security issues.
}
public KeyAgreement getKeyAgreement(AlgorithmParameterSpec aps) {
// Problem: the code bellow should be comment in the current
// code. However, the ECParameterSpec may not be able to use
// for the old style "EC" key agreement.
//
// JDK crypto provider can take special action to avoid this
// issue in the JCA/JCE implementation. But it cannot be
// granted other provider can do this as well, and old
// provider may run into problems as well.
if (aps instance of ECParameterSpec) {
return KeyAgreement.getInstance("EC");
}
}
What's the problem with ECPublicKey/ECPrivateKey/ECKey? It's mainly
about the ECParameterSpec:
ECParameterSpec ECKey.getParams()
and ECParameterSpec is using java.security.spec.EllipticCurve. This
design makes it pretty confusing to use ECPublicKey/ECPrivateKey/ECKey
for RFC 7748 (Edwards curve form and Montgomery curve form).
Can EllipticCurve be extended to support more forms? The
java.security.spec.EllipticCurve defines two methods to get the
coefficients of Weierstrass form.
public BigInteger getA()
public BigInteger getB()
The 'A' and 'B' may not exist in other forms, for example the
(3)(4)(5) forms above. While, the spec might be able to be updated by
throwing UnsupportedOperationException for getA() and getB() for the
(3)(4)(5) forms, and define new extended classes for new forms, like:
public MCEllipticCurve extends EllipticCurve // Montgomery curve
public EDEllipticCurve extends EllipticCurve // Edwards curve
Instead of converting, I was thinking about mapping. E.g. Montgomery A
and B matches the A and B of the curve. But the "x" of the Montgomery
point is just the "x" of the ECPoint with the "y" left as null. For
Edwards, it looks like you would map "d" to A. For [3] I'd map "r" to
A. I'd leave B as null for both- no reason to throw an unsupported
exception as the code generally has a clue about what types of keys
they're dealing with (or we provide a marker so they can figure it out).
The conversion in and out for points is a conversion from little endian
to big endian and vice versa, but that only has to be done if you're
importing or exporting a parameter set and that's an implementation
issue not an API issue.
Basically, all the math is BigIntegers under the hood. The curve25519
RFC specifies an implementation that's little endian, but the actual
math is just math and things like the public key is really just a
BigInteger.
Old code would just continue to work - since it would not be using the
new curves. New code would have to look for the curve type marker (e.g.
the ECField) if there was the possibility of confusion.
I understand your points. The mapping may be confusing to application
developers, but no problem for new codes if following the new coding
guideline. I'm not very sure of the old code, for similar reason to use
the converting solution.
For example, an Edwards curve form of the SubjectPublicKeyInfo field in
a X.509 cert is parsed as X509EncodedKeySpec, and "EC" KeyFactory is
used to generate the ECPublicKey. The algorithm name of the ECPublicKey
instance is "EC", and the parameter is an instance of ECParameterSpec.
Somehow, the ECPublicKey leave the key generation environment, and the
curve OID is unknown in the new environment. Then the public could be
used improperly. In the past, it's fine as the only supported form is
Weierstrass form, there is no need to tell the curve forms in a crypto
implementation. However, when a new form is introduces, identify the EC
form of a key is an essential part for the following crypto operations.
Old providers or codes may not be able to tell the form, as may result
in compatibility issues.
However, I'm not very sure of the compatibility impact (see above).
3. Where we are not now?
Using named curves is popular. There is a ECGenParameterSpec class
using named curves:
ECGenParameterSpec ecgp =
new ECGenParameterSpec(secp256r1);
KeyPairGenerator kpg = KeyPairGenerator.getInstance("EC");
kpg.initialize(ecpg);
KeyPair kp = kpg.generateKeyPair();
ECPublicKey pubKey = (ECPublicKey)kp.getPublic();
String keyAlgorithm = pubKey.getAlgorithm(); // "EC"
However, it is used for key generation only. Once the keys are
generated, there is no public API to know the name of the curve in
ECKey. ECKey.getAlgorithm() will return "EC" only. If it is required
to known whether a key is of a named curve, the solution is not
straightforward.
This ties back to "getEncoded()" representations. Under the hood, if
you do a getEncoded() there's a "which name does this parameter set
match up to" search which checks various tables for an OID and uses that
in an X.509 SPKI output object. On input, the table lookup has to see
whether or not it understands the curve OID (or the key type OID -
depending).
To deal with this without having to modify the internal parameter tables
I currently match keys against parameter sets that have known OIDs.
I see.
4. A general proposal
Support named curves could be a solution for #2 and #3 concerns above.
For named curves, the parameters are defined explicitly. So, it is
REQUIRED to have the public APIs for named curves' parameters any
more. It can be something hidden in the implementation layer. The key
pair generation may looks like:
KeyPairGenerator kpg =
KeyPairGenerator.getInstance("ECWithSecp256k1");
KeyPair kp = kpg.generateKeyPair();
PublicKey pubKey = kp.getPublic();
String keyAlgorithm = pubKey.getAlgorithm(); // "ECWithSecp256k1"
As no explicit parameters is required, the EllipticCurve issue for
Edwards curve form and Montgomery curve form in #2 is not a issue any
more here.
The compatibility impact is limited as the name "ECWithSecp256k1" is
not used in the past, and the Weierstrass form APIs, like
ECKey/ECParameterSpec/EllipticCurve, are not necessarily to be used in
this solution.
The benefits: simplify the APIs for named curves (including the
Weierstrass form), and simplify the support of named curves for
Edwards curve form and Montgomery curve form.
The disadvantages: no support of arbitrary curves (no surprise as this
is a named curve solution), and new learn curve to use this new solution.
Right now there are 3 major APIs (JCA, PKCS11 and Microsoft CSP) and at
least 4 major representational domains (Raw, PKIX, XML and JSON). In
the current situation, I can take a JCA EC Public key and convert it to
pretty much any of the other APIs or representations. For much of the
hardware based stuff (ie, smart cards), I go straight from JCA into raw
and vice versa. Assuming you left the "getEncoded()" stuff in the API
and the encoding was PKIX, I'd have to encode to PKIX, decode the PKIX
to extract the actual raw key or encode a PKIX blob and hope that the
KeyFactory stuff actually worked.
It's not just support of arbitrary keys, but the ability to convert
things without having to do multiple steps or stages.
Good point! It would be nice if transaction between two formats could
be done simply. Using X.509 encoding is doable as you said above, but
maybe there are spaces to get improvements.
I need more time to think about it. Please let me know if any one have
a solution to simplify the transaction if keeping use the proposed named
curves solution.
Your solution would probably work reasonably well for TLS or IPSEC - but
would not work well for anything else.
Properly a little bit more than TLS and IPSEC, but definitely not
everything else.
5. Can be more aggressive?
It looks amazing to support arbitrary curves for Edwards curve form
and Montgomery curve form, as JDK did for Weierstrass form. However,
because of the compatibility impact (see #2), a new set of algorithms
names, interfaces and specs may be required. It could be overloaded
if the requirements are not so strong in practice. If arbitrary
curves support is strong, it can be re-considered in the future.
Per my understanding, supporting named curves and arbitrary curves can
be two things, and can be considered in different stages. However, the
design needs to take care of the potential conflicts between the two
solutions.
As I understand it, the JEP process takes some time and right now
proposed changes *might* make it into JDK10? Do you really want to
do multiple JEPs to handle multiple new Edwards and Montgomery curves?
It really depends per my understanding. If I have a good idea, I would
do it all in one JEP. Otherwise, I may do it step by step so that the
high priority requirements are not delayed before I have a mature
solution to meet more requirements.
If we can hide most of this under the current EC covers, then the
implementations can just implement the plugin interface and do that now.
You are right. If everything goes smoothly, no public APIs update is
expected. It's a kind of a provider implementation job, although some
external algorithm names may be defined (like "ECWithSecp256k1" or
"XDH") for this proposal.
Thanks & Regards,
Xuelei
