LAST summer, Tony Sale flicked the switch on a parallel processing machine that in terms of speed can put the latest PCs in the shade. So what? PCs are built on the idea of processing one instruction at a time, so a machine that carries out many instructions at once is bound to have the edge. What is surprising, however, is that Sale’s machine is built from a design drawn up in the early 1940s. It is a replica of the first electronic computer ever built.
Cracking codes
Colossus, as the machine was called, played a decisive part in cracking the codes used by Hitler’s high command during the Second World War. It was conceived at Bletchley Park, a stately home about 70 kilometres north of London which served as the centre for Britain’s codebreaking activities. Now, you might think that such a pioneering machine would have a high profile: an object to be lauded for its innovatory technology and historical significance. But no.
When the war ended, the code-breakers’ equipment was either spirited away by the security services or destroyed on the orders of Prime Minister Winston Churchill. Even the blueprints were burnt. The Russians were the new enemy and Churchill wanted to make sure that they did not find out how the British broke codes. So the details of Colossus have stayed a well-guarded secret for more than fifty years. Only since last year, following publication of secret documents in the US, has Sale-a former member of MI5-been allowed to put a rebuilt version of the machine on display. And only since then has the full importance of Colossus emerged.
Advertisement
At the height of the war, Bletchley Park housed 8000 people working round the clock to decode German military messages. It was home not only to technical experts, but also to some of Britain’s best mathematicians. They all worked on discrete tasks-engineers made precision wheels, electricians connected wires and clerks processed 2 million punch cards a week. Only a handful knew they were building and using the first computers.
Across the North Sea, the Germans used two coding systems to keep their radio messages secret. They routed everyday military messages, such as orders to submarines, through the famous Enigma machines. But Hitler and his high command shared vital strategic information using a device made by the electronics company Lorenz. At the outset of war, the Allies knew how Enigma worked but still had to develop ways to crack the codes it relied on. But with the Lorenz machine, things were worse: they didn’t even know what it looked like.
In fact, the Lorenz Schlüssel-zusatz 40, or Tunny as the British called it, resembled an old mechanical cash register which plugged into a teleprinter. An operator typed a message on a keyboard which used the standard international teleprinter code, or Baudot code, to convert each character into a 5-bit “word” made of marks (x) and spaces (•) equivalent to binary 1s and 0s. The teleprinter blurted out each character as a short string of electrical pulses. But before transmitting a character, Tunny first transformed it into another-apparently at random-so the final message came out as nonsense.
To do this, the machine separated each digital word into its five bits, and modified them with signals generated by two sets of five coding wheels (see Diagram below). These wheels were driven by central shafts and had teeth round their edges that could be left up or folded down. Each wheel changed • into x and vice versa, or left them unchanged, depending on the state of the tooth at that position. In effect, the coding wheels disguised the original character by adding to it two, 5-bit characters (see “Binary magic”).
This simple setup was made more complicated to confuse eavesdroppers. First, two motor wheels turned the second set of five coding wheels intermittently. Secondly, the Germans changed the state of the teeth-known as the wheel patterns-at regular intervals. Finally, before every message, the sending operator turned each wheel to a new “start setting” and transmitted it to the receiver. Once the receiving machine was set up with the correct wheel patterns and start settings, it produced the same sequence of obscuring characters as the transmitting machine. And since in binary maths, addition is the same as subtraction, simply adding these obscuring characters to the incoming nonsense characters regenerated the original message.
All this was hidden from the Bletchley code-breakers. Then, on 30 August 1941, a German radio operator made a mistake that had a profound impact on the course of the war. The operator sent a 4000 character message, after which the receiving station replied “didn’t get that, please resend”. So the operator did. But, he or she used the same start settings, which was strictly forbidden because the machine then generated the same stream of obscuring characters.
Fortunately for the Allies, German messages always began with the word Spruchnummer or “message number”, and the operator abbreviated it on the second run to Spruchnr. The Bletchley cryptanalyst John Tiltman found that when he added the two messages, the obscuring characters cancelled out to leave the binary sum of two virtually identical plain text messages displaced by three characters (the difference between Spruchnummer and Spruchnr.). By guessing text and working back and forth between the two messages, Tiltman deciphered both.
Four month’s toil
Now, however, as the secrecy surrounding Colossus disperses, it is clear that this incident carried a much more important message. Bletchley had a string of 4000 obscuring characters with which to try to learn something about Tunny. This task fell to Bill Tutte, a young mathematician from the University of Cambridge. He separated every character into its five bits and began writing out the first bit of every character on tables with differing numbers of columns. When he reached 41 columns, a repeating pattern began to emerge. For the other four bit streams, other important numbers emerged: 31, 29, 26 and 23.
After four months’ toil, Tutte had deduced the entire design of the machine. It was the “greatest intellectual feat of the whole war”, says Sale. “And only six people outside the Lorenz codebreaking team ever understood the significance.”
The five numbers that Tutte found turned out to be the number of teeth on the first set of coding wheels, which he called the K wheels. The fact that the pattern emerged at all arose from an unexpected feature of Tunny. While the K wheels clicked round one tooth every time a character passed through, the second set of wheels did not. These five “S” wheels moved round at irregular intervals, depending on the positions of the teeth of the two motor, or M, wheels.
This arrangement made “sound cryptographic sense”, says Sale, because it produced a long string of obscuring characters with no repeating patterns. But for about a third of every message, the S wheels were static, giving Tutte a window through which he could “see” the K wheels in action.
For all its brilliance, Tutte’s feat did little to speed up intelligence gathering. It still took the code-breakers two months to find the correct combination of start settings to decode a message. The mathematician Max Newman conceived an approach to automate this task, and Colossus was the answer. It was built in 1943 at the Post Office Research Station at Dollis Hill, near London, under the direction of electronic engineer Tommy Flowers.
Understanding Colossus is easiest with some simple maths. An encrypted message Z is made by adding streams of the obscuring characters K and S, from the two sets of coding wheels, to the plain text P. In other words: Z = P + K + S. In binary mathematics this translates to Z + K = P + S. Colossus completed the left side of this equation. It allowed the code-breakers to regenerate the K stream which, when added to the encrypted message, left plain text masked only by the S stream. This could be cracked by more conventional techniques.
Colossus included five banks of thyratron valves each of which mimicked a K wheel. The thyratrons in a bank fired one after another to create a stream of pulses equivalent to xs. The output from each thyratron could be blocked, to create a • simply by inserting a plug in a plug board. So the plugs played the same role as the teeth on Tunny’s K wheels.
Once the teeth settings, or wheel patterns, were known, Colossus could produce a K stream of obscuring characters identical to the one the Germans sent. The remaining problem then was to discover the relative positions of the K stream and the characters in the encrypted message-in other words, to find the machine’s start settings.
Searching for zeros
This was Colossus’s main task, and the solution lay in two mathematical findings. Astonishingly, analysis of Lorenz messages revealed that they contained a higher number of pairs of repeated characters than would be expected by chance. Secondly, in binary mathematics, adding 1 and 1 or 0 and 0 produces 0. The Baudot version of this is that when a character is added to itself, the sum is •••••. The code-breakers saw that if they took two copies of the same message, shifted one version to the right by a single character, and added the copies together, they would see ••••• every time a pair of repeated characters appeared. This technique became known as the delta method, and the sum simply as the delta (
).
Here, the code-breakers indulged in some logical wizardry. They added the delta of an entire message (Z) to the delta of the K stream (K) to obtain another stream of characters Z + K. With any old obscuring characters, this sum added up to ••••• as often as would be expected by chance. But the code-breakers found that when they used the correct sequence of obscuring characters, the frequency with which ••••• appeared increased slightly. Identifying this peak, they reasoned, would give them the start settings for the K wheels.
The processing power needed to handle all five bit streams at once, however, would have been monumental. So Flowers designed Colossus to do the job two wheels at a time. For the first two K wheels, K1 and K2, Colossus worked with just the first two bitstreams from a message (Z1 and Z2), doing the sum K1 + K2 + Z1 + Z2 , and counting the number of times the answer was •.
Colossus ran through this procedure hundreds of times for every message, starting the process each time on different valves in its thyratron equivalents of the K1 and K2 wheels. This way, it tested every start setting for the two wheels. The run that produced the highest number of •s gave the correct start settings for K1 and K2. With these settings in the bag, Colossus was let loose on the other K wheels.
The technology that performed all this was exceptional. Colossus had thyratron banks equivalent to all 12 of Tunny’s wheels. Mark I, which began work in January 1944, contained 1500 valves. Mark II, which started work on 1 June 1944, contained 2500. For the time, this was a huge number. It read incoming messages from a continuous loop of punched tape which spooled 48 kilometres an hour past a light source and bank of photoelectric cells to convert the characters into electronic pulses. It handled 5000 characters per second.
The machine added bits together in specialised valves called pentodes. But the real innovation was the memory. In order to calculate deltas, Colossus had to “remember” a bit for a split second until its neighbour arrived. For this task, it used a bank of capacitors which it charged up and discharged as needed.
Clerks used the start settings found by Colossus to set up Bletchley’s own version of a Tunny machine. This stripped the K stream out of an encryted message and turned out plain text masked by the S stream. But, of course, the S wheels didn’t click round with every character. In fact, about a third of any message produced by Tunny was plain text, says Frank Carter, a retired mathematician who is working with Sale. “This was scattered about,” he says. “But there may have been little groups of text that could be read.”
At this point, conventional decryption techniques using “cribs” came into play. Cribs are characters, words or chunks of text that the Allies could pinpoint in a message. Fortunately for the Allies, the German messages had very rigid structures-Spruchnummer, for example, had triggered the whole Colossus saga. Likewise, the Germans used abbreviations to describe weather conditions. If the weather was known, then the appropriate abbreviation would appear in a known position within an encrypted message. The British even provoked the Germans into giving away cribs by dropping mines at precise longitude and latitude at sea. The German Navy would then transmit a message containing the known grid references.
Using such methods, the code-breakers divined the start settings for the M and S wheels. This process was “more art than science”, says Carter, “requiring high levels of logical skill and an extremely good knowledge of German”. So finally, the clerks set up their Tunny with the K, M and S start settings and, with luck, it typed out fluent German.
Sometimes, Colossus searched a message for an excess of repeated characters in vain. Statistical noise simply obliterated any increase in •s that existed. In this case, the machine could be plugged up to run one of several dozen other algorithms. So, although Colossus could not “store” a program in its memory, it was programmable-albeit only for special purposes. “It exploited the germ of the idea of programming,” says Donald Michie, emeritus professor of machine intelligence at the University of Edinburgh. “There’s no doubt that it was the first high-speed electronic computer.”
It was Michie, with help from the statistician Jack Good, who showed in 1943 how Colossus could be reprogrammed to perform the most difficult task facing the code-breakers. This was to identify the wheel patterns: the order of obscuring characters generated by each wheel.
The method stemmed once again from the sum K1 + K2 + Z 1 + Z2. For Lorenz traffic, remember, this sum is more likely than not to equal • (or 0). Another, ingenious way to express this is that the odds are in favour of Z1 + Z2being equal to K1 + K2. The code-breakers used this relationship to guess the orders of •s and xs in K1 and K2 from an encrypted message. The next step, automated by Michie’s method, was to use a long iterative process to firm up those guesses. Once you had K1 and K2, It was a “trivial task” to work out the order of obscuring bits produced by the K1 and K2 wheels, says Michie.
Colossus’s algorithms have been declassified only in recent years, with the wheel pattern algorithms last on the list-the British security services have stopped using these only in the past five years. This is why so much has been kept secret. “It was not the technology of the computers used to break the codes that worried the government,” says Sale. “It was the algorithms.”
Colossus turned out to be a potent weapon. It gave the Allies extraordinary insight into the thinking of the German top brass from Hitler to Kesselring and Rommel. Colossus became operational just before the D-Day landings and confirmed that the Allies’ diversionary tactics were working. By 1945, Britain kept 10 Colossus machines busy, decrypting 1200 messages a month.
If the story of Colossus is extraordinary, so too is Sale’s. After leaving MI5 in 1968, he set up his own electronics company and helped the British Science Museum to rebuild an early valve computer and the Babbage Engine, the mechanical calculating machine designed by Charles Babbage. While doing this, he became fascinated by the Bletchley computers and decided to try to rebuild Colossus. Sale’s goal is to stop the achievements made at Bletchley from being forgotten. After all, the American computer industry makes great boasts about its first electronic computer ENIAC, which calculated shell trajectories. But it wasn’t completed until 1946.
But where should Sale start. After Churchill’s blitz on Bletchley, all that remained of Colossus was eight photos and a few circuit diagrams kept illegally by Bletchley staff. Eventually, he scared up enough information to get started, by talking to “wrinklies”-the surviving pioneers from Bletchley. But another hurdle loomed. Security chiefs at the Government Communications Headquarters (GCHQ) in Cheltenham were reluctant to allow Sale to proceed.
It took until November 1993 before they relented. But even then, GCHQ told Sale that he could build only the short-lived mark I Colossus, which had no memory. He was forbidden to connect any wires. But, with his own money, contributions from a few Bletchley pioneers and the British electronics firm Quantel, Sale quietly began to rebuild Mark II, complete with memory, and got part of the machine running.
Now fate took a hand. In March 1996, the US National Security Agency declassified a bundle of 5000 documents on Bletchley and handed it to the National Archives and Records Administration library in Washington DC. The papers, it turned out, contained reports of Colossus which had ended up at the NSA because US Army personnel had worked at Bletchley and sent home chapter and verse on the British effort. Publication of all this information freed Sale to put his rebuilt Colossus on display. It is now on show at Bletchley Park.
And Sale does not intend to stop there. If he can find the money, he wants to rebuild the Bombe, the machine that mathematicians Alan Turing and Gordon Welchman designed to crack the Enigma codes. “The Bombe was a dedicated parallel processor of immense power,” says Sale. But again, few details survived.
Light years
Just before Christmas, Sale visited the US National Archives library and uncovered a file named the “British bomb”. It turned out to be a complete description of the Bombe, with 50 photographs of the original machine. “We jumped a light year,” says Sale. “We are already showing the photos to the wrinklies . . . it is triggering all manner of lost memories.”
Sale believes that the work done fifty years ago also has an important message for today’s computer industry. Dedicated processors such as Colossus and the Bombe perform their tasks very efficiently. PCs, which act as general platforms for many tasks, cannot compete. To prove his point, Sale has written programs for a Pentium PC that emulate Colossus and the Bombe. The Pentium takes twice as long as Colossus to come up with start settings for Tunny, and what took the Bombe 15 minutes in 1943 still takes the PC 18 hours.
“The world has gone for the general platform approach,” says Sale. “It rules the world. But not always for the best.”
* * *
Binary magic
THE Baudot code was an early digital code that converted every character on the teleprinter keyboard into a 5-bit digital word. For example:
When an operator typed a character, the Lorenz machine encrypted it by adding two obscuring characters. The first of these came from what became known as the K wheels, the second from the S wheels.
The rules of addition are simple.
One of the curious properties of these rules is that any character added to itself always gives the same answer:
This fact became the key to Bletchley’s success. The code-breakers devised the delta method, in which they added an entire message to itself, but with one version displaced a single character to the right.
This method revealed the presence of any repeated characters by producing a “/”-in other words, five •s (or five 0s).
- Further reading: Codebreakers edited by Harry Hinsley and Alan Stripp, OUP.
- More about Bletchley Park and Collossus is available at http://www.cranfield.ac.uk/ccc/BPark/