Details

JEP

Status: Closed

P3

Resolution: Delivered

Adam Petcher

Feature

Open

SE


S

M

324
Description
Summary
Implement key agreement using Curve25519 and Curve448 as described in RFC 7748.
Goals
RFC 7748 defines a key agreement scheme that is more efficient and secure than the existing elliptic curve DiffieHellman (ECDH) scheme. The primary goal of this JEP is an API and an implementation for this standard. Additional implementation goals are:
 Develop a platformindependent, allJava implementation with better performance than the existing ECC (native C) code at the same security strength.
 Ensure that the timing is independent of secrets, assuming the platform performs 64bit integer addition/multiplication in constant time. In addition, the implementation will not branch on secrets. These properties are valuable for preventing sidechannel attacks.
NonGoals
RFC 7748 will only be implemented in the SunEC provider. It is not a goal of this JEP to implement this standard in other providers.
The implementation in SunEC will not support arbitrary domain parameters. The JCA API should permit, through extension, the specification of arbitrary domain parameters. Such extension is outside of the scope of this JEP.
Success Metrics
 All test vectors in RFC 7748 pass.
 Throughput (as measured by derived keys per second in the existing key agreement benchmark) will compare favorably to the existing ECC implementation (of similar security strength) on all platforms.
 A statistical test (which needs to be developed) will show that the timing of the key agreement operation does not vary with the private key.
Motivation
Cryptography using Curve25519 and Curve448 is in demand due to their security and performance properties. Key exchange using these curves is already supported in many other crypto libraries such as OpenSSL, BoringSSL, and BouncyCastle. This key exchange mechanism is an optional component of TLS 1.3, and is enabled in earlier TLS versions through commonlyused extensions.
Description
The X25519 and X448 functions will be implemented as described in RFC 7748, and these functions will be used to implement new KeyAgreement
, KeyFactory
, and KeyPairGenerator
services in the existing SunEC provider. The implementation will use the constanttime Montgomery ladder method described in RFC 7748 in order to prevent side channel attacks. The implementation will ensure contributory behavior by comparing the result to 0 as described in the RFC.
Largenumber arithmetic will be performed using a new modular arithmetic library. This library will have two significant advantages over BigInteger
:
 Most operations will be performed in constant time. Some operations may vary with the size of their operands if those operands are not secrets in any relevant algorithm. For example, timing of exponentiation will vary with the size of the exponent, but the exponent value is not a secret in RFC 7748. The API documentation of this library will describe the timing behavior of each operation.
 Performance will be improved by avoiding carry operations and leveraging properties of the specific finite fields used in the EC operations.
This new library will be in an internal JDK package, and will only be used by new crypto algorithms. We expect to use it in EdDSA (signatures using Curve25519 and Curve448) and Poly1305 (message authentication) implementations in the near future. The library uses a reducedradix representation inspired by the one in the EdDSA paper.
Because the arithmetic avoids carry operations, it is possible that it will overflow and produce incorrect results if it has bugs or it is used incorrectly. For example, addition operations don't carry, so a limited number (typically one) of addition operations can be performed before each multiplication operation. The library will contain defenses against misuse (e.g., throw an exception if too many additions occur), and it must be carefully tested to ensure that it doesn't overflow.
API
The JCA API for RFC 7748 will use the name "XDH" to identify all services related to this mechanism (KeyAgreement
, KeyPairGenerator
, KeyFactory
, etc.). The algorithm names "X25519" and "X448" will also be defined to mean XDH using Curve25519 and Curve448, respectively. This allows a convenient shorthand (e.g., KeyPairGenerator.getInstance("X448")
) that also makes it easier to locate a provider that supports the desired curve. Names like "X25519" and "X448" should not simply be aliases of "XDH"the service returned for these names should be initialized with the correct curve, and it may reject any keys that use a different curve.
AlgorithmParameterSpec
:
A new class called NamedParameterSpec
will be used to specify which curve is used (X25519 or X448). This class uses a single standard name to specify a set of parameters, and it is intended to be reused by other algorithms that make use of named parameters. For example, it could be used for named groups in (finite field) DiffieHellman. NamedParameterSpec
will be inserted into the class hierarchy above ECGenParameterSpec
, so that ECGenParameterSpec
will also be a NamedParameterSpec
.
KeySpec
:
The new class XECPublicKeySpec
can be used to specify public keys. This class has a BigInteger
member which holds the u
coordinate of the point. The new class XECPrivateKeySpec
can be used to specify private keys. This class has a byte array member which holds the (encoded) k
input to the X25519 and X448 functions described in RFC 7748. Both of these KeySpec
classes have an AlgorithmParameterSpec
member that specifies the curve and other algorithm parameters.
The existing X509EncodedKeySpec
class can also be used for public keys. The existing PKCS8EncodedKeySpec
class can also be used for private keys.
Key
interfaces:
New interfaces XECPublicKey
and XECPrivateKey
will be added to provide access to information contained within key objects. The representation of key data in these interfaces will be identical to the representation in XECPublicKeySpec
and XECPrivateKeySpec
. Both interfaces will extend from the new interface XECKey
, which will provide access to the AlgorithmParameterSpec
which defines the curve and other algorithm parameters.
Example API usage:
KeyPairGenerator kpg = KeyPairGenerator.getInstance("XDH");
NamedParameterSpec paramSpec = new NamedParameterSpec("X25519");
kpg.initialize(paramSpec); // equivalent to kpg.initialize(255)
// alternatively: kpg = KeyPairGenerator.getInstance("X25519")
KeyPair kp = kpg.generateKeyPair();
KeyFactory kf = KeyFactory.getInstance("XDH");
BigInteger u = ...
XECPublicKeySpec pubSpec = new XECPublicKeySpec(paramSpec, u);
PublicKey pubKey = kf.generatePublic(pubSpec);
KeyAgreement ka = KeyAgreement.getInstance("XDH");
ka.init(kp.getPrivate());
ka.doPhase(pubKey, true);
byte[] secret = ka.generateSecret();
Alternatives
A few alternatives related to the implementation were considered:
 It would be possible to perform field arithmetic using
BigInteger
. Initial prototyping indicates thatBigInteger
is around 10 times slower than the custom modular arithmetic library. For example, X25519 withBigInteger
takes around 2.5 ms, vs 0.25 ms for the custom library run on the same platform in initial testing. Also,BigInteger
does not have constanttime multiplication, which would eliminate some of the sidechannel resistance of these functions.  A native implementation (such as the existing ECC code) may provide better performance. Initial prototyping shows that an implementation in Java is fast enough for typical purposes. For example, X25519 (in Java) takes around 0.25 ms vs the secp256r1 group operation (in C) which takes around 1 ms on the same platform. So initial results suggest that a Java implementation should be fast enough.
 It is possible to implement this key agreement using the existing ECC code, but this approach does not provide all of the security/performance benefits of RFC 7748.
Testing
Testing will include the test vectors from RFC 7748. These vectors include one million iterations of the X25519 and X448 functions, which will take around 15 minutes to complete. If we want to run these regularly, we can parallelize them by splitting them into batches of 10100 thousand each.
Testing the arithmetic library will be slightly more challenging, because the conditions that cause overflow may not be likely to occur naturally. The representations used for Curve25519 and Curve448 should be developed along with rigorous mathematical proofs that they do not overflow. These proofs will contain boundary conditions related to every underlying operation (add, multiply, carry, reduce) that can be incorporated into regression tests.
Risks and Assumptions
A significant risk is the complexity and subtlety of the modular arithmetic implementation. This risk can be mitigated by developing a rigorous proof of correctness for the arithmetic, and thorough testing.
Attachments
Issue Links
 is blocked by

JDK8181611 Test plan for Key Agreement with Curve25519 and Curve448
 Resolved
 relates to

JDK8171277 Elliptic Curves for Security in Crypto
 Resolved

JDK8181594 Efficient and constanttime modular arithmetic
 Resolved
 links to