JEP draft: Improved ECC Implementation

OwnerAdam Petcher
TypeFeature
ScopeJDK
StatusDraft
Componentsecurity-libs / javax.crypto
EffortS
DurationM
Created2018/06/07 20:24
Updated2018/09/11 13:16
Issue8204574

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

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

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 fixed-length 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 long-term 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 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

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.