Key Points:
- Max Newman designed a machine called Heath Robinson after the cartoonist designer of fantastic machines, which decrypted secret messages.
- Flowers was an engineer who designed and built Colossus to meet Max Newman’s requirements for a machine to speed up the breaking of the Lorenz cipher.
- Colossus was able to reduce the time to break Lorenz messages from weeks to hours, just in time to decipher messages which gave vital information to Eisenhower and Montgomery prior to D-Day.
Colossus computer of Max Newman and Tommy Flowers
WWII hindered the progress of computer inventors like Atanasoff and Zuse but had the opposite effect on the first British steps toward the creation of electronic computers. During the war, the Department of Communications of the British Foreign Office created machines that used electronic circuits to assist the British in decoding intercepted German radio messages, coded with special machines. The English electronic computers were created by a group of people, with the leading role of the famous English mathematician Maxwell Newman and the engineer Thomas Flowers. Many others played important roles, including Alan Turing and C. E. Wynn-Williams.
Bletchley Park pictured above
The interception and decoding of German messages was a significant factor in the Allied victory, a fact kept secret until recently. The work was carried out in great secrecy at Government Code and Cipher School in Bletchley Park, GC&CS, a Victorian estate, situated some 80 km north of London. According to the historian Harry Hinsley, the work of crypto analysts in GC&CS was of great importance for the Allied victory and shortened the wartime by some two years.
An Enigma cipher machine
The German army started using Enigma cipher machines for the coding of military messages in 1925. Contrary to the beliefs of the Germans, the Enigma machine was not secure. In 1928, the Poles acquired the knowledge about the German military Enigma by intercepting one, in customs, being sent to the German Embassy in Warsaw, and examined it. A whole series of Enigma machines was produced at the factory in Warsaw. A group of brilliant mathematics students at Poznan University (Rejewski, Rozycki and Zygalski) was recruited to work in the cryptological section of the Polish General Staff. In 1932, they decrypted the German Enigma signals. To facilitate decryption Rejewski designed an electromechanical programmable machine which he called Bomba (Polish for bomb), because of the bomb-like ticking noise it made. In July 1939, the Poles gave the French and the British replicas of Polish-made Enigmas together with the drawings and information on the Enigma, Bomba, and the decryption information. Two mathematicians working at GC&CS, Alan Turing and Gordon Welchman, developed an improved version of the Bomb machine and over 200 of the Bombes were built by the British Tabulating Machine Company.
The British were very enthusiastic about the possibility of decoding all the German military correspondence by means of the Bombs, but suddenly at the beginning of 1940, the interceptors started to catch German messages, coded with different machines, which were impossible to decode. What happened?
A vintage cipher machine
At the end of 1930s the German Army High Command asked the company C. Lorenz AG to produce for them a high-security teleprinter cipher machine to enable them to communicate by radio in complete secrecy. The Lorenz AG designed the SZ40 and SZ42 cipher machines, based on the additive method for enciphering teleprinter messages invented in 1918 by the Gilbert S. Vernam, of Brooklyn, New York (see the patent of Vernam). Since the 1940 the Enigma machine was generally used by field units, the Lorenz machine was used for high-level communications (including Hitler’s orders) which could support the heavy machine, teletypewriter and attendant fixed circuits. The Vernam system enciphered the message text by adding to it, character by character, a set of obscuring characters thus producing the enciphered text which was transmitted to the intended recipient. The simplicity of Vernam’s system was that if the obscuring characters were added in a rather special way (known as modulo 2 addition), then exactly the same obscuring characters added in the same way to the received enciphered message, cancelled out the obscuring characters and retrieved the original message. Vernam proposed that the obscuring characters should be completely random and pre-punched onto paper tape to be consumed character by character in synchronism with the input message characters. Such a cipher system using purely random obscuring characters is unbreakable.
The difficulty was, in a hot war situation, to make sure that the same random character tapes were available at each end of a communications link and that they were both set to the same start position. The Lorenz Company decided that it would be operationally easier to construct a machine to generate the obscuring character sequence. Because it was a machine, it could not generate a completely random sequence of characters. It generates what is known as a pseudo random sequence. Unfortunately for the German Army it was more pseudo than random and that was how it was broken. The amazing thing about SZ machines (in contrast with the Polish codebreakers’ success with the Enigma machine) is that the code breakers in GC&CS never saw an actual SZ machine until right at the end of the war, but they had been breaking the Lorenz cipher for two and a half years.
John Tiltman was one of the top code breakers in Bletchley Park and he took a particular interest in these enciphered teleprinter messages. They were given the code name fish and the messages which, as was later found out, were enciphered using the Lorenz machine were known as tunny. Tiltman knew of the Vernam system and soon identified these messages as being enciphered in the Vernam manner. Because the Vernam system depended on addition of characters, Tiltman reasoned, if the operators had made a mistake and used the same Lorenz machine starts for two messages, then by adding the two cipher texts together character by character, the obscuring character sequence would disappear. And British got a bit of fat—in August 1941 two German operators made a horrendous mistake, sending the same message 2 times (something absolutely forbidden by instructions) and a smart British interceptor catch the both messages. Tiltman got the messages and for the first time succeeded to recover completely both texts. That was the break-through.
Then over the next two months the Research section in GC&CS worked out the complete logical structure of the cipher machine. In the beginning of 1942 the Post Office Research Labs at Dollis Hill were asked to produce an implementation of the logic worked out by code breakers. Frank Morrell produced a rack of uniselectors and relays, which emulated the logic. It was called Tunny. So now when the manual code breakers in the Testery had laboriously worked out the settings used for a particular message, these settings could be plugged up on Tunny and the cipher text read in. If the code breakers had got it right, out came German. But it was taking four to six weeks to work out the settings. This meant that although they had proved that technically they could break Tunny, by the time the messages were decoded the information in them was too stale to be operationally useful. The codebreakers deadly needed a faster machine.
The famous English mathematician Max Newman now came on the scene. He thought that it would be possible to automate some parts of finding the settings used for each message, using electronic devices. He created a specification of a machine, which was built by the engineers at the Dollis Hill. The logic was built by means of relays, but the counters are electronic, by design of Charles Eryl Wynn-Williams (T. Flowers was also involved). The machine was called Heath Robinson after the cartoonist designer of fantastic machines.
Heath Robinson was delivered to GC&CS in June 1943. The machine compares two data flows, which are entered by means of two tape readers. The first tape contains the intercepted message, and the second, the probable decrypted message. Comparing continuously the two tapes and shifting the letters sooner or later will decode the message, and the result will be printed on a typewriter. Heath Robinson presented some problems, however. The optical tape readers gave errors if a long stretch of adjacent holes or no holes occurred on the tapes. The major problem was keeping the two tapes in synchronism at over 1000 characters per second. Even a slight misalignment would render the whole process worthless. Heath Robinson however worked well enough to show that Max Newman’s concept was correct.
Newman then went to Dollis Hill, where he was put in touch with Thomas Flowers. Flowers was the brilliant Post Office electronics engineer who designed and built Colossus to meet Max Newman’s requirements for a machine to speed up the breaking of the Lorenz cipher. He had already given some advices in building of Heath Robinson. Flower’s major contribution was to propose that the wheel patterns be generated electronically in ring circuits thus doing away with one paper tape and completely eliminating the synchronization problem. This required a vast number of electronic valves, but he was confident it could be made to work. He had, before the war, designed Post Office repeaters using valves. He knew that valves were reliable provided that they were never switched on and off. Nobody else believed him! Later Flowers will say: “My suggestion, made in February 1943, was met with considerable skepticism. The first reaction was that a machine with the number of tubes that was obviously going to be needed would be too unreliable to be useful. Fortunately, this criticism was defeated by the experience of the Post Office using thousands of tubes in its communication network. These tubes were not subject to movement or handling, and the power was never switched off. Under these conditions, tube failures were very rare.”
Colossus (called later Colossus Mark I) design started in March 1943. By December 1943 all the various circuits were working and the Colossus was dismantled shipped up to GC&CS and assembled. Colossus used state-of-the-art vacuum tubes (thermionic valves), thyratrons and photomultipliers to optically read a paper tape and then applied a programmable logical function to every character, counting how often this function returned “true”. The computer (see the upper photo) was operational in January 1944 and successful on its first test against a real enciphered message tape. Colossus was able to read up to 5000 characters per second (cps), with the tape moving through it at about 50 km an hour, and reduced the time to break Lorenz messages from weeks to hours and just in time for messages to be deciphered which gave vital information to Eisenhower and Montgomery prior to D Day. These deciphered Lorenz messages showed that Hitler had swallowed the deception campaigns, the phantom army in the South of England, the phantom convoys moving east along the channel, that Hitler was convinced that the attacks were coming across the Pas de Calais and that he was keeping Panzer divisions in Belgium. After D-Day the French resistance and the British and American Air Forces bombed and strafed all the telephone and teleprinter landlines in Northern France, forcing the Germans to use radio communications and suddenly the volume of intercepted messages went up enormously.
In June 1944 was developed an improved version of Colossus Mark I, called Mark II, and eight more machines were quickly built to handle the increase in messages. The Mark I was upgraded to a Mark II, and there were thus ten Mark II Colossi in the GC&CS by the end of the war. By the end of hostilities 63 million characters of high grade German messages had been decrypted. Mark II contained 2500 valves and 800 relays and was capable to read up to 25000 cps (five times faster that Mark I), due the combination of a parallel processing and buffer memory (registers), and contains a circuit for automatically changing the program when a probable code pattern was discovered.
Each of the ten Colossi occupied a large room in Bletchley Park. The racks were 2.3 m high of varying widths. There were eight racks arranged in two bays about 5.5 m long plus the paper tape reader and tape handler. The input of data was cipher text, punched onto 5-hole paper tape and read at 5000 cps. The output was buffered onto relays, and printed on a typewriter. The processor had a memory of 5 characters of 5 bits, held in a shift register, pluggable logic gates, and 20-decade counters arranged as 5 by 4 decades. The clock speed was 5 KHz, derived from sprocket holes in the input tape. Programming of the Colossus’ cross-correlation algorithm was achieved by a combination of telephone jack plugs, cords and switches.
After Victory Day, suddenly it was all over. Eight of the ten Colossi were dismantled in Bletchley Park. Two went to London and were dismantled in about 1960 and in the same year all the drawings of Colossus were burnt, and of course, its very existence was kept secret. In the 1970s information began to emerge about Colossus. Professor Brian Randell of Newcastle University started researching the machine. Dr. Flowers and some of the other design engineers wrote papers in the 1980s describing Colossus in fairly general terms.
Colossus was the first of the electronic digital machines with programmability, albeit limited in modern terms. It was not, however, a fully general Turing-complete computer, even though Alan Turing worked at Bletchley Park, nor a stored program computer. It was not then realized that Turing completeness was significant; most of the other pioneering modern computing machines were also not Turing complete (e.g. the Atanasoff Berry Computer, the Harvard Mark I electro-mechanical relay machine, the Bell Labs relay machines (by George Stibitz et al), or the first designs of Konrad Zuse). The notion of a computer as a general-purpose machine, that is, as more than a calculator devoted to solving difficult but specific problems, would not become prominent for several years.
Because of his parallel nature, Colossus is very fast, even by today’s standards. The intercepted message punched onto ordinary typewriter paper tape is read at 5000 characters per second. The sprocket holes down the middle of the tape are read to form the clock for the whole machine. This avoids any synchronization problems, whatever the speed of the tape, that’s the speed of Colossus. Tommy Flowers once wound up the paper tape drive motor to see what happened. At 9600 characters per second the tape burst and flew all over the room at about 100 kmh! It was decided that 5000 cps was a safe speed. At 5000 cps the interval between sprocket holes is 200 microseconds. In this time Colossus will do up to 100 Boolean calculations simultaneously on each of the five tape channels and across a five character matrix. The gate delay time is 1.2 microseconds which is quite remarkable for very ordinary valves. It demonstrates the design skills of Tommy Flowers.
In 1994, a team led by Tony Sale began a reconstruction of a Colossus at Bletchley Park. When the machine (see the upper image) was ready, in November 2007, to celebrate the project completion and to mark the start of a fundraising initiative for the National Museum of Computing, a contest was organized—the rebuilt Colossus against radio amateurs worldwide in being first to receive and decode 3 messages enciphered using the Lorenz SZ42 and transmitted from radio station DL0HNF in the Heinz Nixdorf MuseumsForum computer museum. The challenge was easily won by radio amateur Joachim Sch??th who had carefully prepared for the event and developed his own signal processing and decrypt code using the computer language Ada. The Colossus team was hampered by their wish to use World War II radio equipment, delaying them by a day because of poor reception conditions. Nevertheless, the victor’s 1.4 GHz laptop, running his own code, took less than a minute to find the settings for all 12 wheels. The German code breaker said: ???My laptop digested ciphertext at a speed of 1.2 million characters per second—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. That is a remarkable speed for a computer built in 1944.”
The image featured at the top of this post is ©"Bletchley Park - Block B - The Bletchley Park Story - Enigma machines - Enigma" by ell brown is licensed under BY 2.0..