# 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
~~~