The Provable Security of Ed25519: Theory and Practice

A standard requirement for a signature scheme is that it is existentially unforgeable under chosen message attacks (EUF-CMA), alongside other properties of interest such as strong unforgeability (SUF-CMA), and resilience against key substitution attacks. Remarkably, no detailed proofs have ever been given for these security properties for EdDSA, and in particular its Ed25519 instantiations. Ed25519 is one of the most efficient and widely used signature schemes, and different instantiations of Ed25519 are used in protocols such as TLS 1.3, SSH, Tor, ZCash, and WhatsApp/Signal. The differences between these instantiations are subtle, and only supported by informal arguments, with many works assuming results can be directly transferred from Schnorr signatures. Similarly, several proofs of protocol security simply assume that Ed25519 satisfies properties such as EUF-CMA or SUF-CMA. In this work we provide the first detailed analysis and security proofs of Ed25519 signature schemes. While the design of the schemes follows the well-established Fiat-Shamir paradigm, which should guarantee existential unforgeability, there are many side cases and encoding details that complicate the proofs, and all other security properties needed to be proven independently. Our work provides scientific rationale for choosing among several Ed25519 variants and understanding their properties, fills a much needed proof gap in modern protocol proofs that use these signatures, and supports further standardisation efforts. * We provide a summary of changes in Appendix C. Related Work History of EdDSA and Ed25519 Ed25519-Original is just one instantiation of the more general EdDSA signature scheme, which was introduced in the same paper [1], [6] . EdDSA is itself a variant of the well-known Schnorr signature scheme [20], [21] . Ed25519 is EdDSA instantiated over curve Edwards25519 [1] and remains by far the most popular instantiation of EdDSA, despite its later extension to support alternative curves [7], [22] . EdDSA instantiations such as Ed25519-Original can sign and verify signatures substantially faster than almost all other signatures schemes at similar security levels. For schemes that have comparable speeds, Ed25519-Original further provides considerably smaller signatures, producing 64-byte signatures and 32-byte public keys. Additionally, EdDSA is widely considered to provide better resistance to side-channel attacks than alternative schemes. However, the original papers [1], [6] contain no formal statements (and consequently, no actual proofs) of its security properties. By virtue of its outstanding performance with respect to efficiency and bandwidth, EdDSA was standardised by the IETF between 2015 and 2017 [7] . In 2019, EdDSA was proposed to also be adopted as part of NIST's Digital Signature Standard (DSS) [10], [11] . In early 2020, the public call for comments was closed [12] , but as of writing, no new version has appeared. G IMP-KOA CID,A (pp): 1 (pk, sk) $← -KGen(pp) 4 rsp$ ← -A(ch, st) 5 return V 2 (pk, com, ch, rsp) G IMP-PA CID,A (pp): 1 (pk, sk) $ ← -KGen(pp)