EdDSA and Ed25519

Ed25519 was designed after a decade of ECDSA keys lost to bad random numbers. Its nonce is derived from the key and the message, so a signer with a broken random number generator is still safe. The best-known flaw since then has been in how libraries let it be called.

Rests on
The ECDLP on Curve25519 (or Curve448 for Ed448)
Standards
RFC 8032; added to FIPS 186-5 in 2023
Sizes
Ed25519: 32-byte public key, 64-byte signature
Best known attack
Pollard's rho, about 2126 for Ed25519. In practice, fault attacks and API misuse
Quantum
Broken by Shor's algorithm

The scheme

EdDSA is a Schnorr signature. A key is a 32-byte secret, hashed with SHA-512 into two halves: a scalar a, clamped as in X25519, and a 32-byte prefix. The public key A = aG is the encoded curve point. To sign a message M:

  1. Derive the nonce deterministically: r = SHA-512(prefix ‖ M) mod L.
  2. Compute R = rG.
  3. Compute the challenge k = SHA-512(R ‖ A ‖ M) mod L.
  4. Compute S = r + k·a mod L. The signature is R ‖ S, 64 bytes.

The verifier checks that SG = R + kA. Compared with ECDSA there is no modular inversion, the signature is a point and a scalar rather than two scalars, and the challenge hashes the public key, which binds each signature to one key.

The code that builds this page implements RFC 8032 directly, in twisted Edwards coordinates on the same field as X25519. It reproduces the first 3 Ed25519 test vectors of the RFC byte for byte. Here is test 1, the signature on the empty message:

e5564300c360ac729086e2cc806e828a84877f1eb8e5d974d873e065224901555fb8821590a33bacc61e39701cf9b46bd25bf5f0595bbe24655141438e7a100b

RFC 8032 section 7.1, test 1, recomputed at build time

Deterministic nonces

The nonce is the part of ECDSA that fails in practice: a repeated or biased k gives up the key. EdDSA derives r from the secret prefix and the message, so it cannot repeat across different messages without a SHA-512 collision, and it needs no random number generator at all. Signing "Pay Alice 10 coins" twice with the key of RFC test 2 produces the same 64 bytes both times, and the build checks it.

The cost is the one discussed on the ECDSA page: identical computations invite fault attacks, since a single glitched signature can be compared with a correct one on the same message. Hedged variants add randomness to the derivation for devices exposed to faults.

The double public key oracle

Determinism has a precondition that the API has to enforce: the public key hashed into the challenge must be the signer's own. In 2022 researchers at Mysten Labs reported that dozens of Ed25519 libraries exposed signing functions taking the secret key and the public key as separate arguments, and did not check that they matched. Their list reached 45 affected libraries by 2023, and the issue was later presented to NIST by Chalkias, Garillot and Nikolaenko.

If an attacker can get the same message signed twice, once with the right public key A and once with any other A′, the nonce r is the same, because it depends only on the prefix and the message. The challenge differs, because it hashes the public key. The two signatures share R and give two equations:

S1 = r + k1a,   S2 = r + k2a  ⇒  a = (S1 − S2) / (k1 − k2) mod L The same algebra as ECDSA nonce reuse

The build does exactly this with the key of RFC test 2, signing "Pay Alice 10 coins" once with its own public key and once with the public key of test 3:

R    = 6ba9af07d432e16f16d2939e626920fa1d51792a5cc6896ea9a174b036191efe
S1   = f3a72ea07060776b155c0670726ceae6077edbbc8df847770a1e2958ad24a30b
S2   = 4299bff83c958579b02999ae503090b15e12805afb094c1ec48658422e4b1901

a    = 012e502eb0249a255e1c827f3b6b6c7ea21f1371569f98e5707992d506d199c7

Two signatures on one message with different public keys, and the scalar recovered from them (little-endian encodings for R and S)

The recovered a satisfies aG = A. It is the signing scalar, and it is all a forger needs, since any nonce works: the build signs "Pay Mallory everything" with it, and the signature verifies under the victim's public key. The fix is to derive the public key from the secret inside the signing function, or to check that the two match.

Verification rules and batch verification

EdDSA's verification has more edge cases than its signing, because of the cofactor 8 and non-canonical encodings. Implementations have disagreed on whether to check SG = R + kA or 8SG = 8R + 8kA, whether to accept S ≥ L, and which encodings of R and A to accept. For most uses this does not matter. For consensus systems, where every node must reach the same verdict on every signature, it does. RFC 8032 requires rejecting S ≥ L, which prevents the malleability that affects ECDSA, and later work has pinned down the remaining rules.

Where it stands

Ed25519 is the default signature in SSH keys, in Signal, in Tor and in many blockchains, and it has been in FIPS 186-5 since 2023. Its classical security is that of the ECDLP on Curve25519, about 2126. Like every elliptic-curve scheme it falls to Shor's algorithm, and NIST IR 8547 proposes disallowing it after 2035 in favour of ML-DSA or SLH-DSA.

Primary sources

  1. S. Josefsson and I. Liusvaara, RFC 8032, Edwards-Curve Digital Signature Algorithm (EdDSA) (2017)
  2. D. J. Bernstein, N. Duif, T. Lange, P. Schwabe and B.-Y. Yang, "High-speed high-security signatures", Journal of Cryptographic Engineering 2 (2012)
  3. K. Chalkias, F. Garillot and V. Nikolaenko, "Taming the many EdDSAs", NIST Crypto Reading Club (2023)
  4. NIST FIPS 186-5, Digital Signature Standard (DSS) (2023)