Overview

This is an IEEE S&P 2021 research paper by Jacqueline Brendel, Cas Cremers, Dennis Jackson, and Mang Zhao (CISPA Helmholtz Center for Information Security and ETH Zurich). It provides the first detailed security analysis and proofs for the Ed25519 (EdDSA) signature scheme, which was introduced in 2011 by Bernstein, Duif, Lange, Schwabe, and Yang but published without precise security statements. Ed25519 is used in TLS 1.3, SSH, Tor, ZCash, and Signal-based protocols such as WhatsApp, yet its various instantiations differ subtly and prior protocol proofs simply assumed the needed properties held. The paper closes that proof gap and gives scientific rationale for choosing among Ed25519 variants.

Key points

• Distinguishes several deployed variants: Ed25519-Original (Bernstein et al.), Ed25519-IETF (standardized in RFC 8032), and stricter versions used by LibSodium and ZCash that add group-element checks.
• Proves that Ed25519-Original is existentially unforgeable under chosen message attacks (EUF-CMA), following the Fiat-Shamir paradigm, but that its reference source code accepts mangled signatures and is therefore not strongly unforgeable.
• Proves that Ed25519-IETF, thanks to an added scalar bound check on S in the verification equation, achieves strong unforgeability (SUF-CMA), which rules out signature malleability. Malleability enabled real attacks such as the Mt. Gox transaction-mauling on Bitcoin.
• Proves all Ed25519 variants resist key substitution attacks, but shows the strongest resilience (M-S-UEO, message-bound security) holds only for variants that reject small-subgroup and low-order group elements during verification.
• Analyzes subtle encoding details: cofactored vs cofactorless verification, scalar clamping, point validation, and low-order points, showing these choices materially change which security notions hold.
• Supplies missing assumptions used by prior computational proofs of TLS 1.3 and SSH, and supports NIST standardization efforts by clarifying which exact variant provides which guarantees.

Relevance to Truestamp

Truestamp signs blocks and proof material with Ed25519, so the paper’s formal grounding of EUF-CMA and SUF-CMA for specific Ed25519 variants directly informs Truestamp’s Ed25519 signature choices and the malleability/strong-unforgeability guarantees expected of a signature scheme used in verifiable proofs.

Citations

1. The Provable Security of Ed25519: Theory and Practice. Jacqueline Brendel, Cas Cremers, Dennis Jackson, Mang Zhao; CISPA and ETH Zurich; IEEE Symposium on Security and Privacy (S&P), 2021.