User Tools

Site Tools


collosal_first_electronic_computer

COLOSSAL 1st Electronic Computer

All this from APC Magazine July 2021

FEATURES / FEATURE A COLOSSAL SECRET Ian Evenden discovers how British WWII braniacs, faced with an impossible task, helped save millions of lives and invented the computer as we know it.

apcuk2107_article_052_01_01 A Lorenz SZ42 cipher machine on display at Bletchley Park museum.

(© JACK TAYLOR/GETTY IMAGES) Your country is at war, and you start picking up directional radio signals that sound like nothing you’ve ever heard before. The enemy is highly mechanised, makes use of the latest technology, and has a record of using complex codes and ciphers in its transmissions. This is something new, however. Instead of the dots and dashes of the Morse code you’re used to intercepting, this sounds like a harsh wailing.

These days, we’d probably equate the sound with a 56K modem, but back in the 1940s, it was known as teleprinter code. Nazi high command, not content with the “unbreakable” Enigma cipher it used to spread orders among its armies and navies, was also using a machine for higher-level communications called the Lorenz SZ that British codebreakers had never seen, and would not see until the end of World War II. Despite this, they were able to deduce how it worked, and crack the encipherment.

This is the story of a country house in England full of mathematicians, crossword enthusiasts, the occasional genius, and a man from the postal service more used to creating automated telephone exchanges. Together, they read German military communications and shortened WWII by up to four years, saved possibly millions of lives, and created Colossus, the first programmable electronic computer, in the process.

This is a complicated story, and we’ve had to leave bits out, but bear with us, there’s still a lot of backstory. The tale of how the British, Alan Turing in particular, cracked Enigma, opening up Nazi communications, and making it possible to anticipate their every move is already fairly well known, but it has some parallels with the decryption of the Lorenz machine that can’t be ignored. The Nazis had mechanised the sending of secret messages, so a mechanised approach was needed for reading them. Lorenz had similar weaknesses to the Enigma, especially if you could be confident of the content of certain parts of messages, such as ending everything with “Heil Hitler,” for example.

Enigma was an electro-mechanical machine with three, sometimes four, rotor wheels and a plugboard. Input came from a keyboard, and its output was a lamp that lit up behind a grid of letters. The rotors moved every time a key was pressed, one full rotation triggering the next one to move, then the next. The plugboard swapped letters over, so connecting A to S always switched those letters. With three rotors from a set of five in use, and 10 connections on the plugboard, the machine was capable of nearly 159 quintillion (18 zeroes) combinations. Adding a fourth rotor, as the German Navy did, just made things worse.

Lorenz had 12 rotors, and acted as an add-on to a teleprinter machine (you type at one end, the message comes out printed on paper tape at the other), but otherwise operated in a similar way. Once the machine’s settings for the day were entered, however, it was much more automatic. The enciphered text was encoded as a 5-bit Baudot code (International Telegraph Alphabet No. 2) for transmission, which made use of a modulated on/off signal – binary, in other words – that was the source of the modem-like screeching the British listening stations were picking up.

“It was a binary machine, but not understood as a binary machine,” says Paul Gannon, author of Colossus: Bletchley Park’s Greatest Secret. “They used a different terminology at the time – mark and space. They didn’t think of it as zero and one; that’s a backward projection from what we know now.”

The Lorenz machine then encrypted the Baudot further with a Verman stream cipher. Ten of the 12 rotors in the machine generated a key stream in two groups of five, which was combined with the plaintext using a logical operation known as Exclusive Or (XOR). The remaining two wheels added a pseudorandom “stutter” to the key stream, complicating it further. Each rotor had a different number of cams on it, which could be raised or lowered to create the wheel settings. The total number of settings is a number so large it would be followed by 150 zeroes (there’s 18 in a quintillion, remember).

“There’s no reason why it had to be like this,” says Gannon, “but with Enigma they would write the message down on a piece of paper, one guy would then read out the message, another would type in each letter of the message and read off the encoded letter, then write it down. Then somebody else would transmit that using Morse code. At the other end, they would read the Morse code, and reverse the message with an Enigma set up with the same settings. But the teleprinter was a central communications tool within Germany, and especially with the Nazis when they took over, and so they wanted to carry on using it. First of all they transmitted from teleprinter to teleprinter over cables, and then using a wireless link.”

Gannon continues: “Your message was automatically encrypted and at the other end automatically decrypted, so all you needed was one typist at each end, rather than three people writing things down. Nobody saw the encrypted version of the message. The teleprinter was the key to communications within the German army, and this suited the British at the time because they had cracked the German naval and air force Enigma, but hadn’t cracked the army Enigma. So when they started intercepting these weird sounds, which they described as being like a cow wailing, it took some time to work out what they were.”

apcuk2107_article_052_01_02 Frontal view of the reconstructed Colossus at The National Museum of Computing, Bletchley Park, UK.

apcuk2107_article_052_01_03 A Colossus Mark II computer being operated by Dorothy Du Boisson (left) and Elsie Booker (right), 1943.

(© TED COLES /WIKIMEDIA,) The first transmissions were intercepted in 1941, a link between Berlin, Germany, and Athens, Greece. Used to dealing with Morse code, the British classified these as NoMo, or non-Morse, and the Berlin-Athens link picked up the code name Tunny (tuna fish). Tunny would become the code name for the Lorenz machine itself (Geheimschreiber, or secret writer, in German) after the link closed in 1942, while the teleprinter operation as a whole became Fish. As new links sprang up, they attracted new species of sea life: Berlin to Tunis was Herring, Berlin to Paris Jellyfish, and Berlin to Oslo was given the code name Mullet. This was a recurring theme – three-rotor Enigma transmissions were code-named Dolphin, while four-rotor transmissions were Shark. The intelligence gathered by codebreaking was known as Ultra, and was an incredibly closely guarded secret.

apcuk2107_article_052_01_04 The wheels in the Lorenz machine each have a series of cams that can raise or lower, which were the settings Colossus calculated.

Bletchley Park, home of the innocuously named Government Code and Cipher School (think today’s NSA), is a country house in the middle of England, built in the 1880s. These days, it’s a museum, but during WWII, it was a branch of the British intelligence services. Its activities were so highly classified that it wasn’t until 1974, with the publication of a book, The Ultra Secret, by F. W. Winterbotham, that details began to trickle out.

What took slightly longer to emerge, however, were the details of what they’d built there. The Enigma cipher was broken through human ingenuity (a lot of early work had been done in Poland during the 1930s, and transferred to Britain at the outbreak of war), and a series of electromechanical devices known as Bombes, which simulated the rotors of the Enigma machine and could sift through possible settings to crack that day’s wheel order and plugboard connections – effectively a brute force attack but using human brainpower, some wartime heroics (such as snatching a codebook from a sinking submarine), and user errors, such as transmitting two identical messages with different settings, to lower the number of permutations necessary. Lorenz, being far more complex, required a different approach.

At this point, Thomas H. Flowers, known as Tommy, the top man in research and development at the General Post Office Research Station at Dollis Hill, London, became involved. He was the son of a bricklayer, in contrast to the middle- or upper-class types usually found at Bletchley Park, and had earned a degree in electrical engineering by taking evening classes. He’d been exploring the use of electronics in telephone exchanges – usually powered by young women before this point in time – and was convinced he could build an all-electric one.

Which is how he came to the attention of Alan Turing, who asked the Post Office for help. “The issue started really with the Enigma when the German navy introduced a fourth rotor wheel,” says Gannon. “A fourth rotor was just too big a job for an electromechanical device to sort out, so they set up two or three different projects.” His first project with Turing was abandoned, but Turing was impressed enough to introduce Flowers to Max Newman, who was leading the assault on Lorenz in his “Newmanry” – the part of Bletchley Park working on automation.

“Turing wasn’t directly involved in the whole Tunny question,” says Gannon. “But he was a general consultant on all sorts of things at Bletchley Park, so got a little bit involved well before they even came up with the idea of Colossus. When they were stuck on how to decipher the messages that they were picking up, he suggested using a technique known as the Delta.”

The math involved is too much for a humble PC magazine, but it involves repeated characters (a feature of German, which is full of SS, EE, TT, and LL). The ciphertext can be manipulated in such a way that certain relationships appear between characters that wouldn’t be there if it was random, and from this the movements of one set of wheels in the Lorenz machine could be deduced. It was called Delta for the Greek letter, and the word “difference,” because XOR is the same as modulo 2 subtraction.

“This became a key factor in what Colossus did,” says Gannon, “as the way the Lorenz machine was built meant that two of the wheels generated an intermittent stutter in order to try to increase the periodicity of the wheels. By using the Delta technique, you could observe these stutters because you’d get a regularity, lines of spaces coming through. You could then statistically see through different layers of the cipher.”

This method of attacking Lorenz was carried out in the “Testery,” the part of Bletchley Park run by Ralph Tester, and supplemented by machines in the Newmanry. Flowers’ first design for Newman was called the Heath Robinson (named for a British illustrator not dissimilar to Rube Goldberg), produced in conjunction with his colleague Frank Morell at the Post Office Research Station. Begun in January 1943, it was delivered to Bletchley Park in June, and worked pretty much straight away.

To understand how, we must step back a bit. In 1941, a Nazi radio operator made a mistake. He transmitted a message of 4,000 characters from Athens to Vienna using Lorenz, but it wasn’t received properly. Vienna asked Athens to repeat the message, but didn’t encrypt this request. The British immediately began to listen very carefully. The 4,000 characters were sent again, but without changing the key settings. This was very bad practice – in fact it, was forbidden – and to make things worse, the two messages weren’t quite identical; the operator used abbreviations to make it shorter. In cryptography, this is known as a “depth,” and can be used to break into the cipher.

Enter the enormous brains of Bill Tutte, a British/Canadian mathematician, and John Tiltman, a British Army intelligence officer. Tiltman deduced that it was a Vernam cipher using the XOR function, and was able to extract the key. This huge feat of intellect relied on Turing’s observation that, once you had recognised and removed the effect of the first five wheels in the machine from the message, what was left, though still unreadable, was not statistically random. It took two months, but Tutte, backed by other members of the Research Section, was able to work out the complete structure of the Lorenz machine, despite never having seen one, from this one mistake by a radio operator in Athens.

apcuk2107_article_052_01_05 Tommy H. Flowers, telephone exchange expert and builder of the first electronic computer

apcuk2107_article_052_01_06 Max Newman, British mathematician, codebreaker, and computer builder

apcuk2107_article_052_01_07 C. E. Wynn-Williams, inventor of Colossus’s counting device.

apcuk2107_article_052_01_08 A table showing the effect of the XOR function on 1 and 0 inputs.

It was this break-in that first Delta and then Heath Robinson were designed to exploit – removing the effect of the first five wheels from the enciphered message, so that manual methods could do the rest. It used two synchronised paper tapes for data storage (each punched with up to five holes, one for every bit of the Baudot code), and was largely electromechanical apart from a few thermionic valves – key components of electronics for the first half of the 20th century until the invention of the transistor. The characters of the message were punched into the paper tape, which was passed at speeds of up to 2,000 characters a second past a photoelectric reader. Flowers’ valve-based “combining unit” then applied the XOR logic that Tutte had figured out, passing the result to a counting unit designed by Dr. C. E. Wynn-Williams from the Telecommunications Research Establishment at Malvern. This used a thyratron – a sort of high-voltage thermionic valve – to count the number of 0s generated. The higher the 0 count, the more likely the key sequence was correct.

The Heath Robinson was slow and a bit unreliable. Paper tapes could stretch, putting them out of sync, and the display of the 0 count was overwritten with each new count, leading to lost data if not written down in time. Many of the shortcomings were dealt with as the machine was improved, but Flowers realised he could produce a machine that generated the key stream electronically. This meant a lot more valves. The idea that up to 2,000 valves could work together reliably was not popular. They weren’t seen as reliable, with a tendency to blow like old-fashioned light bulbs.

“There was a dispute between Gordon Welchman [Assistant Director for Mechanisation at Bletchley Park in 1943] and Flowers, where Welchman was trying to get Flowers kicked out of Bletchley Park because he was wanting to use too many electronics,” says Gannon. “His ideas would have used up all the electronic valves in the country.” Gannon’s theory, based on his research, is that Turing intervened and took Flowers’ side. This was just as well, as Flowers’ work at the Post Office had shown that valves blew from stresses that were greatest when they were powered up. His solution? Don’t turn the machine off. A team of 50 people set about building something completely new.

apcuk2107_article_052_01_09 A Colossus computer, used during World War II at Bletchley Park, on display at The National Museum of Computing in the UK.

(© JACK TAYLOR/GETTY IMAGES) Colossus Mark I, with 1,600 valves, arrived at Bletchley Park on January 18, 1944, and attacked its first message on February 5. A Mark II machine, with 2,400 valves, became operational on June 1, just in time for D-Day, the Allied invasion of France, and would be joined by 11 more. The Mark II had 12 rings of thyratrons that simulated the 12 wheels of the Lorenz machine, and a six-character shift register of Flowers’ design which, along with the five electronic counters, gave it five-way parallelism, so it was five times faster than the original and easier to operate. Its speed was still limited by the paper tape, but it meant the British were reading high-level Nazi communications, including those signed by Hitler, just hours after they were sent.

Colossus was built for one task, and so couldn’t be called a general-purpose computer. Its programmability was limited, with the programs held in the positions of switches and jack panel connections, but its algorithms could cover five billion combinations of variables. Of course, the Germans hadn’t sat still, and by August 1944, the wheel settings on all Lorenz machines were being changed daily, leading to a lot of work.

After the war, Colossus was a secret for 30 years. Units 1–10 were dismantled, their parts returned to the Post Office or Newman’s Royal Society Computing Machine Laboratory at the University of Manchester. Flowers was ordered to burn all documentation. “That was a terrible mistake,” he said later. “I was instructed to destroy all the records, which I did. I took all the drawings and the plans and all the information about Colossus on paper and put it in the boiler fire. And saw it burn.”

Units 11 and 12 survived, however, and as the Government Code and Cipher School was renamed Government Communications Headquarters (GCHQ) and moved to a new building at Cheltenham, they, plus two replica Lorenz machines, were taken along. They remained there until 1960, used mainly for training and for checking that one-time pads (an unbreakable form of sending secret messages) were sufficiently random.

Those who knew about the machines, however, dispersed into academia and industry. The idea that high-speed digital computing was feasible and reliable was a powerful one, but it didn’t catch on everywhere; when Flowers applied for a bank loan to build another machine, he was rejected because the idea was not considered likely to work. Constrained by the Official Secrets Act, he could not argue that he’d already built one. He remained at the Post Office Research Station, where he became head of the switching division, finally building his all-electric telephone exchange in 1950. He moved to Standard Telephones and Cables Ltd, and retired in 1969. He published a book on telephone exchanges in 1976, received an honorary doctorate in 1977, the Martlesham Medal in recognition of his achievements in computing in 1980, and in 1993 was awarded a college certificate, having completed a course in basic information processing on a PC. He died in 1998.

Recognition was not something the man who built the first computer sought in his lifetime, but it has come to him, slowly. There are at least two roads named for him, and a computing center for young people, The Tommy Flowers Centre, opened in 2010 near where he was born. At the R&D center operated by British Telecom (BT) – the successor to the Post Office in running Britain’s phone network – a life-size bronze bust of Flowers was unveiled in 2013, and in 2016, BT opened the Tommy Flowers Institute, a training center for postgraduates moving into the telecommunications industry.

And despite the blueprints being destroyed, enough material survived in engineers’ notebooks (a surprising amount of the material had made its way to the US) for a Colossus Mark II to be rebuilt between 1993 and 2008. The optical tape reader was rebuilt by its original designer, Dr. Arnold Lynch, and the working unit stands today in the position occupied by Colossus No. 9 at Bletchley Park, now The National Museum of Computing. It’s the size of a bus, and makes a noise like the world’s worst industrial metal band falling down the stairs.

A competition to celebrate the rebuilt Colossus pitted it against modern computers in receiving and decoding Lorenz messages. The winner, Joachim Schüth, using a 1.4GHz laptop and his own program written in Ada, took 46 seconds to find the settings for all 12 wheels. Colossus took three hours and 15 minutes. “My laptop digested ciphertext at a speed of 1.2 million characters per second, 240 times faster than Colossus,” said Schüth at the time. “If you scale the CPU frequency by that factor, you get an equivalent clock of 5.8MHz for Colossus. That is a remarkable speed for a computer built in 1944.” Remarkable indeed. Intel wouldn’t get there for another 35 years.

© WIKIMEDIA, INTERNATIONAL SPY MUSEUM, RICARDO FERREIRA DE OLIVEIRA ■

collosal_first_electronic_computer.txt · Last modified: 2021/07/27 20:00 by geoff