• Conférence invitée au Crypto Reading Club de l'Institut national des normes et de la technologie (NIST) des États-Unis : diapositives - Taming the Many EdDSAs (pages 28-39), Konstantinos Chalkias, François Garillot, Valeria Nikolaenko (2023). Taming the Many EdDSAs & Ed25519 Signing Attacks.

Couverture médiatique et sur les réseaux sociaux de cette attaque

• NIST Crypto Reading Club « Taming the Many EdDSAs » (8 mars 2023)
• The Daily Swig « Des dizaines de bibliothèques cryptographiques vulnérables au vol de clés privées » (28 juin 2022)
• Risky Biz News « Nouvelle vulnérabilité crypto : des dizaines de bibliothèques cryptographiques ont mal implémenté l'algorithme de signature numérique Ed25519 » (28 juin 2022)
• Article de blog SafeHeron « Analyse des risques liés à l'utilisation d'Ed25519 : la clé privée de votre portefeuille peut être volée » (17 juin 2022)
• kryptera.se « Vulnérabilité dans la plupart des bibliothèques ed25519 » (en suédois) (29 juin 2022)
• Difesa e Sicurezza et Yoroi « Librerie crittografiche ed25519 potenzialmente non sicure » (en italien) (1er juillet et 29 juin 2022)
• Article Medium du professeur Bill Buchanan OBE « Ed25519 is Great, But ... » (1er juillet 2022)
• Reddit r/crypto (meilleur post du mois - 18 juin 2022)
• Reddit r/cryptography (17 juin 2022)
• Tweets intéressants :
  • tweet 1 (par Kostas Kryptos - « Les 26 bibliothèques vulnérables d'origine »)
  • tweet 2 (par Kostas Kryptos - « Conséquences des 40 bibliothèques vulnérables »)
  • tweet 3 (par Catalin Cimpanu - « 40 bibliothèques cryptographiques sont impactées par la même mauvaise implémentation d'Ed25519 »)
  • tweet 4 (par Kenny Paterson - « Potentiel de récupération à grande échelle de clés privées EdDSA, cf. http://kopenpgp.com où le même vecteur a été exploité dans les bibliothèques OpenPGP »)
  • tweet 5 (par Steven Galbraith - « Un danger pour les signatures déterministes : mieux vaut vérifier qu'il s'agit de la bonne clé publique ! »)
  • tweet 6 (par Riyaz Faizullabhoy - « Si vous utilisez EdDSA en production, allez-y jeter un œil »)
  • tweet 7 (par Bart Preneel - « Rappel : implémenter correctement et en toute sécurité des algorithmes cryptographiques est difficile »).
• Défis CTF (capture the flag) mettant en scène cette attaque :
  • ImaginaryCTF - JWT25519 (200pts) (30 juin 2022)

Quel est le problème ?

Notez que normalement, et conformément à la rfc8032 associée, les signatures EdDSA sont déterministes : pour un même message d'entrée à signer, une signature unique composée de deux éléments, un point de courbe R et un scalaire S, est renvoyée.

Un détail algorithmique est que la clé publique du signataire n'intervient que dans le calcul déterministe de la partie S de la signature, mais pas dans la valeur R. Cela implique que si un adversaire pouvait d'une manière ou d'une autre utiliser la fonction de signature comme un oracle (qui accepte des clés publiques arbitraires en entrée), il serait alors possible d'obtenir, pour le même message, deux signatures partageant le même R et ne différant que sur la partie S. Malheureusement, lorsque cela se produit, on peut facilement extraire la clé privée ; ce post StackOverflow explique pourquoi cela est possible.

Cela dit, les API publiques ne devraient PAS autoriser une paire de clés privée/publique dissociée comme entrée de signature. Pour contourner ce problème, de nombreuses implémentations stockent la clé publique avec la clé privée (ou la graine) et considèrent l'ensemble de la paire de clés comme le secret, OU elles redérivent toujours la clé publique dans la fonction de signature. Malheureusement, un grand nombre de bibliothèques existantes ne traitent pas ce problème et autorisent des clés publiques arbitraires en entrée sans vérifier si la clé publique d'entrée correspond à la clé privée d'entrée.

Bien sûr, cela ne signifie pas que toutes les applications dépendant de ces bibliothèques sont sujettes à des attaques d'exposition de clés ; en réalité, la plupart sont probablement sûres car elles n'exposent généralement pas l'API concernée à leurs utilisateurs et couplent leur paire de clés publique/privée juste avant l'invocation de sign. D'un autre côté, même lorsque ces API ne sont pas exposées, certaines applications adoptent des stratégies de modèle de menace TCB différentes quant à la gestion et au stockage des clés privées et publiques. Cela dit, pour prévenir cette attaque, les développeurs devraient également mettre en œuvre un protocole de protection de l'intégrité des clés publiques.

Nous listons ici quelques bibliothèques concernées ainsi que les références de code associées.

Fig 1. Un exemple de mauvaise utilisation de l'API dans la crate Rust ed25519-dalek.

Bibliothèques concernées

• C: OpenGNB
  https://github.com/gnbdev/opengnb/blob/master/libs/ed25519/sign.c#L7

• C: GNU Nettle
  https://github.com/gnutls/nettle/blob/fe7ae87d1b837e82f7c7968b068bca7d853a4cec/ed25519-sha512-sign.c#L43

• ASM/C: iroha-ed25519 (Hyperledger Project)
  https://github.com/hyperledger/iroha-ed25519/blob/main/lib/ed25519/ref10/ed25519.c#L27 et https://github.com/hyperledger/iroha-ed25519/blob/main/lib/ed25519/amd64-64-24k-pic/ed25519.c#L30

• C: ed25519-donna (Andrew Moon)
  https://github.com/floodyberry/ed25519-donna/blob/master/ed25519.c#L59

• C: ed25519 (Orson Peters)
  https://github.com/orlp/ed25519/blob/master/src/sign.c#L7

• C: libbrine (Kevin Smith)
  https://github.com/kevsmith/libbrine/blob/master/src/ed25519/sign.c#L7

• C++: Ed25519 (ArduinoLibs)
  https://rweather.github.io/arduinolibs/classEd25519.html#a36ecf67b4c5d2d39a31888f56af1f8a5

• C#: ed25519 (Hans Wolff)
  https://github.com/hanswolff/ed25519/blob/master/Ed25519/Ed25519.cs#L146

• C#: Ed25519 (CryptoManiac)
  https://github.com/CryptoManiac/Ed25519/blob/972829ac688847895d5105f19ca1e5777131b421/Chaos.NaCl/Internal/Ed25519Ref10/keypair.cs#L7

• Dart: ed25519_dart (Oleksii Semeshchuk)
  https://github.com/semolex/ed25519_dart/blob/master/lib/src/ed25519_dart_base.dart#L200

• Dart: riclava_ed25519 (riclava)
  https://github.com/riclava/ed25519/blob/master/lib/ed25519.dart#L125

• Clojure: ed25519 (Kevin Downey)
  https://github.com/hiredman/ed25519/blob/master/src/ed25519/core.clj#L168

• Haskell: hs-scraps (Vincent Hanquez)
  https://github.com/vincenthz/hs-scraps/blob/master/Crypto/Signature/Ed25519.hs#L115

• Java: ed25519-java (k3d3)
  https://github.com/k3d3/ed25519-java/blob/master/ed25519.java#L144

• Java: ed25519 (Bjorn Arnelid)
  https://github.com/BjornArnelid/ed25519/blob/master/src/ed25519/application/Ed25519.java#L32

• Java: Punisher.NaCl (Arpan Jati)
  https://github.com/arpanj/Punisher.NaCl/blob/c9619ca3028b90d0556c0473e4eba1d429a3744c/Punisher.NaCl/src/Punisher/NaCl/Ed25519Operations.java#L72

• Java: ED25519 (Mick Michalski)
  https://github.com/michami/ED25519/blob/master/ED25519.java#L60

• Java: vRallev/ECC-25519 (Ralf Wondratschek)
  https://github.com/vRallev/ECC-25519/blob/master/ECC-25519-Java/src/main/java/net/vrallev/java/ecc/Ecc25519Helper.java#L102

• Perl: Crypt::Ed25519 (Marc Lehmann)
  https://metacpan.org/release/MLEHMANN/Crypt-Ed25519-0.9/view/Ed25519.pm#$signature-=-Crypt::Ed25519::sign-$message,-$public_key,-$private_key

• Python: ed25519.py (auteurs d'Ed25519)
  https://ed25519.cr.yp.to/python/ed25519.py

• Python: ed25519 (Python Cryptographic Authority)
  https://github.com/pyca/ed25519/blob/main/ed25519.py#L243 (les auteurs mentionnent qu'elle n'est de toute façon pas sûre contre les canaux auxiliaires)

• Python: python-pure25519 (Brian Warner)
  https://github.com/warner/python-pure25519/blob/master/pure25519/eddsa.py#L21

• Python: nmed25519 (naturalmessage)
  https://github.com/naturalmessage/nmed25519/blob/master/nmed25519.py#L150

• Python: ed25519.py (Shiho Midorikawa)
  https://gist.github.com/elliptic-shiho/f41fd75cc30646a61d7ad63043fdd56e#file-ed25519-py-L77

• Python: bindings pour ed25519-dalek : py-ed25519-bindings
  https://github.com/polkascan/py-ed25519-bindings/blob/master/src/lib.rs#L111

• Swift: ed25519swift (pebble8888)
  https://github.com/pebble8888/ed25519swift/blob/master/Ed25519ref/ed25519s.swift#L120

• JS: supercop.js (1p6 Flynx)
  https://github.com/1p6/supercop.js/blob/master/index.js#L29

• JS: substack/ed25519-supercop (James Halliday)
  https://github.com/substack/ed25519-supercop/blob/master/index.js#L3

• C: libeddsa (Philipp Lay)
  https://github.com/phlay/libeddsa/blob/master/lib/ed25519-sha512.c#L85

• C#: SommerEngineering/Ed25519 (Thorsten Sommer)
  https://github.com/SommerEngineering/Ed25519/blob/master/Ed25519/Signer.cs#L80

• CUDA: ChorusOne/solanity
  https://github.com/ChorusOne/solanity/blob/master/src/cuda-ecc-ed25519/sign.cu#L10

• C: ncme/c25519 (Daniel Beer et Nikolas Rösener)
  https://github.com/ncme/c25519/blob/master/src/edsign.c#L115

• C: luazen (Phil Leblanc)
  https://github.com/philanc/luazen/blob/master/src/x25519.c#L508 (les auteurs ont modifié la fonction pour accepter pk au lieu de la sk nacl d'origine de 64 octets, qui inclut pk dans les 32 derniers octets)

• C++: amber (Pelayo Bernedo)
  https://github.com/bernedogit/amber/blob/master/src/group25519.cpp#L1661

• C: FLD ECC AVX2 (Armando Faz-Hern'{a}ndez and Julio L'{o}pez and Ricardo Dahab)
  https://github.com/armfazh/fld-ecc-vec/blob/master/src/sign255.c#L391

• Elixir: mwmiller/ed25519_ex (Matt Miller)
  https://github.com/mwmiller/ed25519_ex/blob/master/lib/ed25519.ex#L146(La clé publique est facultative. Selon le commentaire de l'auteur : si seule la clé secrète est fournie, la clé publique en sera dérivée. Cela ajoute une surcharge significative)

• PHP (C wrapper): php-ed25519-ext
  https://github.com/encedo/php-ed25519-ext/blob/master/ed25519-ext.c#L93

• Nim: niv/ed25519.nim (Bernhard Stöckner)
  https://github.com/niv/ed25519.nim/blob/master/ed25519.nim#L26

• Typescript: mipher (Marco Paland)
  https://github.com/mpaland/mipher/blob/master/src/x25519.ts#L936

• Lua: LuaMonocypher
  https://github.com/philanc/luamonocypher/blob/main/src/luamonocypher.c#L268

• Crystal: monocypher.cr
  https://github.com/konovod/monocypher.cr/blob/master/src/monocypher.cr#L39

• Python: py_ssh_keygen_ed25519 (Péter Szabó)
  https://github.com/pts/py_ssh_keygen_ed25519/blob/master/ed25519_compact.py#L128 (La clé publique est facultative)

• Javascript: KinomaJS
  https://github.com/Kinoma/kinomajs/blob/701879d37e7fe5001420e0053cd60df6b91e4553/xs6/extensions/crypt/crypt_ed25519.js#L92 (La clé publique est facultative)

• Haskell: gen-ed25-keypair
  https://github.com/awakesecurity/gen-ed25-keypair

• C: horse25519 (Yawning Angel)
  https://github.com/Yawning/horse25519/blob/master/src/ref10/sign.c#L7 Note : ce dépôt inclut une copie de l'implémentation ref10 ed25519 de djb, extraite de supercop pour éviter d'ajouter une autre dépendance, mais l'objectif est de fournir un exécutable autonome qui effectue la génération de paires de clés ed25519 personnalisées (vanity). Bien qu'il utilise l'API d'une manière inhabituelle, c'est intentionnel car il fait déjà quelque chose d'extrêmement exotique et inhabituel en matière de génération de clés, et la bibliothèque n'est pas destinée à être utilisée pour la signature.

Bibliothèques corrigées

• C: Trezor firmware
  Corrigé dans cette PR : https://github.com/trezor/trezor-firmware/pull/2349 (Correctif fusionné le 27 juin 2022)

• Java: ed25519-elisabeth (Jack Grigg)
  Corrigé dans ce commit : https://github.com/cryptography-cafe/ed25519-elisabeth/commit/49545ce47d550fed807522dff86546c812ccbbac (Correctif fusionné le 19 juin 2022)

• C: Harbour (Viktor Szakats)
  Corrigé dans ce commit : https://github.com/vszakats/hb/commit/bae610b63d35c6c1793d94a3bf9467c3b1eded18 (Correctif fusionné le 30 juin 2022)

• Rust/Wasm: polkadot-js/wasm
  Corrigé dans cette PR : https://github.com/polkadot-js/wasm/pull/381/files (Correctif fusionné le 3 juillet 2022)

• C: horse25519 (Yawning Angel)
  Corrigé dans cette PR : https://github.com/Yawning/horse25519/pull/3 (Correctif fusionné le 15 août 2022)

• Erlang: erlang-libdecaf
  Corrigé dans ce commit : https://github.com/potatosalad/erlang-libdecaf/commit/16ba07ea122660e95f6cfa9107e28ed58bada713. Logique traitée dans cette issue : ed25519-unsafe-libs/issues/7 (Correctif fusionné le 28 août 2022)

• Rust: ed25519-dalek (Isis Agora Lovecruft)
  Corrigé dans cette PR : https://github.com/dalek-cryptography/ed25519-dalek/pull/205 (Correctif fusionné le 22 octobre 2022)

• C: Monocypher (Loup Vaillant)
  Corrigé dans ce commit : https://github.com/LoupVaillant/Monocypher/commit/da7b5407d20329f21a53ea993f516fb55e2f5e26 (Correctif fusionné le 27 février 2023)

Faux positifs (probablement sûrs)

Bibliothèques initialement signalées comme vulnérables, mais retirées de la liste suite aux retours de la communauté.

• Go: threshold-ed25519 — Signatures à seuil utilisant Ed25519
  https://gitlab.com/unit410/threshold-ed25519/-/blob/main/pkg/ed25519.go#L161 -> voir le rapport https://github.com/MystenLabs/ed25519-unsafe-libs/pull/9 (signalé le 27 octobre 2022 par nitronit)