Que savons-nous de l'attaque de la grille ?
Pour commencer, l' algorithme de signature numérique à courbe elliptique (ECDSA) est un schéma de signature numérique courant que nous voyons dans bon nombre de nos revues de code. Il a certaines propriétés souhaitables, mais peut également être très fragile pour récupérer la clé privée avec une attaque par canal latéral qui révèle moins d'un bit du nonce secret.
ECDSAest une forme spéciale de l'algorithme de signature numérique(DSA).DSAest un schéma de signature numérique assez courant, qui est défini par trois algorithmes : génération de clé, signature et vérification. L'algorithme de génération de clé génère des clés privées et publiques ; la clé privée est responsable de la création des signatures ; et la clé publique est responsable de la vérification des signatures. L'algorithme de signature prend un message et une clé privée en entrée et génère une signature. L'algorithme de vérification prend un message, une signature et une clé publique en entrée et renvoie une valeur detrueoufalse, indiquant si la signature est valide.
DSA est défini pour tout groupe mathématique, et ce schéma est sûr tant que le problème du logarithme discret est difficile pour ce groupe. Un groupe couramment utilisé est celui des entiers modulo un nombre premier p.
Avec ce groupe, nous aurons un générateur de groupe g et une fonction de hachage cryptographiquement sécurisée H. Nous pouvons supposer que p , g et H seront de notoriété publique.
La génération de clé fonctionne en sélectionnant d'abord au hasard une valeur x parmi des entiers modulo p . Ensuite, la valeur est calculée y = g^x mod p
La clé privée de la signature est
x, et la clé publique esty. La clé de signature doit être gardée secrète, car c'est elle qui permet de faire des signatures.
L'algorithme de signature crée une signature à partir du message m et de la clé secrète x . Tout d'abord, un élément de groupe aléatoire est généré k . C'est ce qu'on appelle un nonce, ce qui est important lorsqu'il s'agit d'attaques.
Ensuite, les valeurs sont calculées r = g^k mod p et s = ( k^-1 ( H ( m ) + xr )) mod p
Ici k^- 1 , est le groupe inverse, et H ( m ) est le résultat du calcul du hachage m, et de l'interprétation du résultat comme un entier modulo p .
La signature est définie comme une paire de ( r , s ). (Remarque : si l'une des valeurs de r ou sest égale à 0, l'algorithme redémarre avec la nouvelle valeur de k ).
L'algorithme de vérification reçoit en entrée une signature ( r , s ), un message et une clé publique y. mSoit ŝ = s^-1 , alors l'algorithme renvoie true si et seulement si r , s ≠ 0 и r = ( g H ( m ) y r ) ŝ .
Ce contrôle de validation fonctionne car g^H( m ) y^r = g^H(m)+ xr = g^ks, et donc (g^H(m)y^r)^ŝ = g^k = r
Un schéma de signature numérique est considéré comme sûr s'il ne peut pas être contrefait.
L'immuabilité a une signification cryptographique formelle, mais à un niveau élevé, cela signifie que vous ne pouvez pas créer de signatures sans connaître la clé secrète (sauf si vous avez copié une signature déjà existante créée à partir de la clé secrète). S'est avéré DSAimpossible à simuler sous l'hypothèse d'un journal discret .
DSA est défini sur un groupe mathématique. Lorsqu'il est DSA utilisé avec le groupe de courbes elliptiques comme ce groupe mathématique, nous l'appelons ECDSA. Le groupe de courbes elliptiques se compose de points de courbes elliptiques, qui sont des paires de ( x , y ), qui satisfont l'équation y^2 = x^3 + ax + b pour certains a , b . Pour cet article de blog, tout ce que vous devez savoir, c'est qu'en utilisant des courbes elliptiques, vous pouvez définir un groupe fini, ce qui signifie que vous obtenez le générateur de groupe, g (point de courbe elliptique) , et les opérations d' addition et de multiplication de points exactement comme celle-ci comme vous peut avec des entiers. Puisqu'ils forment un groupe fini, générateur,g , sera d'ordre fini, p. Ce billet de blog ne vous expliquera ni ne vous demandera de savoir comment fonctionnent ces opérations sur les courbes elliptiques .
ECDSA fonctionne de la même manière que DSA, mais avec un groupe différent. La clé secrète x sera toujours une valeur aléatoire modulo entiers p . Maintenant, la clé publique y est toujours calculée comme y = g^x , sauf que g est maintenant un point sur la courbe elliptique. Cela signifie que y sera également un point sur la courbe elliptique (auparavant y était un entier modulo p ). Une autre différence est la façon dont nous calculons la valeur de r . Nous générons toujours un nonce aléatoire k sous la forme d'un entier modulo p comme précédemment. Nous calculerons g^k , mais encore une fois, g est un point d'une courbe elliptique, et, par conséquent, g^k aussi. Par conséquent, nous pouvons calculer ( x^k , y^k ) = g^k et définir r = x^k . maintenant le sens s peut être calculé comme avant, et nous obtenons notre signature ( r , s ), qui est toujours un entier modulo p , comme avant. Pour vérifier, nous devons corriger le fait que nous avons calculé r un peu différemment.
Donc, comme avant, nous calculons la valeur de
( g^H(m)y^r)^ŝ, mais maintenant cette valeur est un point sur la courbe elliptique, donc nous prenonsxla coordonnée de ce point et la comparons à notre valeur der.
Récupération de clés secrètes à partir de nonces réutilisés NONCES
Maintenant que nous comprenons de quoi il s'agit ECDSA et comment il fonctionne, démontrons sa fragilité . Encore une fois, puisqu'il s'agit d'un schéma de signature numérique, il est impératif que la clé secrète ne soit jamais révélée à qui que ce soit d'autre que la personne qui signe le message.
Cependant, si le signataire émet la signature et émet également le nonce utilisé, l' attaquant peut immédiatement récupérer la clé secrète .
Disons que je libère une signature ( r , s ) pour un message m et que je découvre accidentellement que j'ai utilisé un nonce k .
Puisqu'on s = ( k^-1 ( H ( m ) + xr )), peut facilement calculer la clé secrète :
s = (k^-1(H(m) + xr))
ks = H(m) + xr
ks – H(m) = xr
x = r^-1(ks – H(m))
Par conséquent, le signataire doit non seulement garder sa clé privée secrète , mais tous ses nonces qu'il a jamais générés sont secrets.
Même si le signataire garde chaque nonce
NONCESsecret , s'il répète accidentellement un nonceNONCES(même pour des messages différents), la clé secrète peut également être récupérée immédiatement .
Soient ( r , s 1 ) et ( r , s 2 ) deux signatures créées sur des messages m 1 et m 2 (respectivement) à partir du même nonce k - puisqu'elles ont le même nonce, les valeurs r seront les mêmes, donc c'est très facile à détecter pour un attaquant :
s1 = k^-1(H(m1) + xr) and s2 = k^-1(H(m2) + xr)
s1 – s2 = k^-1(H(m1) – H(m2))
k(s1 – s2) = H(m1) – H(m2)
k = (s1 – s2)^-1(H(m1) – H(m2))
Une fois que nous avons récupéré le nonce k en utilisant la formule ci-dessus, nous pouvons récupérer la clé privée en effectuant l'attaque décrite précédemment.
Digérons cela un instant.
Si le nonce
NONCESde signature est divulgué, la clé secrète peut être immédiatement récupérée , ce qui brise tout notre schéma de signature .
De plus, si deux nonces se répètent, quels que soient les messages, un attaquant peut facilement le détecter et récupérer immédiatement la clé secrète , brisant à nouveau tout notre schéma.
C'est assez fragile et ce ne sont que de légères attaques !
Mais il y a une nouvelle Lattice Attack qui a été décrite en détail (Joachim Breitner et Nadia Heninger)Йоахим Брайтнер и Надя Хенингер
Document [PDF] : Biased Nonce Sense : Attaques en treillis contre les signatures ECDSA faibles dans les crypto-monnaies
Dans la blockchain Bitcoin, nous avons trouvé une certaine transaction :
transaction : 08d917f0fee48b0d765006fa52d62dd3d704563200f2817046973e3bf6d11f1f
pour les adresses Bitcoin : 15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E
et on a réussi à multiplier les fausses signatures et à appliquer la grille
où utiliser le script Python algorithmLLL.py avec l'installation de packages dans GOOGLE COLAB
INSTALLER >> SAGE + ECDSA + BITCOIN + algorithme LLL
Nous avons réussi à passer
Private Keyd'Bitcoin Walletune transaction faible enECDSA.
Clé privée trouvée !
https://www.blockchain.com/btc/address/15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E
ADDR: 15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E
WIF: 5JCAmNLXeSwi2SCgNH7wRL5qSQhPa7sZvj8eDwxisY5hJm8Uh92
HEX: 31AFD65CAD430D276E3360B1C762808D1D051154724B6FC15ED978FA9D06B1C1 Cette vidéo a été créée pour le portail CRYPTO DEEP TECH afin d'assurer la sécurité financière des données et la cryptographie à courbe elliptique secp256k1 contre les signatures ECDSA faibles dans la crypto-monnaie BITCOIN
Vidéo : https://youtu.be/YP4Xj6gUcf4
Télégramme : https://t.me/cryptodeeptech
Source : https://cryptodeep.ru/lattice-attack
No comments:
Post a Comment