A visit to the National Museum of Computing in Bletchley Park

Last Friday, I went to the National Museum of Computing (TNMOC) in Bletchley Park, home of the British Government Code and Cypher School during World War II. It was hosting a special event to celebrate two new acquisitions: a Lorenz teleprinter recently found on eBay and a Lorenz SZ42 cipher machine on long-term loan from the Norwegian Armed Forces Museum. TNMOC now has all of the key parts (either original or rebuilt) used in the process of encryption, interception, and decryption of Lorenz messages sent by the German High Command during WWII. Five women of the WRNS (Women's Royal Navy Service, whose members are often called "wrens") who operated Colossus and the relatives of others who contributed to breaking Lorenz attended this special event.

John Whetter, one of the leaders of the team at TNMOC that rebuilt the British Tunny (in the background), holds a Spruchtafel, next to the Lorenz machine on loan from Norway.

The Lorenz cipher

The story of Lorenz, Bill Tutte, and Tommy Flowers is perhaps less well known than the story of Enigma and Alan Turing. The Enigma machine encrypted messages sent among units of the German army, navy, and air force. It had 3 or 4 rotors and operated directly on an alphabet of 26 letters, which were then transmitted in Morse code.

The Lorenz SZ42, on the other hand, was custom-built for the German High Command to send the most important strategic messages to its Field Marshals. It was more complex and less portable than an Enigma machine. The Lorenz cipher could handle letters, punctuation, and spacing: each character was encoded as 5 bits according to the Baudot code. The machine had 12 wheels, each with a number of cams (pins) on it. The numbers of cams on the wheels were co-prime. The "key" was in two parts: the starting position of each wheel ("wheel setting"), and the pattern of raised or lowered cams on each wheel ("wheel pattern"). The wheel settings were supposed to be changed for each message, while the wheel patterns were changed infrequently—for the first few years. When the wheel patterns did begin to change more frequently, however, Colossus II was operational and could find them.

The entire process of intercepting a message went roughly as follows.

1. Setting up to send the message

• The sending operator in Berlin picks six pairs of letters at random from a prepared sheet.
• He or she types them in to the teleprinter (without the Lorenz machine attached). The output is a paper tape with punched holes corresponding to the Baudot encoding of the letters.
• Next, the operator uses a board of wheel settings (a Spruchtafel) to determine the starting position of the Lorenz SZ42's rotors. Each of the letters corresponds to a number.

German Lorenz operators consulted a Spruchtafel to determine which wheel settings (starting positions) to use based on a given 12-letter indicator. (source)

2. Encrypting and sending the message

• Now, the teleprinter operator in Berlin hooks up the Lorenz encryption machine to the teleprinter and types the plaintext message.
• The encrypted message is output on the same perforated paper tape, again encoded with the Baudot code.
• The paper tape corresponding to the 12-letter indicator and the ciphertext is fed to a radio transmitter, which broadcasts it.

3. Intercepting the message

• Radio receivers at an intercept station at Knockholt, Kent (south-east of London) pick up the encrypted message.
• The faint signals are fed to an undulator, which uses an ink pen to record a continuous trace of the signal on a strip of paper tape, the "slip".
• Slip readers (people, not machines) translate the highs and lows on the slip to characters according to the Baudot code. To minimize errors, two or more slip-readers read each transmission.
• The characters are typed in to a perforator that produces another strip of paper upon which the characters are encoded in Baudot code.
• The intercepted message is sent to Bletchley Park (100 km away) in two ways: by secure landline and by motorcycle courier.

4. Decrypting the message

• The perforated tape is fed to Colossus, which outputs the most likely wheel settings (Colossus I) and wheel patterns (Colossus II onwards).

The input to the Colossus machine is perforated paper tape with characters in 5-bit Baudot code.

WWII-era cryptography vs. modern cryptography

I went to TNMOC with Thyla van der Merwe, another PhD student at Royal Holloway, to speak to the guests for a few minutes about cryptography today and how it works now compared to how it worked in the WWII era.

Thyla and Marie-Sarah next to TNMOC's rebuilt Colossus.

Thyla explained the benefits of using a stream cipher, like the Lorenz cipher—they're fast, they don't propagate ciphertext errors, and they require only small buffers. These properties made it appropriate for encrypting radio transmissions. She pointed out how ordinary citizens of the WWII era probably didn't use encryption, while today, it is ubiquitous: everyone who's been online or had a cell phone has used it.

I talked about what makes "modern" cryptography different. At the time of WWII, public-key cryptography had not yet been discovered, so sharing keys for any kind of symmetric protocol was still hard. Cryptography in that era also didn't have the precise definitions, clear assumptions, and rigorous security reductions we have today. (Katz and Lindell's textbook does a wonderful job of explaining these three features of modern cryptography.) Although these more formal aspects of modern cryptography are powerful, their strength in the real world is limited in two ways. First, they may not capture all of the information or capabilities an attacker may have (e.g., side-channel attacks). Second, and maybe even more importantly, they come with the assumption that protocols are implemented and used exactly as they should be.

For example, cryptographers know how important it is that a stream cipher (like the Lorenz cipher) never re-uses the same keystream for different messages, because the XOR of two ciphertexts would equal the XOR of the two plaintexts. If the two messages are similar, then keystream re-use is particularly dangerous. This mistake is exactly what led cryptanalysts at Bletchley Park to decrypt two long messages and obtain 4000 characters of keystream: in August 1941, a long message was retransmitted with a few minor changes, but with the same key settings. Within a few months, cryptanalyst John Tiltman had recovered the keystream. By January 1942, Bill Tutte had fully reverse-engineered the Lorenz machine... without ever having seen it!

The operator or implementer of a cryptographic protocol that uses a stream cipher may not understand how important it is that the keystream never be re-used, or may simply make a mistake. This type of mistake hasn't happened only in WWII. In the late 1990s, the IEEE 802.11 standard specified the WEP (Wired Equivalent Privacy) protocol for Wi-Fi networks. WEP uses the stream cipher RC4 to encrypt traffic from access points (wireless routers) to mobile stations (all devices wirelessly connected to the network). Partly due to the WEP protocol's design, and partly due to how the access points' keys tended to be managed in practice, the same RC4 keystream was frequently re-used in implementations. (The key supplied to RC4 was a concatenation of a 24-bit IV, sent in plaintext along with each encrypted message, and a 40-bit shared secret key, which was rarely changed.) Read more about WEP's shortcomings in Borisov, Goldberg, and Wagner's CCS 2001 paper.

Modern cryptography may offer many new tools, definitions, and rigorous proofs, but some things will never change: designing protocols that are secure in the real world is still really hard, and breaking cryptographic schemes still requires a great deal of creativity, analysis, and dedication.

More about the Lorenz story

Determining how the Lorenz machine worked was only the first step. Tommy Flowers, an engineer at the Post Office Research Station, designed and built an emulator, "Tunny," of the Lorenz machine. An entire section at Bletchley Park (the "Testery," named after the section head, Ralph Tester) was devoted to decrypting the messages—which they did by hand for the first 12 months. Max Newman and Tommy Flowers designed and built machines to speed up the decryption process: the "Heath Robinson" and "Colossus". Colossus was the first electronic digital machine that was programmable (with plugs and switches). Heath Robinson and Colossus were operated (and named, actually) by members of the WRNS.

• TNMOC news release about the event on 3 June.
• FISH and I: transcript of a lecture given by Bill Tutte at the University of Waterloo in 1998. (Bill Tutte was one of the first members of the Department of Combinatorics and Optimization at the University of Waterloo, in which department I studied.)
• Colossus: Breaking the German 'Tunny' Code at Bletchley Park: a well-illustrated article by B. Jack Copeland, a Professor of Philosophy and Director of the Alan Turing Archive for the History of Computing who has written books about Alan Turing and Colossus.
• The Lorenz cipher machine and the Colossus: articles written by Tony Sale, who was one of the founding trustees of TNMOC and led the team that rebuilt Colossus.