JEP draft: Improved ECC Implementation
Owner  Adam Petcher 
Type  Feature 
Scope  JDK 
Status  Draft 
Component  securitylibs / javax.crypto 
Effort  S 
Duration  M 
Created  2018/06/07 20:24 
Updated  2018/09/11 13:16 
Issue  8204574 
Summary
Develop modern implementations of Elliptic Curve DiffieHellman (ECDH) and the EllipticCurve 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 primeorder curves. By using these formulas, the implementation can be simpler, more efficient, and more resilient against sidechannel attacks.
The desired properties of the improved implementation are (in decreasing priority):
 The implementation will not branch on secrets, thus ensuring that it protects secrets from cache and timing side channels.
 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.
 Performance should be at least as good as the current implementation for the same curve.
 All Java implementation, to reduce the threat of memory errors.
This JEP will provide an improved implementation of the primeorder 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.
NonGoals
 Curves other than secp256r1, secp384r1, and secp521r1 are out of scope.
 The implementation will not support arbitrary curve parameters, since some optimizations are curvespecific.
 Some providers may support private keys represented using BigInteger (via ECPrivateKey or ECPrivateKeySpec), but not encoded private keys. It is not a goal for the new implementation to interoperate with these providers. SunEC does support encoded private keys, so the new implementation will interoperate with SunEC.
 It may be possible to support the BigInteger interface by using a new subclass of BigInteger that only supports branchfree operations. This is out of scope for this JEP, but it may be considered separately in the future.
Success Metrics
 All existing ECDH and ECDSA regression tests (including test vectors) pass
 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.
 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 colocated adversary. Sidechannel resilient implementations of legacy ECC algorithms are increasingly common in competing crypto libraries like OpenSSL. The JDK should also have sidechannel resilient implementations of these algorithms in order to be competitive.
Description
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. Unfortunately, this means that users must opt in to using the new implementation by modifying the provider list in the 'java.security' file or by specifying the provider name in the code. We can explore ways for this implementation to be used by default in the future.
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 fixedlength array) without branching. So these classes will not be supported by the new implementation, and any attempt to use them will result in an exception. The implementation will still be fully functional through the use of KeyPairGenerator
to produce ephemeral keys and PKCS8EncodedKeySpec
for longterm keys. So no new API classes are planned.
The initial implementation produced using this JEP 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.
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 curvesthe 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 256bit 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 36 new finite field arithmetic classes, bringing the grand total up to 510 classes. These classes contain handoptimized 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 thirdparty 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 (with the new provider enabled) to ensure that the behavior is correct. 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.