In January 1942 the research section managed to reverse-engineer the Tunny machine on the basis of a single repeated message approximately 4,000 characters in length. William Tutte made the crucial break, deducing the structure and function of two of the machine’s various internal wheels. At this stage the rest of the research section joined in and soon the whole machine was laid bare, without any of them ever having set eyes on one. It was, to say the least, a remarkable feat. The problem now that they knew the workings of the machine was how to read the message traffic. The difficulty was the wheel settings. Each message had its own wheel settings – its own ‘combination’, chosen by the German operator before enciphering the message – and could not be read until its combination was known.
In November 1942 Tutte invented a way of discovering wheel settings known as the ‘Statistical Method’. The rub was that the method seemed impractical, involving a very large amount of time-consuming work. This was the sort of work that, given enough time, a human computer could carry out – basically, the comparing of two streams of dots and crosses, counting the number of times that each had a dot in the same position. However, given the amount of comparing and counting that the method required, the intelligence in the message would be stale before the work was finished. Tutte explained his method to Newman, who suggested using electronic counters. It was a brilliant idea. In December 1942 Newman was given the job of developing the necessary machinery.
Electronic counters involving small numbers of valves had been in use in Cambridge before the war, in the Cavendish Laboratory, for counting sub-atomic particles. These had been designed by C. E. Wynn-Williams, a Cambridge don, but now involved in research at the Telecommunications Research Establishment (TRE) in Malvern. Newman worked out the cryptanalytical requirements for the planned machine and called in Wynn-Williams to design the electronic counters. Newman also approached Francis Morell, head of the telegraph and teleprinter group at Dollis Hill, to engineer the rest of the machine. (Morell’s group was located in the same building as Flowers’ switching group.) Turing himself appears to have had no direct involvement in Newman’s project, although Newman has remarked in this connection that Turing ‘was always full of ideas and he liked to talk about other people’s problems’.
Construction started in January 1943, and the machine began operating in June of that year, in Newman’s new machine-section, the Newmanry. The Newmanry consisted initially of Newman himself, Michie, two engineers, and 16 Wrens. The section was housed in Hut 11, originally the first bombe room. The machine was soon named ‘Heath Robinson’ by the Wrens. Smoke rose from it the first time it was switched on (a large resistor overloaded). Part of Heath Robinson consisted of a huge angle-iron metal frame resembling an old-fashioned bedstead standing on end; this became known as the ‘bedstead’. Around the bedstead wound two long loops of teleprinter tape. Each loop was made by gluing together the two ends of a single length of tape. The two tapes were supported by a system of pulleys and wooden (later aluminium) wheels of diameter about ten inches. The tapes were driven by sprocket-wheels which engaged a continuous row of sprocket-holes along the centre of each tape. Both tapes were driven by the same drive-shaft so that they moved in synchronization with each other. The maximum speed of the tapes was 2,000 characters per second.
Each tape had rows of holes punched across its width. Every row was a letter, or other keyboard character, represented in international teleprinter code. In order to describe these patterns on the tape, as well as the pulsed patterns that made up the enciphered transmissions themselves, Bletchley used ‘×’ to mark the position of a hole (or pulse) and ‘•’ to mark the absence of a hole (or no pulse). The hole/no-hole patterns on the tape were read photo-electrically. Once these patterns had been converted by the photo-electric reader into electrical pulses, they were modified and combined in a specified way by a ‘combining unit’ (a logic unit, in modern terminology). The resulting number of pulses was counted by Wynn-Williams’ counting unit. The combining could be varied by means of replugging cables. Dollis Hill made the combining unit and the bedstead, and TRE the counting unit. In all Heath Robinson contained about two dozen valves.
The central idea of Tutte’s Statistical Method is as follows. Tunny encrypts each letter of the plain-text by adding another letter to it. The internal mechanism of the Tunny machine produces its own stream of letters, known at Bletchley as the ‘key-stream’, or simply key. Each letter of the cipher-text is produced by adding a letter from the key-stream to the corresponding letter of the plain-text. Tunny produces its key-stream by adding together two other letter streams which it generates, called the psi-stream and the chi-stream at Bletchley (from the Greek letters Psi and Chi). The psi-stream is produced by a mechanism consisting of five ‘psi-wheels’ and the chi-stream by a mechanism consisting of five ‘chi-wheels’. For example, if the first letter from the chi-wheel mechanism is M (••××× in teleprinter code) and the first letter from the psi-wheel mechanism is N (••×ו), then the first letter of the key-stream is M + N, which under the rules of Tunny letter-addition is T (••••×). (Tunny adds letters by adding the individual dots and crosses that compose them.) Finally, supposing that the first letter of the plaintext is e.g. R (•×•×•), the first letter of the cipher-text is R + T, or G (•×•××).
If, say, the plain-text is 4,000 characters long, then 4,000 consecutive characters from the chi-stream are used in the course of forming the cipher-text. These letters from the chi-stream will be referred to simply as ‘the chi’ of the message. Tutte’s method exploits a fatal weakness in the design of Tunny which renders the chi amenable to attack. The method depends on knowing the Tunny machine’s wheel-patterns – patterns of cams or ‘pins’ around the circumference of each wheel. The Research Section established what these patterns were in the course of reverse-engineering the machine, and although the Germans changed the patterns from time to time, Bletchley kept on top of the changes thanks to operator errors. What Tutte discovered was that after some massaging, the chi of the message is recognizable on the basis of the cipher text, provided that the wheel patterns are known. Once the message chi has been found it is an easy step to the settings of the chi-wheels, one part of the message’s ‘combination’.
What both Robinson and Colossus did, initially, was use Tutte’s Statistical Method to find the settings of the chi-wheels (other methods came later). Knowing the settings of the chi-wheels gave the codebreakers enough of a head-start that they were able to discover the settings of the psi-wheels by eye, given ‘a knowledge of “Tunny-German” and the power of instantaneous mental addition of letters of the Teleprint alphabet’. Once the settings of all the wheels were known, the codebreakers had the message’s ‘combination’. From there on it was left to clerks to decipher the complete message.
The crucial massaging required by Tutte’s method involves forming what is called the ‘delta’ of a character stream. The delta is the stream that results from adding together each pair of adjacent letters in the original stream. For example, the delta of the short stream MNT is produced by adding M to N and N to T. The last two columns of the following table contain the delta of the stream MNT. The rules for dot-and-cross addition are: dot plus dot is dot, cross plus cross is dot, dot plus cross is cross, cross plus dot is cross.
M N T M+N N+T
• • • • •
• • • • •
× × • • ×
× × • • ×
× • × × ×
The idea of the delta is that it tracks changes in the original stream. If a dot follows a dot or a cross follows a cross at a particular point in the original stream, then the corresponding point in the delta has a dot. A dot in the delta means ‘no change’. If, on the other hand, there is a cross followed by a dot or a dot followed by a cross in the original stream, then the corresponding point in the delta has a cross. A cross in the delta means ‘change’. (The whole idea was invented by Turing.)
Tutte’s all-important discovery was that the delta of a message’s cipher-text and the delta of the chi usually correspond somewhat: where the one has a dot, so does the other, more often than not.
Here, then, is Tutte’s method for finding the chi of a given cipher-text when the wheel-patterns are known. Suppose, for the sake of illustration, that the cipher-text is 10,000 characters long. First, form the delta of the cipher-text. Then, use the patterns of the chi-wheels to start generating chi-stream (as we may imagine, by hand with paper and pencil). It is the patterns of the cams around the circumferences of the chi-wheels that determine which letters the chi-mechanism produces, and if these patterns are known it is possible to calculate the entire chi-stream. Generate 10,000 successive characters of the chi-stream. Form their delta, and compare the result with the delta of the cipher-text, counting how many times the two have dots in the same places and how many times crosses in the same places. Add these two scores and record the total. It probably won’t be very good, since the chances are that at the start of the simulated generation of chi-stream, the positions of the chi-wheels were not the same as those used in producing the cipher-text. The five chi-wheels are like the moving parts of a combination lock, and it is only when they are set to the exact combination that the German operator used at the start of enciphering the message that they will produce the chi of the message. The goal of Tutte’s method is to find that combination. So now generate the next character in the chi-stream, and compare the delta of the 2nd to the 10,001st characters of the stream with the delta of the cipher-text. And so on. Since the motion of the chi-wheels is circular, eventually the complete chi-stream will have been examined. The stretch of chi-stream whose delta matches the delta of the cipher-text more closely than any of the other stretches do (and there may be no more than a 55–60 per cent correspondence) is probably the message chi.
Why do the delta of a message’s cipher-text and the delta of the message chi tend to correspond? At bottom, this is because of the all-or-nothing way in which the psi-wheels move – the great weakness of Tunny. The Tunny machine’s heart, its twelve wheels, stand side by side in a single row, like plates in a dish rack – the five psis, the two motor wheels and the five chis. The chi-wheels all move forward together one step every time a key is pressed at the keyboard, whereas the psi-wheels may all move forward one step when the key is pressed or may all stand still. Whether the psi-wheels move or not is determined by the motor wheels (or in some versions of the machine, by the motor wheels in conjunction with yet other complicating features). Whenever a stroke at the keyboard is not accompanied by a movement of the psi-wheels, what is added to the letter produced by the chi-wheels is whatever letter the psi-wheels produced on the last occasion when they did move. It follows that the delta of the letters contributed by the psi-wheels will contain a column consisting of five dots every time the psi-wheels stand still and ‘miss a turn’ (because in this case they contribute the same letter twice, so there is absolutely no change). These columns of dots in the psi’s delta produce the correspondence that Tutte discovered. If instead of the psi-wheels either all moving together or all standing still, the designer had arranged for them to move independently, then the delta of the cipher-text and the delta of the chi would not have tended to correspond and the chink that let Tutte in would not have existed.
Colossus generated the chi-stream electronically. The cipher-text was on a loop of tape on a bedstead. In the case of Heath Robinson, the complete chi-stream was punched on one of its tapes before the search commenced, the other tape carrying the cipher-text. The two tapes ran on the Robinson’s bedstead in such a way that the tape containing the cipher-text was progressively stepped through the chi-tape, one character at a time. In practice, the search would be simplified by punching onto the chi-tape only the dots and crosses produced by the first and second of the five chi-wheels, resulting in a much shorter tape. Tutte had shown that his method of counting correspondences worked in this case too (and for this reason it was sometimes called the ‘1+2 break in’). Once the settings of the first two chi-wheels had been found, the settings of the others would be chased by the same procedure.
Heath Robinson was effective, but there were problems. Tapes would stretch, causing them to go out of synchronization, would tear, and would come unglued. It was clear that one machine was not going to be anywhere near enough. Newman proposed to order a dozen more Robinsons from the Post Office. Flowers had first been called in, at Turing’s suggestion, when Morell’s group was having difficulty with the design of the combining unit. Flowers had not been involved in the basic design of the Robinson and did not think much of the machine. The difficulty of keeping two paper tapes in synchronization at high speed was a conspicuous weakness. So was the use of a mixture of valves and relays in the counters, because the relays slowed everything down. Flowers suggested a new machine, all electronic, with only one tape. However, opinion at Bletchley was that a machine containing the number of valves that Flowers was proposing – about 2,000 – would not work reliably. In any case, there was the question of how long the development process would take. Newman decided that his section should press ahead with the Robinson, and left Flowers to do as he wished. At Dollis Hill Flowers just got on with building the machine that he could see was necessary. Colossus was entirely his idea.
Colossus I had approximately 1,600 valves and operated at 5,000 characters per second. The later models, containing approximately 2,400 valves, processed five streams of dot-and-cross simultaneously in parallel. This boosted the speed to 25,000 characters per second. By means of repluggable cables and a panel of switches, Flowers deliberately built more flexibility than was strictly necessary into the logic stages of Colossus I. These, like the combining unit of Heath Robinson, did the deltaing and the comparing. As a result of this flexibility, new methods could be implemented on Colossus as they were discovered. Michie and Good soon found a way of using Colossus I to discover the wheel patterns themselves. (Prior to the summer of 1944, the Germans changed the cam patterns of the chi-wheels once every month and the cam patterns of the psi-wheels at first quarterly, then monthly from October 1942. After 1 August 1944 wheel patterns changed daily.) Colossus II, installed shortly before D-Day, was supplied with a special panel for use when breaking wheel patterns. Following the delivery of Colossus II, new Colossi arrived in the Newmanry at roughly six-week intervals.
If Flowers could have patented the inventions that he contributed to Ultra, he would probably have become a very rich man. As it was, the personal costs that he incurred in the course of building the Colossi left his bank account overdrawn at the end of the war. Newman was offered an OBE for his contribution to the defeat of Germany, but he turned it down, remarking to ex-colleagues from Bletchley Park that he considered the offer derisory.
Colossus was far from universal. Nevertheless, Flowers had established decisively and for the first time that large-scale electronic computing machinery was practicable. Even in the midst of the attack on Tunny, Newman was thinking about the universal Turing machine. He showed Flowers Turing’s 1936 paper about the universal computing machine, ‘On Computable Numbers’. (Not being a mathematical logician. Flowers ‘didn’t really understand much of it’.) There is little doubt that by 1944 Newman had firmly in mind the possibility of building a universal Turing machine using electronic technology. It was just a question of waiting until he ‘got out’. In February 1946, a few months after his appointment to the Fielden Chair of Mathematics at the University of Manchester, Newman wrote to the Hungarian–American mathematician John von Neumann (like Newman, considerably influenced by Turing’s 1936 paper, and himself playing a leading role in the computing developments taking place in the US):
I am … hoping to embark on a computing machine section here, having got very interested in electronic devices of this kind during the last two or three years. By about eighteen months ago I had decided to try my hand at starting up a machine unit when I got out… I am of
course in close touch with Turing.
The implication of Flowers’ racks of electronic equipment would have been obvious to Turing too. Flowers said that once Colossus was in operation, it was just a matter of Turing’s waiting to see what opportunity might arise to put the idea of his universal computing machine into practice.
Such an opportunity came along in 1945, when John Womersley, head of the Mathematics Division of the National Physical Laboratory (NPL) in London, invited Turing to design and develop an electronic computing machine for general scientific work. Womersley named the proposed computer the Automatic Computing Engine, or ACE – a homage to Babbage.
During the remainder of 1945 Turing designed his electronic stored-program universal machine, completing his technical report, ‘Proposed Electronic Calculator’, before the end of 1945. This was the first relatively complete specification of an electronic stored-program general-purpose digital computer. An earlier document (May 1945), ‘First Draft of a Report on the EDVAC’, written by von Neumann in the US, discussed at length the design of a stored-program computer, but in fairly abstract terms, saying little about programming, hardware details, or even electronics. Turing’s ‘Proposed Electronic Calculator’, on the other hand, contained specimen programs in machine code, full specifications of hardware units, detailed circuit designs, and even an estimate of the cost of building the machine (£11,200). Turing’s ACE and the proposed EDVAC computer differed fundamentally in their design; for example, the EDVAC had what is now called a central processing unit, or cpu, whereas in the ACE, the various logical and arithmetical functions were distributed among different hardware units.
The Bletchley Park Codebreakers Page 39