[curves] Ed25519 / EdDSA key leakage due to fragility in recommended nonce procedure

[D. J. Bernstein]

Greg Maxwell writes:
> If I sign with a mismatched or corrupted public key the signature
> algorithm will complete "successfully" but the signature will be
> invalid.

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
signing input.

(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
unique-signature check.

> 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

   https://mailarchive.ietf.org/arch/msg/cfrg/pv7X8hrBtMGfmlCMHsLhJDXPHso

for an analysis of the security issues and ecosystem impact.

---Dan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20200128/864fd26f/attachment.sig>