Joachim Schüeth is the winner of National Museum of Computing's Colossus Cipher Challenge. Using his laptop, Schüeth unravelled a code transmitted from the Heinz Nixdorf Museum in Germany, from a Lorenz SZ42 Cipher machine, used by the German High Command to relay secret messages during the World War II.
Speaking in front of Colossus at Bletchley Park, Schüeth said: "It was unfair because I was using a modern PC, while Colossus was created more than 60 years ago. It really is astonishing and humbling that the world's first programmable, digital computer was created in the 1940s. Without those Bletchley Park pioneers, I would be out of a job."
According to a famous quote by Max Planck, the founder of quantum physics, truth never wins -- its opponents just go extinct.
What Planck described in the context of paradigm shifts in natural sciences can often be observed in a similar fashion in computer technology. For example, the increasing use of Linux as an alternative operating system for applications in industry and government did not emerge because senior management could be convinced, but because a new generation of IT specialists who grew up using Linux on their home computers is shifting into management positions. (For reasons of code maturity and stability I prefer the BSD derivatives over Linux, but that is a different story.)
During the work for my diploma and Ph.D. in Physics in the research group of Professor Bodenstedt at the University of Bonn, I had a similar experience concerning the choice of programming languages. We were using a complex apparatus for our experiments which had been designed by Bodenstedt. Together with two other undergraduates we were three newbies in the group, and there was the generation of older students who just finished their Ph.D.s and soon left to take up jobs in industry. They had written software in Fortran to control the apparatus and to do the data evaluation on a PDP-11/23. It was decided around that time that the PDP was to be retired and replaced by a VMEbus system. That system came with a C compiler, but the elder students told us -- before they left -- that C was an awful language and that programs written in it were hard to read. They advised us to continue programming in Fortran when porting the software to the new system.
Sure enough, as they had left, we were happy to do all the programming in C rather than Fortran. And although I had taken a course in Fortran before and was about equally familiar with Fortran and C at the time, I did not find the Fortran programs easy to read at all because of the heavy use they had made of common blocks (named groups of global variables). Although I missed in C some of the features that Fortran provided and which Ada now gives me back (such as runtime boundary checks, compiler generated error messages which pinpoint the line of source code where something went wrong at run time, or the ability to declare variable sized arrays without the clumsy use of malloc), I was convinced that C was the better choice for the project.
The moral of that experience to me was that I did not want to become like those older students. Although not in fear of going extinct, I decided to keep an open mind towards other programming languages. Whenever I hear someone else, especially younger people, talk about a programming language that they really like, I have a look at it to see what its value may be. The list of languages I came across that way includes C++, Java, Haskell, and Python. I vaguely remember also flipping through the pages of a book on Ada at a local book store some 10 years back, but it did not catch me at the time.
First Contact With Ada
A friend of mine works for the automotive industry and told me a while back that for safety reasons they were only allowed to use MISRA-C in a certain project. The MISRA standard defines a language subset of C through a long list of rules that forbid the use of dangerous C features.
Because I work in IT security consulting and have seen source code in a wide range of quality during software reviews, it was interesting to see what code practices are used in safety critical systems. When something goes wrong with the security products that we evaluate at work, the damage is usually not catastrophic. If a design or implementation error goes unnoticed, someone might loot a bank account, steal a car, or watch Pay TV without paying. This is really minor damage compared to the loss of lives that could result from a failure of a safety critical system. Although defending against a smart attacker requires different techniques than preventing accidents, the IT security community can certainly learn from the practices used in safety critical systems design.
It was while searching the web for keywords like "software" and "safety" that I fully became aware of Ada. Its mentioning was ubiquitous in the safety community. There were reports, for example, that a large airplane manufacturer only allows Ada in the development of critical software components for its aircrafts. There was also an analysis of the crash of the Ariane 5 501 rocket during its virgin flight, and a piece of Ada source code from the control system was shown. Ada was not to be blamed for the collective failure of developers and management, and to me this was just another example that Ada is used in high-profile applications. There was also a comparison with MISRA-C which concluded that 80 percent of the MISRA rules are not applicable to Ada because the language does not allow to do the many dangerous things that C does. One report stated that while porting an application from Java to Ada, a design error was discovered because of the strong emphasis that Ada puts on variable types.
Ada was favored so unanimously in the safety community that there had to be more to it than just someone being too lazy to learn another language. So I decided to have a closer look at Ada, and I really was surprised.
I had not expected to find in Ada all the features of a modern programming language. For example, the concepts of object-oriented languages like data abstraction, information hiding, inheritance, and overloading of functions and operators are all there, plus useful features like named arguments. I had thought that most of these had been inventions of newer languages. That any discrete type can be used as an array index type, not just the predefined integer type, is a feature that sets Ada aside from most languages that I have seen so far. Array boundaries are inherent attributes of an array in Ada and thus passed along when an array is used as a function or procedure argument, helping the programmer in avoiding index overflows.
This list of features is certainly not complete, but I was so impressed by the strengths of Ada that I decided to seriously learn the language. Although it is not as quickly grasped as Python, for example, the concepts of Ada are clearly thought out, logical and more easily remembered than those of C++ or Java. The simplest solution to a problem is usually the least troublesome one to use, although it may not be the easiest one to find. This rule is often neglected in the design of IT systems, but my impression is that the designers of Ada thought twice before adopting any concept or language feature.
The Cipher Event
It was during the time I was learning Ada that I heard of the Cipher Event which was organized by the British National Museum of Computing to celebrate the rebuild of Colossus Mark 2 at Bletchley Park. The Colossus machines had been used during World War II by the codebreakers in Bletchley Park to decipher the telegraph messages between high-level command stations of Nazi Germany. The radio teletype traffic was encrypted with a Lorenz SZ42 cipher machine, codenamed "Tunny" by the British codebreakers. Colossus was an ingeniously constructed, highly specialized computing machine, which efficiently implemented statistical algorithms used to break the keys of intercepted transmissions. As one of the first computers, Colossus was far ahead of its time.
During the Cipher Event, texts encrypted with a real SZ42 were transmitted from the amateur radio station at the Heinz Nixdorf Museum in Paderborn, Germany, to a receiving station in Britain. Two teams would then compete in decrypting the messages, one using the reconstructed Colossus machine, and one using a PC program that emulates Colossus in software.
The announcement of the Cipher Event also invited radio amateurs around the world to receive the messages and try their hand at decrypting them. Being a radio amateur myself and dealing with cryptography as part of my work in IT security, this was an intriguing challenge to me. It is easy to produce a theoretical estimate that a modern computer could be faster than Colossus, but it was a real technical challenge to actually intercept the radio signals and to break the key of the messages in real time.
I figured that standard teletype modems and software would not be of much use, because the cipher stream contains non-printable characters (control characters of the Baudot code) which might not be recorded properly, and also because the historical tone frequencies were going to be used. In addition, any loss of a character in the received ciphertexts means that the following text is no longer in sync with the steps of the SZ42 cipher algorithm. Recording a wrong character from time to time does not prevent the code breaking, but loosing characters does. I figured that I would need a special reception software to analyze the audio data, with a robust method of clock recovery. To perform the subsequent cryptanalysis, I decided to also write my own software, based on detailed material on the SZ42 and its cryptographic weaknesses that is available on the Internet.
An important decision to make was which programming language to choose. I quickly ruled out Python because of the low performance of a scripting language. Anyways, I was taking part in a competition where speed mattered, so I wanted a compiled language.
The Cipher Event was still two months away, but I knew I would find time to seriously work on the project only during weekends. Thus the speed of code development was a factor that had to be considered. After about 16 years of intensive use of C, I felt proficient in that language, but had only studied Ada for about half a year during my spare time, writing humble programs like a Sudoku solver. On the other hand, I had the long-term goal of becoming more proficient in Ada, so I finally decided to use it in my code development for the Cipher Event, even if it might make reaching that short-term goal more difficult.
And I was again surprised by Ada: I had expected that I might be struggling with the features of a language that I did not know for long, but the programming in Ada turned out to be very enjoyable. Ada allowed me to concisely express the algorithms I wanted to implement. Computing the Fourier amplitudes of the frequencies of interest, convoluting the demodulated signal with the symbol patterns of the Baudot alphabet, and extracting the teleprinter symbol stream with clock recovery based on a phase-locked loop were all easily implemented in Ada. Representing the SZ42 in software by declaring data types for the wheels and putting them together to a data type for the entire machine felt a bit like building a real machine piece by piece. While implementing the cryptographic attacks on the SZ42, I could concentrate on the design of the algorithms, while their representation in Ada was straightforward.
On November 15, 2007 I took my laptop to the nearby radio shack of the amateur radio club of Bonn. Being initially hampered by poor radio propagation and noise, I could finally record and decrypt several of the transmitted Cipher Challenges. Running on a 1.4 GHz CPU, the Ada program that does the code breaking found the correct settings of all 12 key wheels of the SZ42 within 46 seconds. This was way faster than Colossus, which completed the same task within about three and a half hours. Colossus reads the ciphertext input from a punched paper tape looping at a speed of 5000 characters per second. On my computer, I measured the equivalent speed to be about 1.2 million characters per second, which is 240 times faster. When scaling the CPU frequency by this factor, Colossus is equivalent to a 5.8-MHz computer. Measured by Moore's law, this is an enormous speed for a machine built more than six decades ago.
After my successful decryption of the messages, I felt very honored by received congratulations form Bletchley Park and by being invited to receive a prize for winning the challenge. The trip was in January 2008 and seeing Colossus at work was much more exciting than watching my laptop.
Conclusion
Being a bit discouraged by Planck's observation, I am not writing this to convince management people of the strengths of Ada. For a long time, the language was only accessible to a more or less closed group of programmers due to the lack of a free compiler. This and not any shortcomings of the language itself must be the reason why Ada has found only limited use in the past. Thanks to the GPL version of the GNAT compiler that AdaCore contributed to the GNU Compiler Collection (GCC), there is now an Ada compiler available that software enthusiasts can use free of charge. This lets students to try out the language, and it lets universities offer programming courses based on Ada. Computer geeks who can afford learning a language simply because it is cool have now access to an Ada compiler. My hope is that some day they will grow into positions in IT industry and bring Ada into the widespread use that the language deserves, without having to convince anybody.
