Cryptographie appliquée. Comment nous avons restauré des bitcoins pour 300 mille dollars

Je vais partager avec vous une histoire. Il y a une vingtaine d'années, j'ai obtenu un diplôme en physique, mais j'étais engagé dans l'ingénierie inverse et la cryptanalyse. Notre entreprise AccessData a travaillé à la fin des années 90 et au début des années 2000. Ensuite, le gouvernement américain a progressivement levé les restrictions à l'exportation de la cryptographie, mais la protection par mot de passe dans la plupart des programmes était encore plutôt inutile. Nous avons pris des programmes bureautiques, j'ai effectué une ingénierie inverse et trouvé l'algorithme de cryptage, puis brisé la protection cryptographique.

C'était un flot infini d'énigmes mathématiques intéressantes, mais pas particulièrement difficiles. Pendant tout ce temps, j'ai écrit une quarantaine de crackers de mots de passe. Nous les avons vendus à des utilisateurs à domicile, à des administrateurs système et à des organismes d'application de la loi locaux et fédéraux. J'ai dû me rendre plusieurs fois au centre de formation fédéral des forces de l'ordre à Glinko pour expliquer aux gars des services secrets, du FBI et de l' ATF les bases de la cryptographie et comment utiliser nos produits.

Je me souviens surtout de deux projets. Le premier était Microsoft Word 97. Avant son apparition, les fichiers étaient cryptés à l'aide de XOR octets de texte clair et d'une chaîne de 16 octets qui était sortie à partir du mot de passe. Les octets les plus courants dans un fichier Word étaient généralement 0x00, 0xFF ou 0x20 (espace), nous avons donc simplement choisi le caractère le plus courant dans chaque colonne et vérifié 3 à ¹⁶ options. La récupération des clés se produisait généralement instantanément, mais pour que les gens ne pensent pas qu'ils avaient gaspillé de l'argent, nous avons inséré une petite animation similaire à la scène des hackers hollywoodiens avec beaucoup de caractères aléatoires, d'où le mot de passe correct émerge progressivement.

Microsoft Word 97 a tout changé. Peut-être que MSDN a également révélé le format de cryptage, mais notre petite entreprise ne pouvait pas se permettre un abonnement. Et pas le fait que nous serions autorisés à écrire un programme de piratage après avoir reçu des informations. Pour comprendre, dans SoftICE, j'ai défini un point d'arrêt immédiatement après avoir entré le mot de passe, puis j'ai lentement remonté la pile jusqu'à ce que je trouve un algorithme. C'était avant la sortie d'IDA Pro, donc j'avais des dizaines de pages d'impressions avec un code assembleur strié d'un marqueur rouge sur mon mur. J'étais très content quand j'ai finalement compris. À cette époque, Microsoft n'était autorisé à exporter que la cryptographie 40 bits, de sorte que la société a consciencieusement mis en œuvre la cryptographie strictement autorisée: ils ont haché à plusieurs reprises le mot de passe dans MD5 en utilisant "salt" (octets sélectionnés au hasard dans le fichier),pour obtenir une clé de 40 bits, puis du sel a été ajouté et haché à nouveau. La vérification des mots de passe sur les ordinateurs de cette époque a pris environ une demi-seconde. Nous avons dû utiliser une attaque par dictionnaire car il était presque impossible de déchiffrer un mot de passe avec force brute. En conséquence, nous avons écrit un cracker de mot de passe pour les grandes entreprises et agences. Le programme a exécuté la force brute d'un espace de clé de 40 bits en utilisant ces instructions fantaisies MMX Pentium. J'ai entendu dire qu'elle avait travaillé pendant neuf mois avant de récupérer le mot de passe.Le programme a exécuté la force brute d'un espace de clé de 40 bits en utilisant ces instructions fantaisies MMX Pentium. J'ai entendu dire qu'elle avait travaillé pendant neuf mois avant de récupérer le mot de passe.Le programme a exécuté la force brute d'un espace de clé de 40 bits en utilisant ces instructions fantaisies MMX Pentium. J'ai entendu dire qu'elle avait travaillé pendant neuf mois avant de récupérer le mot de passe.

Un autre projet vraiment amusant est l'archive zip. Phil Katz, créateur de PKZIP, a pris une décision inhabituelle pour cette période de documenter son format de fichier et d'inclure cette documentation dans le progiciel, ce qui a fait de ZIP un format préféré pour les développeurs. Roger Schlafly a développé un chiffrement de flux pour crypter les archives. La norme zip est rapidement devenue la plus populaire sous Windows, et de nombreux autres formats, tels que les fichiers java .jar et les documents OpenOffice, étaient en fait des fichiers zip avec une structure de répertoires spécifique à l'intérieur. La version open source du programme s'appelait InfoZIP, elle était la base de presque tous les archiveurs zip propriétaires, tels que WinZip. Quand j'ai commencé à pirater WinZip, il occupait 95% du marché.

Eli Biham et Paul Kocher ont publié une description de l'attaque avec un texte en clair connu (texte avant chiffrement), mais dans notre cas, le texte en clair connu a été archivé . Pour obtenir les codes Huffman au début d'un fichier compressé, vous avez essentiellement besoin de tout le fichier. L'attaque était pratiquement inutile pour les forces de l'ordre.

Le chiffrement zip contient 96 bits d'état interne, divisés en trois blocs de 32 bits appelés key0, key1etkey2. Le premier et le troisième sont l'état interne de deux copies de CRC32, un registre à décalage linéaire avec rétroaction (un modèle mathématique simple qui vous permet de créer des séquences pseudo-aléatoires). En bref, pour mettre à jour l'état avec un nouvel octet de données, vous diminuez tout d'un octet (en supprimant l'octet inférieur), puis effectuez XOR avec une constante de la table de conversion indexée par l'octet de données après XOR avec l'octet inférieur. key1Est l'état interne d'un générateur de congruence linéaire tronqué (TLCG). Pour mettre à jour son état interne, nous ajoutons un octet de données, multiplié par une constante, que nous appelleronscet ajoutez-en un. Le chiffrement fonctionne comme suit: entrez l'octet de données dans le premier CRC32, puis prenez l'octet inférieur et entrez-le dans le TLCG, puis prenez l'octet supérieur à partir de là et entrez-le dans le deuxième CRC32, puis prenez l'état et le carré (environ), puis émettez le deuxième octet entraîner un flux d'octets. Pour initialiser 96 bits de l'état interne, vous commencez avec un état connu et cryptez le mot de passe, puis cryptez dix octets de sel.

PKZIP obtient ses octets salés, allouant de la mémoire sans l'initialiser, il contient donc des morceaux de matériel provenant d'autres programmes ou images en cours d'exécution, ou de documents, peu importe. Cela fonctionnait bien sous Windows, mais sur de nombreux systèmes Unix, la mémoire s'initialise automatiquement lorsqu'elle est allouée. InfoZIP sélectionne les octets de sel en utilisant la fonctionrandLangage C. Il a initialisé l'état du générateur de nombres aléatoires en créant un horodatage XOR sur l'ID de processus, puis a généré dix octets par fichier. Dans ce cas, connaissant l'horodatage et l'identifiant du processus, il était possible, théoriquement, de récupérer les octets de l'en-tête, ce qui, à son tour, permettait de mener une attaque de Biham et Kocher. Il semble que les auteurs d'InfoZIP étaient au courant de cette attaque car ils sont allés plus loin - et ont chiffré l'en-tête à l'aide d'un mot de passe. Ainsi, l'attaquant n'avait que deux fois le texte en clair chiffré, et l'attaque n'aurait pas fonctionné.

Je l'ai remarqué, car le mot de passe est le même dans les deux passages, le premier octet du flux est le même dans chacun d'eux. De la même manière que lorsque l'interrupteur d'éclairage est commuté deux fois, il reste où il était au début, lorsque l'octet est répété XOR avec le même octet de flux, il reste intact. Cela m'a permis de développer une attaque très puissante uniquement sur le texte chiffré : après avoir reçu cinq fichiers cryptés dans l'archive, j'ai pu sortir l'état interne de la fonctionrandsans avoir à regarder l'horodatage ou à connaître l'ID du processus. Ensuite, j'ai pu générer les en-têtes originaux non chiffrés. Étant donné que seulement quelques bits dans chaque partie du chiffrement affectent la partie suivante, je pourrais également deviner quelques bits d'état et vérifier si le décodage des octets suivants donne la réponse que j'attendais. En avançant, je devais deviner de moins en moins de morceaux de clé. Chaque fichier supplémentaire a également permis d'exclure davantage de documents clés potentiels; à cette époque, cela prenait plusieurs heures sur un seul bureau. J'ai publié un article à ce sujet et j'ai eu l'occasion de le présenter au Japon lors de la conférence Fast Software Encryption 2001.

Bientôt, j'ai quitté AccessData, travaillé pour une startup sur les réseaux de neurones pendant un an, passé trois ans à étudier pour une maîtrise en informatique à l'Université d'Auckland avec Chris Kaloud, commencé mes études de doctorat avec le physicien mathématicien John Baez à l'Université de Californie Riverside, travaillé pendant six ans Au sein de l'équipe Google Applied Security, il a terminé son doctorat et, quelques années plus tard, est devenu CTO de la nouvelle startup.

Il y a environ six mois, j'ai reçu de manière inattendue un message sur LinkedIn d'un Russe. Il a lu l'article que j'ai écrit il y a 19 ans et voulait savoir si l'attaque fonctionnerait sur une archive qui ne contient que deux fichiers. Une analyse rapide a montré qu'il nécessite une énorme quantité de puissance de calcul et d'argent. Puisqu'il n'y a que deux fichiers, à chaque étape de la sélection, il y a beaucoup plus de faux positifs. Le résultat est ^{2 773} clés possibles pour les tests, soit près de 10 sextillions. J'ai calculé qu'un grand cluster sur le GPU fonctionnera pendant un an, et son coût sera d'environ 100 000 dollars. Il m'a frappé en disant qu'il avait accepté de dépenser autant d'argent pour restaurer la clé.

Le fait est qu'en janvier 2016, il a acheté des bitcoins pour environ 10 à 15 000 $ et a placé les clés dans un fichier zip crypté. Maintenant, ils coûtaient plus de 300 000 $, et il ne se souvenait pas du mot de passe. Heureusement, il avait toujours l'ordinateur portable d'origine et il connaissait exactement l'heure de cryptage. Étant donné qu'InfoZip génère une entropie basée sur un horodatage, cela a promis de réduire considérablement le nombre d'options clés possibles «à seulement» 10 quintillions - et a rendu l'attaque tout à fait réalisable en quelques mois sur une batterie de GPU moyenne. Nous avons signé un contrat et je me suis mis au travail.

J'ai passé un peu de temps à récupérer l'attaque décrite dans l'article. À mon grand regret, il y avait quelques détails délicats que j'ai manqués dans l'article, mais je les ai retravaillés. Et puis j'ai découvert que j'avais fait une terrible erreur en évaluant la quantité de calcul!

Dans mon attaque d'origine, j'ai deviné les octets élevés des clés key1 · c, key1 · c ² , key1 · c ³ et key1 · c ⁴ . Au moment où j'ai deviné ce quatrième octet, je connaissais l'état complet du reste du chiffre; J'avais juste besoin de convertir ces quatre octets en key1 d'origine, et c'est tout. Je passerais en revue l'espace d'état 32 bits pour key1 et vérifierais chacun pour voir s'il donne les bons octets élevés. Cependant, ici, il faudrait vérifier des quintillions de clés; si vous avez besoin de faire 2 ³² tests sur chacun, cela prendrait plusieurs centaines de milliers d'années.

Je me souvenais vaguement que certains travaux avaient été effectués sur la cryptanalyse TLCG par la réduction de la base du réseau, alors j'ai déterré l'article original. Donc c'était ça! Il fallait juste déterminer le réseau avec les vecteurs de base donnés par 2 ³² et le degré de constante de TLCG, puis faire la réduction de la base du réseau. Sur une base réduite, je pouvais restaurer l'état d'origine à partir d'octets élevés en multipliant simplement les matrices.

C'est du moins l'idée. Il a fallu cinq octets pour arriver au seul résultat correct, et à ce moment-là, je n'avais que quatre attaques. Le processus décrit dans l'article a rarement donné la bonne réponse. Cependant, je savais que la réponse devait être proche de la bonne, donc je pouvais passer en revue toutes les valeurs possibles de key1 et vérifier la différence entre la vraie réponse et la vraie. La différence a toujours été l'un des 36 vecteurs! Avec cette optimisation, je peux réduire la recherche à seulement 36 options au lieu de quatre milliards. Nous sommes toujours en activité.

De plus, nous avons été confrontés au problème du transfert de données entre des machines avec un GPU. Mon partenaire commercial, Nash Foster, a été impliqué dans la mise en œuvre du GPU. Il m'a informé de la rapidité avec laquelle diverses opérations sont effectuées et a écrit la plupart des structures de support pour l'application avec mon code de crypto-cracking. Comment obtenir ces pétaoctets de clés candidates pour les tests GPU? Ils seront inactifs presque tout le temps, jetant leurs noyaux en prévision du travail. Il m'est venu à l'esprit qu'à chaque étape de mon attaque, beaucoup de bits sont vérifiés, puis qu'un seul des 65 000 candidats environ est enregistré. Si je pouvais trouver un moyen de sortirces bits sont basés sur les informations disponibles, et pas seulement par force brute, j'économiserais beaucoup de travail et, plus important encore, beaucoup de trafic réseau. Le problème ici était des algorithmes trop compliqués, représentant un mélange de champs finis avec des anneaux d'entiers, mais ils ne s'adaptent pas très bien les uns aux autres.

J'ai pensé à d'autres attaques cryptanalytiques que je connais. L'un d'eux était l'attaque «rencontre au milieu». Elle semblait une candidate prometteuse. L'attaque est appliquée à un chiffrement par blocs lorsqu'il utilise une partie du matériel clé pour effectuer la première moitié du chiffrement et l'autre partie pour la seconde. Cela s'appliquait au code zip, mais le matériau clé dépassait de loin le nombre de bits au milieu. Ensuite, il m'est venu à l'esprit, que faire si nous utilisons la linéarité du CRC32: si nous effectuons l'opération XOR sur les deux sorties du dernier CRC32, alors le résultat sera indépendant de key2! Au lieu de calculer l'état intermédiaire du chiffre et de le stocker dans une table, je calculerais le XOR des deux états intermédiaires et le stockerais à la place.

J'ai écrit une réunion différentielle «réunion au milieu» et je l'ai lancée sur mon ordinateur portable. L'étape, qui prenait auparavant plusieurs heures, est maintenant terminée en quelques secondes. L'étape suivante, qui pourrait prendre une semaine sur la batterie de GPU, s'est terminée en quelques heures sur un processeur puissant. Je ne pouvais pas optimiser suffisamment la troisième étape de l'attaque pour affecter la vitesse globale, mais il n'était pas nécessaire de déplacer complètement les données: nous venons de calculer les candidats pour chaque GPU sur l'ordinateur avec ces cartes. Nash a écrit du code GPU qui a fonctionné à une vitesse incroyable.

L'attaque a duré dix jours et s'est soldée par un échec.

Mon coeur était brisé. Manquons-nous l'une des clés possibles? Nous sommes revenus et avons regardé l'identifiant de processus maximum sur son ordinateur portable et avons constaté que c'était plusieurs bits de plus que ce à quoi nous nous attendions, et donc qu'il y avait un peu plus de sources possibles pour rand. J'ai également revérifié tout notre code. Peut-être que nous avons manqué quelque chose? Peut-être que la version sur le CPU fonctionnait différemment que sur le GPU? Enfin, j'ai trouvé que la version sur le GPU ne pouvait pas trouver la bonne clé lorsqu'elle était deuxième dans la liste des candidats, mais seulement la première. En fouillant dans le code, nous avons constaté que nous avons confondu l'index de bloc avec l'indice de flux lors du calcul du décalage dans la structure de données.

Nous avons corrigé l'erreur, réexécuté le code et trouvé la clé correcte dans la journée. Notre client était très satisfait et nous a donné un gros bonus pour trouver la clé si rapidement et lui faire économiser beaucoup d'argent au-delà de notre estimation initiale.

Maintenant je cherche du travail. Si vous avez des problèmes intéressants avec l'analyse technique ou l'optimisation, faites le moi savoir.

---