How hard can it be? – Part 2: The crib that would not stop

by Christian Rudolph

A recreational four-part summer series about trying to recover the settings of real wartime Enigma messages, eighty years after Bletchley Park had already read them.

At the end of the last part I had a ranked heap of maybes and no way to choose between them. The statistical attack had told me roughly where the answer lived and then declined to point at it. So I did what any self-respecting researcher does when the hard way is not working: I checked whether someone else had already done it.

This is not cheating. This is literature review.

Standing on the shoulders of one individual on GitHub

Somewhere on the internet, I reasoned, this message and its solution might exist. It is a real intercept from a real collection; surely it had been broken and written up somewhere. After a quick search I found precisely one relevant link: a GitHub repository containing the same ciphertext, together with some plaintext – and a note that the decryption had never been completed.

That was simultaneously encouraging and deflating. Encouraging, because some plaintext is worth a great deal. Deflating, because if the person who had clearly put serious effort into this had not finished it, my afternoon of enthusiasm, which had expanded to several days by now, was looking optimistic.

But the partial plaintext was the gift. Because a fragment of known plaintext, lined up against the ciphertext, is a crib – and a crib is precisely what Bletchley Park ran on. I had stumbled, eighty years later, into the actual method.

Why a machine can not hide a letter from itself

To see why a crib is so powerful, you need one fact about Enigma that I already mentioned last time: the machine can never encipher a letter as itself. Press A and you can get any lamp except A. This falls straight out of the reflector – the current has to come back along a different path than it went in, so it can never arrive back where it started.

This sounds like a trivial quirk, but it is, in fact, a crowbar.

Suppose I think a stretch of the message decrypts to a known word – say the ciphertext ADAAH corresponds to the plaintext KEINE. I can immediately test whether that alignment is even possible, before touching a single rotor, just by checking: does any letter of KEINE sit directly above the same letter in the ciphertext? If the crib says E and the ciphertext also says E in the same slot, that alignment is impossible – the machine could never have done it – and I can throw it away. Slide the crib one place along, test again. Most positions die instantly on this rule alone. The self-encoding quirk, the thing that looks like a footnote, does an enormous amount of the work of finding where the crib belongs.

The Bombe, in one paragraph

Once you have a plausible alignment, the deeper question is: is there a machine setting that turns this crib into this ciphertext? My instinct was to picture it letter by letter. If plaintext K becomes ciphertext A, and plaintext E becomes ciphertext D, is there a rotor order and starting position where the machine does both at once – and then all the other pairs too?

That instinct is right, and it is roughly what the Bombe tested. But the cleverness – and it is way, way cleverer than my mental picture – is in how the constraints link up. A crib does not give you isolated pairs. It produces a network.

Because letters recur, the pairs chain into loops: A connects to K connects to some other letter connects back round. The Bombe tested whether an entire loop could be satisfied simultaneously by one configuration. A contradiction anywhere in the loop killed that configuration outright. A configuration with no contradiction was a STOP – the machine physically halted, and you had a candidate set of Enigma machine settings.

This is the "better experiment" I promised at the end of Part 1. The statistical attack gave a probability. The Bombe gives a defined answer: stop or no stop, consistent or contradictory. No eyeballing 2,500 near-misses, which, as we have seen in part 1, do not even look like German anyway.

And here is the part that still delights me. Remember the plugboard – the villain of Part 1, the thing that smeared every statistical decrypt into mush? The Bombe's loop logic is immune to it. Around a closed loop the unknown plugboard connections cease to matter in the way they do for statistical attacks. Turing did not defeat the plugboard by out-computing it. He asked a question the plugboard could not interfere with. That is the whole art.

Playing the STOP, and what you play it on

A STOP gives you rotor order and starting position – but not yet the plugboard, and not yet a guarantee. It is a candidate. You then have to set up those rotor settings, run the whole message through, and see whether German comes out. If it does: triumph. If it doesn't: that STOP was a coincidence – loops can be satisfied by chance now and then – and you go to the next STOP and try again.

I spent a happy while doing this on various Bombe simulators, of which there are several of varying fidelity. And it is worth saying what the codebreakers actually ran their candidates on, because there is a persistent muddle about it. They did not, in the main, decode on Enigmas. They used Typex machines adapted to emulate Enigma – the British cipher machine, modified to behave like the German one. This is a small irony worth savouring: Typex was in most respects the better machine. It had more rotors, a more complex stepping arrangement, and – unlike Enigma – it was never broken by the other side. Britain read Germany's mail on a machine Germany never learned to read. But a standard Typex could no more decode Enigma than one door key opens another lock; it had to be specifically adapted for the job. The superiority and the incompatibility are both true at once.

AUFKLAERUNGSRAUM ADRIA

The crib itself, once I had it aligned, was tantalisingly readable. It began – in the clipped telegraphic German of a reconnaissance report – with what amounted to reconnaissance area Adriatic, a Luftwaffe reconnaissance window over the Adriatic.

Except the crib would not behave. Two things about it nagged. There was an odd V sitting where the German word AUFKLÄRUNG really wants its Ä, an Umlaut that would have been written as AE – the text read as though it said AUFKLAVRUNG. And it seemed to be missing an S: AUFKLAERUNGSRAUM had lost its S and read AUFKLAERUNGRAUM. At this point I had no idea what to make of either. Was it a mistake in the transcription I had found? A mistake in my alignment? Damage to the original? A quirk of how the intercept had been recorded? Or something genuinely wrong in the ciphertext? I could not tell, and – this is the important part – nothing I had let me tell.

So I did the only thing available: I tried the crib several ways. With the V and without it. With the missing S restored and without it. I played around, running variant after variant through the Bombe simulator, hoping one of them would lock into place and stop.

None of them stopped.

The impasse

That is a peculiar result. No stop does not tell you what is wrong. It tells you only that something is – that somewhere in the chain of assumptions, the crib text, the alignment, the machine model, the ciphertext itself, at least one link is faulty, and the loop logic is quietly refusing to be satisfied by any of it. A STOP is a definite yes. No stop, across every variant you can think to try, is a definite nothing, and nothing is much harder to argue with.

I had reached the point the GitHub author had reached before me, by a slightly different road, and stuck at the same place. I could not solve it. In fact, I did not even know whether the British had solved it in 1941 or whether it was displayed precisely because it was never decrypted but "work in progress".

At this point I had been trying, on and off, for the better part of two weeks. My original estimate of "an afternoon with a laptop" was beginning to look a tad optimistic.

When the front of the message refuses to give way, there is only one thing left to do. Turn it over, and start reading everything around the message.

That is where the next part goes.

Similar and related posts:

• Part 1 of this series can be found here
• Part 3 of this series can be found here
• Part 4 of this series can be found here