Secret Services & Cracking Enigma: The Bombe

"In the years that followed the First World War, the British cryptanalysts in Room 40 continued to monitor German communications. In 1926 they began to intercept messages that baffled them completely. Enigma had arrived, and as the number of Enigma machines increased, Room 40’s ability to gather intelligence diminished rapidly.[...]The speed with which the Allied cryptanalysts abandoned hope of breaking Enigma was in sharp contrast to their perseverance just a decade earlier in the First World War.[...]One nation, however, could not afford to relax. After the First World War, Poland reestablished itself as an independent state, but it was concerned about threats to its newfound sovereignty. To the east lay Russia,[...] and to the west lay Germany[...]Sandwiched between these two enemies, the Poles were desperate for intelligence information, and they formed a new cipher bureau, the Biuro Szyfrów. If necessity is the mother of invention, then perhaps adversity is the mother of cryptanalysis."

[The Code Book, Simon Singh]

The whole process started indeed in Polland in the Biuro Szyfrów, where the disappointed German Hans-Thilo Schmidt, a public dependent of the Chiffrierstelle, brought the papers in which was represented the general structure of the Enigma machine and thanks to a machine intercepted in the Polish mail (They then bought a commercial Enigma machine and used the gathered information to convert it into a military one)

This was actually a great step since, before these info, they only had mathematical analysis data, which, let's be honest here, were more or less useless without the machine. But even in this case "The strength of the cipher depends not on keeping the machine secret, but on keeping the initial setting of the machine (the key) secret"...an expedient that by itself was capable to lay approximately 1.58 x 10^20 possible keys between the Allies and the solution...a result which was more or less impossible to reach in useful time...
This was true untill the matematician Marian Rejewski found a leak in the comunication system: the repetition. The German infact used to comunicate with the daily key the message one (3 letters, one for each rotor) twice (for a total of 6)...Rejewski tabulated the relationships between the first and fourth characters as follows:

   ABCDEFGHIJKLMNOPQRSTUVWXYZ
      O                                   L                K
Given enough messages intercepted in one day, he could complete this table, giving him something like:

   ABCDEFGHIJKLMNOPQRSTUVWXYZ
   FOXPVBUNWYACRIZELDTQGJMKHS

I know that it seems to be leading nowhere, but Rejewski kept playing at it and discovered a property which was going to overturn their work.
He noticed that "A" in the top row was related to "F" in the bottom. He went to "F" in the top row and saw that it was related to "B" in the bottom. He went to "B" in the top row and saw that it was related to "O" in the bottom. He continued this search until he ended up with the "A" in the top row again, and then repeated this game through the rest of the table until there were no more characters left. The example above gives:

   A -> F -> B -> O -> Z -> S -> T -> Q -> L -> C -> X -> K -> A
   D -> P -> E -> V -> J -> Y -> H -> N -> I -> W -> M -> R -> D
   G -> U -> G

Rejewski did the same operationd with different sets of messages sent on different days, and noticed that the pattern of the number of chains and the number of links in the chains varied widely from day to day and he cleverly realized that this pattern provided a fingerprint characteristic of the initial rotor setup. The important thing about it is that it dependeds only on the number of chains and on the number of links in the chains; the exact characters in the chains were irrelevant.

Example of fingerprints structure

  1 chain with 10 characters
  2 chains with 5 characters
  1 chain with 6 characters      rotor order ACB rotor                                 position XHJ

  1 chain with 13 characters
  1 chain with 5 characters
  2 chains with 4 characters     rotor order BAC rotor                                 position FCD

Once the catalog containing all fingerprints was finished, the Poles could then identify the right key and decode all intercepted messages sent during the day, and start over again the day after knowing that most of the work was already done...at least until the Germans altered their usual way of transmitting messages, but Rejewski fought back. Even if his old fingerprints catalog was useles,but instead of rewriting it, he devised a mechanized version of it, which could automatically search for the correct scrambler settings. Rejewski’s invention was an adaptation of the Enigma machine, able to rapidly check each of the 17,576 settings until it spotted a match. Because of the six possible scrambler arrangements, it was necessary to have six of Rejewski’s machines working in parallel, each one representing one of the possible arrangements. Together, they formed a unit that was about three feet high, capable of finding the day key in roughly two hours. The units were called bombes, a name that might reflect the ticking noise they made while checking scrambler settings.

Bomba kryptologiczna  drawing 

from M.Rejewski’s papers

"The bombes effectively mechanized the process of decipherment. It was a natural response to Enigma, which was a mechanization of encipherment"

If you feel like you've missed something go on and check the previous posts related to this one, which are Secret Services & Patents: The Enigma Machine and Technology & The Enigma Machine
If you wanna dig deeper,you can satisfy your thirst for knowledge, you can click on the word links  or on the links of my sources.


Continues...

Sources:
The Code Book, Simon Singh
http://www.bletchleypark.org.uk/content/machines.rhtm
http://www.vectorsite.net/ttcode_08.html#m1
http://en.wikipedia.org/wiki/Bombe
http://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma