Simon Josefsson simon@josefsson.org writes:
A complete explanation of how the attack works would be good to have documented, I suspect it is easy to fall into this trap.
I haven't looked that hard for references, but if I follow pointers from the rust CVE, I end up on the general attack is listed in https://en.wikipedia.org/wiki/Schnorr_signature#Key_leakage_from_nonce_reuse
Let's work out the details for Ed25519, starting from to RFC 8032, Sec 5.1.6. Inputs to the signature process are the private key and the message M. The public key A is derived from the private key (part of step 1).
Assume instead that A is an auxilliary input (like in Nettle). Say we sign the same message M twice with the same private key but with two different public key inputs A and A'.
In step 2, we compute a scalar r as
r = SHA-512(dom2(F, C) || prefix || PH(M)) mod L
This scalar, as well as the corresponding point R = [r]B (step 3), is the same for both signatures. This corresponds to a repeated nonce in DSA.
Next, we compute
k = SHA512(dom2(F, C) || R || A || PH(M)) mod L
in step 4, and for the second public key A' we instead get
k' = SHA512(dom2(F, C) || R || A' || PH(M)) mod L
When A != A', then almost surely k != k' (mod L), and hence (k - k') is invertible modulo L.
Finally, in step 5, we compute
S = (r + k * s) mod L
and
S' = (r + k' * s) mod L
where s is the secret scalar derived from the private key. The attacker knows S and S' (part of the two returned signatures) and k and k' (computed from A/A' and M as part of normal signature verification). So the secret scalar can be recovered as
s = (k - k')^{-1} (S - S') (mod L)
This is not technically the "ed25519 private key" (since that is defined as a string from which s is derived using a presumably oneway hash function), but it's just as good for the purpose of forging valid signatures.
I think one curious option to avoid the problem is to change the computation in step 2 to something like
r = SHA-512(dom2(F, C) || prefix || A || PH(M)) mod L
Then A and A' will give two distinct r and r', and the attack fails. This is technically breaking the spec, and will fail all official test vectors for the deterministic Ed25519 signature operation. But when the private key is kept secret, no verifier can notice the difference.
Then a signing oracle that lets the attacker choose the A input is about the same as a signing oracle that lets the attacker choose the M input.
But I wouldn't want to make a change like that without some rather serious review. (And it is certainly possible to tweak the computation of r to completely backdoor Ed25519; it's unfortunate that without knowing the private key, it is impossible to check that a signature was computed according to spec).
Regards, /Niels