Enigma: Enigma


Enigma: Enigma Developed and patented (in 1918) by Arthur Scherbius Many variations on basic design Eventually adopted by Germany For both military and diplomatic use Many variations used Broken by Polish cryptanalysts, late 1930s Exploited throughout WWII By Poles, British, Americans


Enigma: Enigma Turing was one of Enigma cryptanalysts Intelligence from Enigma vital in many battles D-day disinformation German submarine “wolfpacks” Many other examples May have shortened WWII by a year or more Germans never realized Enigma broken  Why? British were cautious in use of intelligence But Americans were less so (e.g., submarines) Nazi system discouraged critical analysis…


Enigma: Enigma To encrypt Press plaintext letter, ciphertext lights up To decrypt Press ciphertext letter, plaintext lights up Electo-mechanical


Enigma Crypto Features: Enigma Crypto Features 3 rotors Set initial positions Moveable ring on rotor Odometer effect Stecker (plugboard) Connect pairs of letters Reflector Static “rotor”


Substitution Cipher: Substitution Cipher Enigma is a substitution cipher But not a simple substitution Perm changes with each letter typed Another name for simple substitution is mono-alphabetic substitution Enigma is an example of a poly-alphabetic substitution How are Enigma “alphabets” generated?


Enigma Components: Enigma Components Each rotor implements a permutation The reflector is also a permutation Functions like stecker with 13 cables Rotors operate almost like odometer Reflector does not rotate Middle rotor occasionally “double steps” Stecker can have 0 to 13 cables


Enigma Rotors: Enigma Rotors Three rotors Assembled rotors


Rotors and Reflector: Rotors and Reflector Each rotor/reflector is a permutation Overall effect is a permutation Due to odometer effect, overall permutation changes at each step


Why Rotors?: Why Rotors? Inverse permutation is easy Need inverse perms to decrypt! Pass current thru rotor in opposite direction Can decrypt with same machine Maybe even with the same settings… Rotors provide easy way to generate large number of permutations mechanically Otherwise, each perm would have to be wired separately (as in Purple cipher…)


Wiring Diagram: Wiring Diagram Enter C Stecker: C to S S permuted to Z by rotors/reflector Stecker: Z to L L lights up


Enigma is Its Own Inverse!: Enigma is Its Own Inverse! Suppose at step i, press X and Y lights up Let A = permutation thru reflector Let B = thru leftmost rotor from right to left Let C = thru middle rotor, right to left Let D = thru rightmost rotor, right to left Then Y = S-1D-1C-1B-1ABCDS(X) Where “inverse” is thru the rotor from left to right (inverse permutation) Note: reflector is its own inverse Only one way to go thru reflector


Inverse Enigma: Inverse Enigma Suppose at step i, we have Y = S-1D-1C-1B-1ABCDS(X) Then at step i X = S-1D-1C-1B-1ABCDS(Y) Since A = A-1 Why is this useful?


Enigma Key?: Enigma Key? What is the Enigma key? Machine settings What can be set? Choice of rotors Initial position of rotors Position of movable ring on rotor Choice of reflector Number of stecker cables Plugging of stecker cables


Enigma Keyspace: Enigma Keyspace Choose rotors 26!  26!  26! = 2265 Set moveable ring on right 2 rotors 26  26 = 29.4 Initial position of each rotor 26  26  26 = 214.1 Number of cables and plugging of stecker Next slide Choose of reflector Like stecker with 13 cables… …since no letter can map to itself


Enigma Key Size: Enigma Key Size Let F(p) be ways to plug p cables in stecker Select 2p of the 26 letters Plug first cable into one of these letters Then 2p - 1 places to plug other end of 1st cable Plug in second cable to one of remaining Then 2p - 3 places to plug other end And so on… F(p) = binomial(26,2p)  (2p1)  (2p3)    1


Enigma Keys: Stecker: Enigma Keys: Stecker F(0) = 1 F(1) = 325 F(2) = 44850 F(3) = 3453450 F(4) = 164038875 F(5) = 5019589575 F(6) = 100391791500 F(7) = 1305093289500 F(8) = 10767019638375 F(9) = 53835098191875 F(10) = 150738274937250 F(11) = 205552193096250 F(12) = 102776096548125 F(13) = 7905853580625 F(0) + F(1) + … + F(13) = 532985208200576 = 248.9 Note that maximum is with 11 cables Note also that F(10) = 247.1 and F(13) = 242.8


Enigma Keys: Enigma Keys Multiply to find total Enigma keys 2265  29.4  214.1  248.9  242.8 = 2380 “Extra” factor of 214.1 2265  29.4  248.9  242.8 = 2366 Equivalent to a 366 bit key! Less than 1080 = 2266 atoms in observable universe! Unbreakable? Exhaustive key search is certainly out of the question…


In the Real World (ca 1940): In the Real World (ca 1940) 5 known rotors: 543 = 25.9 Moveable rings on 2 rotors: 29.4 Initial position of 3 rotors: 214.1 Stecker usually used 10 cables: 247.1 Only 1 reflector, which was known: 20 Number of keys “only” about 25.9  29.4  214.1  247.1  20 = 276.5


In the Real World (ca 1940): In the Real World (ca 1940) Only about 276.5 Enigma keys in practice Still an astronomical number Especially for 1940s technology But, most of keyspace is due to stecker If we ignore stecker… Then only about 229 keys This is small enough to try them all Attack we discuss “bypasses” stecker


Enigma Attack: Enigma Attack Many different Enigma attacks Most depend on German practices… …rather than inherent flaws in Enigma Original Polish attack is noteworthy Some say this is greatest crypto success of war Did not know rotors or reflector Were able to recover these Needed a little bit of espionage…


Enigma Attack: Enigma Attack The attack we discuss here Assumes rotors are known Shows flaw in Enigma Requires some known plaintext (a “crib” in WWII terminology) Practical today, but not quite in WWII


Enigma Attack: Enigma Attack Let Pi be permutation (except stecker) at step i S is stecker M = S-1 P8S(A)  S(M) = P8S(A) E = S-1 P6S(M)  S(E) = P6S(M) A = S-1 P13S(E)  S(A) = P13S(E) Combine to get “cycle” P6P8P13S(E) = S(E) Suppose we have known plaintext (crib) below


Enigma Attack: Enigma Attack Also find the cycle E = S1 P3S(R)  S(E) = P3S(R) W = S1 P14S(R)  S(W) = P14S(R) W = S1 P7S(M)  S(W) = P7S(M) E = S1 P6S(M)  S(E) = P6S(M) Combine to get P6 P141 P7 P61 S(E) = S(E)


Enigma Attack: Enigma Attack Guess one of 229 settings of rotors Then all putative perms Pi are known If guess is correct cycles for S(E) hold If incorrect, only 1/26 chance a cycle holds But we don’t know S(E) So we guess S(E) For correct rotor settings and S(E), All cycles for S(E) must hold true


Enigma Attack: Enigma Attack Using only one cycle in S(E), must make 26 guesses and each has 1/26 chance of a match On average, 1 match, for 26 guesses of S(E) Number of “surviving” rotor settings is about 229 But, if 2 equations for S(E), then 26 guesses for S(E) and only 1/262 chance both cycles hold Reduce possible rotor settings by a factor of 26 With enough cycles, will have only 1 rotor setting! In the process, stecker (partially) recovered! Divide and conquer!


Bottom Line: Bottom Line Enigma was ahead of it’s time Weak, largely due to combination of “arbitrary” design features For example, right rotor is “fast” rotor If left rotor is “fast”, it’s stronger Some Enigma variants used by Germans are much harder to attack Variable reflector, stecker, etc.


Bottom Line: Bottom Line Germans confused “physical security” and “statistical security” of cipher Modern ciphers: statistical security is paramount Embodied in Kerckhoffs Principle Pre-WWII ciphers, such as codebooks Security depends on codebook remaining secret That is, physical security is everything Germans underestimated statistical attacks


Bottom Line: Bottom Line Aside… Germans had some cryptanalytic success Often betrayed by Enigma decrypts In one case, before US entry in war British decrypted Enigma message German’s had broken a US diplomatic cipher British tried to convince US not to use the cipher But didn’t want to tell Americans about Enigma!


Bottom Line: Bottom Line Pre-computers used to attack Enigma Most famous, were the Polish “bomba”, British “bombe” Electro-mechanical devices British bombe, essentially a bunch of Enigma machines wired together Could test lots of keys quickly Noisy, prone to break, lots of manual labor