Wettangebot: Verschlüsselung geknackt - mit Erklärung

[Henryk Plötz]

Moin,

Also, wir fangen an mit dem "Geheimtext" (aWRZYWpoZiBrMDsqJydvaVVPIE9IYiU6L1O1tcggtHkgVVnkFoz9SPpPP84eapS/pzTsc...) von http://remso.de/wette.php: ciphertext. Relativ offensichtlich ist das BASE64-codiert, also erstmal [code]$ base64 -d < ciphertext > ciphertext.d64[/code] um ciphertext.d64 zu erhalten. Das wird die Datei sein mit der wir ab jetzt arbeiten.

Wir wissen: Es ist eine einfache Polyalphabetische Substitution. Die übliche erste Vorgehensweise ist Autokorrelation: autocorr.c: [code] henryk@dawn ~/xorwette $ time ./autocorr ciphertext.d64 > ciphertext.autocorr

real 0m6.487s user 0m6.080s sys 0m0.010s [/code]

Oder als Graph:

Wie wir sehen sehen wir nichts. Die Autokorrelation bringt uns in diesem Fall also nichts, nichtmal die Schlüssellänge. Nagut, nächste Standardvorgehensweise für unbekannte Dateien ist ein Hexdump ([code]hexdump -C ciphertext.d64 | less[/code]): und

Da sind mehrere ASCII-Zeichen am Dateifang was sehr verdächtig ist und bei einer verschlüsselten Datei nie passieren dürfte. Aber am Dateiende ist's noch viel schlimmer: viel ASCII-Text, der sich auch noch wiederholt (klassisch für polyalphetische Chiffrierungen wenn immer wieder das gleiche Zeichen verschlüsselt wird). Das war die Stelle an der mir klar war dass dieses Verfahren sehr einfach gebrochen werden können müsste. Wenn man sich die Verteilung der Byte-Werte ansieht (und vor allem das most significant bit) sieht man dass die Datei mit etwa 26 Bytes ohne MSBit gesetzt beginnt und mit etwa 600 bis 700 Byte mit nur wenigen MSBit gesetzt endet, dazwischen scheinen die Werte zufällig verteilt zu sein. Eigentlich[tm] sind zufällig aussehende Bytewerte ein Zeichen für ordentliche Verschlüsselung, bzw. andersrum: Wenn die Bytes nicht zufällig verteilt sind ist es nicht ordentlich verschlüsselt. Wir haben schon die nicht-zufällige Verteilung am Anfang und Ende festgestellt, also keine ordentliche Verschlüsselung, also werden das in der Mitte einfach komprimierte Daten sein.

Was beginnt mit ein paar Bytes ohne MSBit gesetzt, enthält komprimierte Daten und endet mit relativ vielen gleichen (0) Bytes mit nur wenigen MSBit gesetzt? Theorie: ZIP. Eine ZIP-Datei würde mit den vier Bytes ['P', 'K', '\x03', '\x04'] beginnen, wir behalten das mal im Hinterkopf.

Vielleicht erstmal die Schlüssellänge bestimmen. Dazu müssten wir die Wiederholungen am Ende der Datei quantisieren. Ein paar der auffälligen Muster suchen und Abstände bestimmen: "qpsz}|" zu "qpsz}|", "<:cbmlbm" zu "<:cbmlbm" usw. Problem: Da kommen dauernd unterschiedliche Abstände raus. Eigentlich[tm] sollten die Abstände gleich sein und gleich der Schlüssellänge sein. Demnach hätten wir gleichzeitig Schlüssellängen von 49, 173, 172, 46, 47, 171, usw. Wir erinnern uns an http://forum.de.selfhtml.org/archiv/2008/4/t169920/#m1110125 mit dem Link zu http://tm3-fuhrpark.de/send_file.php?infile=send_file.php (jetzt defunct, konservierte Version hier). Dort wurde nicht die straight-forward Vigenère-Verschlüsselung verwendet sondern eine unmotivierte (und nur wenig sicherere) Variante: Statt den Schlüssel direkt zu wiederholen, wird er vor jeder Wiederholung um 5 rotiert. Nebenbei ist da noch ein Bug drin der pro Schlüssel-Wiederholung ein Zeichen Klartext unverschlüsselt in die Ausgabe schreibt (die Prüfung ist auf if ( $j > strlen($schl_kopie) ) statt auf if ( $j >= strlen($schl_kopie) ), was erlaubt dass auf $schl_kopie[strlen($schl_kopie)] zurückgegriffen wird, was "" ergibt und ord("") ergibt einfach 0 ohne Warnung. Mir ist das dann später beim programmieren meiner eigenen Version in Python aufgefallen weil Python eine Exception wirft wenn man ord auf "" anwendet.

Mit diesen Erkenntnissen wenden wir jetzt mal noch ein neues und cooles Werkzeug an: Dotplots. Damit kann man Selbstähnlichkeiten in großen Strings graphisch darstellen.

zeigt einen beliebigen Teil in der Mitte der Datei, ohne selbstähnlichkeit, alles sehr zufällig. Gut verschlüsselt oder gut komprimiert.

vom Ende der Datei (die Achsenbeschriftungen sind falsch, da muss jeweils noch 47034 addiert werden) ist interessanter. Viel Selbstähnlichkeit. Um das zu filtern habe ich ein Tool (Vorsicht, da ist ganz viel anderer Code, teilweise mit if False auskommentiert drin) geschrieben was alle wiederholten Teile aus der Datei extrahiert (ein paar Strings werden bis zu fünfmal wiederholt) und den Dotplot nur für diese Teile malt. Das sollte direkt den Keystream geben (falls das konstante Zeichen 0x0 ist, wie bei ZIP zu vermuten). Wenn man dann zum Zwecke der Rauschunterdrückung den Dotplot nur für 4gramme malt, sieht das so aus:

Die Stellen wo die Hauptdiagonale fehlt sind die Stellen für die kein wiederhergestellter Keystream existiert (dort wurde also nicht das konstante Zeichen verschlüsselt). Das führt dazu dass auch alle Wiederholungen des keystreams an dieser Stelle unterbrochen sind. Ein Beispielkeystream, erstellt mit dem ursprünglichen Algorithmus von send_file.php, Schlüssellänge 175, Sprungweite 45 sieht so aus:

Wir sind also ganz gut auf dem Weg.

Durch Messen der Abstände der Nebendiagonalen zur Hauptdiagonalen müssten wir relativ direkt auf Schlüssellänge und Sprungweite kommen. Pustekuchen. Ich hab die Abstände der beiden wichtigsten Nebendiagonalen (die zusammen den Schlüssel repräsentieren sollten, die anderen sollten nur Spiegelungen sein) mal eingezeichnet:

Die Abstände sind nicht gleich, sondern verändern sich. Hier wird geschummelt. Ich habe dann relativ lange versucht auf halbwegs elegante und automatische Weise auf die Art der Veränderung zu kommen. Offenbar wird die Sprungweite die wir aus dem send_file-Algorithmus kennen bei jedem Sprung verändert. Dazu hab ich ein Programm geschrieben was alle Möglichkeiten durchgeht und Bilder generiert. Dann war mir das auswerten der Bilder zu viel und ich hab es die Abstände berechnen lassen und nach den gleichen Abständen gesucht. Da kamen zu viele false positives raus, und mir fiel ein dass ich ja gar nicht gleiche Abstände haben will, sondern identische Punkte. (In C programmiert und mit -O3 übersetzt dauert das übrigens nur 40 Sekunden.) Da kamen bloß noch zwei positives raus: Schlüssellänge 125 und Initialsprungweite 73, sowie 125 und 20. Die sind zwar beide unterschiedlich, erzeugen aber am Ende der Datei exakt das gleiche Bild wie die bekannten Schlüsselstromdaten (grün theoretische Daten, kaum zu sehen rot die echten Daten):

Am Anfang der Datei sind die beiden aber unterschiedlich, und keines von beiden passt. Um wenigstens ein bisschen bekannten Klartext am Anfang der Datei zu generieren bin ich dann dazu übergegangen die ersten paar Bytes des Geheimtextes mit Bytefolgen vom Ende der Datei zu xoren. Die generierten Varianten habe ich dann dem file-Kommando vorgelegt um zu schauen ob es welche davon am Magic erkennt. Zu viele false positives: Von rund 5 Mio varianten hat file 500.000 nicht als "data" abgetan, aber die restlichen manuell zu durchsuchen war mir dann doch zu umständlich. Eins fiel aber auf: Da waren verdammt viele große "U"s (0x55) drin.

Stellt sich raus dass der feste Klartext am Dateiende ein "U" ist. Wenn man die letzten ca. 600 Bytes mit 0x55 xort, kriegt man direkt den Schlüsselstrom, nur von wenigen anderen Bytes unterbrochen (da wo der Klartext nicht fest U war). Auf dieser Basis kann decrypter-final.py (nein, ist noch nicht final, ist bloss finaler als die Vorversion "decrypter.py") das Ende der Datei entschlüsselt. Es berechnet die Sprungwerte mit den Parametern von eben (125 und 20 oder 125 und 73), weiss dann welche Bytes im Geheimtext welchen Schlüsselbytes entsprechen, macht eine kurze Häufigkeitsanalyse um die Stellen wegzuwerfen wo das Klartextbyte nicht fest ist und wendet ausserdem noch den oben angesprochenen Null-Byte-Bug an um den exakten Wert des festen Klartextzeichens (U) zu ermitteln und einzubeziehen. Das liefert ciphertext.decrypter-final (die eigentlich plaintext.decrypter-final heissen müsste) wo man den String ...UUUUUULAME3.96.1UUUUU... in allerschönster Klarheit lesen kann, sowie den Schlüssel 'ZOIFG15+\xa7$%&/()=?J;MJHGTRE xfghjuio67897856358 #+\xb4\xb42^^fghjkghujk ascdvbnm,\xdf0oizu57856  jbjhf k oihioiUI OH IOJ JOP OH UZGTF D' (oder eine Rotation davon).

Kurzes Googlen zertrümmert damit auch die ZIP-Theorie. Was wir sehen ist ein LAME-Tag, welches in MP3-Dateien vorkommt. Der Dateianfang ist leider auch nicht intakt, weder 125;20 noch 125;73 sind die korrekten Parameter (oder vielleicht ist der Algorithmus auch noch etwas unvollständig).

Mit der neuen MP3-Theorie bewaffnet widmen wir uns nochmal dem Dateianfang. Unter Umständen könnte doch dort ein ID3v2-Tag sein, das würde sich durch die drei Bytes ['I', 'D', '3'] äussern. Wir versuchen also alle möglichen Rotationen des Schlüssels bis wir schliesslich herausfinden dass der Schlüssel mit [' ', ' ', 'j'] anfängt, danach dann halt der Rest. Das gibt uns 125 Bytes bekannten Klartext am Dateianfang, damit müsste doch was zu machen sein.

Hauptaufgabe ist jetzt, die korrekte Variante der Schlüsseldrehungen zu finden, ausgehend von der Hypothese aus decrypter-final.py. Da wir zum Glück alle 126-Byte-Blöcke unabhängig voneinander behandeln können machen wir das iterativ. Den Offset für Block Teil 0 definieren wir als 0; die Offsets für die Blöcke 374 bis 379 kennen wir. Jetzt kommt die Stunde von decrypter-knownkey.py. Ausgehend von diesen vorgegebenen Offsets, der Theorie für die anderen Offsets, und mit Hilfe von mp3val gehen wir Schritt für Schritt vor, in der Art von: [code]for i in seq 0 125; do ./decrypter-knownkey.py _ 4 $i; done[/code] (dauert 13 Sekunden) und [code]mp3val plaintext.decrypter-knownkey.try..4.*[/code] um zu sehen dass 79 der beste Wert ist, 3: 79 im Source ergänzen, dann [code]for i in seq 0 125; do ./decrypter-knownkey.py _ 4 _ $i; done[/code] und [code]mp3val plaintext.decrypter-knownkey.try..4._.*[/code] was 30 liefert, usw.

Irgendwann wird uns das manuell zu albern und wir automatisieren: decrypter-findoffsets.py (enthält Teillösungen in Kommentaren, sowie die vollständige Lösung). Das findet zwar nur ca. alle 4 oder 5 Offsets (dauert etwa 'ne dreiviertelstunde, mit Unterbrechungen alle 4 minuten wegen Zweideutigkeiten, die man aber auch noch automatisieren hätte können), nämlich genau die an den MP3-Frame-Grenzen, aber das muss genügen. Nachdem das durchgelaufen ist kann man die Datei sogar schon abspielen! http://www.ploetzli.ch/xorwette/plaintext.decrypter-knownkey.try.d86ba0c9d85198431471aa04b1be59dfa6d38f6d Klingt spooky, aber die Sprache ist verständlich. Erinnert an CSI.

Jetzt wieder drüber nachdenken und versuchen das Schema der beobachteten Offsets zu generalisieren. Dieses Restklassengewurschtel verursacht bei mir jedesmal Kopfschmerzen. Also: Ausgehend von

{
374:   5, # diff  50
375:  81, # diff  49
376:  33, # diff  48
377: 111, # diff  47
378:  65, # diff  46
379:  20, # diff  45
}

nehmen wir als Arbeitshypothese an dass von hinten gesehen die Differenz von 45 ausgehend jeweils um 1 steigt. Gesagt, eingegeben, den hinteren Teil der Datei wiederhergestellt. Das geht gut bis zu 303: 40, # diff 121. Zum Glück sind 302 und 301 zwei Blöcke deren Offsets wir von mp3val kennen: 85 und 6. Zusammen macht das eine Differenz von 46. Ausserdem ist 40 zu 84 eine Differenz von 45. Hier beginnt eine neue Straße! Also neue Theorie für die Offsets formuliert: Von Block 379 mit Offset 20 und Differenz 45 nach vorne steigt die Differenz je um 1, bis sie 120 erreicht hat, und fängt dann bei 45 wieder an. Das stellt die Datei vollständig wieder her: http://www.ploetzli.ch/forumtst/plaintext.decrypter-knownkey.try.b290ec282ee4fb1d5c09cb08b3b5497b8e099d5f

Ergänzend könnte man noch einen alternativen Offset-Generator definieren, von vorne her. Subtraktion von 45 mod 125 ist nämlich Addition von 80 mod 125 und Subtraktion von 120 mod 125 ist Addition von 5 mod 125. Kalles Offset-Generator sah also vermutlich so aus, das liefert die gleichen Werte:

def offset_generator(keylen):
  offset=0
  diff=5
  while True:
    yield offset
    diff = diff+1
    if diff > 80: diff = 5
    offset = (offset+diff)%125

Zusammenfassend: Algorithmus komplett vernichtet. Der Algorithmus ist so schwach und da war so viel erratbarer Klartext dass wir ihn brechen konnten, ohne den Algorithmus zu kennen, und nebenher noch den Algorithmus zu reverse engineeren. Mit nur einer gegebenen Ausgabe. Jetzt wo die Struktur des Algorithmus bekannt ist, bringt es auch nichts die Parameter zu ändern. Wie gesagt kann ich in C alle Schlüssellängen und alle Initialdifferenzen von 1 bis 250 (jeweils) in 40 Sekunden ausprobieren. Wenn man jetzt die magischen Zahlen 80 und 5 ändern würde, könnte man die bei bekannter Schlüssellänge, ebensoleicht alle durchprobieren. Und selbst wenn die Schlüssellänge nicht gegeben ist kann man sie entweder leicht erraten oder durchprobieren.

Verstärkt wurden diese Probleme nur noch durch die prozeduralen Fehler: Kein zufälliger Schlüssel, Bug in der Implementierung.

Also: AES nehmen, oder, wenn man konservativ sein will, 3DES, und alles wird gut. Selbstgebaute Verschlüsselsungsverfahren von Laien gehen immer schief. Selbst Profis machen gerne Anfängerfehler (lustige Anekdote http://www.trust-us.ch/ds/66/008_aes.html Abschnitt "Telekom sorgt für Heiterkeit"). Nur Verschlüsselungsalgorithmen die öffentlich bekannt sind und wenigstens ein paar Jahre lang von Kryptologen ergebnislos untersucht wurden sind vertrauenswürdig.