# jemdoc: addcss{rbh.css}, addcss{jacob.css} = ch4: cracking the enigma ~~~ {}{raw} postWWI   Rej   baton   geese   cryptic   Tcrack   kidnap   ~~~ ~~~ {}{raw}

post-WWI: Poland and Rejewski

~~~ ~~~ - Britain\/France\/America: lean\/hungry {{=>}} fat\/lazy - Germany|Poland|Russian {{=>}} Biuro Szyfrów - Ciezki \+ /Monsieur Rex/ \+ HT Schmidt - 1939: Poles have rotor wirings - daily key info -- plugboard pairings, eg. AL PR TD BW KF OY -- rotor-slot placements, eg. 231 -- initial rotor settings, eg. QCW - message protocol: for each msg -- day-key pairings -- day-key placements -- new rotor setting - msg prefix: rotor setting, repeated, day-key encrypted -- e.g. msg-key PGH sent as prefix {{eQCW(PGHPGH) = KIVBJE}} ~~~ ~~~ {}{raw}

Rejewski cracks Enigma

~~~ ~~~ - exploit doubling in encrypted msg-key prefix - for each possible day-key (rotors, placements, setting), construct {{1->4 2->5 3->6}} permutation \"fingerprint\" - build lookup table: fingerprint {{->}} Enigma key (r, p, s) - for each new day -- collect msg prefixes -- from prefixes, find day-key fingerprint -- from fingerprint, lookup day-key -- from day-key, msg-keys, deduce plugboard cabling -- now complete day-key (r, p, s, cabling) known -- from complete day-key, read all msg-keys -- from msg-keys, decrypt all msgs ~~~ ~~~ {example}{from prefixes to fingerprint} L O K R G M 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 M V T X Z E P M R X J K T M P E D V Y P Z X . . . . . . F Q H P L W O G B M V R X U Y C Z I T N J E A S D K represent permutation (above, 1-4) as product of cycles A -> F -> W -> A B -> Q -> Z -> K -> V -> E -> L -> R -> I -> B C -> H -> G -> O -> Y -> D -> P -> C J -> M -> X -> S -> T -> N -> U -> J so 1-4 is a (3,7,7,9) permutation ~~~ ~~~ {exercise: find fingerprint for key 123 DDN}{} V E C J I B E W O P F A K D A L Y T 1-4: L C V T E O 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 B A H Q D Z J J Y S I B Y T I Q W V P Q X E Y R Q P G Y F A V 2-5: F Q P A L R 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 C R M U Q N I D U R C J M Z Z K N U L Y O U M W K X N B S S D 3-6: I T J B T G 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 H J G E K H B U K L V H J W V F O O U G P X D P C R L N K M S A S D R G I S B Z G N X O H T Z Z W N F I H C F M M W X X E ~~~ ~~~ {}{raw}

Poles pass baton

~~~ ~~~ - 3-rotor 5-slot lookup table: 1 year to build - but now Poles can crack German communications -- e.g. Goering\'s 1934 Warsaw visit - small German modifications - Rejewswki builds /bombe/ - 6 bombes, parallel, check 17576 settings each: 2 hours - Langer had the day keys - 1938 Dec: 2 new rotors (now 5) -- new rotor internal wiring ? -- now 60 placements instead of 6 - 1938 Jan: 20 cables instead of 12 ~ :( - Schmidt gone - 1939 Jul -- Poles give French/Brits Enigma replicas -- bombe blueprints - 1939 Sep ~ WWII ~~~ ~~~ {}{raw}

geese that never cackled

~~~ ~~~ - Room 40 {{=>}} GCCS, Bletchley Park (2 million words/day) -- Alastair Denniston -- linguistics classics puzzles math science -- Oxbridge -- crack day key: few hours - shortcuts -- try /cillies/ -- each rotor in different position from previous day - 19th century math -- 1900 Hilbert's problems -- 1931 Godel undecidability -- 1936 Koenig graph theory text ~~~ ~~~ {}{raw}

Turing

~~~ ~~~ - b 1912 London (parent: India) - 1926 Sherbourne by bike - met Chris Mercom d 1930 - 1931 King's College Cambridge - 1937 /On Computable Numbers/ TM\/UTM /Entscheidungsproblem/ - 1939 Bletchley Park ~~~ ~~~ {}{raw}

Rejewksi and Enigma

~~~ ~~~ - exploit 6-gram msg prefix: repeated 3-gram, encrypted day-key - use e1(p) ↔ e4(p) ~ e2(p) ↔ e5(p) ~ e3(p) ↔ e6(p) ~ to identify r,s,p - factors out plugboard pairings ~~~ ~~~ {}{raw}

Turing and Enigma

~~~ ~~~ - expected repeated 3-gram to stop - exploit probable ptext/ctext crib - use ptext/ctext loops to categorize rotor settings - factors out plugboard pairings - ptext/ctext crib alignment: {{e(x) ≠ x (??)}} ~~~ ~~~ {}{raw}

Bletchley Park

~~~ ~~~ - 1941 Sep ~ Churchill visit - Turing wants more staff, Travis says no - 1941 Oct ~ /Dear Prime Minister {{...}}/ - Churchill: /{{make sure ... all they want ... extreme priority}}// - 1942 ~ 49 bombes - Daily Telegraph crossword, under 12 minutes ? (6 out of 25) ~~~ ~~~ {}{raw}

cryptic crosswords

~~~ ~~~ - [https://en.wikipedia.org/wiki/Cryptic_crossword\#History_and_development wiki] - [http://www.telegraph.co.uk/history/world-war-two/11151478/Could-you-have-been-a-codebreaker-at-Bletchley-Park.html DT 1942 crossword] - [http://www.sarahlolley.com/intro-to-cryptic-crosswords.html Sarah Lolley's cryptic intro] - [http://webdocs.cs.ualberta.ca/~hayward/crypto/other/gmcrypt.pdf globeandmail cryptic 2017-02-27] ~ ~ hints: 1 def 9 def 10 ana 11 dbl 12 pieces 14 def def 16 ana 18 def 19 def def 22 pieces 23 pieces 24 pieces 2 def 3 def 4 ana 5 def 6 def 7 ana 8 def def 13 pieces 15 pieces 17 ana 20 pieces 21 def def ~~~ ~~~ {}{raw}

Turing Enigma cracker: crib cycles

~~~ ~~~ {}{} * get crib and ciphertext * find possible alignment ...wettervorhersage........ KVBVRBCPZFQFNTTQEQOGYIIOYNG * for this alignment, draw Turing graph: join two letters if they are aligned at some position G P A Z | \| | S--Q--O--E--R--F--V--W H--N | / |/ C--T--B * find cycle in graph (a.k.a. Turing bombe menu): - E->R->T->E positions 5 15 14 5 * give this info to bombe operator * operatoro will return matching Enigma key: - rotors I-II-III ZUB cycle 5-15-14-5 H-W-N-H * now you know uncabled letters ....H........NW intxt ....W........HN outtxt ~~~ ~~~ {next: find plugboard cabling}{} * try Enigma replica key: I II III ZUB with no cables KVBVRBCPZFQFNTTQEQOGYIIOYNG ctxt XFXTVNNHQZLWJYDSGGYMUHTGEYT ptxt (no plugboard cables) ...wettervorhersage........ desired ptxt * make deductions no cables: 5-15-14-5 H->W->N->H all cables: 5-15-14-5 E->R->T->E so cable EH WR NT * make more deductions ps j ptext/ctext x:Y ok => no further cabling with x Y ps j not ok => further cabling x Y (and/or) KVBVRBCPZFQFNTTQEQOGYIIOYNG XFXNETTEQZLRHERSJGYMUENGHEN ptxt (pairs EH WR NT) ...wettervorhersage........ desired ++++ +++++ + <- ok ... so BC EFGH PQRST ok ? <- F:Z F ok, so must be pair VZ KVBVRBCPZFQFNTTQEQOGYIIOYNG ctxt XXXWETTERVLRHERSJGYMUENGHEN ptxt (pairs EH WR NT VZ) ++++++?+++++ + <- Q:L, Q ok, so pair LO ++++++ +++++?+ <- E:J, E ok, so pair AJ KVBVRBCPZFQFNTTQEQOGYIIOYNG XXXWETTERVORHERSAGEMUENCHEN cables EH WR NT VZ LO AJ ~~~ ~~~ {exercise}{} * find 1st possible alignment of crib with ciphertext * for your alignment, draw Turing diagram * find cycle, and write down info you would give to bombe operator W E T T E R V O R H E R S A G E C A L A I S L O J L A X I O O H N X P Q H C B E S H V I V R H P V Y Q E A Z E M ~~~ ~~~ {}{raw}

kidnapping codebooks

~~~ ~~~ {} - networks: Wehrmacht, Afrika, Luftwaffe, Kriegsmarine - KM 8 rotors, atypical msg form, diff't msg-key protocol - U-boat wolfpack - gardening: mine location crib - pinching stealing codebooks, e.g. Operation Ruthless - Gadenia/Gonzenhein report conclusion: natural disaster or spy ~~~ ~~~ {}{raw}

anonymous cryptanalysts

~~~ ~~~ {} - ULTRA: German Italian Japanese deciphering - Greece Italy Sicily Normandy landings - FW Winterbotham /The Ultra Secret/ - Rejewski, Denniston, Turing: no credit in lifetime - Turing -- 1952 convicted of homosexuality -- hormone treatment, security clearance withdrawn -- 1954 June cyanide apple -- [https://scholar.google.com/citations?user=f8HQJLAAAAAJ&hl=en AT google scholar] ~~~ ~~~ - war of nerves nepotic vista even lacerate reckon resent go astern shot token profits personality apple oath nectar reviewed enslave interrogate taken to task fortunes crackle trepan hoist fool ~~~