A Fishy Project at Bletchley Park

May 29, 2011

Back in January, I wrote about a project to rebuild one of the world’s first computers, the EDSAC, at Bletchley Park in the UK, home of the National Museum of Computing.  Bletchley Park was also the home, during World War II, of the Government Code and Cipher School, also called Station X, which was the center of British code-breaking efforts against the Axis powers.  It was the site of the successful operation, led by Alan Turing, to intercept and decrypt the German Enigma messages.

An article at the BBC site reports that another important artifact of computing history at Bletchley Park has now been reconstructed: the Tunny machine.  This was a machine designed to assist in routine decoding of the German Lorenz cipher, which was used for communications between the German High Command in Berlin and field headquarters.  Unlike the Enigma cipher, which was used to encode text to be transmitted by radio in the form of Morse code, the Lorenz machine was an attachment to a teleprinter (teletype).  It implemented a Vernam stream cipher as text was typed into the teleprinter.

A Vernam cipher takes as its inputs two streams of bits or characters: a plain-text stream, T, and a key stream, K.  The enciphered output stream is produced by performing an exclusive-OR [XOR] operation between T and K.  This operation works according to this logical truth table:

T K Output
0 0 0
0 1 1
1 0 1
1 1 0

If this cipher is implemented with a truly random key stream, then it is a one-time pad, the one provably unbreakable cipher.   However, key distribution for such  a method would present serious problems, so in practice a pseudo-random number generator [PRNG] is usually used to generate the key stream.  Obviously, it is vital that the generating process produce a stream that is effectively random.

The Lorenz device was, effectively, an electro-mechanical PRNG attached to the teleprinter.  The British cryptanalysts were able to deduce its design without ever seeing the device, because the Germans made a fundamental error — what you might call a rookie mistake — in August 1941.  A Lorenz message was sent by one operator, but not correctly received at the other end.  A clear-text request for a re-transmission was made, and then the message was re-sent using the same key stream, a serious no-no.  In addition, the sender made slight changes (e.g., using abbreviations) to the original plain text.  Because of these errors, the Bletchley Park analysts were able to recover both the plain text and the key stream used, and the mathematician Bill Tutte was able to deduce how the Lorenz device worked.

The Tunny machines were, in essence, a reverse-engineered copy of the decrypting Lorenz device.  (The name came from the practice of referring to the Lorenz intercepts as “fish” traffic; ‘tunny’ is a British English word for tuna.)   The BBC article has a short video explaining more about how they worked.

The reconstruction work is impressive, especially since, according to John Pether, one of the leaders of the project team, there was not all that much to go on:

Mr Pether said the lack of source material made the rebuild challenging.

“As far as I know there were no original circuit diagrams left,” he said. “All we had was a few circuit elements drawn up from memory by engineers who worked on the original.”

Most of the work done at Bletchley Park during the war was kept secret for many years afterwards.  It’s fascinating to see how much truly innovative work remained largely unknown for so long.


%d bloggers like this: