Cryptology by Discovery: An Introduction to Conjecture and Proof

Section 4.5 Cribs and Bombes

Our next section about cryptanalysis related to the Enigma machine moves to Bletchley Park in England. Bletchley Park was the World War II home for the Government Code and Cypher School (GC&CS). Its codebreakers included Alan Turing, Gordon Welchman, Hugh Alexander, Stuart Milner-Barry and many, many others. Mathematicians were also heavily recruited at Bletchley Park. The codebreaking work at Bletchley Park had many fascinating success stories, but in this section we will focus on the cryptanalysis of the Enigma machine and the work of Alan Turing.

The Polish work to break Enigma messages relied heavily on the repeated encryption of the message key and developing some electro-mechanical devices to help check the many potential initial settings. The codebreakers at Bletchley Park relied heavily on the Polish work, especially the deduction of the wirings of the rotors and the Zygalski sheets. The Zygalski sheets became ineffective in May of 1940 when the repeated encryption of the message key was discontinued. Fortunately, Alan Turing, Gordon Welchman and others were working on a new idea to use cribs to make deductions about inital settings. This required designing more elaborate machines, called bombes after the Polish bomba, to check all the possible initial settings very quickly.

In order to use a crib for decrypting ciphertext, it is necessary to know an exact word or phrase that will occur in the plaintext. Early decryption work allowed cryptanalysts to learn patterns in German messages that allowed them to discover many useful cribs. One main type of message that helped for cribs was weather reports that were sent at the same time everyday. According to Copelands's “The Essential Turing” other routine phrases that occurred often and became cribs include:

• Wetter fuer die nacht (weather for the night)

• Zusand ost waertiger kanal (situation eastern channel)

• Feuere brannten wie befohlen (beacons lit as ordered)

Finding the location of cribs in the ciphertext was made easier by the property that the Enigma machine will never encrypt a letter as itself.

For an example, we will turn to a training manual for the Enigma machine that Turing wrote for use at Bletchley Park. This was known affectionately at Bletchley Park as the “Prof's Book”, but if more officially known as Turing's “Treatise on the Enigma”. In it, he describes how to use a matched matched plaintext/ciphertext pairing from a crib to find cycles of letters. We will refer to these at Turing loops. The ciphertext in the top row is paired with the plaintext in the bottom row. The full plaintext is “Keine Zusaetze Zumvorberiqt” which is German for “No additions to Preliminary Report.”

Example 4.5.2.

In this example, two main loops are shown, one in green and one in orange. These are the shortest possible loops since they involve only two letters at two different positions. There is a loop connecting A and E at positions 2 and 5. There is also a loop connecting E and I at positions 3 and 10. Remember that encryption and decryption is the same for Enigma so it doesn't matter if the letters are in the plaintext or the ciphertext to create a loops.

A plaintext/ciphertext pairing would produce a longer loop if it takes more steps to connect back to the starting letter. For example, if a crib produced the following ciphertext/plaintext pairing

position	1	4	6	9
CT	D	N	N	Z
PT	K	K	Z	D

From Investigation: Turing Loops you should have found all connections from the given ciphertext/plaintext pairing. A diagram showing all of these connections was known as a menu. You can compare your work to Turing's menu in Figure 4.5.5. Can you spot the mistake in Turing's menu?

The importance of the loops stems from Turing's idea for how to use them to design electrical circuits in the bombe machines. The bombe machines essentially consisted of multiple scrambling units of Enigma machines (no plugboards) connected together and could reject possible settings very quickly if they did not contain an appropriate electrical circuit corresponding to a loop. To illustrate how this works, we first consider how a loop would work if there were no cables connecting letters in the plugboard. Suppose we have the A-E loop at positions 2 and 5 as in Example 4.5.2. Then we must have an initial setting where A is encrypted as E and then three steps later in Enigma machine, A must also be encrypted as E. To test if this works for rotor setting AAA and wheels I,II,III we need to connect two Enigma machines in the following way.

• Set machine 1 to setting AAA and wheels I,II,III. [Corresponding to position 2 in loop]

• Set machine 2 to setting AAD and wheels I,II,III [Corresponding to position 5 in the loop which is 3 positions after position 2.]

• Connect machine 1 to machine 2 so that the output of machine 1 becomes the input of machine 2. Type A on first machine. It should output E which becomes the input to the second machine. Then the second machine should output A. So with the machines wired together, we want to input A and see if the connected machines output A.

• If not, change the wheel settings to AAB and AAE and try again. Then we would also need to try all possible arrangements of the rotors.

There is also some chance the middle wheel might turn in the process if the notch on that rotor is activated, so that must also be considered. This is already a lot of things to check and we have been ignoring the plugboard. However, Turing importantly realizes that loops are “characteristics of the crib which are independent of the Stecker.” [“Treatise on the Enigma”, p98] The loops will still happen even if the plugboard component is not present. They will just happen with different letters. For example, if the plugboard swaps A and K, and we remove the plugboard cables, now K will be the letter that goes to itself instead of A. We illustrate this idea with the mini enigma simulator. In the mini enigma simulator there is a C-F loop at positions 0 and 2.

The mini enigma has cables that swap A&C and E&F. If we remove all swaps in the plugboard, then there is still a two letter loop at positions 0,2. However, it is now an A-E loop instead of a C-F loop as in Figure 4.5.7. The C changed to A because of the AC swap in the plugboard, and the F changed to E because of the EF swap in the plugboard. (If you want to try this yourself in the code, change the second line of code from plug=[["A","C"],["E","F"]] to plug=[["A","A"],["E","E"]]. )

Turing's brilliant idea for designing the bombe was to work backwards. Find loops from ciphertext/plaintext pairings and use them to find rotor settings that would satisfy the loops. More precisely the goal was to use these loops to find stecker values for the letters in the loops or to determine that there is no possible set of stecker values and thus rule out the given setting. Multiple loops were necessary to narrow down the possibilities successfully. However, Gordan Welchman's important contribution for the addition of a diagonal board eventually allowed this technique to work with smaller cribs and no loops. Gordan Welchman in “The Hut Six Story” writes

The idea that flashed into my mind in the School was that by interconnecting the scramblers in a completely new way, one could increase the effectiveness of the automatic test by a very large factor. I saw that we need not depend on obtaining three closed loops. Instead a bombe could be constructed that would make use of configurations [...] involving one loop or no loops at all.

The first bombe, named “Victory”, was installed in March 1940 initially without the diagonal board. Some messages were broken in May and June 1940 using “Victory” and some captured Enigma settings. Eventually the diagonal board was added to “Victory” and a second bombe (with diagonal board) named “Agnus Dei” or “Aggie” was installed in August 1940. With the diagonal board and two working machines, 178 messages were read in 1940. The bombes were very effective on air force and army traffic and these were regularly broken throughout the rest of the war. Many more bombes were built to handle the proliferation of different channels of communications (each with their own key). Naval messages were harder because of a double encryption and the introduction of a four rotor naval Enigma machine in 1942. These required additional work and additional bombes, but in general, the use of bombes to decrypt German messages was very successful!

Photo from Wikipedia

A sample Enigma message from 1944 with a crib and its resulting menu is in Figure 4.5.9. In this case the crib is “YYABSTIMMSPRUQ”. This crib comes from the German abstimspruch which means test message. (So it was not a particularly interesting message at the time, but very interesting for us to have a historical example.) The writing in red is a guess that this crib occurs at the end of the message and gives the associated menu.

Images from Enigma red messages collection at Bletchley Park

Turing's work on designing bombes was only one of his important wartime contributions to cryptanalysis. He also worked on indicator systems for Naval Enigma traffic, the Lorenz cipher machine, and voice encryption. Starting in 1937 German Naval traffic (codenamed SHARK) was encrypted with two different methods: first a combination of tables of bigram and trigram (blocks of two or three letters) to send the message indicator settings, and then with an Enigma machine. In 1942, this was further complicated with the addition of a fourth rotor. Turing worked on identifying the German Navy's indicator procedure and developed a pencil and paper technique called “Banburismus” to reduce the amount of bombe time using a statistical scoring method based on probabilities. The Lorenz cipher machine was a different type of machine cipher (codenamed TUNNY). Turing worked out a technique, known as “Turingery”, for determining the cam settings of the wheels. In 1942, Turing went to the United States to serve as a consultant for US Navy's codebreaking work on the Enigma. He also worked at Bell Labs on speech encryption techniques for telephone systems (both breaking systems and designing a secure system). When Turing returned to England in 1943, he worked on a different system for voice encryption called Delilah at Hanslope Park.

Photo taken by the author at the National Cryptologic Musuem

After the war, Turing continued his interest in building programmable computing machines. He designed the Automatic Computing Engine at the National Physical Laboratory, and helped to develop the Manchester computers in Max Newman's Computing Machine Laboratory at the Victoria University of Manchester. He also wrote papers on artificial intelligence and mathematical biology.

Photo from National Physical Laboratory