An episode of Computerphile attempted to answer the question - https://www.youtube.com/watch?v=RzWB5jL5RX0.

TL;DW: With some clever tricks, and the advantage of hindsight, it can be done reasonably quickly on a modern computer.

I'm not sure I'd count that as brute-force because his method can't decrypt every possible message. He's using a statistical test to determine whether a given configuration is better or worse and then uses that to narrow down the search space, but he clarifies it's not generic - it can't decrypt all possible messages (ones which trip up his tests) and also requires a minimum message length for the statistical tests to be effective.

It's still extremely cool, don't get me wrong, but I don't think it's really what OPs asking. Given what's mentioned in the video (~12:50) and what some other commenters have mentioned I get the impression an actual brute-force is not really practical.

Interesting stuff. I guess it gets in to what counts as a a brute force, as most of the brute force attacks I've seen (e.g. password cracking) lean pretty heavily on clever maths and statistical hacks to reduce the search space as much as possible.

That's fair, there's probably more gray area in the definition than I suggested. I think the difference to me is that this is exploiting a weakness in the encryption itself rather than just guessing what the likely combination is. For password cracking, you're typically not exploiting the encryption but rather what passwords are more likely to be used than others.

It would still take many orders of magnitude longer than the current age of the universe to brute-force decrypt an Enigma message on todays fastest desktop.

Hmm, the universe is over 10^17 seconds old and the key space is apparently only a few orders of magnitude larger, so this seems wrong.

It's only 2^69, or 512 exa-decryptions. A 4090 does 44 tera ops/sec (roughly 2^45), so we're left with 2^24 × ops per decode. If it takes 1000 ops to check a key, that's 2^34, or 16 billion seconds. About 500 years.

Give or take a few centuries, it's very far from the age of the universe.

Also curious!

But how do you know that the outcome you have is the right one?

It's text. It's not something formatted.

If I encrypted a JSON string, gave it to you, you can brute-force all day trying to parse the output as a JSON string. If it works, you probably have it right.

But here? Because of how the Engima machine works you still get an output. And since we don't need to decode this output (like JSON to an actual JavaScript Object) we don't have that many ways of validating the output.

It's German from 1945. Abbreviations, different (older) spelling, spelling mistakes, ... all make it really hard to distinguish real output from incorrect output.

Although all keys generate some string of letters and numbers, the right key will produce a message with reasonable letter frequencies and of course with legible words.

For English, about 13% of letters are "e", so if the frequency is too far off that it is probably not the right key; likewise, if 13% of the letters are "z" it is also not likely to be the right key. By applying frequency checks to the most and least common letters it should be a fairly strong filter for plausible keys.

This is what the successful decrypt of another Enigma message looks like:

UUUVIRSIBENNULEINSYNACHRXUUUSTUETZPUNKTLUEBECKVVVCHEFVIERXUUUFLOTTXXMITUUUVIERSIBENNULZWOUNDUUUVIERSIBENNULDREIZURFLENDERWERFTLUEBECKGEHENXFONDORTFOLGTWEITERESX

There's enough code language being used in these messages that frequency analysis is not going to a major help (especially since it doesn't work well on very short texts anyways).

Well the triple U (not sure why they use that) and the spelling of the letters is simple enough to check for that I guess.

From what I can gather this says something like:

To U4701 Sync message, Lubeck base, From commander 4th U-boat fleet, go with U4702 U4703 to Flender Shipyard Lubeck, more to follow

It's less gibberish than it looks like at first. They really shot themselves in the foot by not having numbers on the enigma system, this would have really made messages much shorter because they had to write them all out.

There's so much specific jargon in there that would make it really easy to detect a correct message IMO. Just make a simple list of very common words and tally up.

Indeed frequency analysis wouldn't work though but it's still pretty possible IMO.

I looked at multiple messages on that website and the pattern seems to be triple letters are for single letters and abbreviations. My theory is because if you get a letter wrong in a word and "possible" becomes "possifle" then it is still intelligible, but if "u five one four" means u-boat 514 and you get the U wrong, then it could end up as A514 and mean something airplane 514, so to be safe the letter u gets transmitted thrice.

I think your theory is correct. Back when messages where not checksummed, the French Navy used to do exactly this and sent abbreviations three times in a row. I'm quite certain that the French Navy was not the only one to do this since our communications techniques were heavily influenced by foreign nations like the US.

>Well the triple U (not sure why they use that)

The machine works a bit weirdly, in that as you find some correct settings, your results converge towards the legible result. You can get 95% of the settings correct, and produce quite legible results, at which point you stop solving. So the correct result there might actually be any other three char combo like "ABC" or "UAK", but the analyst stopped investigating, because the rest of the message was reasonably legible.

It is a bit abbreviated. However it's not hard to add such common abbreviatiosn to a dictionary for attacking (plus the tripled letters should make it even easier).

vier -> vir

sieben -> siben

nul -> null

Was frequency analysis based on already decoded messages used?

There's enough German words in there, often appearing twice, that it would be very strange if this wasn't the decrypted data. If they could just read the message and understand it(and they had the German experts and general knowledge to do so), there's really no reason(and no time, the information is only useful for so long) to perform any kind of statistical analysis to confirm it's correct.

Is that a syn-ack in there or am I just imagining it?

I was curious if GPT could handle this. I couldn't get GPT-3.5 to figure it out, but GPT-4 was very quick to propose an interpretation. It's far more confident than I could imagine being, even if I could speak German, but this sort of thing feels like an application that a large language model might excel in.

---

Given that the message is decrypted from German, it seems to be a mix of letters and numbers that are likely military terms, geographical locations, and orders. Here's the translated meaning:

"Vier fünf null eins Y nach R. Stützpunkt Lübeck. Chef Vier. Flotte Mit Vier fünf null zwei und Vier fünf null drei zur Flender Werft Lübeck gehen. Dort folgt Weiteres."

In English, this roughly translates to:

"Four five zero one Y to R. Base Lübeck. Chief Four. Fleet with Four five zero two and Four five zero three go to Flender shipyard Lübeck. More to follow there."

This appears to be a set of instructions for a fleet of ships, possibly submarines (given the context of WWII and German naval operations), directing them to a particular location (the Flender shipyard in Lübeck) and notifying that further instructions will be provided upon arrival. "Four five zero one", "Four five zero two", and "Four five zero three" are likely codes for specific ships or units in the fleet. "Y nach R" could be coordinates or specific route instructions.

Just because it's confident, doesn't mean it's right. But it probably contains training data from this or similar sites.

https://enigma.hoerenberg.com/index.php?cat=The%20U534%20mes...

> Interpretation (preliminary):

> [An] U-4701, nachrichtlich [an] U-Stützpunkt Lübeck von Chef 4. U-Flottille: Mit U-4702 und U-4703 zur Flender Werft Lübeck gehen. Von dort folgt Weiteres.

> Translation (preliminary):

> [To] U-4701, for information [to] Submarine Base Lübeck from Chief of 4th Submarine Flotilla: With U-4702 and U-4703 go to Flender Dockyard at Lübeck. From there more follows.

There are about 2^67 different Enigma machine initial settings. The inverse probability of the appearance of a real seven letter German word (LUEBECK) twice in this message is a number that's pretty close to 2^67. So if you decrypted a message with incorrect settings you might expect to see those two appearances of LUEBECK, or a similarly misleading occurence. The presence of even a few of the other recognizable German words (or common abbreviations such as triple letters and the shortened names for the numbers) makes it overwhelmingly likely that this is the correct plaintext.

That would be true if it actually did the decryption, but my point was, an LLM doesn't decrypt. It just has the encrypted string followed by the decrypted string in its training data and so it outputs something that's almost correct. (the numbers being wrong 4501, 4502, 4503 instead of 4701, 4702, 4703 - maybe some bugged training data, maybe hallucination).

Sure, and I said it was confident, not correct.

I find it interesting that it pulled some kind of interpretation from the string. Far more than I would have. I asked it to translate the English data back into a similarly plaintext string and then asked a second instance to decode it and it came back with a similar, slightly distorted response.

The point is more to say that a language model is exactly the sort of thing that would be used to determine whether a given potentially decoded plaintext string is actually decoded, and given various anachronisms and shorthands our personal language models may not be adequate.

But a giant one that's been fed all sorts of data including examples of text of similar usage sounds actually like it might be exactly the tool for this problem.

Seems mostly reasonable, except for consistently translating SIBEN to fünf (five) rather than sieben (seven).

Actually, with that particular message, ~~frequency analysis~~ incidence of coincidence will help immensely, to the point of making it easy to solve.

With a modern block cipher, a partial key doesn't help. If you have 120 bits of a 128 bit AES key or whatever, decrypting the cipher text with your partial key will give pure noise. Even if you flip just one random bit in the key, the decrypt will be indistinguishable from complete randomness. Not so with Enigma; if you have parts of the key correct, parts of the rotor settings correct, parts of the wheel selection correct, patterns in the plaintext will show up as patterns in the ciphertext. The more of the key you have, the more those patterns will show up when you run the decryption routine against the ciphertext.

Natural language has a quirk where letters are more likely to be repeated. If you calculate the percentage of letters that are repeated, this gives you the incidence of coincidence. Incidence of coincidence is preserved by a partial Enigma key. So in that particular plaintext, all those repeated UUUs, those repeated NN, those XX and TT, those will light up like quasars.

Incidence of coincidence analysis should just tell you outright what all of the rotor settings are. From then you'll need someone familiar with German and the code language to be able to figure out the plugboard settings, but that's not as difficult as you might think.

Rather than raw letter frequency, more powerful is frequency of digraphs, and that surely does not appear random in that context, instead spiking with common digraphs such as IE, EI, UN, NU.

Also going for longer cribs such as NUL, EINS, ZWEI, DREI etc proves generally fruitful. There is also a story about the crib HEILHITLER toward the end of a message being particularly useful for code breakers but I don't know if that is genuine or contemporary disinformation to cover true code breaking capabilities, akin to the story of carrots being good for darksight[1] as cover for improved radar capability.

[1] https://www.smithsonianmag.com/arts-culture/a-wwii-propagand...

As mentioned elsewhere, a signature of enigma ciphertext is that a letter can never encode as itself.

This gives you some crude form of error checking.

The rest of it as you mentioned makes it difficult to determine, data mining the possible results for common abbreviations from other plaintext could narrow.It down.

That doesn't help at all because every key you try will lead to a candidate plaintext with no letters in common with the ciphertext.

I’m not sure being German or from 1945 has much to do with this. I’d think if I had some candidate plaintext that looked German and where a letter didn’t map to itself it’s likely to be right.

Sure, you could argue that it’s not quite as unambiguous as JSON but, in the realm of all possible plaintext, I’d say JSON and 1945 German aren’t too far apart in terms of likelihood of getting a false positive on a string of non-trivial size.

If you want a bit more certainty you could just try it on another string (which is the next step in the process either way), and then another. At least to me the constraints of “German and a char doesn’t map to itself” seem like pretty limiting factors here.

I don't think it's as simple as you're assuming. The "char doesn't map to itself" is a feature of the hardware design, there's no such thing as a key that allows that to happen so it doesn't reduce your search space. But additionally, the messages were extremely terse (~250 character limit), had no punctuation or spaces, and only had the 26 alphabet characters. Depending on the message in question it already doesn't look much like German, and the ones writing these messages also purposely vary their spelling/names/wording to make it harder to analyze. IMO the chance of finding "potentially plausible messages" seems higher than you'd want if you're starting with zero idea what the plaintext is supposed to be.

Why was there a character limit? I always thought the only limit was the slow transmission speed of morse messages.

From what I have read it was specifically to make it harder to decrypt the messages :D Longer messages are easier to analyze.

Interesting. That probably does makes it a bit harder to verify but there are still plenty of “words” that are to be expected. My point being that if a German receiver can’t parse it, then what’s the point of send it. And if they can parse it we can encode the rules they’re using to parse it (i.e. at the very least a dictionary of “words”) to give us some decent confidence. And beyond that, using the key on multiple messages effectively increases the char limit to “max chars * message count”.

Also, I agree it doesn’t reduce the search space but I think the post I was replying to was talking more about difficulty of verifying the correctness of a decrypt that reducing the search space. That was definitely my point ant least. Either way, as you say, this definitely doesn’t reduce the search space.

It would be awesome if there's a message that when decoded incorrectly said "Drink your Ovaltine", but when decoded correctly was a different message

Remind me of “Deniable Encryption”[1], where a single encrypted input decrypts to multiple plausible plain texts (including the real one, obviously) so that, if, for example, you were caught and asked to decrypt it, you can decrypt to the non-incriminating version.

[1] https://en.m.wikipedia.org/wiki/Deniable_encryption

You validate the same way they did back in the 30s and 40s. You use Cribs.

https://en.wikipedia.org/wiki/Known-plaintext_attack

Worse than that: there's no authentication tag!

When it says something funny and german

I mean I'd use known text of other messages to get some likely statistical properties of the message.

I'd make a fast approx check for some of these properties that can run during brute force, then feed anything that passes that check to a better check, then finally to a human (maybe nowadays put an LLM before the human stage).

There's a chance to miss the translation if it doesn't match other messages but this seems like a decent approach.

It’s an interesting question, but mechanical rotor encryption machines fell out of favour reasonably quickly after WW2 (early 1960s?) - which suggests that even with the limited computing resources of the time they were no longer secure ie you don’t need brute force to crack messages, some other cryptanalysis technique could do it.

Edit: Though it might have been that purely electronic cryptographic machines were just cheaper and stronger by that point.