Angewandte Kryptographie. Wie wir Bitcoins für 300.000 Dollar restaurierten

Ich werde eine Geschichte mit Ihnen teilen. Vor ungefähr zwanzig Jahren erhielt ich einen Abschluss in Physik, beschäftigte mich aber mit Reverse Engineering und Kryptoanalyse. Unsere Firma AccessData arbeitete in den späten 90ern und frühen 2000ern. Dann hob die US-Regierung nach und nach die Beschränkungen für den Export von Kryptografie auf, doch der Passwortschutz in den meisten Programmen war immer noch ziemlich nutzlos. Wir haben Office-Programme erstellt, Reverse Engineering durchgeführt, den Verschlüsselungsalgorithmus herausgefunden und dann den kryptografischen Schutz aufgehoben.

Es war ein endloser Strom interessanter, aber nicht besonders schwieriger mathematischer Rätsel. Für die ganze Zeit habe ich ungefähr vierzig Passwort-Cracker geschrieben. Wir haben sie an Privatanwender, Systemadministratoren sowie lokale und föderale Strafverfolgungsbehörden verkauft. Ich musste mehrmals zum Schulungszentrum für Strafverfolgungsbehörden des Bundes in Glinko, um den Mitarbeitern des Geheimdienstes, des FBI und der ATF die Grundlagen der Kryptographie und die Verwendung unserer Produkte zu erklären .

Ich erinnere mich besonders an zwei Projekte. Das erste war Microsoft Word 97. Bevor es angezeigt wurde, wurden die Dateien mit XOR-Bytes Klartext und einer 16-Byte-Zeichenfolge verschlüsselt, die vom Kennwort ausgegeben wurde. Die häufigsten Bytes in einer Word-Datei waren normalerweise 0x00, 0xFF oder 0x20 (Leerzeichen). Wir haben also nur das häufigste Zeichen in jeder Spalte ausgewählt und 3 bis ¹⁶ Optionen aktiviert . Die Schlüsselwiederherstellung erfolgte normalerweise sofort, aber damit die Leute nicht glaubten, Geld verschwendet zu haben, haben wir eine kleine Animation ähnlich der Hollywood-Hacker-Szene mit vielen zufälligen Zeichen eingefügt, aus der nach und nach das richtige Passwort hervorgeht.

Microsoft Word 97 hat alles geändert. Vielleicht hat MSDN auch das Verschlüsselungsformat enthüllt, aber unser kleines Unternehmen konnte sich kein Abonnement leisten. Und nicht die Tatsache, dass wir nach Erhalt von Informationen ein Programm zum Hacken schreiben dürfen. Um dies zu verstehen, habe ich in SoftICE unmittelbar nach Eingabe des Kennworts einen Haltepunkt festgelegt und dann den Stapel langsam nach oben verschoben, bis ich einen Algorithmus gefunden habe. Dies war vor der Veröffentlichung von IDA Pro, also hatte ich Dutzende Seiten mit Ausdrucken mit einem Assembler-Code, der mit einer roten Markierung an meiner Wand versehen war. Ich war sehr erfreut, als ich es endlich herausfand. Zu dieser Zeit durfte Microsoft nur 40-Bit-Kryptografie exportieren, daher implementierte das Unternehmen pflichtbewusst streng zulässige Kryptografie: Sie haben das Kennwort in MD5 wiederholt mit "salt" (zufällig ausgewählte Bytes aus der Datei) gehasht.Um einen 40-Bit-Schlüssel zu erhalten, wurde Salz hinzugefügt und erneut gehasht. Die Kennwortprüfung auf Computern dieser Zeit dauerte etwa eine halbe Sekunde. Wir mussten einen Wörterbuchangriff verwenden, da es fast unmöglich war, ein Passwort mit brutaler Gewalt zu knacken. Aus diesem Grund haben wir einen Passwort-Cracker für große Unternehmen und Agenturen geschrieben. Das Programm führte die Bruteforce eines 40-Bit-Schlüsselraums mit diesen ausgefallenen MMX-Pentium-Anweisungen aus. Ich habe gehört, dass sie einmal neun Monate gearbeitet hat, bevor ich das Passwort abgeholt habe.Das Programm führte die Bruteforce eines 40-Bit-Schlüsselraums mit diesen ausgefallenen MMX-Pentium-Anweisungen aus. Ich habe gehört, dass sie einmal neun Monate gearbeitet hat, bevor ich das Passwort abgeholt habe.Das Programm führte die Bruteforce eines 40-Bit-Schlüsselraums mit diesen ausgefallenen MMX-Pentium-Anweisungen aus. Ich habe gehört, dass sie einmal neun Monate gearbeitet hat, bevor ich das Passwort abgeholt habe.

Ein weiteres wirklich lustiges Projekt sind Zip-Archive. Phil Katz, der Erfinder von PKZIP, traf für diese Zeit eine ungewöhnliche Entscheidung, sein Dateiformat zu dokumentieren und diese Dokumentation in das Softwarepaket aufzunehmen, was ZIP zu einem bevorzugten Format für Entwickler machte. Roger Schlafly entwickelte eine Stream-Verschlüsselung zum Verschlüsseln von Archiven. Der Zip-Standard wurde unter Windows schnell zum beliebtesten Standard, und viele andere Formate, wie z. B. Java-Java-Dateien und OpenOffice-Dokumente, waren Zip-Dateien mit einer bestimmten Verzeichnisstruktur. Die Open-Source-Version des Programms hieß InfoZIP und war die Basis für fast alle proprietären Zip-Archivierer wie WinZip. Als ich anfing, WinZip zu hacken, nahm es 95% des Marktes ein.

Eli Biham und Paul Kocher veröffentlichten eine Beschreibung des Angriffs mit bekanntem Klartext (Text vor der Verschlüsselung), aber in unserem Fall wurde der bekannte Klartext archiviert . Um die Huffman-Codes am Anfang einer komprimierten Datei zu erhalten, benötigen Sie im Wesentlichen die gesamte Datei. Der Angriff war für die Strafverfolgung praktisch nutzlos.

Die Zip - Chiffre 96 Bits des internen Zustand enthält, aufgeteilt in drei 32-Bit - Blöcke genannt key0, key1undkey2. Der erste und dritte sind der interne Zustand von zwei Kopien von CRC32, einem linearen Schieberegister mit Rückkopplung (ein einfaches mathematisches Modell, mit dem Sie pseudozufällige Sequenzen erstellen können). Kurz gesagt, um den Status mit einem neuen Datenbyte zu aktualisieren, verschieben Sie alles um ein Byte nach unten (verwerfen des unteren Bytes) und führen dann XOR mit einer Konstanten aus der Konvertierungstabelle aus, die durch das Datenbyte nach XOR mit dem unteren Byte indiziert wird. key1Ist der interne Zustand eines abgeschnittenen linearen kongruenten Generators (TLCG). Um den internen Status zu aktualisieren, fügen wir ein Datenbyte hinzu, multipliziert mit einer Konstanten, die wir aufrufencund fügen Sie eine hinzu. Die Verschlüsselung funktioniert wie folgt: Geben Sie das Datenbyte in das erste CRC32 ein, nehmen Sie das untere Byte und geben Sie es in TLCG ein, nehmen Sie das obere Byte von dort und geben Sie es in das zweite CRC32 ein, nehmen Sie den Status und das Quadrat (ungefähr) und geben Sie dann das zweite Byte aus führen zu einem Strom von Bytes. Um 96 Bit des internen Status zu initialisieren, beginnen Sie mit einem bekannten Status, verschlüsseln das Kennwort und verschlüsseln dann zehn Byte Salt.

PKZIP erhält seine Salt-Bytes und ordnet Speicher zu, ohne ihn zu initialisieren. Daher enthält es Materialstücke aus anderen laufenden Programmen, Bildern oder Dokumenten. Dies funktionierte unter Windows einwandfrei, aber auf vielen Unix-Systemen wird der Speicher bei der Zuweisung automatisch initialisiert. InfoZIP wählt Salzbytes mit der Funktion ausrandC Sprache. Er initialisierte den Status des Zufallszahlengenerators, indem er einen XOR-Zeitstempel für die Prozess-ID erstellte und dann zehn Bytes pro Datei generierte. In diesem Fall war es theoretisch möglich, unter Kenntnis des Zeitstempels und der Prozesskennung die Bytes des Headers wiederherzustellen, was wiederum die Durchführung eines Angriffs von Biham und Kocher ermöglichte. Es scheint, dass InfoZIP-Autoren von diesem Angriff wussten, weil sie einen Schritt weiter gingen - und den Header mit einem Passwort verschlüsselten. Somit hatte der Angreifer nur das Doppelte des verschlüsselten Klartextes, und der Angriff hätte nicht funktioniert.

Ich habe dies bemerkt, da das Passwort in beiden Durchgängen gleich ist und das erste Byte des Streams in jedem von ihnen das gleiche ist. Genauso wie beim zweimaligen Schalten des Lichtschalters bleibt er dort, wo er am Anfang war. Wenn das Byte XOR mit demselben Stream-Byte wiederholt wird, bleibt es unberührt. Dadurch konnte ich einen sehr mächtigen Angriff nur auf Chiffretext entwickeln : Nachdem ich fünf verschlüsselte Dateien im Archiv erhalten hatte, konnte ich den internen Status der Funktion ausgebenrandohne auf den Zeitstempel schauen oder die Prozess-ID kennen zu müssen. Dann könnte ich die ursprünglichen unverschlüsselten Header generieren. Da nur wenige Bits in jedem Teil der Verschlüsselung den nächsten Teil beeinflussen, könnte ich auch ein paar Bits des Status erraten und prüfen, ob das zweimalige Decodieren der nächsten Bytes die erwartete Antwort liefert. Als ich mich vorwärts bewegte, musste ich immer weniger Teile des Schlüssels erraten. Jede zusätzliche Datei darf auch mehr potenzielle Schlüsselmaterialien ausschließen. Zu diesem Zeitpunkt dauerte es auf einem Desktop mehrere Stunden. Ich habe einen Artikel darüber veröffentlicht und die Gelegenheit erhalten, ihn auf der Fast Software Encryption 2001-Konferenz in Japan vorzustellen.

Bald verließ ich AccessData, arbeitete ein Jahr lang für ein Startup in neuronalen Netzen, studierte drei Jahre lang bei Chris Kaloud für einen Master in Informatik an der University of Auckland, begann mein Doktoratsstudium bei dem mathematischen Physiker John Baez an der University of California Riverside und arbeitete sechs Jahre lang Als Teil des Applied Security-Teams von Google promovierte er und wurde einige Jahre später CTO des neuen Startups.

Vor ungefähr einem halben Jahr erhielt ich ganz unerwartet eine Nachricht auf LinkedIn von einem Russen. Er las den Artikel, den ich vor 19 Jahren geschrieben hatte, und wollte wissen, ob der Angriff auf ein Archiv funktionieren würde, das nur zwei Dateien enthält. Eine schnelle Analyse ergab, dass eine enorme Menge an Rechenleistung und Geld erforderlich ist. Da es nur zwei Dateien gibt, gibt es in jeder Phase der Auswahl viel mehr Fehlalarme. Das Ergebnis sind ^2.773 mögliche Schlüssel zum Testen, fast 10 Sextillionen. Ich habe berechnet, dass ein großer Cluster auf der GPU ein Jahr lang funktionieren wird und seine Kosten etwa 100.000 US-Dollar betragen werden. Er schlug mich und sagte, dass er bereit sei, so viel Geld auszugeben, um den Schlüssel wiederherzustellen.

Tatsache ist, dass er im Januar 2016 Bitcoins für etwa 10 bis 15.000 US-Dollar gekauft und die Schlüssel in einer verschlüsselten Zip-Datei abgelegt hat. Jetzt kosteten sie mehr als 300.000 Dollar, und er konnte sich nicht an das Passwort erinnern. Glücklicherweise hatte er immer noch den Original-Laptop und kannte die Verschlüsselungszeit genau. Da InfoZip die Entropie anhand eines Zeitstempels ableitet, versprach dies, die Anzahl der möglichen Schlüsseloptionen „nur“ auf 10 Billionen zu reduzieren - und machte den Angriff auf eine durchschnittliche GPU-Farm in ein paar Monaten durchaus machbar. Wir haben einen Vertrag unterschrieben und ich machte mich an die Arbeit.

Ich habe einige Zeit damit verbracht, den im Artikel beschriebenen Angriff wiederherzustellen. Zu meinem Leidwesen gab es einige knifflige Details, die ich in dem Artikel übersehen habe, aber ich habe sie wieder ausgearbeitet. Und dann stellte ich fest, dass ich bei der Bewertung des Rechenaufwands einen schrecklichen Fehler gemacht hatte!

Bei meinem ursprünglichen Angriff habe ich die hohen Bytes der Schlüssel key1 · c, key1 · c ² , key1 · c ³ und key1 · c ⁴ erraten . Als ich dieses vierte Byte erraten hatte, kannte ich den vollständigen Zustand des Restes der Chiffre. Ich musste nur diese vier Bytes in den ursprünglichen Schlüssel1 konvertieren, und das war's. Ich würde den 32-Bit-Statusraum für key1 durchgehen und jeden einzelnen überprüfen, um festzustellen, ob er die richtigen hohen Bytes liefert. Hier müssten jedoch Billionen Schlüssel überprüft werden; Wenn Sie jeweils 2 ³² Tests durchführen müssen, würde dies mehrere hunderttausend Jahre dauern.

Ich erinnerte mich vage daran, dass einige Arbeiten an der TLCG-Kryptoanalyse durch Reduzierung der Gitterbasis durchgeführt worden waren, also grub ich den Originalartikel aus. So war es! Es war nur notwendig, das Gitter mit den durch 2 ³² gegebenen Basisvektoren und dem Konstantengrad aus TLCG zu bestimmen und dann die Basis des Gitters zu reduzieren. Auf einer reduzierten Basis könnte ich den ursprünglichen Zustand aus hohen Bytes wiederherstellen, indem ich einfach die Matrizen multipliziere.

Zumindest ist das die Idee. Es dauerte fünf Bytes, um zum einzig richtigen Ergebnis zu gelangen, und zu diesem Zeitpunkt hatte ich nur vier Angriffe. Der im Artikel beschriebene Prozess gab selten die richtige Antwort. Ich wusste jedoch, dass die Antwort nahe an der richtigen liegen sollte, sodass ich alle möglichen Werte von Schlüssel1 durchgehen und den Unterschied zwischen der tatsächlichen und der wahren Antwort überprüfen konnte. Der Unterschied war schon immer einer von 36 Vektoren! Mit dieser Optimierung kann ich die Suche auf nur 36 Optionen anstatt auf vier Milliarden reduzieren. Wir sind noch im Geschäft.

Außerdem standen wir vor dem Problem, Daten zwischen Maschinen mit einer GPU zu übertragen. Mein Geschäftspartner Nash Foster war an der Implementierung der GPU beteiligt. Er beriet mich, wie schnell verschiedene Operationen ausgeführt werden, und schrieb die meisten unterstützenden Strukturen für die Anwendung mit meinem Code für Krypto-Cracking. Wie bekomme ich diese Petabyte an Kandidatenschlüsseln für GPU-Tests? Sie werden fast die ganze Zeit untätig sein und ihre Kerne in Erwartung der Arbeit werfen. Mir ist aufgefallen, dass in jeder Phase meines Angriffs viele Bits überprüft werden und dann nur einer von ungefähr 65.000 Kandidaten gerettet wird. Wenn ich einen Weg zur Ausgabe finden könnteDiese Bits basieren auf den verfügbaren Informationen und erzwingen nicht nur Brute-Force-Informationen. Ich würde viel Arbeit und vor allem viel Netzwerkverkehr sparen. Das Problem hierbei waren zu komplizierte Algorithmen, die eine Mischung aus endlichen Feldern mit Ringen von ganzen Zahlen darstellen, aber nicht sehr gut zueinander passen.

Ich dachte an andere kryptoanalytische Angriffe, von denen ich weiß. Einer von ihnen war der "Meet-in-the-Middle" -Angriff. Sie schien eine vielversprechende Kandidatin zu sein. Der Angriff wird auf eine Blockverschlüsselung angewendet, wenn ein Teil des Schlüsselmaterials für die erste Hälfte der Verschlüsselung und der andere Teil für die zweite verwendet wird. Dies galt für die Zip-Chiffre, aber das Schlüsselmaterial überwog bei weitem die Anzahl der Bits in der Mitte. Dann kam mir der Gedanke, was passiert, wenn wir die Linearität von CRC32 verwenden: Wenn wir die XOR-Operation an den beiden Ausgängen des letzten CRC32 ausführen, ist das Ergebnis unabhängig von key2! Anstatt den Zwischenzustand der Chiffre zu berechnen und in einer Tabelle zu speichern, würde ich den XOR der beiden Zwischenzustände berechnen und stattdessen speichern.

Ich schrieb ein differenziertes Meeting „Meeting in the Middle“ und startete es auf meinem Laptop. Die Etappe, die früher mehrere Stunden dauerte, war jetzt in wenigen Sekunden fertig. Die nächste Phase, die in der GPU-Farm eine Woche dauern konnte, endete in wenigen Stunden auf einer leistungsstarken CPU. Ich konnte die dritte Stufe des Angriffs nicht genug optimieren, um die Gesamtgeschwindigkeit zu beeinflussen, aber es war nicht erforderlich, die Daten vollständig zu verschieben: Wir haben nur die Kandidaten für jede GPU auf dem Computer mit diesen Karten berechnet. Nash schrieb GPU-Code, der mit unglaublicher Geschwindigkeit funktionierte.

Der Angriff dauerte zehn Tage und endete mit einem Misserfolg.

Mein Herz war gebrochen. Fehlt uns einer der möglichen Schlüssel? Wir gingen zurück und sahen uns die maximale Prozesskennung auf seinem Laptop an und stellten fest, dass es einige Bits mehr waren als wir erwartet hatten, und daher gab es etwas mehr mögliche Quellensamen für rand. Ich habe auch unseren gesamten Code überprüft. Vielleicht haben wir etwas verpasst? Vielleicht hat die Version auf der CPU irgendwie anders funktioniert als auf der GPU? Schließlich stellte ich fest, dass die Version auf der GPU nicht den richtigen Schlüssel finden konnte, als sie an zweiter Stelle in der Kandidatenliste stand, sondern nur an der ersten. Beim Durchsuchen des Codes haben wir festgestellt, dass wir den Blockindex mit dem Stream-Index verwechselt haben, als wir den Offset in der Datenstruktur berechnet haben.

Wir haben den Fehler behoben, den Code erneut ausgeführt und innerhalb eines Tages den richtigen Schlüssel gefunden. Unser Kunde war sehr zufrieden und gab uns einen großen Bonus dafür, dass wir den Schlüssel so schnell gefunden und ihm so viel Geld gespart haben, als wir ursprünglich angenommen hatten.

Jetzt suche ich Arbeit. Wenn Sie interessante Probleme mit der technischen Analyse oder Optimierung haben, lassen Sie es mich wissen.

---