ch3: mechanisation

1900   adfgvx   zimm   grail   1timepad   crack   machines  

1900 europe

  • crypta beating crypto

  • 1894 Marconi   1901 St John's Cornwall

  • disruptive technology

  • radio vs wire: broadcast vs private

  • -400 Sun Tzu: nothing should be as favorably regarded … generously rewarded … confidential as intelligence

  • 1905 Santayana: those who cannot remember the past are condemned to repeat it

  • 1935 Churchill: When the situation was manageable it was neglected, and now that it is thoroughly out of hand we apply too late the remedies which then might have effected a cure. There is nothing new in the story. It is as old as the sibylline books. It falls into that long, dismal catalogue of the fruitlessness of experience and the confirmed unteachability of mankind. Want of foresight, unwillingness to act when action would be simple and effective, lack of clear thinking, confusion of counsel until the emergency comes, until self-preservation strikes its jarring gong–these are the features which constitute the endless repetition of history.

  • losers get hungry, winners get fat

crypto pre WWI
  • France: had lost Alsace, getting hungry

  • Germany: had won Alsace, getting fat

  • Kerchoffs → France: crypta teams pre WWI

  • adfgvx: Germany 1918

    • Polybius grid, then columnar transposition (keyword perm)

  • Germany advancing, so no landlines, so radio

  • Germany: no crypta teams until 1916

._   _..   .._.   __.   ..._   _.._ adfgvx

encryption
    A D F G V X
A   8 P 3 D 1 N
D   L T 4 O A H
F   7 K B C 5 Z
G   J U 6 W G M
V   X S V I R 2
X   9 E Y 0 F Q

keyword: CUBE

c  r  a  c  k  e  d  b  y  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?

FG VV DV FG FD XD AG FF XF ** ** ** ** ** ** ** ** ** ** ** ** ** **

C U B E  => B          C           E          U

F G V V      VFXF*******FDFAX*******VGDF*******GVDGF*******
D V F G
F D X D
A G F F
X F * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* *
cracking example (keyword length known: 4)
v d g g f x x g g d d v d f g g d g g v d d f d x d d v v v d d f x a g a a a x

v d d d
d v d d
g d f f
g f d x
f g x a
x g d g
x d d a
g g v a
g g v a
d v v x
cracking methods
  • known: grid, keyword

    • decryption ♠ ♠ ♠ ♠

  • known: grid, keysize

    • try k! decryptions ♠ ♠ ♠

  • known: grid, max keysize

    • try 1 + 2! + ... + k! decryptions ♠ ♠

  • known: keysize

    • k! fixed-digrams-substitution-ciphers ♠ ♠

  • known: keyword

    • f-d-s-cs ♠

crack above: known grid, keysize

grid: Appendix F    keysize: 4
VFXFGDGVDAVFDFAXXVXAVVAVGDFVGVDVXGGVDGFDVDDGFX
----------------------------------------------
perm? try 1234:  e.g. keyword ARTY
12 chars     12 chars     11 chars    11 chars
VFXFGDGVDAVF DFAXXVXAVVAV GDFVGVDVXGG VDGFDVDDGFX

VDGVFFDD ... => s g b t ...   :(
----------------------------------------------
perm? try 1243:  e.g. keyword ARTS
12 chars     12 chars     11 chars    11 chars
VFXFGDGVDAVF DFAXXVXAVVAV GDFVGVDVXGG VDGFDVDDGFX

VDVGFFDD ... => s i b t ...   :(
----------------------------------------------
perm? try ...
                               :(
----------------------------------------------
perm? try 3142: e.g. keyword CUBE
chars     12   12   11   11
try        C    U    B    E

B 11        C 12         E 11        U 12
VFXFGDGVDAV FDFAXXVXAVVA VGDFVGVDVXG GVDGFDVDDGFX

FGVVDVFG ... => c r a c ...   :)

Zimmermann affair

  • 1915 Lusitania

  • 1917 Jan 16 telegram to ambassador/Washington

  • Britain: room 40

  • 1917 Feb 1 unrestricted naval warfare

  • 1917 Feb 3 America stays neutral !?

  • 1917 Feb 23 Br => Mexican telegram to Am ambassador

  • 1917 Apr America to war

  • analogue today: Snowden files

    • Americans tapping Merkel's phone

holy grail: 1-time pad

warmup: running key
  • Vigenere cipher with keyphrase (e.g. from book) as long as key

  • how would Friedman cracking method work?

    • each substring has length 1, so freqency analysis useless

  • how to crack ?

    • in key, and in ptext, uneven kgram distribution

    • e.g. THE AND more common than average trigram

cracking running key
key . . . . . . . . . . . . . . . . . . . . .
ptx . . . . . . . . . . . . . . . . . . . . .
ctx V H R M H E U Z N F Q D E Z R W X F I D K

trigrams: the, and, ...

ptx t h e . . . t h e . . . . . t h e . . . .
key c a n . . . b s j . . . . . y p t . . . .
ctx V H R M H E U Z N F Q D E Z R W X F I D K

key c a n . . . . . . . . . c r y p t . . . .
ptx t h e . . . . . . . . . c i t h e . . . .
ctx V H R M H E U Z N F Q D E Z R W X F I D K

key c a n . . . . . . . . . e g y p t . . . .
ptx t h e . . . . . . . . . a t t h e . . . .
ctx V H R M H E U Z N F Q D E Z R W X F I D K

key c a n a d a . . . . . . e g y p t . . . .
ptx t h e m e e . . . . . . a t t h e . . . .
ctx V H R M H E U Z N F Q D E Z R W X F I D K

ptx t h e m e e t i n g . . a t t h e . . . .
key c a n a d a b r a z . . e g y p t . . . .
ctx V H R M H E U Z N F Q D E Z R W X F I D K

key c a n a d a b r a z i l e g y p t . . . .
ptx t h e m e e t i n g i s a t t h e . . . .
ctx V H R M H E U Z N F Q D E Z R W X F I D K

key c a n a d a b r a z i l e g y p t i r a q
ptx t h e m e e t i n g i s a t t h e y . d .
ctx V H R M H E U Z N F Q D E Z R W X F I D K

key c a n a d a b r a z i l e g y p t c u b a
ptx t h e m e e t i n g i s a t t h e d o c k
ctx V H R M H E U Z N F Q D E Z R W X F I D K

1-time pad ?

  • 1918 US Army Major Joseph Mauborgne

  • use uniform random keys

  • secure from cracking, but

    • random key generation is expensive

    • secure key distribution is expensive

evolution
D D D D D D D D D D D D
c a e s a r c i p h e r
F D H V D U F L S K H U
abcdefghijklmnopqrstuvwxyz
DEFGHIJKLMNOPQRSTUVWXYZABC

abcdefghijklmnopqrstuvwxyz
BLIZARDWNGHJKMOPQSTUVXYCEF
k e y p h r a s e s u b s t i t u t i o n c i p h e r
H A E P W S B T A T V L T U N U V U N O M I N P W A S

S E C R E T S E C R E T S E
v i g e n e r e c i p h e r
N M I V R X J I E Z T A W V

A N H I S T O R I C A L I N T R
r u n n i n g k e y c i p h e r
R H U V A G U B M A C T X U X I

Q T X P L K G G U R E M P D W X
o n e t i m e p a d c i p h e r
E G B I T W K V U U G U E K A O

cracking 1-time pad ?

cracking 1-time pad ?
  • no

    • assume keys are uniform random

    • then all keys are equally likely

    • then, for any fixed ciphertext, all plaintexts are equally likely

    • so impossible to crack (using only ciphertext)

crack 1-time pad ?
ctxt  a b i y x z p j
ptxt? a l l o k t n x
ptxt? s e n d h e l p
1-time pad problems
  • generate keys ?

  • distribute keys ?

  • re-use keys ?

cracking twice-used 1-time pad
  • see Appendix G

  • similar to cracking running-key cipher

  • ct1 = pt1 + key

  • ct2 = pt2 + key

  • guess pt1f (fragment)

  • then keyf = ct1f - pt1f

  • corresponding pt2f = ct2f - keyf

  • how to guess pt1-fragment?

    • guess common trigrams etc or possible cribs

crack this
hint: Euro phone bugging ?  so guess Merkel in message
use gitcode 1tc-reuse cracking subtraction tool

k w f h i p c a e j q v h g i c g k y j e j z r x n
v r b u w o d y q q x y e n m k m x f q v i f i s a d
demo: cracking above re-used 1tc
* look for merkel in ctxt1 and/or ctxt2
  in gitcode, run 1time2crack.py with this input

k w f h i p c a e j q v h g i c g k y j e j z r x n
v r b u w o d y q q x y e n m k m x f q v i f i s a d
m e r k e l m e r k e l m e r k e l m e r k e l

output:
  gibberish, so try further placements of merkel

k w f h i p c a e j q v h g i c g k y j e j z r x n
v r b u w o d y q q x y e n m k m x f q v i f i s a d
  m e r k e l m e r k e l m e r k e l m e r k e l

output:
  gibberish, so try further placements of merkel

...

k w f h i p c a e j q v h g i c g k y j e j z r x n
v r b u w o d y q q x y e n m k m x f q v i f i s a d
        m e r k e l m e r k e l m e r k e l

output:
try guess as plaintext 1
. . . . a d s i q s t h o r i t s r y r v k

so the key fragment that
  gives "m e r k e l" in ptxt 1
  gives "t h o r i t" in ptxt 2
maybe this extends to "a u t h o r i t y"  ?

* 1time2crack.py shows
  "onmerkels" in ptxt 1 corresponds to
  "authority" in ptxt 2

* continue, extending either ptxt fragment by guessing ...

* final answer in gitcode repo

cipher machines

  • calculators: abacus, slide rule, adding

  • cipher discs

  • 14xx Alberti   18xx US civil war   19xx cereal boxes

  • rotor (rotating scrambler) cipher machine

    • 1919 Koch Netherlands

    • 19?? Damm Sweden

    • 192? Hebern US Sphinx of the Wireless

    • 1918 Scherbius/Ritter Enigma

  • Enigma

    • keyboard => plugboard => rotor => rotor => rotor => reflector => rotor => rotor => rotor => plugboard => lampboard

    • reflector: e = e-1

    • plugboard: 12 plugs (to start), so 6 pairs

    • ring

  • Spiess enigma simulator

number Enigma keys (3 rotors, 3 slots)
  • placements of 3 rotors in 3 slots?     3 !

  • initial rotor positions ?     26 * 26 * 26

  • plugboard settings ? (12 plugs)

    • choose 12 letters out of 26

    • (26 choose 12) = 26 ! / ( 12 ! (26 - 12) ! )

    • choose smallest letter (alphabetic order):

    • 1 way

    • choose its mate:

    • 11 ways

    • choose next smallest letter (alphabetic order):

    • 1 way

    • choose its mate:

    • 9 ways

    • ...

    • total (26 choose 12) * 11 * 9 * 7 * 5 * 3

    • 100 391 791 500

  • total number of Enigma keys

    • 263 * 3! * (26 choose 12) * 11 * 9 * 7 * 5 * 3

    • about 1016