Netting the Big Tuna

Intercepting and decrypting enemy messages was an important part of the Allies' strategy during World War II.  Beginning in July 1941, Germany's high command communication used a machine called the Lorenz SZ40 or SZ42, which British intelligence referred to as "Tunny" (named after the fish that Americans call "tuna").  Although the British did not obtain a Lorenz machine until late in the war, the codebreakers at Bletchley Park were able to deduce the machine's operation in January 1942.

The Tunny machine used a typewriter-style keyboard to enter text which was combined with a pseudo-random byte string to produce the cypher text.  This was then transmitted by radio or telegraph to a Tunny machine which was set up to generate the same byte string and combine it with the cypher text to get the plaintext message (a symmetric cypher using a pseudo-random one-time pad).


The key to encrypting and decrypting the cypher is the use of 'exclusive or' or 'xor', which has the property of returning one of the inputs when the xor'ed value is xor'ed with the other input, that is (using '+' for 'xor'), if c = a + b, c + a = b and c + b = a.

The Tunny was attached to a teleprinter (teletype) machine with a 5-bit character encoding.  The Tunny had 12 wheels in groups of 5, 2, and 5.  The first group of wheels, called "chi" (after the Greek letter), all advanced one position with each character, the second group of wheels, called "mu" or "motor wheels", advanced independently, the first wheel with each character, and cams on the first wheel advanced the second in a changeable pattern. Cams on the second wheel of the second group advanced all the wheels in the third group, called "psi", simultaneously in a changeable pattern. The number of cams that could be set on each wheel was relatively prime to (had no common factor with) the number on any other wheel, so more than the 350th power of 2 (105th power of ten) key bytes could be generated without repeating a wheel setting.

The key value was determined by xor'ing the corresponding wheels from the first and third group, that is (using X for chi, S for psi, and K for the key), K1 = X1 + S1, K2 = X2 + S2, K3 = X3 + S3, K4 = X4 + S4, and K5 = X5 + S5, with K = (K1)(K2)(K3)(K4)(K5).  Because all the wheels in the psi group either did or did not advance together, the psi group would sometimes generate the same key value for consecutive characters.  This was exploited by the codebreakers to determine the wheel configuration.  If consecutive bytes of the cypher text were xor'ed and the key values were the same, the result was the xor of the plaintext characters.  If the plaintext was known (for example if the messages contained the same phrases on a regular basis, the plaintext of a message were intercepted, a fake message were transmitted, or an operator left a machine on and put something on top of the keyboard), the pattern of repeated wheel positions could be determined.

There were three steps in breaking a Tunny cypher:  "wheel breaking" discovered which cams were set on each wheel, "wheel setting" discovered the starting point of each wheel, and a reconstruction of the Lorenz machine was used to produce the plaintext message.

In August 1941 two messages with the same indicator (which told the receiving operator the wheel settings) were intercepted; this was a message that was corrupted by atmospheric noise and its retransmission.  John Tiltman xor'ed the cyphertexts to cancel out the key string, leaving the xor of the two plaintexts, then, using the parts of the messages that differed (the characters that matched would result in zeros), guessed the words of the original message over a period of ten days.  Xor'ing the plaintext with its corresponding cyphertext produced the key string, which William T. Tutte used to deduce the design of the machine.  Alan M. Turing invented a method for finding cam settings from messages with the same wheel setting (called a "depth").  Later, Tutte used a statistical analysis of the changes in two channels (columns, "impulses", or bit positions) of the cyphertext to determine the wheel setting.

These manual methods were very slow, and two different machines were used to automate these processes.  The first, designed by Max Newman, was called Heath Robinson, after a British cartoonist who drew outlandish machines to do simple tasks (similar to those of Rube Goldberg).  This matched the hole patterns of two long paper tapes to determine the chi wheel setting.  This was prone to errors due to mispunched tapes or stretching of tapes causing the tapes to lose synchronization.  Heath Robinson also was not fast enough to keep up with message traffic.

The second codebreaking machine, designed by Thomas H. "Tommy" Flowers, was called "Colossus", and was a vacuum tube (thermionic valve)-based program-controlled (externally programmed) special-purpose computer.  This was originally intended to determine the setting of the chi wheels, but was later also used to determine the psi wheel setting and the cam setting.  The first Colossus was completed in January 1944, and an improved model was completed on June 1, 1944, in time for the Normandy invasion on June 6.