JEP 324: Key Agreement with Curve25519 and Curve448

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 Diffie-Hellman (ECDH) scheme. The primary goal of this JEP is an API and an implementation for this standard. Additional implementation goals are:

1. Develop a platform-independent, all-Java implementation with better performance than the existing ECC (native C) code at the same security strength.
2. Ensure that the timing is independent of secrets, assuming the platform performs 64-bit integer addition/multiplication in constant time. In addition, the implementation will not branch on secrets. These properties are valuable for preventing side-channel attacks.

Non-Goals

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

1. All test vectors in RFC 7748 pass.
2. 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.
3. 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 commonly-used 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 constant-time 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.

Large-number arithmetic will be performed using a new modular arithmetic library. This library will have two significant advantages over BigInteger:

1. 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.
2. 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 reduced-radix 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) Diffie-Hellman. 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:

1. It would be possible to perform field arithmetic using BigInteger. Initial prototyping indicates that BigInteger is around 10 times slower than the custom modular arithmetic library. For example, X25519 with BigInteger 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 constant-time multiplication, which would eliminate some of the side-channel resistance of these functions.
2. 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.
3. 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 10-100 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.