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

OwnerAdam Petcher
TypeFeature
ScopeSE
StatusCandidate
Componentsecurity-libs / javax.crypto
Discussionsecurity dash dev at openjdk dot java dot net
EffortS
DurationM
Reviewed bySean Mullan
Endorsed byAlan Bateman
Created2018/03/07 15:14
Updated2018/08/07 15:34
Issue8199231

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 is a new signature scheme that does not replace ECDSA. Additional implementation goals are:

  1. 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.
  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

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

  1. All test vectors in RFC 8032 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 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 it 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 the 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 installing support through 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/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/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

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.