ch4: cracking the enigma

postWWI   Rej   baton   geese   cryptic   Tcrack   kidnap  

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

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

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

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

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

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

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 (??)

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)

cryptic crosswords

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

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

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

    • 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