It turns out that after EdDSA Ed25519 signature adoption, rigorous proofs of its security properties were made, but some of these desirable security properties only apply if some relatively straight forward checks are enforced during verification.
However not all signature libraries for EdDSA Ed25519 perform these checks. Here is some text mostly from the papers explaining the security properties that can be proven and why they are desirable. In addition, the paper's authors provide test vectors on GitHub to help test signature libraries for some edge cases (only 12 tests in total). Might we want to capture those in this specification as an appendix? Below is some potential starting text. Opinions on how much guidance we should supply on this issue? For a more complete over view see the authors presentation this year to NIST.
Ed25519 Provable Security and Library Implementation Reality
Digital signatures may exhibit a number of desirable cryptographic properties among these are (using the definitions from reference 2 below):
EUF-CMA (existential unforgeability under chosen message attacks) is usually the minimal security property required of a signature scheme. It guarantees that any efficient adversary who has the public key $pk$ of the signer and received an arbitrary number of signatures on messages of its choice (in an adaptive manner): ${m_i, \sigma_i}{i=1}^N$, cannot output a valid signature $\sigma^∗$ for a new message $m^∗ \notin {m_i}{i=1}^N$ (except with negligible probability). In case the attacker outputs a valid signature on a new message: $(m^∗, \sigma^∗)$, it is called an existential forgery.
SUF-CMA (strong unforgeability under chosen message attacks) is a stronger notion than EUF-CMA. It guarantees that for any efficient adversary who has the public key $pk$ of the signer and received an arbitrary number of signatures on messages of its choice: ${mi, σi}{i=1}^N$, it cannot output a new valid signature pair $(m^∗, \sigma^∗)$, s.t. $(m^∗, \sigma^*) \notin {m^i, σ^i}{i=1}^N$ (except with negligible probability). Strong unforgeability implies that an adversary cannot only sign new messages, but also cannot find a new signature on an old message.
Binding signature (BS) We say that a signature scheme is binding if no efficient signer can output a tuple $[pk, m, m^\prime, \sigma]$, where both $(m, \sigma)$ and $(m^\prime, \sigma)$ are valid message signature pairs under the public key $pk$ and $m \ne m^\prime$ (except with negligible probability). A binding signature makes it impossible for the signer to claim later that it has signed a different message, the signature binds the signer to the message.
Strongly Binding signature (SBS) Certain applications may require a signature to not only be binding to the message but also be binding to the public key. We say that a signature scheme is strongly-binding if any efficient signer can not output a tuple $[pk, m, pk^\prime, m^\prime, \sigma]$, where $(m, \sigma)$ is a valid signature for the public key $pk$ and $(m^\prime, \sigma)$ is a valid signature for the public key $pk^\prime$ and either $m^\prime \ne m$ or $pk \ne pk^\prime$, or both (except with negligible probability).
It was recently proven in reference 1 and 2 that EdDSA with curve Ed25519 can posses all these desirable cryptographic properties but only if sufficient input validation testing is performed when verifying an Ed25519 based signature. In particular to a achieve the SUF property all validation tests checks specified in RFC8032 must be performed. In addition to achieve the SBS property public keys which are elliptic curve points of "small order" are invalid and must be rejected.
The validation checks of RFC8032 and the "small order point" checks have been incorporated into some Ed25519 implementations recently, however as shown in reference 2 many libraries have not implemented these validation checks. Since these checks are either part of established signature standard (RFC8032) or relatively minimal (there are only eight canonical small order points to check for) it is strongly recommended that implementers of this specification choose a signature library satisfying these conditions. Test vectors to test a signature library can be found at GitHub: ed25519-speccheck
References
- The Provable Security of Ed25519: Theory and Practice, 2020, Jacqueline Brendel, Cas Cremers, Dennis Jackson, and Mang Zhao.
- K. C. Garillot François and V. Nikolaenko, Taming the many EdDSAs, 2020 and accepted to SSR Conference October 2020.
- RFC8032: Edwards-Curve Digital Signature Algorithm (EdDSA)
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent