Summary

Develop modern implementations of Elliptic Curve Diffie-Hellman (ECDH) and the Elliptic-Curve Digital Signature Algorithm (ECDSA).

Goals

The implementations of ECDH and ECDSA, along with the underlying Elliptic Curve Cryptography (ECC) operations in the JDK were initially developed in 2003. Since then, some significant technological advances have been made that affect ECC. In particular, efficient complete formulas have been developed for prime-order curves. By using these formulas, the implementation can be simpler, more efficient, and more resilient against side-channel attacks.

The desired properties of the improved implementation are (in decreasing priority):

1. The implementation will not branch on secrets, thus ensuring that it protects secrets from cache and timing side channels.
2. The implementation will be simplified by using modern formulas for ECC operations. This simplification will make certain types of bugs less likely, and may improve performance.
3. Performance should be at least as good as the current implementation for the same curve.
4. All Java implementation, to reduce the threat of memory errors.

This JEP will provide an improved implementation of the prime-order NIST curves used in TLS: secp256r1, secp384r1, and secp521r1. We will also modify the TLS implementation in SunJSSE to ensure that it still works when the new provider has higher priority than SunEC.

Non-Goals

• Curves other than secp256r1, secp384r1, and secp521r1 are out of scope.
• The implementation will not support arbitrary curve parameters, since some optimizations are curve-specific.
• Provider selection can be used to access the implementation in a more restrictive mode that prevents all branching. In this mode, implementation will not support any API methods that require conversion to/from BigInteger. It is not a goal to support interoperability with other providers that use BigInteger while in this mode.

Success Metrics

1. All existing ECDH and ECDSA regression tests (including test vectors) pass
2. Throughput (as measured by generated key pairs, derived keys, signatures, and verifications per second in the existing benchmarks) will compare favorably to the existing ECC implementation (on the same curve) on all platforms.
3. A statistical test (which needs to be developed) will show that the timing of the key agreement and signature operations does not vary with the private key.

Motivation

The primary motivation for improving the Elliptic Curve Cryptography (ECC) implementation is that threat models have changed in the last 20 years. Modern systems are expected to protect secrets from timing, cache, and similar side channels that can exploited by a co-located adversary. Side-channel resilient implementations of legacy ECC algorithms are increasingly common in competing crypto libraries like OpenSSL. The JDK should also have side-channel resilient implementations of these algorithms in order to be competitive.

Description: API

The new ECC implementation will be accessible in JCA in a new provider using existing algorithm names and curve parameter specifiers. Using a new provider allows for greater assurance that the branchless ECC implementation is being used when it is requested by the user. The new provider will have lower priority than SunEC in the default configuration. It will not be used unless this provider order is changed, or unless it is requested in the code.

The existing API for ECC private keys has some classes that specify private scalar values using BigInteger. There is no way to get a value out of a BigInteger (into, for example, a fixed-length array) without branching. So these classes will not be supported by the new provider, and any attempt to use them will result in an exception. The provider will still be fully functional through the use of KeyPairGenerator to produce ephemeral keys and PKCS8EncodedKeySpec for long-term keys. So no new API classes are planned.

The ECC operations in the new implementation will also be available by default in SunEC, without the restrictions on the use of BigInteger in the API. The use of these operations in SunEC has many of the benefits of the new implementation, but weaker security against side-channel attacks compared to the new provider.

The new provider will not include an AlgorithmParameters service for working with ECC domain parameters and their encodings. Algorithm parameters do not contain secrets, so the existing AlgorithmParameters service in SunEC can be used for this purpose.

Description: Implementation

There are two components of the implementation that are mostly independent: the elliptic curve point arithmetic and the finite field arithmetic. Each component must be constructed to avoid leaking secrets through branching.

For the EC point arithmetic, a good approach is to use the technique described in "Complete addition formulas for prime order elliptic curves" by Renes, Costello, and Batina. The formulas in this paper are relatively simple and efficient, and they include specializations for a=-3 as in the NIST prime curves. The paper provides formulas for point doubling and adding, and it is possible to use these to construct a branchless "double and add" loop using a branchless swap operation. This is similar to the Montgomery ladder used in the implementation of X25519 and X448. The same formulas can be used for all curves---the only thing that varies is one of the curve coefficients, and the finite field, which will have a different implementation for each curve.

For the finite field arithmetic, we can extend the existing field arithmetic library that was developed for X25519/X448, EdDSA, and Poly1305. The NIST primes have a similar structure to the primes used in these schemes, except they tend to have more terms, and the largest term doesn't have many useful factors. So we can continue to use the approach that was used in the Curve25519 field: use a few extra bits in the representation (e.g. 260 bits for the 256-bit field) and shift values around as necessary during reduction. The extra terms cause some extra operations during reduction (compared to more modern fields like in Curve25519), but all coefficients of these terms are +/-1, so these extra operations are all additions/subtractions.

This effort will require the implementation of 3-6 new finite field arithmetic classes, bringing the grand total up to 5-10 classes. These classes contain hand-optimized multiply/carry/reduce functions that maximize the use of primitive values to reduce temporary object allocation. They are somewhat cumbersome to develop, and very difficult to read and understand. A code generator will be used to reduce the development/maintenance burden for all these classes.

Alternatives

• A native implementation (such as the existing ECC code) may provide better performance. Initial prototyping indicates that a Java implementation using modern techniques is at least as fast as the existing C implementation. So Java should be fast enough.

• Users could use a third-party library that provides support for branchless ECC. The motivation for including this implementation in the JDK is described in the Motivation section, above.

Testing

Testing will include running all existing tests for ECDH, ECDSA, and TLS to ensure that the behavior is correct. Some subset of the existing TLS tests will also be executed with the provider order modified so that the new provider will be used. If necessary, small changes to the TLS implementation will be made in order to get these test to pass using the new provider. We will also take this opportunity to ensure that we have adequate test coverage, and develop new tests, if necessary.

Risks and Assumptions

The implementation will use the field arithmetic library developed for XDH, so there is the same risk of overflow and other bugs that produce incorrect results. This risk is mitigated by continuing to analyze and test the field arithmetic library.

There are no standards containing appropriate point arithmetic formulas, so the formulas used in the implementation will come from the academic literature. Because these formulas are relatively new and not standardized, there may be additional risk that they are incorrect and vulnerable.

There is some risk that the new implementation may be slower than the existing ECC implementation that is being replaced. Based on the performance of the initial prototype, this seems unlikely. If necessary, performance of the new implementation can be improved using high-level techniques like precomputation.

On Support for Additional Curves

The three curves implemented under this JEP were selected because they are the only curves allowed in TLS 1.3, other than Curve25519 and Curve448, which have branchless implementations developed under other JEPs. There is a preference in the applied cryptography community to use a small number of well-understood (and well-implemented) algorithms and parameter sets, as opposed to the great diversity that was preferred in the past. So there may not be any motivation to develop modern implementations of additional curves in the near future. Nonetheless, the implementation in this JEP could be extended to support additional curves.

Support for additional NIST-style prime curves could be added trivially by including the domain parameters of the curve and a new finite field implementation. The code generator developed for this JEP should make the finite field development relatively simple.

The initial implementation will likely use EC point arithmetic that is specialized for the NIST domain parameters (a = -3). Some commonly-used curves are very similar to NIST curves in that they are taken over a field defined by a well-structured prime, but they use different coefficients. For example, Koblitz curves use a=0. Support for these curves could be added by implementing more general point arithmetic, or by adding specializations for more coefficients. It would also be necessary to develop finite field implementations for any new field, again using the code generator.

The finite field arithmetic in the implementation depends on the fact that the field is defined by a prime that has some structure (e.g. 2^256 - 2^224 + 2^192 + 2^96 - 1). We would need to implement new techniques for primes without this structure, such as the primes used in Brainpool curves. Brainpool curves can directly reuse the point arithmetic used for the NIST curves.

Finally, none of the techniques implemented for this JEP will work for binary curves. Entirely new techniques for point and field arithmetic would need to be implemented in order to support these curves.