Paper 2020/1244

Taming the many EdDSAs

Konstantinos Chalkias, François Garillot, and Valeria Nikolaenko

Abstract

This paper analyses security of concrete instantiations of EdDSA by identifying exploitable inconsistencies between standardization recommendations and Ed25519 implementations. We mainly focus on current ambiguity regarding signature verification equations, binding and malleability guarantees, and incompatibilities between randomized batch and single verification. We give a formulation of Ed25519 signature scheme that achieves the highest level of security, explaining how each step of the algorithm links with the formal security properties. We develop optimizations to allow for more efficient secure implementations. Finally, we designed a set of edge-case test-vectors and run them by some of the most popular Ed25519 libraries. The results allowed to understand the security level of those implementations and showed that most libraries do not comply with the latest standardization recommendations. The methodology allows to test compatibility of different Ed25519 implementations which is of practical importance for consensus-driven applications.

Note: Submitted to SSR conference on Aug 31, 2020. Accepted to SSR conference on Oct 1, 2020.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.Security Standardisation Research Conference (SSR 2020)
DOI
10.1007/978-3-030-64357-7_4
Keywords
EdDSAed25519malleabilityblockchaincofactor
Contact author(s)
valerini @ fb com
kostascrypto @ fb com
valeria nikolaenko @ gmail com
francois @ garillot net
History
2021-12-02: last of 5 revisions
2020-10-09: received
See all versions
Short URL
https://ia.cr/2020/1244
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1244,
      author = {Konstantinos Chalkias and François Garillot and Valeria Nikolaenko},
      title = {Taming the many EdDSAs},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1244},
      year = {2020},
      doi = {10.1007/978-3-030-64357-7_4},
      note = {\url{https://eprint.iacr.org/2020/1244}},
      url = {https://eprint.iacr.org/2020/1244}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.