Beating Colossus: an interview with Joachim Schueth

A group of enthusiasts at the British National Museum of Computing has recently finished the rebuild of a Colossus computer at Bletchley Park. These machines were used by the British in World War II to break the encryption of military radio traffic from Nazi Germany. Colossus was a highly specialised machine that read its input from an endless paper tape at a speed of 5000 characters per second. A circuitry of electron tubes simulated the function of the crypto machine and calculated statistical properties of the data obtained with trial settings of the decryption key (or part of it, to be more exact). Colossus has to be considered one of the first computers in history, and actually a very powerful one at its time.

The rebuild was celebrated by the Cipher Event in which messages were encrypted using an original SZ42 cipher machine and transmitted by amateur radio from the Heinz Nixdorf Museum in Paderborn, Germany, to a receiving station in Britain. The messages were then processed as in the old days by transfer onto punched paper tape which was then loaded into the rebuilt Colossus.

The announcement of the Cipher Event invited radio amateurs around the world to also intercept the messages and to try their hand at deciphering them, and that is what I did.

You need of course some background in cryptography, or at least some mathematical understanding of the historic encryption method used. To participate in the event in real time, you also needed some skills in shortwave radio teletype operation.

The real challenge was to prepare for the event such that I could receive the radio signals and decipher the texts from the received data. The 5-bit Baudot code used does not have any error correction properties, and a regular teletype modem as I also have it as a radio amateur would get confused by the apparently meaningless sequences of control characters that can occur in the ciphertext. The SZ42 enciphers the messages by XORing a pseudorandom sequence of 5-bit symbols onto the character stream, and the resulting binary output is transmitted. Discarding a character would destroy the synchronisation in the crypto analysis, so it was important not to miss a single character during reception, although it is not really important that all characters are received with their correct value. So I decided to write my own software for the signal decoding.

Also implementing an efficient algorithm to do the actual code breaking was a challenge. Tony Sale has a simulation of Colossus on his web site that is written in JavaScript, but I decided to write my own program based on the detailed descriptions of the SZ42 which can be found at www.alanturing.net. The algorithm I used is not quite the same as that implemented by Colossus, although it exploits the same mathematical weaknesses of the SZ42 cipher.

Refer to Joachim Schueth's webpage "Software for breaking the code of the historic Lorenz SZ42 cipher machine" for more details.

Some people thought that Colossus had a chance because of its specific design for its particular task. But when I ran my program on a laptop with 1.4 GHz CPU, I found that it digested ciphertext at a speed of 1.2 million characters per second, which is 240 times faster than Colossus. If you scale the CPU frequency by that factor, you get an equivalent clock of 5.8 MHz for Colossus. This is a remarkable speed for a computer built in 1944. Even 40 years later many computers did not reach that speed. So Colossus would have had a real chance if the Cipher Event had taken place 20 years ago. But my laptop took only 46 seconds for the hardest challenge, which kept Colossus busy for three and a half hours.

I was interested in modern cryptography already during my time at the university. I have a PhD in physics and do not really know what triggered my interest, but in physics you use computers a lot and the common basis may have been random numbers, which are somehow fascinating for a physicist. Today I have a job in IT security consulting and get in touch with modern cryptography on a daily basis. Before preparing for the Cipher Event, I was actually not very interested in the historic algorithms.

One year back I would have written the software in C, simply because I did not really know Ada at that time. But writing the software in Ada made the whole project much more enjoyable.

To tell you the truth, my prejudice had been for a long time that Ada looks just like Pascal, and Pascal had been obsoleted by C. You also have to type less when writing a program in C (just curly braces instead of "begin" and "end"). In hindsight, I have to say that I was quite stupid, and this even though I was always open to learn new programming languages and have looked at a lot of them.

Ada avoids programming errors by its strong typing model, so you spend less time on debugging your programs. The high level data abstraction allows a more intuitive implementation of algorithms. Modeling the SZ42 in Ada by creating data types for the key wheels and combining them to a data type for the entire machine felt a bit like building a machine piece by piece.

I can only encourage everyone to have a look at Ada. It is a modern programming language with all the features of object oriented languages, like high level abstraction, information hiding, generic programming (similar to C++ templates), and function / operator overloading. Personally I do not have much use for inheritance and run-time polymorphism, but Ada has that too, with concepts that seem more logical to me than those of C++ or Java.

Another interesting feature of Ada is that the language has support for tasking, and that it provides protected types for the safe handling of shared data. On modern multiprocessor systems, you can use the full computing power in number crunching applications by performing calculations in parallel. If the run time system provided by the compiler (usually based on POSIX threads) is designed accordingly, you should be able to do parallel processing on several CPUs just by using the standard language features of Ada. I have not yet tried this, though.

Read the Ada Wikipedia article for more details about this programming language.

The question can actually be split into two: Why not Linux but a BSD system, and among the BSD systems, why NetBSD? The first part is actually more easily answered.

I had been using Linux for a long time, and at some time tried FreeBSD. That immediately turned out to be more convincing: For example, I could download the images from my digital camera via USB flawlessly, while Linux crashed when attempting the same thing. Also, I had no longer to search the web desperately to find a How-To or posting with the solution to a technical problem, because the BSD systems are well documented and somehow you do not run into a problem that often. When writing software that was to run on both Linux and BSD, I often had to find workarounds for the shortcomings of Linux for things that work straight forward on BSD. The design of Linux in general is more towards the quick-and-dirty, while BSD is more mature and more thought has been put into good concepts.

To give just one example, when opening a file which is larger than 2 GB or which shall grow beyond this size by writing to it, Linux requires that you pass an extra option O_LARGEFILE to open() or creat(). The whole point of having sys/types.h is that types like size_t or off_t can be defined with appropriate size, and the BSDs today use 64 bit numbers for these. Not so in Linux, which actually has a separate llseek() function besides lseek(). Inventions like O_LARGEFILE are the reason why Linux is a major nuisance in the Unix world, because the necessary #ifdef clauses will soon pollute the source code of portable applications. O_LARGEFILE is like saying O_YES_I_REALLY_WOULD_LIKE_YOU_TO_GET_THINGS_RIGHT. Who chooses an OS that needs such an option to be passed to the kernel? Why not get it right by default?

So why do I prefer NetBSD among the BSDs? In fact, my prime motivation when switching from FreeBSD to NetBSD were the slower release cycles of NetBSD. The NetBSD design goal of portability also seems to pay off through a more abstract approach to hardware support. My laptop has a somewhat non-standard sound chip which is supported in full-duplex by NetBSD, but not by FreeBSD. But the decision for one of the BSDs is not as clear as the decision BSD versus Linux. I can understand everyone who chooses one of the three major BSD derivatives, FreeBSD, NetBSD, or OpenBSD. The latter has a much more defensive programming style in its IPSec implementation, for example.

There is nothing spectacular at the moment. I will surely continue to use Ada as my primary programming language. NetBSD has a pkgsrc package for GCC 3.4 with Ada enabled, which also supports the tasking features of Ada. Unfortunately, GCC 4.2 which has better optimisations can be compiled with Ada enabled on NetBSD, but it does not include tasking for that platform. Some adjustments to ada/Makefile.in are necessary (they are apparently present for FreeBSD), and some additional files need tweaking. One could base the necessary work on the GCC 3.4 pkgsrc patches for NetBSD. However, I do not consider myself an expert in compiler design, and probably will not find the time to do these things, although I strongly hope that someone does.

Recently I got a new computer with an AMD 64 dual core CPU. NetBSD/amd64 with a multiprocessor kernel runs just fine on that machine. Once I find the time I plan to experiment with the parallel computing features of Ada mentioned above.