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. _______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves