Ed25519 vs ECDSA: How Deterministic Nonces Ended a Recurring Bug

In December 2010, a group calling themselves fail0verflow stood on stage at the Chaos Communication Congress and recovered Sony's ECDSA private key for signing PlayStation 3 code. Not by breaking the elliptic curve maths, which is fine, but because Sony's signing code used the same "random" nonce for every signature it ever produced. Two signatures with the same nonce is all it takes. 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 that this entire failure mode can't happen by construction. Worth understanding why, because the fix tells you something about how cryptographic engineering has matured: from "here is a correct algorithm, use it correctly" to "here is an algorithm that is hard to use incorrectly".

Why the nonce matters so much in ECDSA

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, and RNGs, it turns out, are one of the most reliably broken components in any given system: weak entropy at boot, VM snapshot restores, cloned containers, buggy PRNGs, or just a subtly wrong SecureRandom implementation shipped in an Android release for a couple of years.

The first fix: make ECDSA deterministic anyway

Before Ed25519 existed, the community's answer was RFC 6979: derive 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, so 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 the private key, the message hash, and some fresh randomness folded in through an internal DRBG, rather than from the RNG output directly. 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: determinism from day one

Ed25519, specified in RFC 8032 and designed by Daniel Bernstein and collaborators, took the same lesson and built it into the scheme 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 64-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, and 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 pure function of (key, message). There's no equivalent of the Sony bug to write here: you can't accidentally reuse a nonce because there's no nonce to manage in the API surface at all.

What you give up, and the honest caveat

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: if an attacker can physically glitch a device (a classic smartcard/HSM attack style) into producing a slightly corrupted signature and then get it to sign the exact same message again correctly, 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, and 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 a fairly academic concern next to "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 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, so 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.