1. Die ENIGMA Mythos ENIGMA 2. Mathematische Grundlagen Permutationen Die ENIGMA-Gleichung Wie es gelang die ENIGMA-Chiffre zu brechen Mario Haustein 3. Angriffe Polnische Erfolge Bletchley Park UNIX-Stammtisch Sachsen 29. September 2015 4. Trivia Mario Haustein Mythos ENIGMA 29. September 2015 Mario Haustein 1 / 80 Die ENIGMA Mythos ENIGMA 29. September 2015 2 / 80 Die ENIGMA Die ENIGMA-Maschine ENIGMA-Walzen Funktionsweise I I Elektromechanische Verschlüsselungsmaschine I Eingabebuchstaben werden beim Durchlauf mehrerer Walzen verwürfelt. Die Stellung der Walzen ändert sich mit jedem Buchstaben. ⇒ vergleichweise großer Schlüsselraum I 1918 von Arthur Scherbius erfunden Vielfach modifiziert und erweitert I Von der Wehrmacht eingesetzt I z.T. auch nach dem 2. WK im Einsatz I Ein-/Ausgabealphabet: 26 Buchstaben I Verschlüsselung durch drehende Rotorscheiben (Walzen). I Abbildung: Zwei ENIGMA-Walzen2 1 Abbildung: ENIGMA-Maschine 2 https://en.wikipedia.org/wiki/File:Enigma_rotors_and_spindle_showing_ contacts_rachet_and_notch.jpg 1 Enigma im Verkehrshaus der Schweiz, Luzern von Maximilian Schönherr, Lizenz: CC BY-SA 3.0 Mario Haustein Mythos ENIGMA 29. September 2015 3 / 80 Mario Haustein Mythos ENIGMA 29. September 2015 4 / 80 Die ENIGMA Die ENIGMA ENIGMA-Walzen ENIGMA-Walzen Aufbau Aufbau I Walzenkern I Auf jeder Seite jeweils 26 Kontakte. I Je ein linker Kontakt ist mit einem rechten Kontakt verbunden. ⇒ Permutation I I I I 3 https://de.wikipedia.org/wiki/Datei:ENIGMA_Wired_Rotor_-_National_ Cryptologic_Museum_-_DSC07768.JPG Mario Haustein Mythos ENIGMA Walzenring 29. September 2015 26 Anzeigebuchstaben bzw. Nummern Kann in Bezug zum Kern verstellt werden Enthält Fortschaltkerbe 3 https://de.wikipedia.org/wiki/Datei:ENIGMA_Wired_Rotor_-_National_ Cryptologic_Museum_-_DSC07768.JPG 5 / 80 Mario Haustein Die ENIGMA W1 W2 W3 ETW UKW I Der Strom passiert die Walzen. I I Über die Umkehrwalze wird der Strom erneut durch die Walzen zur ETW geleitet. I Über die Umkehrwalze wird der Strom erneut durch die Walzen zur ETW geleitet. I Eine an die ETW angeschlossene Glühlampe leuchtet auf. I Eine an die ETW angeschlossene Glühlampe leuchtet auf. I Mario Haustein 5 / 80 Aufbau der ENIGMA (ohne Steckerbrett) Bei Tastendruck liegt Strom an der Eintrittswalze an. I 29. September 2015 Die ENIGMA Aufbau der ENIGMA (ohne Steckerbrett) UKW Mythos ENIGMA Mythos ENIGMA 29. September 2015 6 / 80 W1 Bei Tastendruck liegt Strom an der Eintrittswalze an. Der Strom passiert die Walzen. Mario Haustein Mythos ENIGMA W2 W3 ETW 1 1 1 A 2 2 2 B 3 3 3 C 4 4 4 D 5 5 5 E 6 6 6 F 29. September 2015 6 / 80 Die ENIGMA Die ENIGMA Aufbau der ENIGMA (ohne Steckerbrett) UKW I W1 Bei jedem Tastendruck schaltet die rechte Walze einen Schritt weiter. ⇒ Neue Permutation I Bei bestimmten Walzenstellung, schalten auch die anderen Walzen weiter. Mario Haustein W2 Aufbau der ENIGMA (ohne Steckerbrett) W3 ETW UKW 1 1 6 A 2 2 1 B 3 3 2 C 4 4 3 D 5 5 4 E 6 6 5 F Mythos ENIGMA 29. September 2015 I Bei jedem Tastendruck schaltet die rechte Walze einen Schritt weiter. ⇒ Neue Permutation I Bei bestimmten Walzenstellung, schalten auch die anderen Walzen weiter. 6 / 80 Mario Haustein Die ENIGMA W1 Bei jedem Tastendruck schaltet die rechte Walze einen Schritt weiter. ⇒ Neue Permutation I I W2 W3 ETW 1 1 5 A 2 2 6 B 3 3 1 C 4 4 2 D 5 5 3 E 6 6 4 F Mythos ENIGMA 29. September 2015 6 / 80 Die ENIGMA Aufbau der ENIGMA (ohne Steckerbrett) UKW W1 W2 Die ENIGMA-Umkehrwalze W3 ETW I Ursprünglich nicht vorgesehen. 1 1 4 A 2 2 5 B 3 3 6 C 4 4 1 D 5 5 2 E I Erhöhung der Sicherheit, da das Signal die Rotoren doppelt so oft durchläuft. F I Einfache Bedienung, da Verschlüsseln = Entschlüsseln Ziel 6 6 3 Bei bestimmten Walzenstellung, schalten auch die anderen Walzen weiter. Ergebnis I Durch die UKW kann kein Buchstabe in sich selbst verschlüsselt werden. ⇒ Kryptographische Schwäche Mario Haustein Mythos ENIGMA 29. September 2015 6 / 80 Mario Haustein Mythos ENIGMA 29. September 2015 7 / 80 Die ENIGMA Die ENIGMA Schlüsselraum, Teil 1 I Modell I, M3: I I I I Die Walzenringstellung w = 5 Walzen4 k = 3 Walzenschächte u = 2 Umkehrwalzen Anzeige der Walzenstellung I Lage zum Kern ist jedoch einstellbar ⇒ Ein Beobachter kann nicht auf den inneren Zustand der Maschine schließen. Anzahl Walzenlagen: w Y I i = 5 · 4 · 3 = 120 i=w−k+1 I I Grundstellung: 26k = 17576 I Umkehrwalzen: u = 2 ⇒ Die Ringstellung vergrößert den Schlüsselraum. ⇒ 120 · 17576 · 2 = 4.218.240 Kombinationen5 43 Zusatzwalzen für die Marine 11.811.072 Kombinationen 5 Marine: Mario Haustein Die Ringe enthalten Kerben für den „Übertrag“ auf die nächste Walze. Abbildung: Walzenringe6 6 Enigma-rotor-stack-cropped.jpg von Matt Crypto, Lizenz: CC BY-SA 3.0 Mythos ENIGMA 29. September 2015 8 / 80 Mario Haustein Mythos ENIGMA Die ENIGMA 29. September 2015 9 / 80 Die ENIGMA Die Walzenstellung Schlüsselraum, Teil 2 Die Kerbe der linken Walze hat keine Funktion. ⇒ Keine Vergrößerung des Schlüsselraums. I I Hebel schaltet rechte Walze bei jedem Tastendruck weiter (1). I Bei allen anderen Walzen (3) greift er i.A. ins Leere. I Durch Kerbe im Ring einer Walze, greift der Hebel auch bei ihrem linken Nachbarn (1). I ⇒ Der 26. „Übertrag“ der Mittelwalze entsteht durch die Anomalie. I Es drehen sich jedoch immer beide Walzen ⇒ Anomalie. I Vgl. Kilometerzähler: 088 → 089 → 090 → 101 → 102 I 7 I: Der Übertrag erfolgt bei jeder Walze an einer anderen Stelle.7 Die mittlere Walze läuft nur 25 mal um, bis die linke Walze weiterschaltet. I Vergrößerung des Schlüsselraums um 25s−2 · 26 = 25 · 26 = 650 Heer und Luftwaffe 2.741.856.000 Marine 7.677.196.150 Allerdings kein Lawineneffekt Abbildung: Schaltmechanismus (von hinten gesehen, rechte Walze ist links im Bild)8 I Klartext lässt sich auch bei falscher Ringstellung erkennen. I Beispiel: ENIGMA I, UKW A – I – II – III Grund ABH ABQ Q → R, II: E → F, III: V → W, IV: J → K, V: Z → A, VI,VIII,VIII: Z → A und M → N Ring AAR AAA NYSVRQTYPXZAPACWDVFZV UNIXSKNUTPUOBFSACHSEN UNIXSTAMMTISCHSACHSEN 8 Illustration of the ratchet mechanism of an Enigma machine rotor von Wapcaplet, Lizenz: CC BY-SA 3.0 Mario Haustein Mythos ENIGMA 29. September 2015 10 / 80 Mario Haustein Mythos ENIGMA 29. September 2015 11 / 80 Die ENIGMA Die ENIGMA Das Steckerbrett I I Das Steckerbrett Militärisch genutzte ENIGMA-Maschinen waren mit Steckerbrett ausgerüstet. Zwischen Walzen und Tastatur/Lampen konnten durch Steckbrücken bis zu 13 beliebige Buchstabenpaare vertauscht werden. I I Militärisch genutzte ENIGMA-Maschinen waren mit Steckerbrett ausgerüstet. Zwischen Walzen und Tastatur/Lampen konnten durch Steckbrücken bis zu 13 beliebige Buchstabenpaare vertauscht werden. UKW Abbildung: Steckerbrett9 Mythos ENIGMA W2 W3 ETW SB A A B B C C D D E E F F Abbildung: Schaltbild (E und F sind gesteckert) 9 Das Steckerbrett einer ENIGMA von Maximilian Schönherr, Lizenz: CC BY-SA 3.0 Mario Haustein W1 8 Das Steckerbrett einer ENIGMA von Maximilian Schönherr, Lizenz: CC BY-SA 3.0 29. September 2015 12 / 80 Mario Haustein Die ENIGMA Mythos ENIGMA 29. September 2015 12 / 80 29. September 2015 14 / 80 Mathematische Grundlagen Schlüsselraum, Teil 3 I Anzahl Möglichkeiten genau n Paare zu steckern: 1. Die ENIGMA n 1 Y (26 − 2i + 2) · (26 − 2i + 1) 26! = n n! i=1 2 2 · n! · (26 − 2n)! I 2. Mathematische Grundlagen Permutationen Die ENIGMA-Gleichung Ab August 1939 wurden genau 10 Paare gesteckert: ⇒ 150.738.274.937.250 Steckerungen 3. Angriffe Polnische Erfolge Bletchley Park Gesamtschlüsselraum Heer und Luftwaffe Marine I 413.302.643.566.348.536.000.000 ≈ 78 Bit 1.157.247.304.005.897.191.587.500 ≈ 80 Bit 4. Trivia Zum Vergleich: Schlüsselbreite DES 56 Bit Mario Haustein Mythos ENIGMA 29. September 2015 13 / 80 Mario Haustein Mythos ENIGMA Mathematische Grundlagen Permutationen Mathematische Grundlagen Permutationen Eigenschaften von Permutationen I Definition I bezeichnet die identische Permutation. I Das Alphabet A sei eine endliche Menge aus n Elementen. Dann heißt eine Abbildung P der Form P : A ←→ A I I Permuation über A. Der Grad der Permutation lautet n. I Es gibt n! verschiedene Permutationen für A. I Im weiteren gilt A = {A, B, C, . . . , X, Y, Z}. I Anschauliche Darstellung ⇒ Wertetabelle.9 a ABCDEFGHIJKLMNOPQRSTUVWXYZ P (a) E K M F L G D Q V Z N T O W Y H X U S P A I B R C J I I I Hintereinanderausführung von P1 und P2 : (P1 ◦ P2 )(a) = P2 (P1 (a)) Nicht kommutativ: P1 ◦ P2 6= P2 ◦ P1 Kurzschreibweise: P1 ◦ P2 = P1 P2 Eine Permutation P heißt fixpunktfrei, g.d.w. ∀a : P (a) 6= a. I I P (a) = b ⇐⇒ P −1 (b) = a Jede Permutation ist invertierbar, d.h. P −1 existiert stets. P1 ◦ P2 bezeichnet das Produkt der Permutationen P1 und P2 . I I P (a) = a P −1 bezeichnet die inverse Permutation zu P . I Kein Buchstabe wird auf sich selbst abgebildet. Eine Permutation P heißt involutorisch/selbstinvers, g.d.w. P −1 = P . I 9 hier Permutationen P ◦ P = P2 = I die Permutation von ENIGMA-Walze I Mario Haustein Mythos ENIGMA Mathematische Grundlagen 29. September 2015 15 / 80 Mario Haustein Mythos ENIGMA Mathematische Grundlagen Permutationen Zyklendarstellung einer Permutation 29. September 2015 16 / 80 Die ENIGMA-Gleichung Die ENIGMA-Gleichung I Betrachten wir ein a ∈ A. Es gibt ein k, sodass P k (a) = a. I Die Permutation besitzt den Zyklus (a, P (a), P 2 (a), . . . , P k−1 (a)) I Jede Maschineneinstellung erzeugt einer Permutation P ENIGMA-Gleichung Satz 0 P = S ◦ E ◦ WR0 ◦ WM ◦ WL0 ◦ U ◦ WL0 Jede Permutation P lässt sich als Menge disjunkter Zyklen darstellen. Die Darstellung ist bis auf die Ausgangspunkte der Zyklen eindeutig. I Beispielpermuation P : a ABCDEFGHIJKLMNOPQRSTUVWXYZ P (a) E K M F L G D Q V Z N T O W Y H X U S P A I B R C J I Zyklendarstellung von P : I Wi0 = Rki Wi R−ki S E, U Wi R ki ri pi (AELTPHQXRU)(BKNW)(CMOY)(DFG)(IV)(JZ)(S) Mario Haustein Mythos ENIGMA 29. September 2015 17 / 80 Mario Haustein mit −1 0 ◦ WM −1 ◦ WR0 −1 ◦ E −1 ◦ S ki = pi − ri Steckerung Eintritts- / Umkehrwalze Walze in Schacht i Schiebepermutation (B · · · Z A) Kernstellung von Walze i Ringstellung von Walze i Anzeigestellung von Walze i Mythos ENIGMA 29. September 2015 18 / 80 Angriffe Angriffe Frühe Geschichte der ENIGMA 1. Die ENIGMA I 2. Mathematische Grundlagen Permutationen Die ENIGMA-Gleichung Januar 1929: Ein Paket mit einer ENIGMA-Maschine für die deutsche Botschaft läuft an einem Freitag beim polnischen Zoll auf. I I I I 3. Angriffe Polnische Erfolge Bletchley Park I Ab 1931: Der deutsche Spion Hans-Thilo Schmidt liefert ENGIMA-Anleitungen und Schlüsselliste an den französischen Geheimdienst I I I 4. Trivia Mario Haustein I Mythos ENIGMA Angriffe 29. September 2015 19 / 80 Versehentlich nicht als Diplomatengepäck deklariert. Ein deutscher Vertreter fordert die sofortige Herausgabe. Die Maschine wird über das Wochenende analysiert. Am Montag wird das Paket „ungeöffnet“ ausgehändigt. Diese werden an britische und polnische Kollegen weitergegeben. Briten und Franzosen stufen die Informationen als wertlos ein. Den Polen ermöglichen Sie den Einbruch in das ENIGMA-System. Diese Tatsache behalten die Polen (entgegen der Abmachungen) bis 1939 geheim. Mario Haustein Polnische Erfolge Mythos ENIGMA Angriffe 29. September 2015 20 / 80 Polnische Erfolge Die polnischen Codeknacker I Nach einem Kryptographiekurs 1929 zusammen mit anderen Mathematikern um 1932 für das polnische Chiffrierbüro verpflichtet. 3. Angriffe Polnische Erfolge Bletchley Park Abbildung: Marian Rejewski11 Abbildung: Henryk Zygalski12 Abbildung: Jerzy Różycki13 11 https://de.wikipedia.org/wiki/Datei:Marian_Rejewski.jpg 12 https://de.wikipedia.org/wiki/Datei:Henryk_Zygalski.jpg 13 https://de.wikipedia.org/wiki/Datei:Jerzy_Rozycki.jpg Mario Haustein Mythos ENIGMA 29. September 2015 21 / 80 Mario Haustein Mythos ENIGMA 29. September 2015 22 / 80 Angriffe Polnische Erfolge Angriffe Weitere polnische Persönlichkeiten I I 1. Einmal täglich: Walzenlage, Ringstellung, Steckerung einstellen. 2. Walzen laut Tagesschlüssel einstellen (Grundstellung). Leiter des polnischen Chiffrierbüros 3. Dreibuchstabigen Spruchschlüssel zufällig wählen und zwei mal hintereinander eintippen. Maksymilian Ciężki I I I Bedienung der ENIGMA bei der Wehrmacht Gwido Langer I 4. Walzen laut Spruchschlüssel einstellen. Stellvertreter von Langer Verantwortlich für die „deutsche Abteilung“ des Chiffrierbüros 5. Nachricht eintippen. Antoni Palluth I I I Beispiel14 Mitbegründer der AVA-Werke – Ein Funk- und Telekommunikationsunternehmen in Warschau Analysierte die Diplomaten-ENIGMA Später für den Bau von ENIGMA-Nachbildungen und Entschlüsselungsmaschinen zuständig. ABC XYZ XYZXYZ UNIXSTAMMTISCHSACHSEN LHFEFV QBHENAGUFXREIVCJAREQL 14 Walzenlage Mario Haustein Polnische Erfolge Mythos ENIGMA Angriffe 29. September 2015 A-I-II-III, Ringst.: AAA, keine Stecker, Grundst.: ABC, Spruchschlüssel XYZ Mario Haustein 23 / 80 Polnische Erfolge Mythos ENIGMA Angriffe 29. September 2015 24 / 80 Polnische Erfolge Bestimmung der Spruchschlüssel Bestimmung der Spruchschlüssel Permutationsprodukte bestimmen I Geg.: Zwei beliebige Nachrichten M1 und M2 des selben Tages. Beobachtung Ist der 1./2./3. Buchstabe von M1 und M2 gleich, dann ist auch der 4./5./6. Buchstabe von M1 und M2 gleich. I P1 , . . . , P6 sind echt involutorisch. I P1 /P2 /P3 und P4 /P5 /P6 verschlüsseln den selben Buchstaben. ⇒ Die Produkte P1 P4 , P2 P5 und P3 P6 lassen sich hierdurch direkt ablesen. Beispiel I I Schlussfolgerungen I I Sei AJA OON ein verschlüsselter Spruchschlüssel x1 x2 x3 ⇒ P1 (x1 ) = A, P4 (x1 ) = O Es handelt sich um ein Indikatorsystem. Die ersten 6 Buchstaben sind mit dem selben Schlüssel verschlüsselt. ⇒ Wegen Involutorik: P1 (A) = x1 ⇒ Folglich: P4 (P1 (A)) = (P1 P4 )(A) = O Angriffsvektor Lassen sich P1 , . . . , P6 in Erfahrung bringen, können alle Spruchschlüssel eines Tages aufgedeckt werden. Mario Haustein Mythos ENIGMA 29. September 2015 I Benötigen Nachrichten, die das gesamte Alphabet an jeder Stelle abdecken. Pn 1 I 25 / 80 Im Mittel sind dazu n · Mario Haustein i=1 n (ca. 100) Nachrichten notwendig. Mythos ENIGMA 29. September 2015 26 / 80 Angriffe Polnische Erfolge Angriffe Polnische Erfolge Bestimmung der Spruchschlüssel Bestimmung der Spruchschlüssel Zyklendarstellung der Permutationsprodukte Zerlegung der Permutationsprodukte I 42 Nachrichtenindikatoren eines Tages15 AJA DPP JLB MZL QAZ TMW VWE I OON DTX MMW AWY ZYC CGD XRI BOJ EBY KQF NKN RUZ UIJ WFK YZS QBF FVV JHP RIC BPS PUH CKG FGV LBT NOO SCG UMM WRP UHU VLB EBR JZE WEU BGL PCX CVR GCH LHR NOO SCG UMM XNM Satz (Rejewski) UKM IEJ EFM JZE WEU BGL GDL DKX HGD MEI OAS SYU UMM YTO DHK KLG AAZ LYO WJQ BGL HQE DPP IDE MQC PSX TMW UXI ZJQ DTX TSI AVA NNK CGD BXZ SOT (i) Im Produkt zweier echt involutorischer Permutation treten Zyklen gleicher Länge immer paarweise auf. (ii) Jede Permutation, in der Zyklen gleicher Länge paarweise auftreten, lässt sich als Produkt zweier echt involutorischer Permutationen darstellen. P1 = (x1 y1 )(x2 y2 ) · · · (xk yk ) P2 = (y1 x2 )(y2 x3 ) · · · (yk x1 ) Permutationsprodukte in Zyklenschreibweise I I I P1 P4 = (AOLEQZSWPNJM)(BYHKFVXGITCU)(D)(R) P2 P5 = (AYJOZWRCE)(B)(DSN)(FUIPTQVKH)(GLM)(X) P3 P6 = (ANPXKHJSOEIZC)(BWDGUQTRMLYFV) I =⇒ P1 P2 = (x1 x2 . . . xk )(yk . . . y2 y1 ) Rückabbildung nicht eindeutig I I I Durch Intuition muss die richtige Paarung der Zyklen bestimmt werden. Zyklen gegenläufig untereinanderschreiben. Versatz innerhalb eines Paares ebenfalls intuitiv bestimmen. 15 Die Auswahl wurde so getroffen, dass die Zyklen vollständig erschlossen werden können. Aber auch bei Lücken könnte man noch einige Schlüsse ziehen. Mario Haustein Mythos ENIGMA Angriffe 29. September 2015 Mario Haustein 27 / 80 Mythos ENIGMA Polnische Erfolge Angriffe Bestimmung der Spruchschlüssel Zerlegung der Permutationsprodukte Intuitives Erschließen der Spruchschlüssel DKX DHK R.T R.T DPP DTX R.R R.R RUZ RIC D.F D.F I Zwei Einerzyklen (D)(R) in P1 P4 =⇒ (DR) ist ein Zyklus von P1 und P4 I Oft wurden schwache Spruchschlüssel wie AAA, XYZ, ERT, . . . gewählt. I I AJA CVR DPP GCH JLB LHR MZL NOO QAZ SCG TMW UMM VWE XNM Annahme: DPP DTX entspricht dem Spruchschlüssel RRR RRR Wählen aus P3 P6 die Zyklen mit P und R und gleichen gegenläufig ab. −−−−−−−−−−−−→ (ANPXKHJSOEIZC) (LMRTQUGDWBVFY) ←−−−−−−−−−−−− ⇒ P3 = (AL)(NM)(PR)(XT)(KQ)(HU)(JG)(SD)(OW)(EB)(IV)(ZF)(CY) I I Wären P und R im selben Zyklus =⇒ Annahme falsch Wären P und R in Zyklen unterschiedlicher Länge =⇒ Annahme falsch Mario Haustein Mythos ENIGMA 29. September 2015 I 29 / 80 OON → ... UKM → ... DTX → R.. IEJ → ... MMW → ... EFM → ... AWY → ... JZE → ... ZYC → ... WEU → ... CGD → ... BGL → ... XRI → ... GDL → ... ... ... R.. ... ... ... ... ... ... ... ... ... ... ... BOJ DKX EBY HGD KQF MEI NKN OAS RUZ SYU UIJ UMM WFK YTO 28 / 80 Polnische Erfolge Bestimmung der Spruchschlüssel Beispiel 29. September 2015 YZS → ... DHK → R.. QBF → .X. KLG → ... FVV → ... AAZ → ... JHP → ... LYO → ... RIC → D.. WJQ → ... BPS → ... BGL → ... PUH → ... HQE → ... ... R.. .X. ... ... ... ... ... D.. ... ... ... ... ... CKG DPP FGV IDE LBT MQC NOO PSX SCG TMW UMM UXI WRP ZJQ UHU → ... DTX → R.. VLB → ... TSI → ... EBR → .X. AVA → ... JZE → ... NNK → ... WEU → ... CGD → ... BGL → ... BXZ → .B. PCX → ... SOT → ... ... R.. ... ... .X. ... ... ... ... ... ... .B. ... ... Eindeutige Einerzyklen anwenden Mario Haustein Mythos ENIGMA 29. September 2015 30 / 80 Angriffe Polnische Erfolge Angriffe Polnische Erfolge Bestimmung der Spruchschlüssel Bestimmung der Spruchschlüssel Intuitives Erschließen der Spruchschlüssel Intuitives Erschließen der Spruchschlüssel AJA CVR DPP GCH JLB LHR MZL NOO QAZ SCG TMW UMM VWE XNM I OON → ..L UKM → ..P DTX → R.R IEJ → ..U MMW → ..E EFM → ..P AWY → ..A JZE → ..W ZYC → ..F WEU → ..J CGD → ..O BGL → ..N XRI → ..B GDL → ..N ..L ..P R.R ..U ..E ..P ..A ..W ..F ..J ..O ..N ..B ..N BOJ DKX EBY HGD KQF MEI NKN OAS RUZ SYU UIJ UMM WFK YTO YZS → ..G DHK → R.T QBF → .XC KLG → ..S FVV → ..Z AAZ → ..V JHP → ..M LYO → ..D RIC → D.F WJQ → ..H BPS → ..G BGL → ..N PUH → ..Q HQE → ..W ..G R.T .XC ..S ..Z ..V ..M ..D D.F ..H ..G ..N ..Q ..W CKG DPP FGV IDE LBT MQC NOO PSX SCG TMW UMM UXI WRP ZJQ UHU → ..J DTX → R.R VLB → ..I TSI → ..B EBR → .XX AVA → ..Y JZE → ..W NNK → ..T WEU → ..J CGD → ..O BGL → ..N BXZ → .BV PCX → ..R SOT → ..K ..J R.R ..I ..B .XX ..Y ..W ..T ..J ..O ..N .BV ..R ..K AJA CVR DPP GCH JLB LHR MZL NOO QAZ SCG TMW UMM VWE XNM Annahme: DPP DTX → R.. R.. ist RRR RRR Mario Haustein I Mythos ENIGMA Angriffe 29. September 2015 30 / 80 OON → .KL UKM → .OP DTX → RRR IEJ → .IU MMW → ..E EFM → .YP AWY → .QA JZE → .VW ZYC → .FF WEU → .IJ CGD → ..O BGL → ..N XRI → .TB GDL → ..N .KL .OP RRR .IU ..E .YP .QA .VW .FF .IJ ..O ..N .TB ..N BOJ DKX EBY HGD KQF MEI NKN OAS RUZ SYU UIJ UMM WFK YTO YZS → .VG DHK → RJT QBF → .XC KLG → ..S FVV → .ZZ AAZ → .UV JHP → .JM LYO → .FD RIC → DEF WJQ → .HH BPS → .CG BGL → ..N PUH → .AQ HQE → .WW Mario Haustein Mythos ENIGMA Polnische Erfolge Angriffe Bestimmung der Spruchschlüssel Intuitives Erschließen der Spruchschlüssel I IKL JOP RRR OIU C.E XYP TQA UVW FFF HIJ M.O N.N ETB L.N BOJ DKX EBY HGD KQF MEI NKN OAS RUZ SYU UIJ UMM WFK YTO YZS → PVG DHK → RJT QBF → VXC KLG → S.S FVV → ZZZ AAZ → TUV JHP → UJM LYO → GFD RIC → DEF WJQ → HHH BPS → NCG BGL → N.N PUH → YAQ HQE → WWW PVG RJT VXC S.S ZZZ TUV UJM GFD DEF HHH NCG N.N YAQ WWW CKG DPP FGV IDE LBT MQC NOO PSX SCG TMW UMM UXI WRP ZJQ UHU → JJJ DTX → RRR VLB → Q.I TSI → A.B EBR → XXX AVA → TZY JZE → UVW NNK → B.T WEU → HIJ CGD → M.O BGL → N.N BXZ → NBV PCX → YPR SOT → KKK JJJ RRR Q.I A.B XXX TZY UVW B.T HIJ M.O N.N NBV YPR KKK AJA CVR DPP GCH JLB LHR MZL NOO QAZ SCG TMW UMM VWE XNM Annahme: QAZ ZYC → .FF .FF ist FFF FFF Mario Haustein Mythos ENIGMA I 29. September 2015 30 / 80 UHU → .JJ DTX → RRR VLB → ..I TSI → ..B EBR → .XX AVA → .ZY JZE → .VW NNK → ..T WEU → .IJ CGD → ..O BGL → ..N BXZ → .BV PCX → .PR SOT → .KK .JJ RRR ..I ..B .XX .ZY .VW ..T .IJ ..O ..N .BV .PR .KK OON → IKL UKM → JOP DTX → RRR IEJ → OIU MMW → CDE EFM → XYP AWY → TQA JZE → UVW ZYC → FFF WEU → HIJ CGD → MNO BGL → NNN XRI → ETB GDL → LMN IKL JOP RRR OIU CDE XYP TQA UVW FFF HIJ MNO NNN ETB LMN BOJ DKX EBY HGD KQF MEI NKN OAS RUZ SYU UIJ UMM WFK YTO 29. September 2015 30 / 80 Polnische Erfolge Intuitives Erschließen der Spruchschlüssel OON → IKL UKM → JOP DTX → RRR IEJ → OIU MMW → C.E EFM → XYP AWY → TQA JZE → UVW ZYC → FFF WEU → HIJ CGD → M.O BGL → N.N XRI → ETB GDL → L.N CKG DPP FGV IDE LBT MQC NOO PSX SCG TMW UMM UXI WRP ZJQ Annahme: RUZ RIC → D.F D.F ist DEF DEF Bestimmung der Spruchschlüssel AJA CVR DPP GCH JLB LHR MZL NOO QAZ SCG TMW UMM VWE XNM .VG RJT .XC ..S .ZZ .UV .JM .FD DEF .HH .CG ..N .AQ .WW YZS → PVG DHK → RJT QBF → VXC KLG → SSS FVV → ZZZ AAZ → TUV JHP → UJM LYO → GFD RIC → DEF WJQ → HHH BPS → NCG BGL → NNN PUH → YAQ HQE → WWW PVG RJT VXC SSS ZZZ TUV UJM GFD DEF HHH NCG NNN YAQ WWW CKG DPP FGV IDE LBT MQC NOO PSX SCG TMW UMM UXI WRP ZJQ UHU → JJJ DTX → RRR VLB → QSI TSI → ALB EBR → XXX AVA → TZY JZE → UVW NNK → BGT WEU → HIJ CGD → MNO BGL → NNN BXZ → NBV PCX → YPR SOT → KKK JJJ RRR QSI ALB XXX TZY UVW BGT HIJ MNO NNN NBV YPR KKK Annahme: JLB MMW → C.E C.E ist CDE CDE Mario Haustein Mythos ENIGMA 29. September 2015 30 / 80 Angriffe Polnische Erfolge Angriffe Bestimmung der Spruchschlüssel Polnische Erfolge Ermittlung der Walzenverdrahtung Zusammenfassung I Kein Wissen über die Walzenverdrahtung notwendig. I Steckerung hat keinen Einfluss auf das Verfahren. I I Die Walzen waren im Vergleich zur kommerziellen Version anders verdrahtet. I Kenntnis der Verdrahtung wertvoll für weitere Angriffe. I Ausgangspunkt Spruchschlüssel kann bestimmt werden I I ⇒ Ohne Ringstellung keine Entschlüsselung möglich. ⇒ Hilft aber die Walzenverdrahtung zu rekonstruieren. I I I Umsetzungsfehler Ansatz Doppelte Tastung des Spruchschlüssels 26−5 ≈ 80% dass mittlere und linke Walze nicht weiterschalten 26 ⇒ UKW, linke und mittlere Walze bilden Pseudoumkehrwalze ⇒ Entzifferung des schnellen Rotors I Verdopplung des Spruchschlüssels aus Redundanzgründen. ⇒ Verdopplung des Geheimtextes wäre sicherer gewesen. I I I Wahl schwacher Spruchschlüssel Mario Haustein Mythos ENIGMA Angriffe 29. September 2015 31 / 80 Mario Haustein Polnische Erfolge I Annahme: Ringstellung AAA, Ausgangsstellung AAA F = R−6 S −1 P6 SR6 = WR R−6 ◦ Ũ ◦ R6 WR−1 Pi = S ◦ E ◦ Ri WR R−i ◦ Ũ ◦ R−i WR−1 Ri ◦ E −1 ◦ S S I Satz Oktober 1932: Steckerung S für Sept. und Okt. durch Spion aufgedeckt i Pi S = E ◦ R W R R −i ◦ Ũ ◦ R −i WR−1 Ri ◦E Seien A und T Permutationen vom selben Grad. Dann haben A und T −1 ◦ A ◦ T die selbe Zyklenstruktur. −1 Annahme: Geradeausverdrahtung der ETW („deutsche Ordnungssucht“) I I S −1 Pi S = Ri WR R−i ◦ Ũ ◦ R−i WR−1 Ri Mario Haustein Mythos ENIGMA Polnische Erfolge A = R−1 S −1 P1 SR1 = WR R−1 ◦ Ũ ◦ R1 WR−1 .. .. .. . . . Annahme: Mittlerer und langsamer Rotor bleiben stehen −1 32 / 80 Gleichungssystem mit den Unbekannten WR und Ũ Ũ I 29. September 2015 Umstellen der ENIGMA-Gleichung −1 Pi = S ◦ E ◦ Ri WR R−i ◦ WM WL U WL−1 WM ◦R−i WR−1 Ri ◦ E −1 ◦ S {z } | I Mythos ENIGMA Angriffe Vereinfachung der ENIGMA-Gleichung I I Entschlüsselte Spruchschlüssel =⇒ P1 , . . . , P6 bekannt Deutscher Spion lieferte Tagesschlüssel =⇒ Steckerung bekannt Intuition 213 · 13! Lösungen Wenn A, . . . , F unterschiedliche Zyklenstruktur aufweisen . . . ⇒ Mittlere Walze ist weitergerückt ⇒ Eingangswalze falsch geraten 29. September 2015 33 / 80 Mario Haustein Mythos ENIGMA 29. September 2015 34 / 80 Angriffe Polnische Erfolge Angriffe Umstellen der ENIGMA-Gleichung I Lösung der ENIGMA-Gleichung Produkte bilden: AB = WR R−1 ◦ (Ũ R−1 Ũ R) ◦ R1 WR−1 BC = WR R−2 ◦ (Ũ R−1 Ũ R) ◦ R2 WR−1 .. .. . . I BC = CD = DE = EF = | Mario Haustein {z T −1 ◦ AB ◦ BC ◦ CD ◦ DE ◦ WR RWR−1 ◦ WR RWR−1 ◦ WR RWR−1 ◦ WR RWR−1 } | {z T Mythos ENIGMA Angriffe DE = T −1 ◦ CD ◦ T EF = T −1 ◦ DE ◦ T Die Zyklen der Produkte AB, BC, . . . so ausrichten, dass T konsistent. T T T ⇒ Erhalten T = WR RWR−1 I WR R WR−1 WR R−1 WR−1 WR R−1 WR−1 WR R−1 WR−1 CD = T −1 ◦ BC ◦ T T Einsetzen des Vorgängers: −1 BC = T −1 ◦ AB ◦ T ⇒ AB − → BC − → CD − → DE − → EF EF = WR R−5 ◦ (Ũ R−1 Ũ R) ◦ R5 WR−1 I Polnische Erfolge Es bleiben 26 Möglichkeiten den Zyklus von T und R auszurichten. ⇒ Eine Möglichkeit für jede Ausrichtung von Walzenein- und Ausgang. ⇒ Erhalten WR nach Invertierung. I Es bleiben noch 26 Möglichkeiten für die unbekannte Ringstellung. ⇒ Buchstaben müssen evt. zyklisch rotiert werden. } 29. September 2015 34 / 80 Mario Haustein Mythos ENIGMA Polnische Erfolge Angriffe Beispiel zur Bestimmung der Walzenverdrahtung 29. September 2015 Polnische Erfolge Beispiel zur Bestimmung der Walzenverdrahtung AB = (AFEOXJZDSKP)(BUYTMNWQLIC)(G)(H)(R)(V) AB = (AFEOXJZDSKP)(BUYTMNWQLIC)(G)(H)(R)(V) BC = (AOBXUMFEGRS)(CYHVLIZKWPQ)(D)(J)(N)(T) BC = (AOBXUMFEGRS)(CYHVLIZKWPQ)(N)(T)(D)(J) CD = (AXLINDCVZSK)(EGPYMHFROTJ)(B)(Q)(U)(W) CD = (VZSKAXLINDC)(ROTJEGPYMHF)(B)(Q)(U)(W) DE = (BWINHOXTLDZ)(CYVKEGUQRJP)(A)(F)(M)(S) EF = (JPCYVKEGUQR)(DZBWINHOXTL)(A)(F)(M)(S) EF = (AFDWHROJYIN)(BEQPSMGUTZK)(C)(L)(V)(X) F G = (WHROJYINAFR)(QPSMGUTZKBE)(C)(L)(V)(X) T I {G, H, R, V} → {D, J, N, T} wegen AB − → BC I T I {G, H, R, V} → {D, J, N, T} wegen AB − → BC Entweder GR 7→ ND oder GR 7→ TJ wegen BC − → CD I Entweder GR 7→ ND oder GR 7→ TJ wegen BC − → CD I GR 67→ TJ da T und J in unterschiedlichen Zyklen von DE I GR 67→ TJ da T und J in unterschiedlichen Zyklen von DE I Folglich GRHV 7→ NDTJ I Folglich GRHV 7→ NDTJ I Zyklen ausrichten und weitere Paare ableiten. I Zyklen ausrichten und weitere Paare ableiten. T T ABCDEFGHIJKLMNOPQRSTUVWXYZ T = .......................... Mario Haustein Mythos ENIGMA 35 / 80 ABCDEFGHIJKLMNOPQRSTUVWXYZ T = ......NT.........D...J.... 29. September 2015 36 / 80 Mario Haustein Mythos ENIGMA 29. September 2015 36 / 80 Angriffe Polnische Erfolge Angriffe Beispiel zur Bestimmung der Walzenverdrahtung Beispiel zur Bestimmung der Walzenverdrahtung AB = (UYTMNWQLICB)(SKPAFEOXJZD)(G)(H)(R)(V) CD = (VZSKAXLINDC)(ROTJEGPYMHF)(U)(B)(Q)(W) ABCDEFGHIJKLMNOPQRSTUVWXYZ VSRQILNTGWYEXUZHFDCBAJMKOP I T = WN RWN−1 = I In Zyklenschreibweise BC = (AOBXUMFEGRS)(CYHVLIZKWPQ)(N)(T)(D)(J) T = WN RWN−1 = (AVJWMXKYOZPHTBSCRDQFLEIGNU) EF = (JPCYVKEGUQR)(DZBWINHOXTL)(A)(S)(F)(M) F G = (WHROJYINAFR)(QPSMGUTZKBE)(V)(C)(L)(X) I I Polnische Erfolge Ab hier benötigen wir Klartext-Geheimtextpaare bzw. Intuition: T {G, H, R, V} → {D, J, N, T} wegen AB − → BC Referenz −1 Ein mögliches WN Invertieren zu WN Ein- und Ausgang um 6 Stellen verschieben Ringstellung um 2 Schritte korrigieren T I Entweder GR 7→ ND oder GR 7→ TJ wegen BC − → CD I GR 67→ TJ da T und J in unterschiedlichen Zyklen von DE I Folglich GRHV 7→ NDTJ I Zyklen ausrichten und weitere Paare ableiten. T = Mario Haustein ABCDEFGHIJKLMNOPQRSTUVWXYZ VSRQILNTGWYEXUZHFDCBAJMKOP Mythos ENIGMA Angriffe ABCDEFGHIJKLMNOPQRSTUVWXYZ =⇒ Walze III BDFHJLCPRTXVZNYEIWGAKMUSQO WN = I Im Zweifel alle 262 Varianten durchprobieren. 36 / 80 Mario Haustein Polnische Erfolge Mythos ENIGMA Angriffe Ermittlung der Walzenverdrahtung ABCDEFGHIJKLMNOPQRSTUVWXYZ AVJWMXKYOZPHTBSCRDQFLEIGNU ANPRVTXLWCGUEYIKSQOMZBDFHJ ZBDFHJANPRVTXLWCGUEYIKSQOM BDFHJLCPRTXVZNYEIWGAKMUSQO I 29. September 2015 =⇒ =⇒ =⇒ =⇒ =⇒ 29. September 2015 36 / 80 Polnische Erfolge Bestimmung der Grundstellung Zusammenfassung I I I Verdrahtung von zwei Walzen konnte wie gezeigt rekonstruiert werden. I Anschließend Rekonstruktion der dritte Walze und der Umkehrwalze durch mittels Spionagematerial möglich. Die Permutationsprodukte P1 P4 , P2 P5 und P3 P6 sind tagesspezifisch. Ihre Zyklenstruktur ist charakteristisch für . . . I I I Die Steckerung hat keine Einfluss auf diese Zyklen I Katalog von Zyklenstrukturen in Abhängigkeit von Walzenlage und Walzenstellung anlegen. Das Wissen über die Verdrahtung machte Brute-Force-Angriffe erst möglich. I Mario Haustein Mythos ENIGMA Satz: P und P 0 = T −1 P T haben die gleiche Zyklenstruktur. Angriffsvektor Bedeutung der Walzenverdrahtung I Walzenlage + Stellung der Walzenkerne 3! · 263 = 105456 mögliche Zustände 29. September 2015 37 / 80 Über ein Jahr (Nebenbei-)Arbeit zur Aufbau des Katalogs benötigt. Mario Haustein Mythos ENIGMA 29. September 2015 38 / 80 Angriffe Polnische Erfolge Angriffe Zyklometer Polnische Erfolge Zyklometer 0 Z ... A Z ... ... A +3 Abbildung: Maschine zur effizienten Bestimmung der Zyklen16 Abbildung: (Mutmaßliche) Schaltung 16 https://de.wikipedia.org/wiki/Datei:Cyclometer4.png Mario Haustein Mythos ENIGMA Angriffe 16 https://de.wikipedia.org/wiki/Datei:Cyclometer4.png 29. September 2015 39 / 80 Mario Haustein Polnische Erfolge Mythos ENIGMA Angriffe Beispiel Zyklencharakteristik 29. September 2015 39 / 80 Polnische Erfolge Bestimmung der Grundstellung Zusammenfassung Zyklenlängen eines Tages I ENIGMA I mit Umkehrwalze A P1 P4 → 2, 2, 2, 2, 9, 9 I P2 P5 → 1, 1, 3, 3, 9, 9 P3 P6 → 13, 13 Mario Haustein Mögliche Grundstellungen und Walzenlage in ca. 10 bis 20 Min. ermittelbar. I Stecker durch Abgleich mit ungesteckerten Zyklen ermitteln bzw. erraten. Entschlüsselung mangels Ringstellung nicht ohne weiteres möglich. ⇒ Restliche Schlüsselteile durch Ausprobieren bestimmen. I Im Katalog nachschauen Walzenlage III II I II III I I III II II I III II I III I II III I II III I Kernstellung 4 20 10 26 4 13 12 1 4 1 20 13 20 22 21 8 3 19 23 7 17 Mythos ENIGMA Walzenlage II III I III I II I III II II I III II I III I II III Kernstellung 23 3 16 26 25 19 22 15 21 17 8 2 22 5 4 16 21 3 29. September 2015 I I Schwachstellen I I I 40 / 80 Viele Nachrichten begannen mit ANX („An“ + Leezeichen). Fortschalten des mittleren bzw. langsamen Rotors nicht im Katalog erfasst. 1.11.1937: Neue Umkehrwalze =⇒ neuer Katalog 15.9.1938: Neues Indikatorsystem =⇒ Zyklen-Methode wertlos Mario Haustein Mythos ENIGMA 29. September 2015 41 / 80 Angriffe Polnische Erfolge Angriffe Geändertes Chiffrierverfahren ab 15.9.1938 Polnische Erfolge Die Bomba Ansatz 1. Einmal täglich: Walzenlage, Ringstellung, Steckerung einstellen. 2. Grundstellung zufällig wählen und im Klartext übertragen. I Finde je eine Nachricht mit Einerzyklus ein und des selben Buchstabens bei P1 P4 , P2 P5 und P3 P6 . I Beispiel: I Maschinell alle Stellungen der Walzenkerne absuchen: 17 3. Dreibuchstabigen Spruchschlüssel zufällig wählen und zwei mal hintereinander eintippen. 4. Walzen laut Spruchschlüssel einstellen. 5. Nachricht eintippen. sud JAM JVY sud+1 A Beispiel18 J sud+4 Z A J ... qtc ZJS NJL qtc+2 Z A J ... ABC XYZ ABC XYZXYZ UNIXSTAMMTISCHSACHSEN ABC LHFEFV QBHENAGUFXREIVCJAREQL qtc+5 Z A J ... czd+3 Z A J ... = M czd+6 Z A J ... Z ... = = & ⇒ Die Produkte Pi Pi+1 lassen sich nicht mehr rekonstruieren. 17 Wegen czd YGJ GNJ Abbildung: Schema einer Bomba entsprechend des obigen Beispiels Ringstellung kein Rückschluss auf Walzenkerne möglich. I-II-III, Ringstellung AAA, keine Stecker 18 Walzenlage Mario Haustein Mythos ENIGMA Angriffe 29. September 2015 42 / 80 Mario Haustein Mythos ENIGMA Polnische Erfolge Angriffe 29. September 2015 43 / 80 Polnische Erfolge Die Bomba Die Bomba Funktionsweise I Aus den Klartextgrundstellungen ist die relative Lage der Walzen bekannt. Wenn Walzenkernstellung gefunden, die Testbuchstaben (hier J) in jeweils drei passende Paare übersetzt ⇒ Stop. ⇒ Ringstellung aus Stellung der Bomba-Walzen ablesbar. I zu deutsch „Bombe“ I wegen tickendem Motorgeräusch I Laufzeit 2 Stunden I Im November 1938 fertiggestellt I 6 Exemplare gebaut I für jede Walzenlage eine I sud+1 A J sud+4 Z A ... Abbildung: Skizze19 I 15.12.1938: Einführung der Walzen IV und V I 60 Kombinationen qtc+2 A J qtc+5 Z A ... J Z ... = czd+3 A J czd+6 Z A ... J M Z ... = & ⇒ Aufgrund beschränkter Mittel nicht umsetzbar Mythos ENIGMA Z ... = I I 19 https://commons.wikimedia.org/wiki/File:Bomba_full.jpg Mario Haustein J 29. September 2015 44 / 80 Testbuchstabe muss ungesteckert sein. Steckerung am Ende durch Ausprobieren bestimmen. Mario Haustein Mythos ENIGMA 29. September 2015 45 / 80 Angriffe Polnische Erfolge Angriffe Die Bomba Zygalski-Lochblätter Wahrscheinlichkeitsanalyse I p̃ = 40%, dass für zufällige Grundstellung ein Einerzyklus in Pi Pi+3 auftritt. I p̂ = 3,9%, dass Einerzyklus eines bestimmten Buchstabens auftritt. ⇒ Erfolgswahrscheinlichkeit bei n Nachrichten und s Steckern: p(n, s) = (1 − (1 − p̃)n ) · 1− 1 X n−1 i i=0 p(100, 6) = 47,7% =⇒ Fast jeder zweite Tag entzifferbar. I p(·, 10) ≤ 23,1% =⇒ Bomba nicht mehr effizient. von 1.10.1936 1.1.1939 19.8.1939 bis 30.9.1936 31.12.1938 18.8.1939 Anz. Stecker 6 5–8 7 – 10 10 Mythos ENIGMA Angriffe I Bomba war empfindlich gegen Steckerung. I Vorkommen eines beliebigen Einer-Zyklus nur von Kernstellung abhängig. A B C D E F G H I J K L MN O P Q R S T U VWX Y Z ! 2s i n−1−i p̂ (1 − p̂) · 1− 26 I Mario Haustein Polnische Erfolge 29. September 2015 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 46 / 80 Annahme: Ringstellung AAA I Pro Walzenlage und linker Walzenstellung ein Lochblatt I vertikal: mittlere Walze I horizontal: rechte Walze Hier: I I I I I Mario Haustein Polnische Erfolge Umkehrwalze: B Walzenlage: II – I – III Linker Walzenkern: M Bsp.: Mythos ENIGMA Angriffe Anwendung der Zygalski-Lochblätter I =⇒ Einerzyklus bei MRN 29. September 2015 Polnische Erfolge Anwendung der Zygalski-Lochblätter I Ein Durchgang für jede Walzenlage (6) und linke Ringstellung (26). I Ein Durchgang für jede Walzenlage (6) und linke Ringstellung (26). I Einerzyklengrundstellungen am Referenzfeld ( ) übereinanderlegen. I Einerzyklengrundstellungen am Referenzfeld ( ) übereinanderlegen. I Annahmen im Bsp. I I I Mario Haustein I Walzenlage: B – II – I – III Linker Ring: K Annahmen im Bsp. I I Grundstellungen mit P1 P4 -1-Zyklus: I I VRF, JZR, UPX, IOM, TXF, HEE, OJZ, JFZ Walzenlage: B – II – I – III Linker Ring: K Grundstellungen mit P1 P4 -1-Zyklus: I VRF, JZR, UPX, IOM, TXF, HEE, OJZ, JFZ I Löcher geben mögliche Ringstellungen für mittlere und rechte Walze an. I Löcher geben mögliche Ringstellungen für mittlere und rechte Walze an. I Steckerung anschließend durch Versuch & Irrtum bestimmen. I Steckerung anschließend durch Versuch & Irrtum bestimmen. Mythos ENIGMA 47 / 80 29. September 2015 48 / 80 Mario Haustein Mythos ENIGMA 29. September 2015 48 / 80 Angriffe Polnische Erfolge Angriffe Anwendung der Zygalski-Lochblätter Polnische Erfolge Anwendung der Zygalski-Lochblätter I Ein Durchgang für jede Walzenlage (6) und linke Ringstellung (26). I Ein Durchgang für jede Walzenlage (6) und linke Ringstellung (26). I Einerzyklengrundstellungen am Referenzfeld ( ) übereinanderlegen. I Einerzyklengrundstellungen am Referenzfeld ( ) übereinanderlegen. I Annahmen im Bsp. I I I Annahmen im Bsp. I I I VRF, JZR, UPX, IOM, TXF, HEE, OJZ, JFZ Walzenlage: B – II – I – III Linker Ring: K Grundstellungen mit P1 P4 -1-Zyklus: I VRF, JZR, UPX, IOM, TXF, HEE, OJZ, JFZ I Löcher geben mögliche Ringstellungen für mittlere und rechte Walze an. I Löcher geben mögliche Ringstellungen für mittlere und rechte Walze an. I Steckerung anschließend durch Versuch & Irrtum bestimmen. I Steckerung anschließend durch Versuch & Irrtum bestimmen. Mythos ENIGMA Angriffe Walzenlage: B – II – I – III Linker Ring: K Grundstellungen mit P1 P4 -1-Zyklus: I Mario Haustein I 29. September 2015 48 / 80 Mario Haustein Polnische Erfolge Mythos ENIGMA Angriffe Anwendung der Zygalski-Lochblätter 29. September 2015 Polnische Erfolge Anwendung der Zygalski-Lochblätter I Ein Durchgang für jede Walzenlage (6) und linke Ringstellung (26). I Ein Durchgang für jede Walzenlage (6) und linke Ringstellung (26). I Einerzyklengrundstellungen am Referenzfeld ( ) übereinanderlegen. I Einerzyklengrundstellungen am Referenzfeld ( ) übereinanderlegen. I Annahmen im Bsp. I I I Mario Haustein I Walzenlage: B – II – I – III Linker Ring: K Annahmen im Bsp. I I Grundstellungen mit P1 P4 -1-Zyklus: I I VRF, JZR, UPX, IOM, TXF, HEE, OJZ, JFZ Walzenlage: B – II – I – III Linker Ring: K Grundstellungen mit P1 P4 -1-Zyklus: I VRF, JZR, UPX, IOM, TXF, HEE, OJZ, JFZ I Löcher geben mögliche Ringstellungen für mittlere und rechte Walze an. I Löcher geben mögliche Ringstellungen für mittlere und rechte Walze an. I Steckerung anschließend durch Versuch & Irrtum bestimmen. I Steckerung anschließend durch Versuch & Irrtum bestimmen. Mythos ENIGMA 48 / 80 29. September 2015 48 / 80 Mario Haustein Mythos ENIGMA 29. September 2015 48 / 80 Angriffe Polnische Erfolge Angriffe Anwendung der Zygalski-Lochblätter Polnische Erfolge Anwendung der Zygalski-Lochblätter I Ein Durchgang für jede Walzenlage (6) und linke Ringstellung (26). I Ein Durchgang für jede Walzenlage (6) und linke Ringstellung (26). I Einerzyklengrundstellungen am Referenzfeld ( ) übereinanderlegen. I Einerzyklengrundstellungen am Referenzfeld ( ) übereinanderlegen. I Annahmen im Bsp. I I I Walzenlage: B – II – I – III Linker Ring: K Grundstellungen mit P1 P4 -1-Zyklus: I Mario Haustein VRF, JZR, UPX, IOM, TXF, HEE, OJZ, JFZ I Löcher geben mögliche Ringstellungen für mittlere und rechte Walze an. I Steckerung anschließend durch Versuch & Irrtum bestimmen. Mythos ENIGMA Angriffe A Z Y XWV U T S R Q P O NM L K J I H G F E D C B A Z Y X W V U T S R Q P O N M L K J I H G F E D C B 29. September 2015 48 / 80 Annahmen im Bsp. I I I Mario Haustein Walzenlage: B – II – I – III Linker Ring: K Grundstellungen mit P1 P4 -1-Zyklus: I Polnische Erfolge VRF, JZR, UPX, IOM, TXF, HEE, OJZ, JFZ I Löcher geben mögliche Ringstellungen für mittlere und rechte Walze an. I Steckerung anschließend durch Versuch & Irrtum bestimmen. Mythos ENIGMA Angriffe Historische Fakten zum Zygalski-Verfahren I 29. September 2015 Polnische Erfolge Das Treffen von Pyry I Ca. 10 bis 12 Nachrichten waren ausreichend. I Ständige Verbesserungen auf deutscher Seite erschwerten die Entzifferung. I Pro Walzenlage eine Kartei aus 26 Blätter I I Matrix aus 51×51-Feldern (wegen zyklischer Überlappung) Bis Dezember 1938 je 2 Sätze für jede der 6 Walzenlagen hergestellt 25./26.7.1939:20 Zweitägiges Treffen mit Vertretern des britischen und französischen Geheimdienstes bei Pyry nach Warschau angesetzt. I Konferenzsprache ironischer Weise Deutsch I Aufgrund von Sprachproblemen realisierten Briten und Franzosen die polnischen Leistungen nicht. I I I I ca. 1000 Löcher pro Blatt mittels Rasierklingen geschnitten in Nebentätigkeit zu eigentlich Dechiffrieraufgaben ⇒ Treffen wäre am ersten Tag beinahe geplatzt. 15.12.1938: Einführung der neuen Walzen IV und V ⇒ Nun 60 statt 6 Walzenlagen I Die Verdrahtung der Walzen konnte noch ermittelt werden. I Herstellung weiterer Kataloge für das polnische Chiffrierbüro nicht umsetzbar. I Briten und Franzosen konnten keine neuen Erkenntnisse liefern. I Polen legten alle Aufzeichnungen und Verfahren offen. I Je ein ENIGMA-Nachbau an Briten und Franzosen übergeben. 20 Genaues Mario Haustein Mythos ENIGMA 48 / 80 29. September 2015 49 / 80 Datum nicht bekannt Mario Haustein Mythos ENIGMA 29. September 2015 50 / 80 Angriffe Polnische Erfolge Angriffe Nach Kriegsbeginn I Schicksale Restliche Maschinen und Aufzeichnungen wurden sorgfältig vernichtet. I Briten lieferten Zygalski-Blätter für die Walzen IV und V. April 1940: Nachrichten konnten innerhalb von 24 Stunden entschlüsselt werden. I I Kryptographen samt zwei ENGIMA-Nachbauten über Rumänien nach Frankreich (Château de Vignolles nahe Paris) evakuiert. I I I Juni 1940: Evakuierung nach Südfrankreich I Winter bis Sommer 1943: Evakuierung nach Großbritannien Marian Rejewski und Henryk Zygalski I I I I I I I Angriffe 29. September 2015 51 / 80 Am 13.3.1943 bei der Flucht nach Spanien festgenommen. 7.3.1944: In Verhören geben Sie zu, dass die Polen die ENIGMA vor Kriegsbeginn brechen konnten. Antoni Palluth I Mythos ENIGMA Am 9.1.1942 beim Untergang der Lamoricière ums Leben bekommen Gwido Langer und Maksymilian Ciężki I I Kamen 1943 nach England und arbeitet weiter an der ENIGMA. Zygalski blieb in England. Rejewski kehrte 1946 nach Polen zurück. Jerzy Różycki I Kryptographen auf französischer und britischer Seite verschlüsselten ihre Kommunikation untereinander mit der ENIGMA. Mario Haustein Polnische Erfolge Anfang 1943 auf der Flucht verhaftet und im KZ Sachsenhausen interniert. 18.4.1944: Stirbt bei einem Bombenangriff auf die Heinkel-Werke. Mario Haustein Polnische Erfolge Mythos ENIGMA Angriffe 29. September 2015 52 / 80 29. September 2015 54 / 80 Bletchley Park Zusammenfassung der polnischen Erfolge Kurz und knapp . . . I Ohne die polnischen Erkenntnisse wäre die Alliierten nicht in der Lage gewesen in das ENIGMA-System einzubrechen. I Ermittlung der Verdrahtung der Maschine I Entwicklung mechanischer Entschlüsselungsmaschinen I Konzentration auf Mathematik anstatt Linguistik I Ca. 75% der Nachrichten konnten entschlüsselt werden, z.T. noch am selben Tag I Schwachpunkt: Auf Indikatorsystem fixiert 3. Angriffe Polnische Erfolge Bletchley Park ⇒ Es war nur eine Frage der Zeit, bis die Deutschen diesen Fehler erkennen. Mario Haustein Mythos ENIGMA 29. September 2015 53 / 80 Mario Haustein Mythos ENIGMA Angriffe Bletchley Park Angriffe Bletchley Park I I I Bletchley Park (Ausgewählte) Personen in BP I Landsitz ca. 70 km nordwestlich von London. Ab 1939 Sitz der „Government Code and Cypher School (GC&CS)“ Heute nationales Computer-Museum I Alexander Guthrie Denniston (b1.12.1881, †1.1.1961) I I John Hessell Tiltman (b25.5.1894, †10.8.1982) I I I I Abbildung: Herrenhaus von Bletchley Park Entschlüsselung der ENGIMA der Kriegsmarine Erfinder der Turing-Bombe Gordon Welchman (b15.6.1906, †8.10.1985) I 21 Erste britische ENIGMA-Erfolge Entzifferung der Abwehr-ENIGMA Alan Turing (b23.6.1912, †7.6.1954) I I Handschlüsselverfahren, Reichsbahn-ENIGMA Alfred Dillwyn Knox (b23.7.1884, †27.2.1943) I I Leiter von Bletchley Park I Entschlüsselung der ENIGMA von Heer und Luftwaffe Erweiterung der Turing-Bombe 21 https://de.wikipedia.org/wiki/Datei:Bletchley_Park.jpg Mario Haustein Mythos ENIGMA Angriffe 29. September 2015 55 / 80 Bletchley Park I Entwicklung von Lochblattverfahren Verkehrsanalyse Erbeutung von Codebüchern Bletchley Park I Stellvertreter Turings Methode der wahrscheinlichen Worte Hauptwerkzeug zur Bestimmung der ENIGMA-Einstellung I Angriff der Spruchschlüsselverdopplung als nicht zukunftssicher eingeschätzt. I Stattdessen Known-Plaintex-Angriff notwendig. I Weiterentwicklung der polnischen Bomba ⇒ Statt eines einzelnen Buchstaben alle 26 Buchstaben parallel testen. u.v.m. Mario Haustein I ⇒ Suche aller Walzenstellungen, die ein Kryptogramm in einen wahrscheinlichen Klartext überführen. Conel Hugh O’Donel Alexander (b19.4.1909, †15.2.1974) I I 56 / 80 Die Turing-Bombe Harry Hinsley (b26.11.1918, †16.2.1998) I I 29. September 2015 John Robert Fisher Jeffreys (b25.1.1916, †13.1.1944) I I Mythos ENIGMA Angriffe (Ausgewählte) Personen in BP II I Mario Haustein Mythos ENIGMA 29. September 2015 57 / 80 Mario Haustein Mythos ENIGMA 29. September 2015 58 / 80 Angriffe Bletchley Park Angriffe Bletchley Park ENIGMA-Doppelwalzen I I I Kernelement der Turing-Bombe Umkehrwalze =⇒ normale Walze 26 statt 13 elektrische Verbindungen =⇒ 26 parallele Tests W3 −1 W2 −1 W1 −1 UKW W1 W2 W3 A A B B C C D D E E F F Abbildung: Nachgebaute Turing-Bombe22 Abbildung: ENIGMA-Doppelrotor 22 https://upload.wikimedia.org/wikipedia/commons/b/b1/RebuiltBombeFrontView.jpg Mario Haustein Mythos ENIGMA Angriffe 29. September 2015 59 / 80 Mario Haustein Bletchley Park Mythos ENIGMA Angriffe Vorderseite einer Turing-Bombe 29. September 2015 60 / 80 Bletchley Park Cribs Walze links mittig I Crib: wahrscheinlicher Klartext eines Kryptogramms ⇒ Eingabe der Bombe rechts Beispiele Anzeigewalze Doppel-ENIGMA 12 ENIGMAs I I 3 Walzenlagen in einem Durchlauf getestet. Je 12 ENGIMAs; Stellung der langsamen und mittleren Walze identisch. Mario Haustein Mythos ENIGMA 29. September 2015 61 / 80 I Wetterdaten =⇒ Wetterkurzschlüssel I Feindmeldungen I „OBERKOMMANDODERWEHRMACHT“ I „WETTERBERICHT“ I Rangbezeichnungen I Meldungen, die in bereits entzifferten Schlüsselkreisen übertragen wurden. I Gute Cribs erst durch erbeutete Schlüssellisten ableitbar. I Cribs mussten ständig auf ihre Trefferwahrscheinlichkeit untersucht werden. Mario Haustein Mythos ENIGMA 29. September 2015 62 / 80 Angriffe Bletchley Park Angriffe Vom Crib zum Menu Theorie der Turing-Bombe Implikationsbeziehungen Beispiel-Crib I 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 10 21 Das Menu gibt Implikationsbeziehungen an. I U N I X S T A M M T I S C H S A C H S E N P S A W C F J K L P F T N B D F A C U W H I I I 11 I 7 6 F A 12 5 C 17 18 B 10 T 16 3 J H 14 2 19 U C 18 H 8 X Mythos ENIGMA Angriffe 13 21 2 21 N 2 I Diese Verbindungen werden durch 26 Buskabel (A bis Z) nachgebildet. I Jeder Bus hat 26 Adern (a bis z). Mario Haustein 63 / 80 Mythos ENIGMA Angriffe Bletchley Park Theorie der Turing-Bombe Theorie der Turing-Bombe Potentiell korrekte Walzenstellungen Erkennung der korrekten Steckerung 13 C 18 H 21 13 H .. . .. . 18 N 21 29. September 2015 64 / 80 Bletchley Park I Je mehr Zyklen, umso mehr falsche Adern sind elektrisch verbunden. I Legen Spannung an eine Ader eines zentralen Buchstabens (Testregister). I Prüfen wie viele Leitungen im Testregister unter Spannung stehen. Alle Leitungen =⇒ Widerspruch! Nächste Stellung probieren. .. . N 5 S 29. September 2015 C 13 N K Wegen Involutorik kann Kantenrichtung entfallen. Mario Haustein 18 S H M 4 5 C 9 W D 18 Schritte nach korrekter Walzenstellung wird C in H kodiert. 21 Schritte nach korrekter Walzenstellung wird H in N kodiert. 13 Schritte nach korrekter Walzenstellung wird N in C kodiert. ... L 20 15 N 21 E 1 S 13 P Abbildung: Menu zum Crib I Bletchley Park 1 Leitung =⇒ Lösungskandidat ist die aktive Leitung. 25 Leitungen =⇒ Lösungskandidat ist die inaktive Leitung. Eine Walzenstellung ist (wahrscheinlich) korrekt, wenn . . . I in jedem Bus genau eine Leitung existiert, I die alle elektrisch verbunden sind 2 bis 24 Leitungen =⇒ Menu ist zu schwach. I Bestimmung der Steckerung ⇒ Bei Widerspruch sind mehrere Leitungen verbunden (S sei Steckerung). 18 21 13 18 13 S(C) =⇒ · =⇒ · =⇒ = 6 S(C) =⇒ . . . =⇒ S(C) Mario Haustein Mythos ENIGMA 29. September 2015 Die eingesetzten Turing-Bomben hielten in den Fällen 2 bis 4 an. 65 / 80 I Die Bus-Nummer und sein Lösungskandidat sind Steckerpartner. I Steckerung nicht genutzter Busse muss intuitiv bestimmt werden. Mario Haustein Mythos ENIGMA 29. September 2015 66 / 80 Angriffe Bletchley Park Angriffe Die Turing-Welchman-Bombe Fakten zur Turing-Welchman-Bombe I Erweiterung der Turing-Bombe um das Diagonalbrett durch Welchman. I Nun tragen auch Zweige (anstatt nur Zyklen) im Menu zur Lösung bei. Idee des Diagonalbretts I α mit β gesteckert ⇐⇒ β mit α gesteckert I ∀α 6= β : Verbinde Ader β in Bus α mit Ader α in Bus β. a Bletchley Park (α, β ∈ {A, . . . , Z}). I Laufzeit ca. 12 Minuten, inkl. Rüstzeit ca. 20 Minuten I 18.3.1940: Erste Turing-Bombe einsatzbereit (noch ohne Diagonalbrett) I 8.8.1940: Erste Turing-Welchman-Bombe geht in Betrieb I Kriegsende: Über 210 „Bombes“ allein in England in Betrieb I Ab April 1942: Entwicklung von Hochgeschwindigkeitsbomben für die ENIGMA M4 I Weiterschalten der mittleren bzw. linken Walze nicht berücksichtigt. f ··· z .. . A B C D .. . ⇒ Im Zweifel musste das Menu aufgeteilt werden. I Simulator eine Turing-Welchman-Bombe inkl. Anleitung: http://www.lysator.liu.se/~koma/turingbombe/bombe.html Abbildung: Prinzip des Diagonalbretts Mario Haustein Mythos ENIGMA Angriffe 29. September 2015 67 / 80 Mario Haustein Bletchley Park Mythos ENIGMA Angriffe Bestimmung des Tagesschlüssels 29. September 2015 Bletchley Park Die U-Boot-ENIGMA I Die Turing-Bombe liefert nur den Spruchschlüssel und einige Stecker. I Die ENIGMA M4 der U-Boot-Flotte war kryptographisch stärker I Ringstellung und weitere Stecker müssen intuitiv gefunden werden. I 4 Walzen statt nur 3 I Aus praktischen Gründen war die M4 rückwärtskompatibel I Ermittlung des Marine-Tagesschlüssels erfordert „Doppeltauschtafeln“. I I I I I I I 4.3.1941: Kaperung des Schiffs „Krebs“ 7.5.1941: Kaperung des Wetterschiffs „München“ 9.5.1941: Kaperung von U-110 4.6.1941: Kaperung des Versorgungsschiffs „Gedania“ 28.6.1941: Kaperung des Wetterschiffs „Lauenburg“ 27.8.1941: Kaperung von U-570 Schwachstelle Durch bessere Cribs konnte man später Tauschtafeln rekonstruieren. Mythos ENIGMA 29. September 2015 I Wetterkurzmeldungen wurden im 3-Walzen-Modus verschlüsselt. I Der Schlüssel wurde als dem 4-Walzen-Schlüssel abgeleitet. ⇒ Mit 3-Walzen-Bomben und Wettermeldungen konnte ein Teil des 4-Walzen-Schlüssel bestimmt werden. ⇒ Geringere Gefahr, dass die Deutschen Verdacht schöpfen Mario Haustein 68 / 80 69 / 80 Mario Haustein Mythos ENIGMA 29. September 2015 70 / 80 Angriffe Bletchley Park Trivia Fakten zu Bletchley Park I Zu Hochzeiten 9000 Mitarbeiter in 3 Schichten 12000 Mitarbeiter über die gesamte Kriegszeit 80% Frauen Bis zu 4000 Nachrichten pro Tag entschlüsselt. I Ab 1974 wird die Rolle von Bletchley Park bekannt. I Neben der Turing-Bombe kamen noch andere Angriffe zum Einsatz. I I I 1. Die ENIGMA 2. Mathematische Grundlagen Permutationen Die ENIGMA-Gleichung 3. Angriffe Polnische Erfolge Bletchley Park Banburry-Methode Rodding I Herivel Tips =⇒ Führt hier zu weit I I I I I I 4. Trivia 17.1.1940: Erste Kriegsmeldungen werden entschlüsselt. Mail 1941: Regelmäßige Entzifferung möglich. 1.2.1942: Blackout durch Einführung der ENIGMA M4 Dez. 1942: ENIGMA M4 geknackt, Blackout beendet Mario Haustein Mythos ENIGMA 29. September 2015 Mario Haustein 71 / 80 Mythos ENIGMA Trivia Weitere Verfahrensfehler Man ging davon aus, dass die Maschine an sich sicher sei. ⇒ Sicherheit wäre nach Austausch erbeuteter Code-Bücher wiederhergestellt. I Man hielt Spionage für wahrscheinlicher als ein Einbruch in die ENIGMA. ⇒ Einführung spezifischer Schlüsselkreise. I Kryptographische Weiterentwicklungen kamen zu spät bzw. nicht flächendeckend zum Einsatz. I I I I I Übertragung gleicher Nachrichten in unterschiedlichen Schlüsselkreisen. I Keine Füllbuchstaben um Cribs unwirksam zu machen. I Stereotype Dummy-Nachrichten I Schlüssel ließ sich in Teilkomponenten zerlegen. I Künstliche Einschränkung des Schlüsselraums I ENIGMA-Uhr Lückenfüllerwalze Steckbare Umkehrwalze Kürzere Schlüsselperiode Mario Haustein I I I Mythos ENIGMA 72 / 80 Trivia Beurteilung der ENIGMA durch die Deutschen I 29. September 2015 29. September 2015 73 / 80 Keine Wdh. der Walzenlage in 6 Monaten Keine Walze an zwei Folgetagen in selber Position Keine Walze mehr als drei mal im Monat an rechter Stelle Benachbarte Buchstaben dürfen nicht gesteckert werden Mario Haustein Mythos ENIGMA 29. September 2015 74 / 80 Trivia Trivia Filmische Rezeption I „Enigma – Das Geheimnis“ (2001) I I I I I I ENIGMA heute Technisch sehr authentisch Verwendung originaler Verfahren, Schlüssel und Geräte Handelnde Hauptdarsteller fiktiv (A. Turing = Tom Jericho) Haupthandlung fiktiv Historische Rahmenhandlung auf Tatsachen basierend. I Verschlüsselung von LATEX-Dokumenten: https://www.ctan.org/pkg/enigma I Nachbau einer Turing-Bombe: https://sites.google.com/site/bomberebuilt/home I Entschlüsselung nicht geknackter Nachrichten: http://www.bytereef.org/m4_project.html „The Imitation Game“ (2014) I I Technisch und historisch nicht authentisch. Fokus auf der Persönlichkeit A. Turings. I „Das Boot“ (1981) I „U-571“ (2000) Mario Haustein Mythos ENIGMA 29. September 2015 75 / 80 Mario Haustein Trivia Mythos ENIGMA 29. September 2015 76 / 80 Trivia Literatur I Literatur II ENIGMA – The Battle for the Code Hugh Sebag-Montefiore ISBN 978-0-461-49035-7 Das Enigma System Thomas Mayr Diplomarbeit, TU Wien, 2003 http://www.cryptomuseum.com/crypto/enigma/ Umfangreiches ENIGMA-Kompendium Die Chiffriermaschine ENIGMA, Trügerische Sicherheit Heinz Ulbricht Dissertation, TU Braunschweig, 2004 http://www.codesandciphers.org.uk/virtualbp/ Informationen zu Bletchley Park und verschiedenen ENIGMA-Angriffen http://users.telenet.be/d.rijmenants/en/enigmamenu.htm Originaldokumente und -verfahren zur ENIGMA Chiffriermaschinen und Entzifferungsgeräte im Zweiten Weltkrieg: Technikgeschichte und informatikhistorische Aspekte Michael Pröse Dissertation, TU Chemnitz, 2005 http://www.ellsbury.com/enigmabombe.htm Informationen zur Turing-Bombe http://www.lysator.liu.se/~koma/turingbombe/ The Turing Bombe Simulator Mario Haustein Mythos ENIGMA 29. September 2015 77 / 80 Mario Haustein Mythos ENIGMA 29. September 2015 78 / 80 Trivia Trivia Zum Schluss . . . PQMCRMDCTDV! Was wir im Hinterkopf behalten sollten 1. Die falsche Anwendung kann Krypto-Verfahren erheblich schwächen. 2. Auch noch so sichere erscheinende Verfahren werden werden höchstwahrscheinlich bereits gelesen. YNWZID? 3. Die Genies dahinter ernten den Ruhm nie bzw. viel zu spät. 23 Walzen: Mario Haustein Mythos ENIGMA 29. September 2015 79 / 80 A-I-II-III, Ringe: RKX, Stellung: TVP, keine Stecker Mario Haustein Mythos ENIGMA 29. September 2015 80 / 80
© Copyright 2025 ExpyDoc