Today is the first day of the RSA security conference in San Francisco. I will be attending so you can look for some security-related posts in the coming few weeks. But all the cryptography that will be on view in San Francisco is a great excuse to take a look at some of the security on view in a much smaller town about 50 miles northwest of London, namely Bletchley.

I was in the UK last fall and decided to go to the British National Museum of Computing, which is at Bletchley Park, and then have lunch with a friend who ran Northern Europe for VLSI Technology for many years. Since Northern Europe included Sweden, and Sweden included Ericsson, and at one point Ericsson was over 30% of VLSI's business, this was an important job. However, it turned out that I'd screwed up: it was a Monday and the museum is closed on Mondays. However, my friend had another friend who had worked at British Telecom all his career, and in retirement was one of the volunteers on what was known as the "Colossus Rebuild". So instead of sharing the museum with hordes of school parties, I got a private tour.

Colossus was the first programmable digital electronic computer, although it was programmed with plugs and switches, not a stored program. After the war, all the Colossus hardware was destroyed, along with the plans, and everyone who had worked at Bletchley Park was sworn to secrecy, which was only gradually lifted in the 1970s. The most famous computer scientist at Bletchley Park was Alan Turing, but he worked on the so-called Bombes that were used to decode Enigma. Because of the thirty years of secrecy, ENIAC has long been considered the first programmable electronic computer, ever since John von Neumann said it was, but Colossus actually pre-dated it by over two years.

There is a lot of information on the internet about Colossus. But the most comprehensive source is probably Jack Copeland's book Colossus: The Secrets of Bletchley Park's Codebreaking Computers. This is a quote from the book by Tony Sale, who drove the rebuild of Colossus, to give you an idea of how advanced it was:

Colossus is hard-wired and switch-programmed, like ENIAC. Because of its parallel nature, it is very fast, even by today's standards. At 5,000 characters per second the interval between sprocket holes [on the paper tape] 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 ordinary valves [tubes]. Colossus is so fast and parallel that a modern [the book was published in 2006] PC programmed to do the same codebreaking task takes as long as Colossus to achieve a result.

Colossus was created by a team, largely under Max Newman at Bletchley ("the Newmanry") and Tommy Flowers at the General Post Office (GPO, this was still an era when post and telecommunications were in the same organizations in most countries). Colossus was not for decoding Enigma, which was used to distribute daily operational orders by Germany, but to crack a later and more advanced German encryption machine known at Bletchley Park as Tunny, but actually called the Lorenz SZ42. tt was used by the German high command to distribute more strategic plans, and so from the point of view of the Allies, more valuable intelligence. They have one at the museum, and as you can see it has 12 rotors. In the top right, you can see that each rotor had little movable lugs that could be used to set the code for the day. Unlike Enigma, which was cumbersome to use since each character had to be entered manually, the Lorenz had a keyboard and teleprinter, so it was much more convenient.

However, the number of rotors and how they operated was not known. Bill Tutte, a Cambridge University graduate spent three months analyzing the data in detail, and managed to work out the complete architecture of the machine, despite never having seen one and knowing nothing about it. This has been described as the "greatest intellectual feat of WWII". Below is his sketch, showing how many of those lugs there were on each rotor (so how many positions there were for that rotor, too). If you add them all up, there are a total of 501, to give you an idea of the scale of the challenge.

In fact, when this machine was first brought into use, the Germans tested it with text that didn't need to be kept secret. So they wouldn't take a great deal of care not to re-use wheel settings. On 30 August 1941, a German telegraphist made an error and sent two long messages with the same indicator. The first message had been corrupted by static, but the second time the operator made very minor deviations (it was not accurate to the exact character). This allowed Tiltman to deduce the two plaintexts through a mixture of guesswork and mathematics. This enabled them to deduce a lot of the internals of just how the wheels moved. This didn't allow them to decode messages yet, but it meant that if somehow they could find the key, then they could run the same sequence and decode the whole message. This machine, a Tunny Machine, is an electrical version of the Lorentz machine that was built. The wheel settings (which lugs were moved into the active position) are the red plugs, from the top the five chi wheels, the two mu wheels, and the five psi wheels. Given a message on five-hole paper tape, it would decode the message and print the decoded text. Of course, that assumed that you had already broken the code and knew the wheel and lug positions.

Colossus itself used tubes for the processor. There was no good memory technology available and so the message to be decoded could not be stored directly. It was held on a paper tape loop. The tape-reader would process 5,000 characters per second, so even a long message of 4,000 words could be read in five seconds, and so processed 12 times per minute. The data-stream was split into five and processed in parallel. I haven't dug into the architecture enough to know whether Colossus was the first "multicore" computer, too!

Below is the back of Colossus. You don't need to count them, but there are 501 special valves/tubes called "thyratrons". If that number of 501 seems familiar, yes, it is the total number of lugs on the rotors. A thyratron:

is a thermionic valve but with a small quantity of neon in the envelope, instead of a vacuum. It is switched to the on-state when the grid becomes positive with respect to the cathode, but can then be switched off only by reducing the anode potential to stop the flow of current.

It is thus a sort of primitive memory element requiring just a single valve/tube, as opposed to most approaches to memory that required at least two tubes of which only one could be on (like the crossed nand-gates in a flipflop). This array of 501 thyratrons held the positions of all the lugs that were then being tested against the encrypted message held on the paper tape.

After the war, Turing (in London) and Newman (in Manchester) started separate projects to build a universal programmable computer. Historians assumed that they were taking the ideas from the ENIAC group in the US, and further developing them. In fact, the common heritage was Colossus.

Flowers, who built Colossus, saw ENIAC shortly after the end of the war and said that Colossus, with its elaborate facilities for logical operations, was "much more of a computer than ENIAC". I don't know enough about the internal architectures of either machine to have an opinion on how true this is, or if it is just pride in what they had created but could not talk about. Flowers himself went in a slightly different direction after the war, given his employer, and pioneered the all-electronic telephone exchange.

Visiting

To visit the British National Museum of Computing, go to Bletchley Park. But don't go to the main Bletchley Park entrance, which is just for the buildings that housed the wartime code-breakers, but rather go to the back of the site (there are signs). It has a separate entrance and a separate entrance fee. If you don't have a car, you can take the train to Bletchley from London Euston, and it is literally a couple of hundred yards from the station. The museum is closed on Mondays, as I discovered (although Bletchley Park itself is open).

The National Museum of Computing has its own section of the overall Bletchley Park website.

 

Sign up for Sunday Brunch, the weekly Breakfast Bytes email.