Etape 14 : L’importance d’un k aléatoire
Nous allons discuter maintenant comment et pourquoi les signatures ECDSA qui Sony a utilisé dans la Playstation 3 étaient défectueux et comment elle a permis les pirates d’accéder à la clé privée de la PS3 ECDSA.
Donc, vous n’oubliez pas les équations nécessaires pour générer une signature... R = k * G et S = k ^ -1 (z + dA * R) mod p... Eh bien, la force de cette équation est dans le fait que vous avez une équation à deux inconnues (k et dA) donc il n’y a aucun moyen de déterminer ou l’autre des personnes.
Toutefois, la sécurité de l’algorithme est basée sur sa mise en œuvre et il est important de s’assurer que 'k' est généré de façon aléatoire et qu’il est impossible que quelqu'un peut deviner, calculer ou utiliser une attaque de synchronisation ou de tout autre type d’attaque afin de trouver la valeur aléatoire 'k'. Mais Sony a fait une énorme erreur dans leur mise en œuvre, ils ont utilisé la même valeur pour 'k' partout, ce qui signifie que si vous avez deux signatures, tous deux avec le même k, puis ils les deux auront la même valeur de R , et cela signifie que vous pouvez calculer k en utilisant deux signatures de S de deux fichiers avec des hachages z et z' et signatures S et S' respectivement :
S – S' = k ^ -1 (z + dA * R) – k ^ -1 (z' + da * R) = k ^ -1 (z + da * R-z'-dA * R) = k ^ -1 (z-z')
So : k = (z – z’) / (S – S’)
Une fois que vous savez k, alors l’équation de S devient une équation à une inconnue et est ensuite facilement résolue pour dA :
dA = (S * k-z) / R
Une fois que vous savez la clé privée dA, vous pouvez désormais signer vos fichiers et la PS3 la reconnaîtra comme fichier authentique signé par Sony. C’est pourquoi il est important de s’assurer que le nombre aléatoire utilisé pour générer la signature est en fait "cryptographiquement aléatoire". C’est aussi pourquoi il est impossible d’avoir un custom firmware au-dessus de 3,56, simplement parce que depuis la version 3.56, Sony ont fixé leur mise en œuvre de l’algorithme ECDSA et utilisé les nouvelles clés pour lesquels il est maintenant impossible de trouver la clé privée...
Un autre exemple de ce problème est lorsque certains clients bitcoin utilisé cryptographiquement non générateur de nombres aléatoires (sur certains navigateurs et certains clients Android) qui a causé leur faire signer leurs transactions avec la même valeur de 'k', et des personnes mal intentionnées ont pu trouver la clé privée de leur portefeuille de bitcoin et voler leurs fonds.
Cela montre l’importance d’utiliser un nombre réellement aléatoire chaque fois que vous effectuez une signature, que vous exposerez la clé privée si la valeur R de la paire de signature (R, S) est identique sur les deux signatures différentes.
Une bonne blague à ce sujet apparaît en bande dessinée de xkcd 221 (voir image ci-dessus) qui est devenu l’image de go-to pour illustrer cette question. L’image a été souvent réutilisé chaque fois qu’une telle erreur de mise en œuvre de l’algorithme qui s’est passé.
L’algorithme ECDSA est très sûr pour lesquels il est impossible de trouver la clé privée... tant que la mise en œuvre se fait correctement bien sûr. S’il y avait un moyen de trouver la clé privée, puis la sécurité de chaque ordinateur, le site Web, le système peut être compromise étant donné que beaucoup de systèmes comptent sur ECDSA pour leur sécurité, et il est impossible de craquer.