The Imitation Game – The Movie

The number of theoretical permutations of the 26 alphabet, 26! is 0.4 billion billion billion – 0.4 octillion (4 followed by 26 zeros). This is the number of maps from the set of 26 letters to itself, and the size of the space of all maps that the German Enigma machine played in.

The number of maps an Enigma utilized to transform an input letter to another is much smaller. At the core the machine has a handful of rings which implement fixed maps. Each individual ring implements one fixed map of the numbers 1-26 to itself.   The fixedness is important  – bit hard to believe as it appears to considerably simplify the attack – the ring does not vary its map (input-output permutation ) except due to rotation of the ring – which can be in any of 26 different positions. With 3 rings, they could be ordered in 6 ways and total of 6×26^3 maps – only about 106,000. With the 3 rings chosen from 5 available rings instead of 3, there could be 5x4x3 or 60 combinations and 60×26^3 maps – a million. At each letter entry the rotors would change to use another of the ~10600 maps.  Guessing a valid map (10^5) from the much larger space of all maps (4*10^26) made cracking the code impossible – assuming good operating procedures. The plugboard implemented another (fixed) permutation.

The Polish bomba utilized leaked knowledge of both the maps and the known number of rings – and with that information tried a brute force attack for the 3-ring design. Even with knowledge of the machine internals this required ingenuity to look for patterns in the messages – duplicate input letters that were frequently mapped to duplicates in the output reduced the search space.

This worked until the Germans added two more rings to the original 3. At this point the Polish method was not effective. Turing understood a different method was needed.

The machine that was built at Bletchley park and was shown in the movie was also a brute force machine, not a general purpose computer (as I assumed before the movie). It used input text that was likely to be in the transmitted data, encrypted it in several combinations then compared it with the actual transmissions. This is called a chosen plaintext attack.

An interesting aspect in the movie was how hard Turing had to fight to keep the idea of this machine alive as it was an unknown and unproven concept to the military generals. When he succeeded and U-boats were started to be destroyed (with a cover of air surveillance as the source of sighting the subs), Admiral Karl Dönitz on the German side had to convince his own chain of command of the need to change Enigma – a request deflected for several months as the German chain of command bought the air surveillance story. Dönitz eventually succeeded in adding a fourth rotor and the submarine attacks subsided immediately – until a couple subs were captured and the details of the newer rings were found by the British.

In a way, the machines on either side were trying to get smarter but were slowed down by a human bottleneck. The selfish machines.

The basic idea of a small set of pseudo-random (fixed) permutations embedded in a larger space of permutations is utilized in block-ciphers (DES, AES) in form of P-boxes. A difference is the presence of S-boxes which achieve mixing of the inputs so an input pattern does not have a deterministic effect on output patterns.

What’s interesting is an information theoretic notion of security which is not susceptible to attacks. Some of these ideas are used in the IDEA cipher.

Advertisements

2 thoughts on “The Imitation Game – The Movie

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s