Bombes vs Bombs!

Wartime picture of a Bletchley Park Bombe, via Wikipedia.org

I’m mentioned Alan Turing and (some of) his contributions to computer technology, and still managed to not even mention the work which probably had the greatest influence on the world at the time.

For a bit of background, the Enigma machine was a cipher device that was developed in the years after World War I. To simplify dramatically, it used three rotors (four, in some models) which turned in sequence after each key-press, meaning that a specific plaintext letter might be represented by multiple ciphertext letters, and multiple plaintext letters might be represented by the same ciphertext letter. These rotors could be selected from an available set (up to eight), and the initial settings were needed to encode and decode.

In addition, the version of the machine used by the German military, after around 1930, added a “plugboard”, which allowed the operator to “swap” up to ten letter pairs, exponentially increasing the difficulty of breaking the code.

Enter Alan Turing.

In 1938, Turing was working part-time for the UK’s Government Code and Cypher School at Bletchley Park, concentrating on cryptanalysis of the Enigma machine. In the following year, Polish intelligence provided the British and French with details of the Enigma machine’s rotors, along with a method for decryption. The Polish method used a machine they developed – called a “bomba”, which depended (in part) on a weakness in the Enigma cipher which the Germans later corrected.

Turing, along with with his colleague Dilly Knox, developed the specification for a new device, called a “bombe” (as tribute to the Polish machine), which essentially emulated multiple Enigma machines, and allowed for much faster “brute force” attacks on Enigma encryption. While essential to the effort, the bombe might still have been insufficient, if not for other weaknesses in the Enigma encryption.

One weakness was the fact that Enigma was vulnerable to “known plaintext” attacks, in which known elements of a message could be used to simplify decryption. As an example, if every military order included a phrase like “Signed, General X”, this phrase could be used as a “crib” to eliminate a great many wrong (ie, inconsistent) answers, and dramatically speed the process of breaking the code, especially if the crib was predictably placed at the beginning or end of the message. In addition, one quirk of the Enigma machine was that a given letter could not be mapped to itself – this may seem small, but was critical to the speed of the code-breaking, which needed to be done every day.

“Ultra” was the designation used for the intelligence provided by GC&CS at Bletchley Park, but even that name was not used in practice. Instead MI6 (British military intelligence) invented a spy network, run by the fictional master spy, Boniface, to “launder” intelligence provided by decrypting Enigma traffic, so as not to reveal the fact that Enigma had been broken.

It was not until 1974 that the work at Bletchley Park began to be publicly revealed, and even then, the release was selective. It was only in 2012 that Turing’s last two papers on Enigma decryption were released.

This is where the bombs come in, but only as a point of comparison.

In contrast to the long-delayed knowledge that Enigma had been broken, consider the development of nuclear weapons. It is extremely difficult (if not practically impossible) to conceal nuclear weapons testing, as nuclear explosions can be detected in numerous ways, including seismic, hydro-acoustic, infra-sound, air sampling, and satellite surveillance. So, while details like the actual number of warheads, or details of delivery systems may be concealed, the existence of a mature nuclear weapons program can’t.

Which brings us, finally, to Q-day.

I’ve mentioned the quantum apocalypse before, and also the difficulty in understanding the degree to which quantum computing is likely to be practical – at least in the short term.

But consider this. Unlike a nuclear bomb test, which would be apparent immediately, it is entirely possible that we won’t find out about “Q-day” until months, years, or even decades after the fact.

Due to the level of investment, expertise required, and research time-frames involved, leading-edge quantum computer research is almost entirely done by academic institutions and huge corporations.

And governments.

While universities are mainly interested in academic reputation, and corporations are mainly interested in money, governments can (and frequently do) fund research, both overtly and covertly.

Saying that we don’t have cryptographically-relevant quantum computers yet is probably correct, but only goes so far, as we have no way of knowing whether certain governments have secret programs which have already created them, or whether other governments would reveal or conceal that knowledge, if discovered.

All we really know is that publicly-available information suggests that we don’t yet have viable quantum computers, but that could change at any time. The prudent approach would be to assume that quantum computers already exist, and work to ensure that we migrate to quantum-safe encryption as quickly as possible.

Fortunately, we can do that.

And, at this point, there’s probably no real downside.

Cheers!