Electronic computers, part 2: Colossus

Previous part

In 1938, the head of the British secret intelligence quietly acquired an estate of 24 hectares 80 miles from London. It was located at the intersection of railways going from London to the north, and from Oxford in the west to Cambridge in the east, and was an ideal place for an organization that no one should have seen, but also located in quick access to most of the important knowledge centers. and the authorities of Britain. The estate, known as Bletchley Park , became the British center for breaking ciphers during World War II. This is probably the only place in the world known for its involvement in cryptography.
')

Tanni

In the summer of 1941, Bletchley was already working hard on hacking the famous Enigma cryptographic machine used by the German army and navy. If you watched a movie about British cipher crackers, then they told you about Enigma, but we will not cover it here - because soon after the invasion of the Soviet Union in Bletchley, they discovered the transfer of messages with a new type of encryption.

Cryptanalysts pretty soon unraveled the general nature of the machine used to transfer messages, which they called "Tanni."

Unlike Enigma, whose messages had to be decrypted manually, Tanni was directly connected to the teletype. The teletype transformed each character entered by the operator into a stream of points and crosses (similar to the dots and dashes of Morse code) in the standard Bodo code with five characters per letter. It was unencrypted text. Tanni simultaneously used twelve wheels to create her own parallel stream of points and crosses: a key. She then added the key to the message, producing an encrypted text transmitted over the air. Addition was made in binary arithmetic, where the points corresponded to zeros, and the crosses - ones:

0 + 0 = 0
0 + 1 = 1
1 + 1 = 0

Another Tunney on the recipient's side with the same settings gave out the same key and added it to the encrypted message in order to issue the original one, which was printed on paper by the recipient's TTY. Suppose we have a message: "dot plus dot dot plus". In numbers it will be 01001. Add a random key: 11010. 1 + 0 = 1, 1 + 1 = 0, 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, so that we get the encrypted text 10011. By re-adding the key, you can restore the original message. Check: 1 + 1 = 0, 1 + 0 = 1, 0 + 0 = 0, 1 + 1 = 0, 0 + 1 = 1, we get 01001.

The analysis of the work of Tanni was facilitated by the fact that in the early months of its use, senders passed on wheel settings that should be used before sending a message. Later, the Germans released codebooks with preset wheel settings, and the sender only needed to send a code by which the recipient could find the desired wheel setting in the book. As a result, they began to change codebooks on a daily basis, because of which Bletchley had to crack the settings of the code wheels every morning.

Interestingly, cryptanalysts have unraveled the function of Tunni based on the location of sending and receiving stations. It connected the nerve centers of the highest German command with the army and the commanders of army groups on various European military fronts, from occupied France to the Russian steppes. It was a tempting task: breaking into Tanni promised direct access to the enemy’s intentions and capabilities at the highest level.

Then, thanks to a combination of the mistakes of the German operators, cunning and persistent determination, the young mathematician William Tat advanced much further than simple conclusions about the work of Tanney. Not seeing the car itself, he completely determined its internal structure. He logically derived the possible positions of each wheel (each of which had its own prime number), and exactly how the wheel arrangement generated the key. Armed with this information, Bletchley built copies of the Tanney, which could be used to decrypt messages — right after the wheel was properly configured.


12 wheels of a machine key using Lorenz’s cipher known as Tanni

Heath Robinson

By the end of 1942, Tat continued to attack Tanni, developing a special strategy for this. It was based on the concept of a delta: the sum modulo 2 of a single signal in a message (point or cross, 0 or 1) with the following. He realized that due to the intermittent movement of the wheels of Tanni, there was a connection between the delta of the ciphertext and the delta of the key text: they had to change together. So if you compare the ciphertext with the key text created on different wheel settings, you can calculate the delta for each one and count the number of matches. A much greater than 50% number of matches should mark a potential candidate for a real message key. In theory, the idea was good, but it was impossible to put it into practice, since it required making 2400 passes for each message in order to check all possible settings.

Tat brought this task to another mathematician, Max Newman, who led the department at Bletchley, which everyone called “Newmania.” Newman, at first glance, was an unlikely candidate to lead a sensitive British intelligence organization, since his father was from Germany. However, it seemed unlikely that he would spy for Hitler, since his family was Jewish. He was so concerned about the progress of Hitler’s domination in Europe, that he moved his family to a safe place, to New York, shortly after the collapse of France in 1940, and for some time he thought about moving to Princeton.


Max newman

It so happened that Newman had the idea of ​​working on the calculations required by the Tata method — by creating a machine. Bletchley has become accustomed to using cryptanalysis machines. This is how the Enigma was hacked. But Newman conceived a certain electronic device to work on the Tanny cipher. Before the war, he taught at Cambridge (one of his students was Alan Turing), and knew about electronic counters built by Wynn-Williams to count particles in Cavendish. The idea was as follows: if you synchronize two looped films that scroll at high speed, one of which contains a key, and the other contains an encrypted message, and each element is considered a processor that counts deltas, then an electronic counter could sum up the results. After reading the final score at the end of each run, it was possible to decide whether this key was potential or not.

It so happened that a group of engineers with the right experience just existed. Among them was Winn-Willes himself. Turing recruited Winn-Williams from the Melvern radar lab to help create a new rotor for a machine that decodes an Enigma using electronics to calculate turns. Three engineers from the Post Research Station at Dollis Hill, William Chandler, Sydney Brodhurst and Tommy Flowers, helped him with this and another Enigma project: I remind you that the British Post was a high-tech organization and was responsible not only for paper mail, but and for telegraphy and telephony). Both projects failed and the men were left idle. Newman collected them. He appointed Flowers to lead the team that created the “combiner”, which was supposed to count the deltas and transfer the result to the meter Winn-Williams was working on.

Newman took the engineers to build the machines, and the Female Department of the Royal Navy managed his messaging machines. The government trusted high leadership positions only to men, and women coped well, working as operations officers in Bletchley - they were engaged in both the transcription of messages and decoding settings. They very organically succeeded in moving from clerical work to caring for machines that automated their work. They thoughtlessly called their ward car " Heath Robinson ", the British equivalent of Ruba Goldberg [both were cartoonist illustrators who portrayed extremely complex, cumbersome and intricate devices that performed very simple functions / approx. trans.].


The machine "Old Robinson", very similar to its predecessor, the car "Heath Robinson"

And indeed, “Heath Robinson”, in theory, quite reliable, in practice, suffered from serious problems. The main thing was the need for perfect synchronization of two films - encrypted text and key text. Any stretching or slipping of any of the films made the entire passage unusable. To minimize the risk of errors, the machine processed no more than 2000 characters per second, although the belts could work faster. Flowers, reluctantly agreeing with the work of the Heath Robinson project, believed that there was a better way: a machine built almost entirely from electronic components.

Colossus

Thomas Flowers worked as an engineer in the research department of the British post office from 1930, where he initially worked on the study of incorrect and failed connections in new automatic telephone exchanges. This led him to reflect on how to create an improved version of the telephone system, and by 1935 he began to preach the replacement of electromechanical components of the system, such as a relay, with electronic ones. This goal determined his entire career.


Tommy Flowers, around 1940

Most of the engineers criticized electronic components for their capriciousness and unreliability when used on a large scale, but Flowers showed that if they were used continuously and at capacities far below the calculated ones, electronic lamps actually demonstrate an amazingly long service life. He proved his ideas by replacing all terminals that installed a communication tone on a switch that served 1000 lines with lamps; all there were 3-4 thousand. This installation was launched into real work in 1939. In the same period, he experimented with replacing relay registers storing telephone numbers with electronic relays.

Flowers believed that Heath Robinson, for which he was hired, had serious flaws, and that he would be able to solve this problem much better using more lamps and less mechanical parts. In February 1943, he brought an alternative scheme of the machine to Newman. Flowers cleverly got rid of the film with the key, eliminating the problem of synchronization. His car was supposed to generate key text on the fly. She had to simulate Tanni electronically, going through all the settings of the wheels and comparing each of them with the cipher text, recording the likely matches. He expected that such an approach would require the use of about 1,500 electron tubes.

Newman and the rest of Bletchley’s management were skeptical of this proposal. Like most contemporaries of Flowers, they doubted whether electronics could be made to work on such a scale. In addition, even if it can be made to work, they doubted that such a machine could be built in time so that it would be useful in the war.

The head of Flowers in Dollis Hill, however, gave him the go-ahead to gather a team to create this electronic monster - Flowers perhaps did not quite sincerely describe to him how much he liked the idea in Bletchley (If you believe Andrew Hodges, Flowers told his boss that the project was critical for Bletchley’s work, and Radley had already heard from Churchill that Bletchley’s work was an absolute priority). In addition to Flowers, Sydney Broadhurst and William Chandler played a major role in the development of the system, and the whole undertaking took the work of almost 50 people, half of the resources of Dollis Hill. The team was inspired by the precedents used in telephony: counters, branching logic, equipment for routing and signal translation, and equipment for periodic measurements of equipment status. Brothurst was a master of such electromechanical circuits, and Flowers and Chandler were experts in electronics who understood how to transfer concepts from the relay world to the world of valves. By early 1944, the team presented a working model in Bletchley. The giant machine received the name "Colossus", and quickly proved that it could overshadow the "Heath Robinson" by reliably processing 5000 characters per second.

Newman and the rest of the leadership in Bletchley quickly realized that they were wrong in refusing Flowers. In February 1944, they ordered another 12 "Colossi", which were supposed to be operational by June 1 - an invasion of France was planned for that date, although, of course, it was not known to Flowers. Flowers bluntly said that this was impossible, but by making heroic efforts, his team managed to deliver a second car by May 31, in which a new team member, Alan Coombs, made many improvements.

The revised scheme, known as the Mark II, continued the success of the first car. In addition to the film supply system, it consisted of 2400 lamps, 12 rotary switches, 800 relays, and an electric typewriter.


Colossus mark ii

It was customizable and flexible enough to perform various tasks. After installation, each of the women's teams set up their “Colossus” to solve certain problems. A patch panel, similar to the panel for the telephone operator, was needed to tune the electronic rings that simulated the Tanni wheels. A set of switches allowed operators to set up any number of functional devices that processed two data streams: an external film and an internal signal generated by rings. Combining a set of different logical elements, the Colossus could be engaged in calculating arbitrary Boolean functions based on data, that is, such functions that would produce 0 or 1. Each unit increased the counter of the Colossus. A separate control unit made branching decisions based on the state of the counter — for example, stop, and print the output if the counter value exceeded 1000.


Switch Panel for Colossus Settings

Suppose the Colossus would be a general-purpose programmable computer in the modern sense. He could logically combine two streams of data — one on film, and one generated by ring counters — and count the number of units encountered, and that’s all. Most of the "programming" of the "Colossus" took place on paper, and the operators performed a decision tree prepared by analysts: let's say, "if the output of the system is less than X, configure configuration B and execute Y, and otherwise execute Z".


High Level Block Diagram for the Colossus

Nevertheless, the Colossus was quite able to solve the task set for him. Unlike the Atanasoff-Berry computer, the Colossus was extremely fast — it could process 25,000 characters per second, each of which could require performing several Boolean operations. Mark II increased its speed fivefold compared to Mark I, while simultaneously reading and processing five different sections of the film. It refused to link the entire system with slow electromechanical input-output devices, using photocells (taken from anti-aircraft radio fuses ) to read incoming films and a register for buffering the output to a typewriter. The leader of the team that rebuilt the Colossus in the 1990s showed that in his business he could still easily outperform a 1995 Pentium based computer.

This powerful text processing machine has become the hub of the project for breaking the Tanni code. Until the end of the war ten more Mark II were built, panels for which were stamped one piece per month by employees of the postal factory in Birmingham, who had no idea what exactly they were producing, and then they were assembled in Bletchley. One annoyed official from the Ministry of Supply, having received another request for a thousand special valves, asked if “the postal workers are shooting at the Germans”. In this industrial way, and not by manually assembling an individual project, the next computer will be produced no earlier than the 1950s. According to Flower's instructions, for the protection of valves, each Colossus worked day and night until the very end of the war. They stood, quietly glowing in the dark, warming up the wet British winter and waiting patiently for instructions until the day came when they no longer needed them.

Veil of silence

The natural enthusiasm for the intriguing drama unfolding in Bletchley led to an over-exaggeration of the military achievements of this organization. It is terribly absurd to hint, as the film The Imitation Game does, that British civilization would cease to exist if it were not for Alan Turing. The Colossus, apparently, had no influence on the course of the war in Europe. His most publicized achievement was to prove that the fraudulent plan about the landing in Normandy in 1944 worked. The messages received through Tanni said that the Allies successfully convinced Hitler and his command that the real blow would be farther to the east, at Pas-de-Calais. Encouraging information, but hardly reducing the level of cortisol in the blood of the Allied command helped win the war.

On the other hand, the technological advances that the Colossus presented were undeniable. But the world will not know it soon. Churchill ordered that all the “Colossi” that existed at the time of the end of the game be dismantled, and the secret of their device together with them be sent to a landfill. Two cars somehow survived this death sentence, and remained in the ranks of British intelligence until the 1960s. But even then the British government did not lift the veil of silence about working in Bletchley. Only in the 1970s its existence became public.

The decision to permanently ban any discussion of the work carried out in Bletchley Park could be called excessive caution by the British government. But for Flowers, this was a personal tragedy. Deprived of all the merit and prestige of the inventor of the Colossus, he suffered from dissatisfaction and disappointment when his constant attempts to replace the relay with electronics in the British telephone system were constantly blocked. If he could demonstrate his achievement using the example of the Colossus, he would have the influence necessary to realize his dream. But by the time his achievements became known, Flowers had retired a long time ago and could not influence anything.

Several electronic computing enthusiasts scattered around the world suffered from similar problems related to the secrecy surrounding the Colossus and the lack of evidence for the viability of this approach. Electromechanical calculations could remain important for some time. But there was another project that will pave the way for joining the dominant position of electronic computing. Although it was also the result of secret military developments, it was not concealed after the war, but on the contrary, it was opened to the world with the greatest aplomb, under the name ENIAC.

What to read:

• Jack Copeland, ed. Colossus: The Secrets of Bletchley Park's Codebreaking Computers (2006)
• Thomas H. Flowers, “The Design of Colossus,” Annals of the History of Computing, July 1983
• Andrew Hodges, Alan Turing: The Enigma (1983)