Lessons from the Park that still apply today

Iain Standen is the CEO of the Bletchley Park Trust, which is responsible for the restoration of the Park. After the war, the Park was almost completely destroyed and forgotten—partially at least for security reasons. Luckily it was just barely saved and is now a wonderful place to visit and see how such a small place helped change history.

Today I would like to report on a recent trip to Bletchley Park.

You probably know that Bletchley Park was the place where during World War II the British, with help from the Poles, were able to break the Enigma Machine. This machine, which had various models and versions, was the main one used by the Germans to encrypt and decrypt messages during the war. The ability to read their encrypted messages was invaluable to the war effort, and it is claimed that perhaps millions of lives were saved.

My wife, Kathryn Farley, along with her brother Andrew and I were in London recently. During our stay Kathryn set up a day trip to Bletchley Park, which is over an one hour car ride from where we were staying in London. This was a tremendous experience and I would definitely suggest getting to the Park if you can.

## The Park

Bletchley Park consisted of the main house and a number of “huts.” The latter were primitive buildings that were needed as the number of workers grew rapidly during the war. Huts were numbered and their number became strongly associated with the work that was done there.

We will call it the Park, but the actual names used during the war include:

• “B.P.”
• “Station X.”
• “London Signals Intelligence Centre.”
• And for many of the members of the Women’s Royal Naval Service, “HMS Pembroke V.”

Some of the huts:

## The Enigma Machine

I have argued before here that one of the biggest breakthroughs in modern cryptography is the treatment of messages not as a series of letters, but rather treating them as a whole number. This leap from separate letters to a whole number, I believe, is instrumental in enabling researchers to create modern codes: where would we be if we still though of messages as series of letters? How could one even think of methods based on Elliptic Curves?

Jumping back over 60 years we see that the Enigma machines indeed viewed messages as a series of 26 letters. They added simple rules for punctuation: a common rule was that “See you at noon” would become “SEEXYOUXATXNOON”.

Each letter was effectively scrambled by a permutation on 26 letters. Of course the number of such permutations is ${26!}$ which is already a huge number. Yet a code that only used one permutation to encrypt messages would easily be broken. One way to see this is to realize that cryptogram puzzles occur every day in most newspapers, and you are expected to be able to solve them in minutes.

The reason for their weakness is that messages are usually from a languages, such as German in WW II, whose tremendous redundancy makes a single substitution code easily breakable. What the Enigma did was change the permutation used from letter to letter in a wider-ranging manner than any poly-substitution cipher had done before: The first letter used some permutation, this then was changed to a new permutation for the second letter, and so on. The actual way the Enigma machines moved from one permutation to the next was based on a clever use of mechanical wheels, called rotors. How the workings of how these rotors changed the permutations is the key—bad pun—to why Enigma machines were hard to break. The Germans thought their complex motion made the machines unbreakable, but the work at Bletchley Park proved them wrong.

Here is a schematic of how current flowed through the rotors and could be changed by a key-press to turn on a light. The lighted letter was the encryption of the pressed letter. For more details see this:

## The Lessons

The fundamental reason I think the breaking of Enigma is still interesting today, over
70 years later, is that it contains simple lessons even for modern “unbreakable” codes. Here are some of the lessons:

Key Size: The Enigma machines had a huge-size key, since the key included the choice of rotors choice, the rotors’ positions, the plugboard settings, and more. Any attack that was brute-force or even near brute force was hence doomed, and even today it would fail. But of course the key size means nothing if there is an attack that avoids trying all the keys.

Operator Error: The Enigma machines were often misused in practice. The operators often violated simple rules in a way that made the security vastly lower. Examples include re-sending messages over with the same key—called a depth—and using shortcuts in selecting settings of the rotors. For instance, often the rotor settings were only slightly changed from one day to the next. Note, one could argue that operator error today is still happening. It also includes poor implementations of the codes: there are attacks on “unbreakable” modern codes that work because of bad implementations, even with RSA. One of my favorites is the attack that is sometimes called The Bellcore Attack. This exploits errors in the execution of a code. Okay, I was involved in creating this attack along with Dan Boneh and Rich DeMillo.

Hidden Design Flaws: The Enigma machines had a fundamental design flaw. This flaw leaked a fair amount of information, that could be and was exploited in the attacks. The flaw was this property of the Enigma machines:

If the letter ${x}$ was encoded into ${y}$, it is always the case that ${x}$ and ${y}$ are distinct letters.

Put another way: no letter ever encrypts to the itself. This was a tremendous mistake that helped break the whole complex system. One famous example was the following: It was noted that an encrypted message had a long run that had no occurrence of the letter “L.” The only way this could have happened with any reasonable probability is if the message was a series of “L”’s. This enabled a break into that key. The operator had been testing the system and just kept repeating the same key “L” over and over.

Even apart from such mistakes, the system arguably leaked ${\log_2 (26/25) \approx 0.05}$ bits of information per letter. To find a key needing ${N}$ bits to specify, as little as ${20N}$ letters of ciphertext could suffice to determine it. Of course it still took incredible work to extract the key, but Alan Turing’s stroke of genius was how to automate the kind of “puzzle-solving” needed for such tasks.

New Technology: The Enigma machines were actually fairly secure, but the Germans did not envision that the attackers would use a machine to break their machines. These machines, called “bombes,” were critical to the success at the Park. Today the analogy might be that someone already has a working quantum computer and can break any code that depends on discrete log or on factoring. How do we know that our “unbreakable codes” have not already been cracked? Indeed.

A picture of a “bombe” at the Park. These were created to break the Enigma machines:

A curiosity: it is believed that after the war all of the bombes at the Park were destroyed. The ones on display are reproductions. Our tour guide told us that there is a folk belief that perhaps there is an original bombe hidden somewhere on the grounds of the Park. Perhaps during the on-going renovations a bombe will discovered hidden under a floor or in a wall. Who knows—the Park may have more secrets yet to be uncovered.

## Open Problems

I have wondered if our current codes will be looked back on one day and seen to be easy to break. What do you think?