Max Newman

The answer to this problem was in mechanizing the double delta attack in some sort of computer. Max Newman, a mathematician working at Bletchley Park, originated the idea that the double delta attack could be carried out electronically, thus greatly reducing the time needed to determine the wheel settings for a message. He imagined a machine that would take in cipher text as input and compare it to all the possible combinations of two χ wheels. The combination that resulted in the highest correlation between the deltas of these streams would then be chosen as the correct settings for two of the χ wheels.

Heath Robinson

Newman's first request for such a machine resulted in the Heath Robinson electro-mechanical computers. These had significant speed problems, because they required two punched paper tapes to be compared for the double delta attack. When the tapes were run at high speeds, they tended to stretch and get misaligned. Since the machine had essentially two readers that would each read one letter on the tape at a time and compare them, synchronization was very important. The misalignment meant that the results from the Heath Robinson machines could not always be trusted if they were run at reasonably high speeds.

Newman persisted in believing that an electronic method could be found to accelerate the double delta attack. This persistence led him to Tommy Flowers, an engineer working for the Post Office. At Newman's request, Flowers designed Colossus, a machine that would be able to electronically implement the double delta attack and thus greatly decrease the time required to determine the wheel settings for a Lorenz-encrypted message.

Colossus

The Colossus machine greatly surpassed the ability of the Heath Robinson. It was able to read in paper tape at 5000 characters per second, five times as fast as Heath Robinson. Additionally, the Colossus did not need two paper tapes because the output from the χ wheels was generated entirely electronically. Thus, the only tape needed as input was the encrypted message. Although Colossus was designed primarily to implement the double delta attack against the Lorenz cipher, its logic circuits were programmable to a very large extent. The programming was done through plugboards and switches on the back of the machine. Although this seems very different from modern computers which store programs in memory, the electronic generation of the χ wheel output stream makes the Colossus a revolutionary machine.

Colossus machine in acion

The First Electronic Computer

Although ENIAC, the computer built by the US Government in 1945, has often been lauded as the first electronic computer, the Colossus Mk I actually deserves that title. The Colossus was built before ENIAC, but due to the highly classified nature of the work that went on at Bletchley Park, the plans were destroyed and those who had worked on it were sworn to secrecy. However, Colossus was an electronic computer. It meets this qualification, because its fundamental building blocks for logic were thermionic valves, more commonly known in the United States as vacuum tubes. These valves are automatic electronic switches--that is they allow current to flow between anode and cathode only if a third wire is at a certain potential. These perform an almost identical function to transistors in modern computers. In addition the thermionic valves allow switching at speeds on the order of millions per second, much higher than previous computing machines. In fact, the speed of the Colossus was primarily limited by the speed at which the tape containing the cipher text could be read.

Generating the χ Wheels

In order to use the double delta method to find the correct χ wheel settings, first the actual pattern of ones and zeros on each χ wheel had to be known and stored electronically in Colossus. This was accomplished by rings of thyratron valves. A thyratron valve is similar to a thermionic valve, but instead of a vacuum it contains a certain amount of neon gas. This means that once a current is allowed to flow through the valve it continues until a certain opposite voltage is applied to two of the leads. In this way, a thyratron can store one bit of information electronically. Rings of these valves, arranged in precise numbers to mimic the wheels of the Lorenz encryption machine, were used to generate all the possible combinations for two χ wheels. Once the pattern of ones and zeros on the wheels were known, these could be stored in the thyratron rings and used to find the correct settings for several messages.

Running Colossus

The Colossus machine was driven by the tape reader which scanned punch holes in a tape representing the cipher text of a message. The punch holes were converted by a photoelectric reader into a sequence of pulses which were then sent to the arithmetic and logic circuits of Colossus for processing. The tape also contained a series of "sprocket holes" which were used for the timing of the processing. Each pulse from a sprocket hole was essentially one tick of the clock that ran Colossus.

At each tick pulses from the tape and from the thyratron rings are sent to delta circuits which calculate the delta of each stream of bits. The delta circuits contain capacitors which delay a pulse long enough that it can be added (modulo 2) to the next input pulse. This process calculates the delta of each input stream because it will output a one if two consecutive bits are different and a zero when they are the same. The delta of the stream from two columns of bits on the tape (representing two impulses in the encrypted message) and two thyratron rings (representing two χ wheels) are then sent on to be combined by the logic circuits. As described in the page on the double delta attack, the wheel settings that produced the most zeros from the above process were likely to be correct.

Colossus contained counters to keep track of each time the combination of the two input delta streams in the logic circuits produced a zero. An operator of the machine would manually set a threshold which, when it was exceeded by the count of zeros for given wheel settings, would cause the wheel settings and the number of zeros for those settings to be printed out. Thus, all the combinations which produced too few zeros could be ignored because their count would not exceed the threshold and so would not be printed out.

Parallelism

In order to speed up the computation, Colossus was designed to do five comparisons in parallel. A so called "shift register" was used, which would store the last six bits to come off of the tape. In this way, five deltas would be available to be calculated at once. The name "shift register" comes from the fact that, when each new bit comes in to the register all the other ones are shifted over by one place, and the oldest one is removed. The availibilty of six bits means that the five deltas can be taken from the message at a time. If these are all compared to the same output from the thyratron rings, the result is that five consecutive loops of the tape can be done in the time of one loop. So, the advent of the shift register allowed five times as many German messages to be processed as would have been possible otherwise.