[curves] Ed25519 / EdDSA key leakage due to fragility in recommended nonce procedure
D. J. Bernstein
djb at cr.yp.to
Tue Jan 28 07:38:32 PST 2020
Greg Maxwell writes:
> If I sign with a mismatched or corrupted public key the signature
> algorithm will complete "successfully" but the signature will be
The standard defense against faults is for the signer to verify each
signature. This is, e.g., an option in FIPS 186-4 to "detect otherwise
undetected signature generation computation errors". There are types of
faults that this doesn't catch but by definition it catches invalid
signatures, and this includes a much broader class of faults than what
you're talking about.
Note that the standard definition of signing uses a secret key to sign a
message. Verification has a different input, the public key, which in
the fault scenario acts as a double-check on the signing process. The
public key is _not_ a separate input to signing.
Internally, EdDSA implementations normally include a cached copy of the
public key A inside the secret key. When you talk about signing with a
"mismatched" public key A, you seem to be alluding to some API that, in
violation of the standard definition of signing, takes A as a separate
(I must admit to some puzzlement as to how this happens. Surely anyone
designing a cryptographic API understands the standard concept of a
signature system, so there must be some _reason_ for violating the
concept, but I've been unable to find documentation explaining this
reason. For comparison, the smaller tweak of using _signed messages_
rather than _signatures_ directly addresses the well-documented "use the
message without noticing it's a forgery" error pattern.)
I agree that, for an API providing the public key as a separate input to
signing, there's a noticeable risk of a caller screwing up this input
and maybe even managing to pass tests. For EdDSA implementors forced to
provide such an API, I agree that hashing the extra input is a sensible
protection against this risk. Meanwhile the API should be fixed.
> Fortunately, except in extremely exotic usage the nonce generating
> function is externally indistinguishable so the behaviour can be
> changed without breaking protocol compatibility.
Right. Hypothetically, someone adding a unique-signature check as part
of verification could create an incompatibility with reasonable signing
options, but I think it's clear that this should be blamed on the
> For many hash functions (including all Merkle–Damgård style ones)
> inclusion of system parameters like algorithms or generators can be
> made runtime-costless by caching hash-function midstates if care is
> taken to pad values out to compression function boundaries.
There are _much_ bigger problems here than computation time. See
for an analysis of the security issues and ecosystem impact.
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 833 bytes
Desc: not available
More information about the Curves