Zu Beginn dieser Challenge (Unknown text) erhalten wir eine Email von Jessica, die uns mitteilt, dass sie einen unverständlichen -möglicherweise verschlüsselten- Text erhalten hat und beauftragt uns damit, weitere Informationen aus diesem Text zu gewinnen und im besten Fall zu entschlüsseln.
Ein ersten Blick auf den Text lässt uns sofort folgendes feststellen:
– bei den Buchstaben des Textes handelt es sich ausschließlich um Kleinbuchstaben
– die Verteilung der Leerzeichen zeigt, dass nur die Buchstaben verschlüsselt wurden
– die Sonderzeichen im unteren Teil lassen einen Quellcode (Assembler?) vermuten
Mein erster Gedanken bei solchen Texten geht immer in Richtung Caesar-Verschlüsselung und obwohl Wörter wie “nrnvlqqq” schon vermuten lassen, dass es sich nicht um Caesar handelt (da sonst wieder ein Wort mit drei gleichen Buchstaben am Ende entstehen würde) probieren wir es dennoch aus.
rup0rt@lambda:~/unknown_text$ for i in {1..25}; do caesar $i < sp111.first; done
wo, s wvt
xp, t xwu
yq, u yxv
zr, v zyw
as, w azx
bt, x bay
cu, y cbz
dv, z dca
ew, a edb
fx, b fec
gy, c gfd
hz, d hge
ia, e ihf
jb, f jig
kc, g kjh
ld, h lki
me, i mlj
nf, j nmk
og, k onl
ph, l pom
qi, m qpn
rj, n rqo
sk, o srp
tl, p tsq
um, q utr
Der Versuch testweise die ersten Wörter des Textes mit Caesar zu dechiffrieren bringt -wie erwartet- leider keinen Erfolg.
Die nächsthöhere Version einer monoalphabetischen Verschlüsserlung wäre der Vigenere-Chiffre. Anders wie beim Caesar-Chiffre, wo jeder Buchstabe um die gleiche Anzahl von Positionen verschoben wird, werden beim Vigenere-Chiffre die Buchstaben jeweils um eine unterschiedliche Anzahl von Positionen geshiftet. Bestimmt wird diese Verschiebung meist durch ein Schlüsselwort und die Länge des Schlüsselwortes gibt an, nach wievielen Buchstaben sich die Verschiebung wiederholt.
Um Vigenere zu dechiffrieren benötigen wir also das Schlüsselwort, das verwendet wurde um den Text zu verschlüsseln. Der erste Schritt an dieses Schlüsselwort zu gelangen ist zunächst, dessen Länge in Erfahrung zu bringen. Dafür schreibe ich ein kleines Perl-Skript, das für jede mögliche Schlüssellänge, die Häufigkeitsverteilung der Buchstaben bestimmt. Sollte die Anzahl zwischen dem am meisten vorkommenen Buchstaben und die des am wenigsten vorkommenen Buchstaben besonders hoch sein, kann auf eine natürliche Sprache geschlossen werden.
rup0rt@lambda:~/unknown_text$ ./vigenere_keylen.pl sp111.txt Checking key length of 2: min 13, max 36 ( 36.11 % ) --> 5.56 - 2.01 = 3.55 % Checking key length of 3: min 5, max 35 ( 14.29 % ) --> 8.11 - 1.16 = 6.95 % Checking key length of 4: min 4, max 20 ( 20.00 % ) --> 6.18 - 1.24 = 4.94 % Checking key length of 5: min 2, max 21 ( 9.52 % ) --> 8.11 - 0.77 = 7.34 % Checking key length of 6: min 4, max 15 ( 26.67 % ) --> 6.95 - 1.85 = 5.10 % Checking key length of 7: min 2, max 13 ( 15.38 % ) --> 7.03 - 1.08 = 5.95 % Checking key length of 8: min 2, max 10 ( 20.00 % ) --> 6.18 - 1.24 = 4.94 % Checking key length of 9: min 1, max 13 ( 7.69 % ) --> 9.03 - 0.69 = 8.34 % Checking key length of 10: min 1, max 12 ( 8.33 % ) --> 9.27 - 0.77 = 8.49 % Checking key length of 11: min 1, max 9 ( 11.11 % ) --> 7.64 - 0.85 = 6.80 % Checking key length of 12: min 1, max 10 ( 10.00 % ) --> 9.27 - 0.93 = 8.34 % Checking key length of 13: min 1, max 18 ( 5.56 % ) --> 18.07 - 1.00 = 17.07 % Checking key length of 14: min 1, max 8 ( 12.50 % ) --> 8.65 - 1.08 = 7.57 % Checking key length of 15: min 1, max 13 ( 7.69 % ) --> 15.06 - 1.16 = 13.90 % Checking key length of 16: min 1, max 7 ( 14.29 % ) --> 8.65 - 1.24 = 7.41 % Checking key length of 17: min 1, max 7 ( 14.29 % ) --> 9.19 - 1.31 = 7.88 % Checking key length of 18: min 1, max 6 ( 16.67 % ) --> 8.34 - 1.39 = 6.95 % Checking key length of 19: min 1, max 7 ( 14.29 % ) --> 10.27 - 1.47 = 8.80 % Checking key length of 20: min 1, max 7 ( 14.29 % ) --> 10.81 - 1.54 = 9.27 % The key length seems to be: 13.
Die Analyse ergibt, dass bei einer Schlüssellänge von 13 Buchstaben, die Verteilung zwischen Maximum (18) und Minimum (1) im Vergleich zu allen anderen Schlüssellängen am höchsten ist. Wir gehen nun also davon aus, dass das vom Ersteller verwendete Schlüsselwort 13 Zeichen lang ist.
Mit diesem Wissen, hätten wir eine Vigenere-Verschlüsselung nun in 13 Caesar-Verschlüsselungen aufgebrochen. Wie im Beitrag CodeGate 2012 Quals – misc #1 bereits beschrieben, setzt das Brechen von einfachen monoalphabetischen Verschlüsselungen, wie zum Beispiel Caesar, bei einer Häufigkeitsanalyse von Buchstaben der zu Grunde liegenden Sprache an.
Ich schreibe nun also ein weiteres Perl-Skript, das ausgehend von der verwendeten Schlüssellänge versucht, die Buchstaben zu zählen und anhand des häufigsten Buchstabens die Verschiebung zu berechnen. Die Verschiebung orientiert sich dabei an dem häufigsten Buchstaben der zu Grunde liegenen Sprache. Da wir hier von einem englischen Text ausgehen, verwendet das Skript zur Bestimmung der Verschiebung den Buchstaben ‘e’.
rup0rt@lambda:~/unknown_text$ ./vigenere_crack.pl sp111.txt 13 CRACKING position 1: 111 = o CRACKING position 2: 116 = t CRACKING position 3: 121 = y CRACKING position 4: 110 = n CRACKING position 5: 101 = e CRACKING position 6: 97 = a CRACKING position 7: 110 = n CRACKING position 8: 100 = d CRACKING position 9: 101 = e CRACKING position 10: 111 = o CRACKING position 11: 109 = m CRACKING position 12: 100 = d CRACKING position 13: 121 = y CRACKED password: otyneandeomdy
Das Skript hat zwar ein Schlüsselwort ermittelt, das jedoch zunächst keinen Sinn zu ergeben scheint und nicht besonders leicht zu merken sein sollte. Dennoch probieren wir, ob sich der Text damit entschlüsseln lässt. Dazu verwende ich ein weiteres Perl-Skript.
rup0rt@lambda:~/unknown_text$ ./vigenere_decrypt.pl sp111.txt otyneandeomdy hu, t iqs discvefexj iqnderirg mrafzt as usuel keeeqhday. a csublq zr iystem hehexzbfers weve ehaffyng aboyt oodaahate dezioee bgqlity dicdemdudg everc yqad htun they jizaxwk qgreed ebauf feyng locel zefhahk to trenefqc eeme picxudee. qdem the diap uem wuy i manegqd fz ducover jram fsq jrashcen mnp ea slean, i jizaxwk uxtracxep a ozgfle of migmbkeqi of unaptqrqo pqta. worxhxeed oerporaxe yauwe, fersonel bioeghes i degipep ea aeep fov mk pdthqte use enp fqh udteresxizg rtxus, espegimlxj eeme asm wogrop oede thax yau ytsxt find zaxummxu. i attaghqd ayq ef them, tlqaep oentact qe uf kzg mould lmkq azj rkrther mnheeeuwation ebauf etese piegee or nate. ; test tragdly #1 - ruild #35 fsr ecuamt ; http://sgifeqv.zkitduhecw.cax [...]
Der entstandene Text zeigt, dass die Verschlüsselung scheinbar nicht erfolgreich war. Dennoch lassen Wörter wie “usuel”, “everc” oder “fersonel”, die schon relativ nah an englische Begriffe heran kommen, vermuten, dass wir mit einem Vigenere-Chiffre auf der richtigen Spur sind. Nur das Schlüsselwort scheint noch nicht korrekt zu sein. Dies könnte an dem im Text vermuteten Quellcode liegen, die sich von der Häufigkeitsverteilung der Buchstaben nicht zwangsläufig an einer natürlichen Sprache orientieren müssen.
Wie erhalten wir nun also doch noch unserer korrektes Schlüsselwort?
Vielleicht helfen uns die bereits den englischen Wörtern ähnlich erscheinenden Zeichenketten. Aus der Art heraus, wie Vigenere, und damit auch Caesar, funktionieren, muss es möglich sein, über bereits bekannte oder erraten Zeichenketten -im Sinne eines Known-Plaintext-Attacks- das Schlüsselwort zu ermitteln.
Ein weiteres kleines Perl-Skript übernimmt diese Berechnung für mich und passt bei Bedarf mein noch fehlerhaftes Schlüsselwort an. Wir übergeben dem Skript hierzu Teile des verschlüsselten Textes, den von uns vermuteten Klartext, den noch nicht ganz fertigen Schlüssel und die Schlüssellänge.
rup0rt@lambda:~/unknown_text# ./vigenere_known_plaintext.pl qexzzj couple otyneandeomd 13 ofyneandeoqdk rup0rt@lambda:~/unknown_text# ./vigenere_known_plaintext.pl myfwia system ofyneandeoqdk 13 ofynuandeoqdk rup0rt@lambda:~/unknown_text# ./vigenere_known_plaintext.pl ujrmwbuh password ofynuandeoqdk 13 ofjzuandeoqdk
Nachdem wir einige Wörter erraten haben und das Passwort immer wieder angepasst haben, probieren wir nochmals die Entschlüsselung.
rup0rt@lambda:~/unknown_text# ./vigenere_decrypt.pl sp111.txt ofjzuandeoqdk | head hi, i was discretely wandering around as usual yesterday. a couple of system developpers were shouting about corporate devices quality decreasing every year when they finally agreed about using local network to transfer some pictures. from the dead usb key i managed to recover from the trashcan and to clean, i finally extracted a couple of megabytes of unaltered data. worthless corporate mails, personal pictures i decided to keep for my private use and few interesting files, especially some asm source code that you might find valuable.
Das von uns ermittelte Schlüsselwort “ofjzuandeoqdk” scheint zu funktionieren und hat einen gut lesbaren Text erzeugt. Auch der von uns vermutete Quellcode stellt sich nun als assembler-ähnlicher Opcode dar. Der entschlüsselte Text muss jetzt nur noch per Webmail mit dem Betreff “Unknown text” an Jessica zurück gesendet werden um diese Challenge erfolgreich abzuschließen.