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

[Greg Maxwell]

In order to constitute a proof of knowledge Ed25519 / EdDSA prudently
includes the public key explicitly in the challenge hash.

However, the specified Ed25519 nonce generation function does not
include the public key in the hash.

Universally (or almost universally?) ed25519 implementations accept
the public key as an argument to the signing algorithm in order to
avoid doubling their runtime by regenerating it from their secret key.

If I sign with a mismatched or corrupted public key the signature
algorithm will complete "successfully" but the signature will be
invalid.  To the lay eye this seems harmless on its face: why would I
care if someone could trick me into making an invalid signature for
them? They could already generate as many invalid signatures as they
want without my help.

But if I also sign the same message with the same secret key and a
_different_ public key argument (either the right one this time or a
different fake one), and you learn both these signatures you can
simply calculate my private key via nonce reuse.

I would be surprised if some implementation didn't eventually turn out
exploitable due to this. The behaviour is subtle and no
non-cryptographer is likely to anticipate it. It's only obvious in the
sense that experts know that "Does doing X break security?" is true
for most values of X. :)

This could also be used to increase the effectiveness of a fault
attack (e.g. I manage to corrupt just the public key during signing).
At a minimum it would be a good way to hide a bugdoor which would
easily pass review.

The nonce generation function input should be a strict superset of the
arguments into the challenge hash (except for R, of course) to
preserve the expected properties provided by derandomized signing.

This is also related to a general (and I think less serious) weakness
with RFC6979 and other similar schemes where there is commonly no
commitment to either the group, its generator, or the "signature
scheme" the nonce is being used with.  If someone can get me to sign
the same message with the same key using both ECDSA and schnorr or
using the same signature scheme and two distinct generators (generator
is an implicit input to the schnorr challenge hash via the R value),
the lack of these inputs into the nonce function causes the signatures
to leak my key. Fortunately, reusing private keys in different
cryptosystems is already a widely discouraged practice (and no one
ever engages in any widely discouraged practices, right???)...

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.

Synthetic nonces, as advanced by Trevor Perrin, also largely address
these concerns. However, to fully capture the protection against bad
randomness that derandomization provides the nonce function should
still commit to these additional inputs. The scheme described in
Trevor's "Generalizing EdDSA" does not.

I would not call this a vulnerability -- to be that it would need to
be combined with one or more implementations which are unsafe with
respect to this behaviour.  But I think it would be fair to call it an
avoidable fragility similar to how incomplete group laws, randomized
signing, cofactor, prime-subgroup orders which are far from a
power-of-two, underspecified handling of out-of-range values resulting
in malleability, certificate formats that needlessly encode
generators, etc. are ways EC cryptosystems can be fragile which
sometimes result in exploitable vulnerabilities in practice.

Fortunately, except in extremely exotic usage the nonce generating
function is externally indistinguishable so the behaviour can be
changed without breaking protocol compatibility. This means these
issues be avoided with much lower cost than most other sources of
fragility.