Réutilisation de nonce ECDSA : comment un nombre répété révèle une clé privée

Le nombre qui ne doit jamais se répéter

Une signature ECDSA est un couple d’entiers, (r, s). Sa production nécessite trois entrées : la clé privée d, le condensat du message z et un entier secret neuf k, le nonce, abréviation de « number used once » (nombre utilisé une seule fois). Le signataire choisit k dans l’intervalle [1, n−1], où n est l’ordre du point de base G de la courbe, et calcule :

R = k * G                      (a point on the curve)
r = x-coordinate of R  mod n
s = k^-1 * (z + r * d) mod n

signature = (r, s)

Regardez d’où provient chaque valeur produite. s mélange tout : le nonce, le condensat et la clé. Mais r est dérivé de k et de rien d’autre : c’est la coordonnée x de kG, une fonction du nonce et de la courbe seuls. Le message n’y intervient pas. La clé privée n’y intervient pas.

Voilà tout le problème, en une phrase. Deux signatures produites avec le même k porteront le même r, et r est publié avec chaque signature. Un nonce répété n’est pas une défaillance cachée qu’il faudrait découvrir : il se signale au grand jour, dans un champ que tout vérificateur lit et que tout explorateur de blocs conserve pour toujours.

Deux signatures, deux inconnues

Supposons qu’un signataire ait utilisé le même k et la même clé d pour deux messages différents, de condensats z1 et z2. Les deux signatures partagent le même r, d’où :

s1 = k^-1 * (z1 + r * d) mod n
s2 = k^-1 * (z2 + r * d) mod n

Ici, tout est public, sauf k et d. Deux équations, deux inconnues. Multipliez les deux membres de chacune par k pour éliminer l’inverse :

k * s1 = z1 + r * d mod n
k * s2 = z2 + r * d mod n

Le terme r * d est identique dans les deux lignes, car la même clé a signé les deux messages et le même nonce a produit le même r. Soustrayez la seconde équation de la première, et ce terme s’annule, ce qui fait entièrement disparaître la clé privée du calcul :

k * s1 - k * s2 = z1 - z2      mod n
k * (s1 - s2)   = z1 - z2      mod n

k = (z1 - z2) * (s1 - s2)^-1   mod n

On obtient ainsi le nonce. En le reportant dans l’une ou l’autre des équations de l’étape 2, on obtient la clé, puisque d n’y est plus multiplié que par r :

k * s1     = z1 + r * d        mod n
r * d      = k * s1 - z1       mod n

d = (s1 * k - z1) * r^-1       mod n

Quatre étapes, aucune recherche, rien à deviner. Le coût : deux inversions modulaires et une poignée de multiplications, soit quelques microsecondes sur n’importe quelle machine, à partir de données déjà publiques.

Une subtilité pratique : les encodages ne conservent pas toujours exactement le s calculé par le signataire. Bitcoin et plusieurs bibliothèques normalisent vers la forme « low-S » en remplaçant s par n − s lorsqu’il tombe dans la moitié supérieure de l’intervalle. C’est un correctif de malléabilité proposé dans BIP-62 et spécifié comme règle de relais dans BIP-146, sans rapport avec les nonces, mais qui recoupe ce calcul. La valeur récupérée peut alors correspondre à −k plutôt qu’à k, et il faut lever l’ambiguïté de signe avant que les nombres concordent. La difficulté n’en est en rien changée ; la question de l’encodage est traitée à part dans Formats de signature ECDSA.

Rien d’une expérience de pensée

C’est la catégorie de défaillances réelles d’ECDSA la plus prolifique, et les mathématiques n’y sont pour rien. Chaque fois, c’est une implémentation qui a fourni un nonce qu’elle n’aurait pas dû fournir.

• PlayStation 3, 2010. L’implémentation de Sony chargée de signer le micrologiciel utilisait une valeur constante à la place de k. Toutes les signatures qu’elle produisait portaient un r identique, et deux quelconques d’entre elles suffisaient pour en extraire la clé de signature maîtresse de la console. La faille a été démontrée publiquement au 27C3, dans la conférence Console Hacking 2010. C’est l’illustration la plus pure qui soit : l’algorithme était correctement implémenté, à l’exception d’une variable qui ne variait jamais.
• Portefeuilles Android, 2013. Le 14 août 2013, le blog Android Developers a publié Some SecureRandom Thoughts, après avoir enquêté sur ce que le billet décrit comme « la compromission d’une transaction bitcoin qui a conduit à la mise à jour de plusieurs applications Bitcoin le 11 août ». La cause première : les applications utilisant la Java Cryptography Architecture « peuvent ne pas recevoir de valeurs cryptographiquement robustes sur les appareils Android en raison d’une initialisation incorrecte du PRNG sous-jacent ». Les portefeuilles qui signaient sur les appareils concernés tiraient leurs nonces d’un générateur susceptible de démarrer à plusieurs reprises dans le même état. Google a publié un contournement, PRNGFixes, pour les niveaux d’API 16 à 18, et a corrigé la plateforme. Remarquez ce qui a cédé : ni le code cryptographique du portefeuille ni la courbe, mais la primitive du système d’exploitation sur laquelle reposaient l’un et l’autre.
• La catégorie plus large : les nonces biaisés. La répétition complète en est la version bruyante. La version silencieuse, c’est un nonce simplement biaisé : quelques bits qui ne sont pas uniformément distribués, parce que le générateur renvoie des valeurs dans un intervalle légèrement faux, ou les tronque, ou laisse fuiter des informations par son temps d’exécution. Il n’existe pas ici de raccourci algébrique propre, mais le problème se reformule comme la recherche d’un vecteur court dans un réseau euclidien, et la réduction de réseau en vient à bout. L’article Biased Nonce Sense de Breitner et Heninger (Financial Cryptography 2019) a appliqué cette approche aux blockchains publiques et à des scans de l’ensemble d’Internet, et a récupéré des centaines de clés Bitcoin ainsi que des dizaines de clés Ethereum, Ripple, SSH et HTTPS, à partir de nonces qui n’avaient jamais été répétés, seulement imparfaits. La leçon est sévère : « à peu près aléatoire » n’est pas une protection.

Aucun de ces cas n’a nécessité de faille dans ECDSA, et aucun ne se corrige avec une courbe plus grande. L’algorithme exige un secret parfaitement uniforme pour chaque signature et ne donne aucun avertissement lorsqu’il ne l’obtient pas.

Ce que montre la blockchain aujourd’hui

Des valeurs r répétées se trouvent encore dans la blockchain Bitcoin, pour toujours, car une blockchain n’oublie rien. Notre vérificateur de réutilisation de nonce récupère les transactions récentes d’une adresse via l’API mempool.space, extrait les signatures DER des entrées qui dépensent depuis cette adresse et les regroupe par couple (clé publique, r). Voici ce qu’il a renvoyé pour 1BFhrfTTZP3Nw4BNy4eX4KFLsn9ZeijcMm le 20 août 2026 :

address                 1BFhrfTTZP3Nw4BNy4eX4KFLsn9ZeijcMm  (P2PKH)
transactions returned   50      <- API cap, not the full history
  spending from it      30
inputs from address     110
signatures parsed       110     (unattributed 0, taproot 0, unparsed 0)
distinct public keys    1
distinct r values       73      <- 110 signatures, only 73 nonces
repeated-r groups       6
identical duplicates    0

Une clé, 110 signatures, 73 nonces distincts. Tout est dans cet écart : 43 des 110 signatures appartiennent à un groupe qui partage un r avec au moins une autre signature, et dans chacun des six groupes les valeurs s diffèrent, ce qui écarte l’explication bénigne d’une signature dupliquée. Le plus grand groupe :

r = d47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad1
pubkey = 04dbd0c6...49c5ff (uncompressed)

ad698b53bbba9e7d807559ec7d3a466fccb669dd3659a1604a206eeb9965c527  vin 0  2012-12-21
b4922bc8cc3624487cdcf4b0ed5a98a21a4552a48dfe495490a7443dd546821e  vin 0  2012-12-21
8ab813e5a4039eb79484c315e9c0e201c9d80385c3f3650a4c4b974db9172148  vin 0  2012-12-21
0b5315f4d472a22a6937a20a8d44b8e77099f2a951b65c53c9ebf912352504fa  vin 0  2012-12-19
952d8301780ca74fca5f6541db44ba49e47e8514dfdef36bc7e3d534085dbbf6  vin 0  2012-12-19
    ... 5 more, the oldest on 2012-08-16

Deux détails méritent qu’on s’y arrête. D’abord, le deuxième groupe par la taille compte lui aussi dix signatures, qui partagent un autre r, et dans les deux groupes chaque signature occupe le même indice d’entrée dans sa transaction (l’indice 0 pour l’un, l’indice 1 pour l’autre). Ce n’est pas ainsi que se manifeste une collision occasionnelle du RNG. C’est ainsi que se manifeste un générateur réinitialisé dans le même état au début de chaque opération de signature, puis avancé pas à pas : l’entrée 0 reçoit toujours la première valeur, l’entrée 1 la deuxième. Ensuite, la réutilisation s’étend d’août à décembre 2012, presque un an avant la divulgation du problème SecureRandom d’Android. Cette catégorie de défaut sévissait déjà en conditions réelles avant d’avoir un nom public, ce qui rappelle que de telles annonces marquent le moment où un problème a été remarqué, et non celui où il a commencé.

La solution : arrêter de jouer aux dés

La réponse durable n’est pas « utilisez un meilleur générateur de nombres aléatoires ». Elle consiste à retirer complètement le générateur de nombres aléatoires du chemin de signature.

RFC 6979, ECDSA déterministe. Au lieu de tirer k au hasard, dérivez-le : initialisez un générateur déterministe de bits aléatoires fondé sur HMAC (HMAC-DRBG) en lui donnant pour graine la clé privée et le condensat du message, et prenez k dans sa sortie, en effectuant un nouveau tirage si la valeur sort de [1, n−1]. Le résultat a l’apparence d’une valeur uniforme, il est imprévisible sans la clé et, point essentiel, il est fonction du message. Un message différent produit nécessairement un k différent : une réutilisation accidentelle devient structurellement impossible, et pas seulement improbable. Signer deux fois le même message reproduit les mêmes octets, ce qui est sans danger et constitue en prime une propriété commode pour les tests. Aucune source d’entropie n’est consultée au moment de la signature, si bien qu’une source défaillante ne peut pas vous nuire. FIPS 186-5 autorise l’ECDSA déterministe à côté de la forme aléatoire.

RFC 8032, EdDSA. Ed25519 et Ed448 rendent la même idée obligatoire en l’intégrant au schéma : le secret propre à chaque signature est dérivé en hachant un préfixe dérivé de la clé avec le message, et l’API n’offre aucune prise par laquelle quiconque implémente le schéma pourrait substituer une valeur aléatoire. Si vous choisissez un schéma au lieu d’en hériter un, ce mode de défaillance disparaît par construction. Les signatures Taproot de Bitcoin suivent la même philosophie : BIP-340 impose une dérivation déterministe du nonce, avec un aléa auxiliaire facultatif.

Signatures hedged. Le déterminisme pur comporte un compromis qu’il vaut la peine de connaître : une faute provoquée pendant la signature (une perturbation de l’horloge ou de la tension d’alimentation d’une carte à puce) peut amener un signataire déterministe à produire deux signatures différentes du même message avec le même k dérivé, ce qui recrée exactement la situation d’un nonce réutilisé. La RFC 6979 anticipe ce cas au §3.6. La solution hedged injecte un aléa frais dans la dérivation déterministe au lieu de la remplacer, ce qui donne un nonce sûr dès lors que soit la dérivation, soit le RNG est fiable. crypto/ecdsa de Go signe de cette façon ; @noble/curves le propose sous la forme d’une option extraEntropy ; l’aléa auxiliaire de BIP-340 relève de la même idée.

Ce que font par défaut les bibliothèques courantes :

Un « Non » dans ce tableau n’est pas un rapport de bogue. Un nonce aléatoire tiré d’un CSPRNG du système d’exploitation en bon état est une façon parfaitement conforme de signer, et c’est ce que spécifient toutes les éditions de FIPS 186 ; FIPS 186-5 (2023) lui a adjoint la variante déterministe. La colonne mesure une dépendance, pas la justesse : les lignes « Non » misent votre clé privée sur la source d’entropie au moment de la signature, les lignes « Oui » non. Que cela compte ou non dépend de votre déploiement : un serveur durci est un pari très différent d’un appareil embarqué fraîchement démarré, d’une image de VM clonée ou d’un téléphone de 2013. L’aide-mémoire d’interopérabilité des bibliothèques présente côte à côte cette différence et les autres écarts de comportement par défaut.

Ce qu’il faut concrètement faire

• Ne fournissez jamais votre propre k. Si une API de signature accepte un paramètre de nonce, voyez-y un moyen de vous tirer une balle dans le pied plutôt qu’une fonctionnalité, et n’y recourez jamais simplement parce qu’un test avait besoin d’octets reproductibles. La signature déterministe vous les donne déjà, sans risque.
• N’écrivez jamais le générateur vous-même. « On lui donne pour graine l’horodatage et l’ID de la requête » : c’est précisément ainsi que commencent ces incidents. Utilisez le CSPRNG de la plateforme, ou une bibliothèque qui n’en a pas besoin.
• Vérifiez quelle stratégie de nonce vous utilisez réellement. Un test de deux lignes vous en apprend l’essentiel, mais lisez le résultat avec attention, car il ne distingue pas un nonce aléatoire d’un nonce hedged :

import { generateKeyPairSync, sign } from "node:crypto";

const { privateKey } = generateKeyPairSync("ec", { namedCurve: "P-256" });
const msg = Buffer.from("same message, twice");

const a = sign("sha256", msg, privateKey);
const b = sign("sha256", msg, privateKey);

console.log(a.equals(b));
// false in node:crypto  -> random or hedged nonce
// true                  -> deterministic derivation (RFC 6979 or EdDSA-style)

Si les octets diffèrent, vous ne savez toujours pas si le nonce est purement aléatoire ou hedged : seule la documentation de la bibliothèque permet de trancher. S’ils sont identiques, vérifiez qu’il s’agit bien de la RFC 6979 et non d’une solution maison, en comparant votre sortie aux vecteurs à réponse connue de l’annexe A.2 de la RFC 6979. Notre générateur de vecteurs de test ECDSA produit des signatures RFC 6979 pour P-256, P-384, P-521 et secp256k1 à partir d’une graine, de sorte que les mêmes vecteurs se régénèrent plus tard à l’octet près.

• Méfiez-vous des moments de faible entropie. Le premier démarrage d’un matériel embarqué, les VM et conteneurs restaurés à partir d’un instantané partagé, et le tout début de l’initialisation, avant que le pool d’entropie ait reçu sa graine, sont les moments où un nonce aléatoire risque le plus de décevoir. La signature déterministe fait disparaître la question.
• Si vous trouvez une réutilisation, la clé est perdue. Pas affaiblie : perdue, rétroactivement, face à quiconque a vu un jour ces deux signatures. Déplacez les fonds, effectuez la rotation de la clé partout où elle est utilisée, et considérez que toute signature qu’elle a produite peut être attribuée à quelqu’un d’autre.

Sources primaires

• RFC 6979 : utilisation déterministe de DSA et d’ECDSA. La dérivation HMAC-DRBG, sa justification et les vecteurs à réponse connue de l’annexe A ; la mise en garde sur les attaques par faute figure au §3.6.
• RFC 8032 : EdDSA (Ed25519, Ed448), où la dérivation déterministe du nonce fait partie du schéma au lieu d’être une option.
• FIPS 186-5 : la version en vigueur du Digital Signature Standard, qui spécifie ECDSA et autorise la génération déterministe des nonces.
• Some SecureRandom Thoughts : blog Android Developers, 14 août 2013. Le défaut d’initialisation du PRNG de la plateforme, son lien avec la compromission des portefeuilles Bitcoin et le contournement PRNGFixes.
• Biased Nonce Sense : Breitner et Heninger, IACR ePrint 2019/023 / Financial Cryptography 2019. Attaques par réseaux euclidiens contre des nonces simplement biaisés, mesurées sur des données réelles de blockchains et de l’ensemble d’Internet.
• Console Hacking 2010 : 27C3, la démonstration publique de la défaillance de la PlayStation 3 due à un nonce constant.
• BIP-62 et BIP-146 : la canonicalisation low-S (un correctif de malléabilité, pas un correctif de nonce, mais la raison pour laquelle les valeurs récupérées peuvent nécessiter une correction de signe), ainsi que BIP-340 pour le nonce déterministe qu’impose Taproot.
• libsecp256k1 et @noble/curves : deux implémentations largement auditées qui utilisent la RFC 6979 par défaut, et dont le code source est la documentation la plus claire de ce à quoi doit ressembler une dérivation de nonce.

L’article ECDSA vs RSA explique pourquoi cette exigence sur le nonce est l’un des rares véritables avantages opérationnels que RSA conserve encore, et compare les deux algorithmes sur les autres points.