The forgotten father of Colossus

Codebreakers at Bletchley Park in 1942 faced a big problem. Decrypting messages from Germany’s now-famous Enigma encryption engine was progressing satisfactorily with the aid of machines called Bombes that could rapidly mirror Enigma’s operation.

But harder to crack was a more complex engine called the Lorentz SZ40 (SZ42 in a later design) that encrypted 5,000 characters per second. It was used by the Nazi High Command.

A break had come in August 1941 when a German operator, against orders, transmitted the same message twice without changing the settings of the SZ40, with slight mistakes the second time. Remarkably, codebreakers were able to deduce from this both the text of the message and the structure of the machine.

The message and the SZ40’s encrypted output both used the five-bit binary Baudot code used in teleprinters. The output was derived from adding the message stream to a masking ‘keystream’ using binary arithmetic: carry bits were dropped, so the addition was equivalent to an XOR operation (ie using the rules: 1+1=0; 0+0=0; 1+0=1; 0+1=1).

The keystream was generated by five pairs of wheels, one for each of the five bits of a Baudot character. Each wheel had a different pattern of 0s and 1s (to use modern notation), and the key bit came from XOR-ing the two active bits of each pair. Two control wheels complicated matters by moving one of the wheels (called the chi) after each character, and the other (the psi) only sometimes.

Wheel bit patterns changed every month or so but the starting position of each wheel usually changed with each message. By late 1942 codebreakers had found a way of deriving bit patterns from the few occasions when German operators sent two different messages with the same settings, This allowed them to reproduce the entire chi stream, Then a young Cambridge graduate, William Tutte, discovered that XOR-ing the encrypted message with itself, shifted by one character, cancelled out much of the effect of the more static psi wheels and had a high correlation with the chi stream.

So by comparing this stream with the chi stream at successive start points to find the best fit, they could home in on the start position. With this information it was possible to extract the message.

This task would be trivial today. In 1942, few people were aware even of the concept of a computer. But one of them, Alan Turing, had designed one in abstract and he was at Bletchley Park. Some of his ideas had gone into the mechanical logic used to break the Enigma; now Bletchley tried to apply similar methods to the new problem.

The Tutte and chi streams were punched into paper tapes and compared using a system of photo-electric sensors and relays. It worked after a fashion, but it was slow and the tapes tended to fall out of sync. At this point, one of the least-known pivotal figures of the 20th century enters the story.

Like this story? Spread the news by clicking below:

 del.icio.us     Digg this     reddit!