Hi,
I've received a bug report pointing out that misuse of the public key input to ed25519_sha512_sign (and ed448_shake256_sign) is dangerous: If you sign the same message twice using the same private key, but the public key inputs differ, that can be exploited to recover the private key from the two signatures, similar to a classic DSA nonce reuse.
If we compare to how others are dealing with this, a similar issue was considered a bug in a Rust library (see https://rustsec.org/advisories/RUSTSEC-2022-0093.html). On the other end, we have the Golang standard library that represents an ed25519 private key as 64 bytes where the first half are the private key according to RFC 8032, and the second half are the private key. This is motivated by performance, see https://pkg.go.dev/crypto/ed25519.
Some options:
1. Document clearer that the public key argument *must* be the value produced by ed25519_sha512_public_key (e.g., immediately before the signing operation, or computed at key generation time and stored securely bundled with the private key).
Pro: Small change, flexible. Cons: Leaves the possibility for applications to shoot themselves in the feet in this way.
2. Make ed25519_sha512_sign check that the signature is valid, essentially, adding an
assert (ed25519_sha512_verify (...))
before returning.
Pro: Could catch a range of potential bugs and attacks. Cons: Much worse signing performance. Also, avoiding the particular attack reported now depends on the verify operation enforcing canonical representation of the public key.
3. Drop the public key input argument, recompute it for each signing operation.
Pro: Simpler interface, closer to RFC 8032. Cons: Much worse signing performance (but probably not as bad as option (2)). And one would have to think about backwards compatibility.
Note that both (2) and (3) can be implemented as simple wrappers around the current signing function, for applications that are prepared to accept the performance penalty.
Opinions? I'm leaning towards (1).
Regards, /Niels
PS. The reason this is an issue at all is that the public key is hashed together with the message in step 4 of the signing operation (see RFC 8032 5.1.6), but not in step 2. I imagine including the public key was considered to bring some subtle advantage in security; but maybe this should have been weighted differently against the additional api complexity in making an additional public key input highly desirable for performance.
Niels Möller nisse@lysator.liu.se writes:
Hi,
I've received a bug report pointing out that misuse of the public key input to ed25519_sha512_sign (and ed448_shake256_sign) is dangerous: If you sign the same message twice using the same private key, but the public key inputs differ, that can be exploited to recover the private key from the two signatures, similar to a classic DSA nonce reuse.
A private key owner should not trust someone else's copy of its own public key, should they? It is not that different from using someone else's nonce value (or someone else's private key).
A complete explanation of how the attack works would be good to have documented, I suspect it is easy to fall into this trap.
- Document clearer that the public key argument *must* be the value produced by ed25519_sha512_public_key (e.g., immediately before the signing operation, or computed at key generation time and stored securely bundled with the private key).
+1. I'd leave it at documenting the last part of your suggestion here: when you generate a EdDSA key pair, you should store the public key alongside the private key, and use that copy whenever it is needed. Don't throw away the public key (or be ready to re-generate it), and don't trust someone else's version of your public key.
Requiring the public key to be identical to ed25519_sha512_public_key() is hard for an API user without always calling that function, which I'm not sure is necessary.
/Simon
Simon Josefsson simon@josefsson.org writes:
A private key owner should not trust someone else's copy of its own public key, should they?
I wonder how this application error could possibly happen. If you get a signing request with message and a public key (e.g., you're an implementation of ssh-agent), you would typically use the given public key to look up the corresponding private key, and refuse the request if you have no corresponding key pair on file.
Maybe, if you're an ssh-agent with only a single private key, it might be tempting to skip the lookup and just use whatever public key was provided. That would then be broken and leak the private key.
I'd leave it at documenting the last part of your suggestion here: when you generate a EdDSA key pair, you should store the public key alongside the private key, and use that copy whenever it is needed.
Note that with Nettle, ed25519 key generation is selecting a random private key, e.g., reading /dev/random, and then just calling ed25519_sha512_public_key.
Requiring the public key to be identical to ed25519_sha512_public_key() is hard for an API user without always calling that function,
I think this requirement is essential if you want the signing process to be equivalent to what's specified in RFC 8032 (where the public key *is* recomputed for each signature). And then the typical way comply would be as you descibe above: compute the public key once, and store it securely together with the private key.
Regards, /Niels
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
Simon Josefsson simon@josefsson.org writes:
I'd leave it at documenting the last part of your suggestion here: when you generate a EdDSA key pair, you should store the public key alongside the private key, and use that copy whenever it is needed. Don't throw away the public key (or be ready to re-generate it), and don't trust someone else's version of your public key.
Suggested doc update:
--- a/nettle.texinfo +++ b/nettle.texinfo @@ -5732,6 +5732,21 @@ the message first and pass the short message digest as input to the sign and verify functions, however, the resilience to hash collision is then lost.
+One subtle detail is that the public key is prepended to the message in +the signature process, but the public key is @emph{not} included in the +nonce generation. For this reason, it is essential that the @var{pub} +argument to @code{ed25519_sha512_sign} and @code{ed448_shake256_sign} is +always the same as the output of +@code{ed25519_sha512_public_key}/@code{ed448_shake256_public_key}. If +one ever signs the same message twice using the same private key but +with two different values for the @var{pub} input, enough private +information is leaked to let an attacker forge signatures. + +For best performance, it is preferable to compute the public key only +once, when the keypair is generated. It should then be stored together +with the private key so that it cannot be tampered with, to ensure that +the same, correct, value is available for every signing operation. + @defvr Constant ED25519_KEY_SIZE The size of a private or public Ed25519 key, 32 octets. @end defvr
Does that sound right?
Regards, /Niels
Niels Möller nisse@lysator.liu.se writes:
Simon Josefsson simon@josefsson.org writes:
I'd leave it at documenting the last part of your suggestion here: when you generate a EdDSA key pair, you should store the public key alongside the private key, and use that copy whenever it is needed. Don't throw away the public key (or be ready to re-generate it), and don't trust someone else's version of your public key.
Suggested doc update:
...
+One subtle detail is that the public key is prepended to the message in +the signature process, but the public key is @emph{not} included in the +nonce generation. For this reason, it is essential that the @var{pub} +argument to @code{ed25519_sha512_sign} and @code{ed448_shake256_sign} is +always the same as the output of +@code{ed25519_sha512_public_key}/@code{ed448_shake256_public_key}. If +one ever signs the same message twice using the same private key but +with two different values for the @var{pub} input, enough private +information is leaked to let an attacker forge signatures.
But doesn't that assumes the private key was generated with Nettle, or something compatible with Nettle? Is that a reasonable assumption?
My concern was if someone generated a Ed25519 public/private key-pair using some other software. Applications using Nettle should use the (trusted) public key in all cases, rather than the output from ed25519_sha512_public_key(), or? Even if those should be identical in normal situations.
It would be interesting to understand the real-world applications where this scenarios happens.
/Simon
+For best performance, it is preferable to compute the public key only +once, when the keypair is generated. It should then be stored together +with the private key so that it cannot be tampered with, to ensure that +the same, correct, value is available for every signing operation.
@defvr Constant ED25519_KEY_SIZE The size of a private or public Ed25519 key, 32 octets. @end defvr
Does that sound right?
Regards, /Niels
Simon Josefsson simon@josefsson.org writes:
But doesn't that assumes the private key was generated with Nettle, or something compatible with Nettle? Is that a reasonable assumption?
I think it's quite reasonable.
The crucial thing is how the public key is computed from the private key. Nettle does that according to spec (RFC 8032, 5.1.5); at least it appears to agree with test vectors. So let's assume you generate keys with some other tool and import private and public key into an application using nettle.
Then either that other tool also computed the public key according to spec, and then it will be exactly the same as if computed by Nettle. Or it is out of spec in some way, maybe it uses non-canonical representation that happens to interop with other Ed25519-implementations. In the latter case, I think it should be fine to use that pubkey with nettle's signing function, as long as you use it every time, but to me that is a rather obscure corner case.
My concern was if someone generated a Ed25519 public/private key-pair using some other software. Applications using Nettle should use the (trusted) public key in all cases, rather than the output from ed25519_sha512_public_key(), or?
I agree that makes some sense. But... I think it would be prudent, in most cases, to check that private and public keys are consistent whenever a private key file (typically also including a public key) is loaded. If they are inconsistent, that's rather suspicious.
Another point to keep in mind is that in case the private key is used with an implementation that follows RFC 8032 by the letter, whatever pubkey was bundled with the private key is going to be ignored when signing, since it's simply not an input to the signing procedure. "The inputs to the signing procedure is the private key, a 32-octet string, and a message M of arbitrary size."
It would be interesting to understand the real-world applications where this scenarios happens.
I agree it would be interesting it know if there are known implementations/applications using differing pubkeys, and to what degree they interop at all.
Regards, /Niels
Niels Möller nisse@lysator.liu.se writes:
Suggested doc update:
--- a/nettle.texinfo +++ b/nettle.texinfo @@ -5732,6 +5732,21 @@ the message first and pass the short message digest as input to the sign and verify functions, however, the resilience to hash collision is then lost.
+One subtle detail is that the public key is prepended to the message in +the signature process, but the public key is @emph{not} included in the +nonce generation. For this reason, it is essential that the @var{pub} +argument to @code{ed25519_sha512_sign} and @code{ed448_shake256_sign} is +always the same as the output of +@code{ed25519_sha512_public_key}/@code{ed448_shake256_public_key}. If +one ever signs the same message twice using the same private key but +with two different values for the @var{pub} input, enough private +information is leaked to let an attacker forge signatures.
+For best performance, it is preferable to compute the public key only +once, when the keypair is generated. It should then be stored together +with the private key so that it cannot be tampered with, to ensure that +the same, correct, value is available for every signing operation.
@defvr Constant ED25519_KEY_SIZE The size of a private or public Ed25519 key, 32 octets. @end defvr
I've pushed this doc update, and I don't plan any further action.
Regards, /Niels
nettle-bugs@lists.lysator.liu.se
-
Niels Möller -
Simon Josefsson