Articles / Cryptography

1155 words

  • cryptography
  • ed25519
  • ecdsa
  • go
  • nonce-reuse
  • digital-signatures

Why Ed25519 Can't Leak Your Key the Way ECDSA Can

Two ECDSA signatures made with the same nonce are enough to recover the private key. In December 2010, a group calling themselves fail0verflow stood on stage at the Chaos Communication Congress and did exactly that to Sony's PlayStation 3 code-signing key.

They didn't break the elliptic curve maths, which is fine. Sony's signing code used the same "random" nonce for every signature it ever produced. Three years later the same bug, in a different guise, drained Bitcoin from Android wallets after a flaw in Java's SecureRandom caused it to repeat itself under certain conditions. Same root cause, different decade, different victim.

Ed25519 exists partly because of bugs like this. It's not just "ECDSA but with a nicer curve": it changes how the per-signature nonce is generated so this entire failure mode can't happen by construction.

The fix says something about how cryptographic engineering has matured. We've gone from "here is a correct algorithm, use it correctly" to "here is an algorithm that is hard to use incorrectly".

Why one repeated nonce hands over the ECDSA key

ECDSA signing takes a private key d, a hash of the message h, and a fresh random value k (the nonce) for every single signature. Roughly:

R = k * G                  (G is the curve generator)
r = R.x mod n
s = k^-1 * (h + r*d) mod n

The signature is (r, s). Notice that k never appears in the output, only its effects do. That's the point: it's supposed to be a one-time secret that blinds the relationship between the message hash and the private key. If k is properly random and never reused, the scheme is sound.

The moment two different messages get signed with the same k, though, you can eliminate it algebraically. Given (r, s1) over hash h1 and (r, s2) over hash h2 (same r is the tell, since r depends only on k):

s1 - s2 = k^-1 * (h1 - h2) mod n
      k = (h1 - h2) * (s1 - s2)^-1 mod n

Once you have k, recovering the private key is one more step:

d = (s1*k - h1) * r^-1 mod n

That's it. No lattice reduction, no factoring, nothing clever. Just two equations and two unknowns. A short Go program makes the point better than the algebra does:

package main

import (
	"crypto/elliptic"
	"fmt"
	"math/big"
)

// recoverKey demonstrates the classic ECDSA nonce-reuse key recovery.
// Given two signatures that share the same k, it solves for k, then d.
func recoverKey(curve elliptic.Curve, r, s1, s2, h1, h2 *big.Int) *big.Int {
	n := curve.Params().N

	// k = (h1 - h2) / (s1 - s2) mod n
	hDiff := new(big.Int).Sub(h1, h2)
	hDiff.Mod(hDiff, n)
	sDiff := new(big.Int).Sub(s1, s2)
	sDiff.Mod(sDiff, n)
	sDiffInv := new(big.Int).ModInverse(sDiff, n)
	k := new(big.Int).Mul(hDiff, sDiffInv)
	k.Mod(k, n)

	// d = (s1*k - h1) / r mod n
	sk := new(big.Int).Mul(s1, k)
	sk.Mod(sk, n)
	num := new(big.Int).Sub(sk, h1)
	num.Mod(num, n)
	rInv := new(big.Int).ModInverse(r, n)
	d := new(big.Int).Mul(num, rInv)
	d.Mod(d, n)
	return d
}

func main() {
	// Values here would come from two real signatures sharing an r.
	curve := elliptic.P256()
	n := curve.Params().N
	fmt.Println("curve order bits:", n.BitLen())
}

That's roughly forty lines of arithmetic standing between "we found a nonce collision in your signature log" and "we have your private key". Every ECDSA implementation used to lean entirely on the RNG to prevent this.

RNGs, it turns out, are one of the most reliably broken components in any given system. The usual suspects:

  • weak entropy at boot
  • VM snapshot restores
  • cloned containers
  • buggy PRNGs
  • a subtly wrong SecureRandom implementation shipped in an Android release for a couple of years

The retrofit: derive the ECDSA nonce instead of rolling it

Before Ed25519 existed, the community's answer was RFC 6979. It derives k deterministically from the private key and the message hash using HMAC, rather than pulling it from the system RNG at all. Same private key, same message, same nonce, every time, on every machine.

Crucially, the derivation runs the private key through HMAC first. An attacker who only sees signatures can't predict or influence k without already knowing the key.

This closes the nonce-reuse hole without changing the signature algorithm or the curve. It's retrofittable, which is exactly why it exists: there was a huge installed base of ECDSA infrastructure that nobody was going to replace overnight.

Go's own crypto/ecdsa package moved to a similar idea a few years ago, using what the implementation calls "hedged" signing. The nonce is derived from a combination of three things, folded together through an internal DRBG rather than taken from the RNG output directly:

  • the private key
  • the message hash
  • some fresh randomness

You get RFC 6979's protection against a broken RNG, while still keeping some randomness in the mix as a defence against certain fault-injection attacks on purely deterministic schemes (more on that below). Application code calling ecdsa.SignASN1 doesn't need to know or care; it's a change entirely inside the library.

Ed25519 has no nonce for you to get wrong

Ed25519, specified in RFC 8032 and designed by Daniel Bernstein and collaborators, built the same lesson in from the start rather than bolting it on afterwards. There's no separate "nonce generation" step that a careless implementer can get wrong by calling the wrong random function.

The 32-byte private key seed is hashed once with SHA-512 to produce two 32-byte halves:

  • one becomes the actual scalar used as the signing key
  • the other (the "prefix") is mixed with the message itself to produce the nonce for that signature
r = SHA512(prefix || M) mod L

Sign the same message twice with the same key and you get the exact same signature both times. That's a deliberate design choice, not an oversight. It means there is no RNG call anywhere in the signing path that a bad platform, a cloned VM, or a broken container image can starve of entropy.

In Go this is about as plain as cryptographic code gets:

package main

import (
	"crypto/ed25519"
	"crypto/rand"
	"fmt"
)

func main() {
	pub, priv, err := ed25519.GenerateKey(rand.Reader)
	if err != nil {
		panic(err)
	}

	msg := []byte("deploy artifact sha256:abcd1234")
	sig := ed25519.Sign(priv, msg)

	if !ed25519.Verify(pub, msg, sig) {
		panic("signature does not verify")
	}
	fmt.Printf("signature: %x\n", sig)
}

Randomness is only ever needed once, at key generation. After that the signing path is a pure function of (key, message).

Hang on, where did the Sony bug go? There's no equivalent of it to write here. You can't accidentally reuse a nonce because there's no nonce to manage in the API surface at all.

Determinism has one real weakness: fault injection

Determinism isn't free of trade-offs, even if it's a clear net win for the nonce-reuse problem specifically. A signing oracle that always produces the same output for the same input is, in principle, more exposed to certain fault-injection attacks.

The attack goes like this:

  1. An attacker physically glitches a device (a classic smartcard/HSM attack style) into producing a slightly corrupted signature.
  2. They get it to sign the exact same message again, correctly.
  3. Comparing the two can sometimes leak key material, in a way that a fresh random nonce each time would have prevented.

This is a real line of research (see Romailler and Pelissier's differential fault attack work on deterministic ECDSA/EdDSA), not a theoretical footnote. It's the reason "hedged" signing exists as a middle ground: derive the nonce deterministically as a baseline, but still fold in some fresh randomness so an attacker can't force a repeat under identical conditions. Go's ecdsa package takes exactly that hedged approach rather than pure RFC 6979.

For most software that isn't defending against someone with a fault-injection rig pointed at a chip, this is fairly academic. Compare it with "the RNG on this container image comes up in a predictable state after a snapshot restore", which is a bug class Ed25519 removes outright.

ECDSA isn't going anywhere, but new systems have a better default

ECDSA over P-256 remains extremely widely deployed, has FIPS 186-5 blessing, and is what most HSMs and smartcards have supported for the last two decades. It isn't going anywhere.

But for new systems where you get to choose, Ed25519 gives you a signature scheme where an entire, historically well-populated category of catastrophic key-recovery bugs simply doesn't have anywhere to live.

← All articles