JEP 339: Edwards-Curve Digital Signature Algorithm (EdDSA)

Summary

Implement cryptographic signatures using the Edwards-Curve Digital Signature Algorithm (EdDSA) as described by RFC 8032.

Goals

EdDSA is a modern elliptic curve signature scheme that has several advantages over the existing signature schemes in the JDK. The primary goal of this JEP is an implementation of this scheme as standardized in RFC 8032. This new signature scheme does not replace ECDSA.

Additional implementation goals:

• Develop a platform-independent implementation of EdDSA with better performance than the existing ECDSA implementation (which uses native C code) at the same security strength. For example, EdDSA using Curve25519 at ~126 bits of security should be as fast as ECDSA using curve secp256r1 at ~128 bits of security.

• 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

• EdDSA will only be implemented in the SunEC provider. It is not a goal of this JEP to implement this standard in other providers.

• The API for EdDSA and the implementation in SunEC will not support arbitrary domain parameters. Typical uses of EdDSA only use standardized parameter sets such as Ed25519 and Ed448 which can be specified using identifiers, and support for arbitrary curve parameters is not typically needed. The EdDSA API should permit, through extension, the specification of arbitrary domain parameters. Such extension is outside of the scope of this JEP.

• Integration of EdDSA with JSSE for TLS 1.3 will be completed in a follow-on enhancement after this JEP is complete.

Success Metrics

• All test vectors in RFC 8032 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 will show that the timing of the signing operation does not vary with the private key.

Motivation

EdDSA is in demand due to its improved security and performance compared to other signature schemes, and is already supported in many other crypto libraries such as OpenSSL and BoringSSL. This signature scheme is an optional component of TLS 1.3, but is one of only three signature schemes that are allowed in TLS 1.3. Some users may have EdDSA certificates, and may have a strong preference to use EdDSA. These users will appreciate the ability to use EdDSA without having to use a third-party library. An additional benefit of developing an implementation of EdDSA is that it allows us to more easily develop and test the support of this algorithm in TLS 1.3.

Description

New Signature, KeyFactory, and KeyPairGenerator services will be added to the SunEC provider to support EdDSA. New classes and interfaces will be added to the API to represent EdDSA keys, and new standard algorithm names will be added to describe EdDSA signature schemes. The API and implementation will support all EdDSA variants (pure, prehashed, and context).

The point arithmetic will use the double and add operations defined in RFC 8032 along with a branch-free conditional assignment operation to prevent side-channel attacks. The field arithmetic will use the modular arithmetic library that was developed for XDH (JEP 324). The combined implementation will not leak secrets into timing and cache side channels, under some reasonable assumptions on the behavior of the JVM and hardware.

The API will reuse the NamedParameterSpec class developed for XDH in order to describe curve domain parameters and EdDSA variants. New classes and interfaces will be developed for Edwards curve points, EdDSA keys, and signature parameters which include context information.

Example API usage:

// example: generate a key pair and sign
KeyPairGenerator kpg = KeyPairGenerator.getInstance("Ed25519");
KeyPair kp = kpg.generateKeyPair();
// algorithm is pure Ed25519
Signature sig = Signature.getInstance("Ed25519");
sig.initSign(kp.getPrivate());
sig.update(msg);
byte[] s = sig.sign();

// example: use KeyFactory to contruct a public key
KeyFactory kf = KeyFactory.getInstance("EdDSA");
boolean xOdd = ...
BigInteger y = ...
NamedParameterSpec paramSpec = new NamedParameterSpec("Ed25519");
EdECPublicKeySpec pubSpec = new EdECPublicKeySpec(paramSpec, new EdPoint(xOdd, y));
PublicKey pubKey = kf.generatePublic(pubSpec);

Alternatives

• A native implementation (such as the existing ECC code) may provide better performance. The performance of EdDSA should be similar to that of XDH, so a Java implementation will likely be fast enough.

• It is possible to implement this signature scheme using the point arithmetic in the existing ECC code, but this approach does not provide all of the security/performance benefits of RFC 8032.

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

• It may be technically possible to use the existing ECC API classes to specify EdDSA keys and parameters, but this would present a significant risk of key misuse. More information can be found in JDK-8166597.

Testing

Testing will include the test vectors from RFC 8032, augmented with tests for corner cases such as small subgroups and non-canonical values.

Risks and Assumptions

The EdDSA 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.