Brechen der Autokey Chiffre
Um dieses kryptoanalytische Verfahren anzuwenden, muss man sich sicher sein, dass das Chiffrat mit Autokey verschlüsselt ist. Sind Sie nicht sicher, dass es sich um eine Autokey-Chiffre handelt, sollten Sie zuerst die Art der Chiffre bestimmen und überprüfen, ob die Charakteristika zutreffen. Sonst betreiben Sie ggf. unnötigen Aufwand an einem anderen Verschlüsselungsverfahren.Brechen der Variante "Chiffrat anhängen"
Da diese Variante des Autokey einfacher zu brechen ist, wollen wir mit dieser Variante beginnen. Wie bei der Autokey Chiffre nachzulesen, wird hier der Schlüssel nicht wie bei Vigenere wiederholt, sondern es wird dem Schlüssel das gerade entstehende Chiffrat angehängt:Klartext: treffenamfreitagumzweiundzwanziguhrambekanntentreffpunkt
Schlüssel: berlinUVVQNRHVHVEVPOHBYHOKLJSURJHJFTZPBQWTLQFAWGYJJNPXCO
Chiffrat: UVVQNRHVHVEVPOHBYHOKLJSURJHJFTZPBQWTLQFAWGYJJNPXCOOCJKMH
Wir machen uns den Umstand zunutze, dass ab einer bestimmten Position das Chiffrat gleich dem Schlüssel ist und dies liegt uns ja praktischerweise schon vor.
Es bleibt nur noch herauszufinden, welche Position das genau ist. Aber das ist keine große Schwierigkeit. Wir nehmen einfach die Schlüssellänge 3 an und entschlüsseln das Chiffrat mit Vigenere ab Position 4 mit dem Chiffrat als Schlüssel. Wir fahren solange fort, bis sich ein lesbarer Text ergibt.
UVVQNRHVHVEVPOHBYHOKLJSURJHJFTZPBQWTLQFAWGYJJNPXCOOCJKMH <-- Chiffrat
3 xxxUVVQNRHVHVEVPOHBYHOKLJSURJHJFTZPBQWTLQFAWGYJJNPXCOOCJ ...WSWRIQOJOUKMMKANMEVIJIRNSWMQKIRHSVUMPGBYNDPGOPZRAVWKY
4 xxxxUVVQNRHVHVEVPOHBYHOKLJSURJHJFTZPBQWTLQFAWGYJJNPXCOOC ....TWMFUEXAITDGJTHJNCEKGAPPOKSGWXXEKAJHLQTJNHROTBZFHWYF
5 xxxxxUVVQNRHVHVEVPOHBYHOKLJSURJHJFTZPBQWTLQFAWGYJJNPXCOO .....XMARINOUHMXDSADKLLGHYYRLCQISLDUWPPEDVIEJRJZTFBNMIYT
6 xxxxxxUVVQNRHVHVEVPOHBYHOKLJSURJHJFTZPBQWTLQFAWGYJJNPXCO ......NAMFREITAGUMZWEIUNDZWANZIGUHRAMBEKANNTENTREFFPUNKT
^-- Original-Schlüssellänge und Schlüssel für Vigenere-Test
Damit haben wir bereits den Großteil des Klartextes entziffert (in diesem Fall genügen die Informationen) und wissen, dass der Original-Schlüssel 6 Zeichen lang ist. Wenn wir ein paar verdächtige Kandidaten für Schlüssel haben, die in der Länge passen, können wir sie ausprobieren und so evtl. mit etwas Glück auch die ersten sechs Buchstaben ermitteln.Nach diesem Test sollte klar geworden sein, wie unsicher diese Autokey-Variante in Wahrheit ist. Manch einer mag ein sichereres Gefühl bei der Verschlüsselung haben, weil sie komplizierter in der Durchführung ist als die andere Variante und sich der Schlüssel nur Buchstabe für Buchstabe aus dem Chiffrat ergänzt, aber das ist ein fataler Trugschluss.
Brechen der Variante "Klartext anhängen"
Bei dieser Variante bekommen wir den Schlüssel nicht auf dem Silbertablett serviert, denn hier wird der Schlüssel durch den Klartext selbst erweitert.Brechen mit bekanntem Klartextteil (Known-Plaintext-Attack)
1 2 3 4 5
12345 67890 12345 67890 12345 67890 12345 67890 12345 67890 12345 6
Klartext: treff enamf reita gumzw eiund zwanz iguhr ambek annte ntref fpunk t
Schlüssel: berli ntref fenam freit agumz weiun dzwan ziguh rambe kannt entre f
Chiffrat: UVVQN RGRQK WIVTM LLQHP EOOZC VAIHM LFQHE ZUHYR RNZUI XTERY JCNEO Y
Für dieses Beispiel wollen wir annehmen, dass wir wissen, dass es bei der Nachricht um ein Treffen handelt und das dieses, wie üblicherweise, zwischen 20:00 Uhr und Mitternacht stattfinden wird. Wir nehmen also den Klartextteil "ZWANZIGUHR" als Klartext an, der für diese Uhrzeiten vorkommen muss.Da wir wissen, dass der Klartext bei Autokey Schlüsselbestandteil ist, wissen wir auch, dass der Klartextteil "ZWANZIGUHR" als Schlüssel verwandt wurde und wenn wir das Chiffrat damit an alle Positionen beginnend entschlüsseln, muss irgendwann ein lesbares Dechiffrat auftauchen.
Wir wenden das schon beim Brechen der Vigenere Chiffre mithilfe eines bekannten Klartextteils vorgestellte Verfahren an.
Nach Eingabe von Chiffrat und dem Klartextteil "ZWANZIGUHR" in das dort vorgestellte Hilfstool erhalten wir folgende Liste:
...
024: AGVNJZGRYZ
025: DZAVIEFLJQ
026: WEIUNDZWAN
027: BMHZMXKNXI
028: JLMYGIBKSD
...
"WEIUNDZWAN" an Position 26 ist ein Stückchen lesbarer Klartext, das wir notieren. Hier beginnt also unser Schlüssel ZWANZIGUHR
1 2 3 4 5
12345 67890 12345 67890 12345 67890 12345 67890 12345 67890 12345 6
Chiffrat: UVVQN RGRQK WIVTM LLQHP EOOZC VAIHM LFQHE ZUHYR RNZUI XTERY JCNEO Y
Dechiff.: ZWANZ IGUHR
Wir haben damit auch den neuen Klartextteil (und somit auch Schlüsselteil) WEIUNDZWAN erhalten, mit dem wir das Verfahren wiederholen können:
...
018: UDHKBLAGVN
019: LLWUBWDZAV
020: TAGUMZWEIU
021: IKGFPSBMHZ
022: SKRIIXJLMY
023: SVUBNFIQLS
024: DYNGVENPFD
025: GRSOUJMJQU
026: ZWANZIGUHR
027: EEZSYCRLEM
028: MDERSNIIZH
...
Wir erhalten den neuen Klartextteil TAGUMZWEIU
1 2 3 4 5
12345 67890 12345 67890 12345 67890 12345 67890 12345 67890 12345 6
Chiffrat: UVVQN RGRQK WIVTM LLQHP EOOZC VAIHM LFQHE ZUHYR RNZUI XTERY JCNEO Y
Dechiff.: ZWANZ IGUHR
W EIUND ZWAN
Wir fahren mit dem Verfahren fort und finden noch
1 2 3 4 5
12345 67890 12345 67890 12345 67890 12345 67890 12345 67890 12345 6
Chiffrat: UVVQN RGRQK WIVTM LLQHP EOOZC VAIHM LFQHE ZUHYR RNZUI XTERY JCNEO Y
Dechiff.: ZWANZ IGUHR
W EIUND ZWAN
TA GUMZW EIU
AMF REITA GU
REFF ENAMF R
ERLINTREFF
<Schlüssel><---- Klartext -------------------- ... -->
Auffällig ist hier die jeweilige Verschiebung um 6 Zeichen. Das ist unsere Original-Schlüssellänge. Das Original-Schlüssellänge steht also an Pos. 1 bis 6. Die nachfolgenden 6 Zeichen sind damit verschlüsselt worden. Wenn wir nun mit diesen (TREFFE) suchen erhalten wir:
001: BERLIN
BERLIN ist also unser Schlüsselwort und wir können damit das Autokey-Chiffrat komplett dechiffrieren.Brechen ohne bekanntem Klartextteil (Ciphertext-Only-Attack)
Hier wollen wir ein etwas längeres Chiffrat als Beispiel nehmen, da es bei dieser Methode auf die Häufigkeitsverteilung ankommt, die erst bei längeren Texte genau wird.Klartext:
ZURWINTERSZEITALSEINMALEINTIEFERSCHNEELAGMUSSTEEINARMERJUNGEHINAUSGEHENUNDHOLZAUFEINEMSCHLITTENHOLENWIEERESNUNZUSAMMENGESUCHTUNDAUFGELADENHATTEWOLLTEERWEILERSOERFRORENWARNOCHNICHTNACHHAUSGEHENSONDERNERSTFEUERANMACHENUNDSICHEINBISSCHENWAERMENDASCHARRTEERDENSCHNEEWEGUNDWIEERSODENERDBODENAUFRAEUMTEFANDEREINENKLEINENGOLDENENSCHLUESSELNUNGLAUBTEERWODERSCHLUESSELWAEREMUESSTEAUCHDASSCHLOSSDAZUSEINGRUBINDERERDEUNDFANDEINEISERNESKAESTCHENWENNDERSCHLUESSELNURPASSTDACHTEERESSINDGEWISSKOSTBARESACHENINDEMKAESTCHENERSUCHTEABERESWARKEINSCHLUESSELLOCHDAENDLICHENTDECKTEEREINSABERSOKLEINDASSMANESKAUMSEHENKONNTEERPROBIERTEUNDDERSCHLUESSELPASSTEGLUECKLICHDADREHTEEREINMALHERUMUNDNUNMUESSENWIRWARTENBISERVOLLENDSAUFGESCHLOSSENUNDDENDECKELAUFGEMACHTHATDANNWERDENWIRERFAHRENWASFUERWUNDERBARESACHENINDEMKAESTCHENLAGEN
Schlüssel: GRIMM
Chiffrat:
FLZIUMNVNAMXMKSKWMBNXSPMVZTTINRKAGMRVWNHTQYDSZQYAFTVQMEJLZKVQCAGYZORHYFARKLBFMDBTPHNYRWKUPULVLYPHEIADWPIEAARYEDMFUZLYFGQEYPNXMHFHNZTHLUIKRSAWXRDOEEXASCHXMPVNWWPVWJCVVSNOIRBYHEVQJAAIEOANUUNLHYFYSUHRJBRUWKSILWKFRGETHRZUPKWVWUHAVDPWAPIMFOCLVZANHREGUDRJVLEIUXRWTKRRWYLTYRZAOYRUOWHIEWFGFBHVQBIIVNEORKEJUZWIWEVQIEOTRMAOYKWYHRTSYVGUPHWUZPFRMFKWNOOZPELXHHIIOQKPLWUZPFASWVPIUIJWFYEMUAHAMUJKLGKUKLNMKHIMAJYJVTUYSMEGILRUIEHQHNNRLWMERMKORRWLMHIFPGURQAVFPKPLWUZPFRMJTLFMKSAUZMHETLLWMEHYWEVVYOKALTKFWLBCYIFIPKIZSNHWFMHIFXTZYPLKWUDLKISXEIOWENJMLTHWUZPFPGULOLSPKOIGUHYBFLGXMHITOBRWRFMEKOLPVABNLWAZDNWKWAHQKOHYZCSURGOSECKSFZTIHFCRUWILFFKPLWUZPFTSKWETGDMXGQWCGJNLLTLKTHVVLBRQRPPRDUXBRUHGHZXRMFQHAAJANNBVJBZLIEWWDPVIRDLYSJWSWMRSKULYIFVHRHQHFOROEWPKPMUHNXTAVKTUNPHRQRJAZUIEBIYVVSWHJJHAROZHHVNVNUIJBCYIFIPKIZSNHWFMHIFECNIA
Als erstes gilt es, die Schlüssellänge zu bestimmen. Für den ersten Überblick führen wir einen Kappa-Test auf das Chiffrat aus:
1: 4,249%
2: 4,214%
3: 4,163%
4: 4,182%
5: 4,5%
6: 4,308%
7: 4,261%
8: 4,17%
9: 4,038%
10: 4,396%
11: 4,147%
12: 4,284%
13: 4,263%
14: 4,255%
15: 4,506%
16: 4,193%
17: 4,16%
18: 4,082%
19: 4,243%
20: 4,172%
21: 4,096%
22: 4,172%
23: 4,33%
24: 4,36%
25: 4,282%
Die Kappa-Werte sind alle sehr ähnlich. Es gibt keinen Ausschlag irgendwo. Das liegt daran, dass durch die Fortschreibung des Schlüssels durch den Klartext immer wieder andere Buchstabenkombinationen entstehen, die via Vigenere verknüpft werden.Was aber wäre, wenn wir eine Autokey-Entschlüsselung an der Position beginnen lassen würden, die dem Schlüsselwort folgt? Dann würde der (verschlüsselte) Usprungsklartext auf die aus diesen Buchstaben resultierendem Chiffrat treffen und wir würden den verschiebenden (und verschleiernden) Teil herausrechnen. Damit wäre dann wieder eine natürliche Häufigkeitsverteilung gegeben und der Kappa-Test müsste anschlagen.
Wir müssen also nur der Reihe nach durchprobieren. Beginnen wir mit der Annahme der Länge 3 und demnach AAA, mit dem wir unser Chiffrat Autokey-dechiffrieren:
Schlüssel: AAA (3)
Dechiffrat: FLZDJNKMAQAXWKVOMRNBGFOGQLNDXAONASZRDXWEWUUHYFJAVWTAUTEPSVVDVHXLRCDAFVFVWFQFAWYBXRGQHLGDJJRCMUWDNIF...
Kappa-Test
1: 3,845%
2: 3,904%
3: 3,775%
4: 3,942%
5: 3,799%
6: 3,839%
7: 3,878%
8: 3,883%
9: 3,805%
10: 3,837%
11: 3,772%
12: 3,89%
13: 3,888%
14: 3,821%
15: 4,06%
16: 3,939%
17: 3,918%
18: 3,817%
19: 3,888%
20: 3,8%
21: 4,039%
22: 3,753%
23: 3,896%
24: 3,807%
25: 3,75%
Schlüssel: AAAA (4)
Dechiffrat: FLZIPBONYZYKOLUAIBHNPRIZGILUCFGQYBGBXVHGWVRXWEZBEBUUMLKPZOAGROAAHLORANRJRXUSOPJJFAYETRYGBYWFUNCKNRGQ...
Kappa-Test
1: 3,836%
2: 3,825%
3: 3,838%
4: 3,821%
5: 3,772%
6: 3,771%
7: 3,769%
8: 3,849%
9: 3,847%
10: 3,745%
11: 3,873%
12: 3,695%
13: 3,761%
14: 3,773%
15: 3,847%
16: 3,849%
17: 3,794%
18: 4,032%
19: 3,699%
20: 3,819%
21: 3,918%
22: 3,793%
23: 4,038%
24: 3,773%
25: 3,845%
max. 4,038% bei Intervall 23
Schlüssel: AAAAA (5)
Dechiffrat: FLZIUHCWFGFVQFMFBWWBSRTQUHCASTKIAOTHNWZOMDCEENNWWBGIUQDDDFUSNZVMGMPWVSTLVPTIUROILVQZQGBUVZOKBQZBXDSB...
Kappa-Test
1: 4,071%
2: 4,287%
3: 3,989%
4: 4,218%
5: 5,893%
6: 4,124%
7: 3,94%
8: 4,26%
9: 3,91%
10: 8,266%
11: 4,048%
12: 4,198%
13: 3,963%
14: 4,21%
15: 5,504%
16: 4,22%
17: 4,028%
18: 4,168%
19: 4,072%
20: 8,117%
21: 3,555%
22: 4,214%
23: 3,845%
24: 4,417%
25: 5,817%
max. 8,266% bei Intervall 10
Hier haben wir einen deutlichen Ausschlag bei der Schlüssellänge 10. Unsere getestete Schlüssellänge ist aber 5. Wieso ist der Kappa-Ausschlag bei der doppelten Schlüssellänge? Wenn wir den Klartext mit dem Dechiffrat vergleichen
ZURWINTERSZEITALSEINMALEINTIEFERSCHNEELAGMUSSTEEINARMERJUNGEHINAUSGEHENUNDHOLZAUFEINEMSCHLITTENHOLEN Klartext
FLZIUHCWFGFVQFMFBWWBSRTQUHCASTKIAOTHNWZOMDCEENNWWBGIUQDDDFUSNZVMGMPWVSTLVPTIUROILVQZQGBUVZOKBQZBXDSB Dechiffrat
UJSOOGRIMMUJSOOGRIMMUJSOOGRIMMUJSOOGRIMMUJSOOGRIMMUJSOOGRIMMUJSOOGRIMMUJSOOGRIMMUJSOOGRIMMUJSOOGRIMM Vigenere-Dechiffrat
wird es klar: Durch das "Herausrechnen" des AAAAA-Autokeys wurde unser Chiffrat zum Pseudoklartexttext, der einer Vigenere Chiffre gleichgestellt ist mit dem zehnstelligen Schlüssel "UJSOOGRIMM", der sich ständig wiederholt.Unseren Pseudoklartext können wir nun also genauso behandeln und knacken wie eine Vigenere-Verschlüsselung mit der Schlüssellänge 10.