[evan_au]

There were (I guess) hundreds of Enigma machines, each of which was  used for many messages each day- perhaps hundreds a day.

It was not quite that hard.

The code book used by the army told all of these hundreds of machines to use the same rotors, in the same sequence, and the same plugboard settings (so all these machines could communicate with each other). Crack one message to obtain these settings, and you will easily crack all other army messages for that day.

To crack the first message of the day, they picked a message that was the right length for “nothing to report”, and used some idiosyncrasies of Enigma to significantly reduce the space of possibilities (eg the Enigma would never translate a letter to itself - what sounds like a strength was a crucial weakness!).

The navy had more rotors and a different code book than the army.

[Bored chemist]

Nah. You don't need anything like 1000 clock cycles to prove that a particular guess is wrong. Most of them will fail in six memory lookups at the first hurdle.

OK,  for the sake of discussion, here's the start of an encrypted message
KLBV MUTJ TUG
Can you let us know how you would go about decoding it.

[wolfekeeper]

Did you start the plaintext in the conventional way, with the stationcode repeated?

[Bored chemist]

No, but I can if you like.
Alternatively, feel free to come up with your own test data and show us how the process would work.

[wolfekeeper]

The thing is, even with brute force you still have to have a model of the plaintext data.

In addition you don't have enough letters in your plaintext. Because it's shorter than the keyspace, it's probable there's multiple valid plaintexts that could produce that encrypted output.

If we model the plugboard as an array P() and the wheel N's settings as WN() then a single round of the enigma is just:

P'(W1'(W2'(W3'(R(W3(W2(W1(P(x)))))))))) which is 9 lookups, i.e. 9 cache lookups.

And Enigma is symmetric, that's also the decoding pattern, so in around 18 lookups you can run the decryption process twice, and compare the first letter of the stationcode. And with some slightly sneaky modular maths I think you can bring that down to 9 lookups. And, as I noted, most processors are superscalar, and heavily pipelined, so they can test (say) 6 or 8 in parallel depending on how many cores there are in the processor. Given gigahertz clock rates, that is about a billion tests per second.

[evan_au]

P'(W1'(W2'(W3'(R(W3(W2(W1(P(x))))))))))

Did you begin as a LISP programmer?
LISP = “Lots of Infuriating, Stupid Parentheses”

Or is this Functional Programming?

9 cache lookups

But seriously, I am not sure you can do it as a simple table lookup.
Enigma is a polyalphabetic cypher, ie after every letter, the rotors clicked around, creating a different letter translation, ie a different lookup table?

[wolfekeeper]

The lookup is just, in C:

rotorArray[rotorPosition + inputCharacter]

You can avoid having to worry about index overflow by making the array big enough (36*2) and repeating the rotor wiring settings on the end in the array, so you don't have to test for it or do modulo arithmetic on it.

Only the first rotor clicks on in most cases. You do have to worry about that but it doesn't change the order of magnitude of the answer; in most cases the second rotor doesn't click on.

edit: it's actually likely to be less than 9 lookups; you can cache a single lookup table for all the centre W2'(W3'(R(W3(W2())))))) permutations and reuse that over and over; that should bring it down to 5 lookups.

[Bored chemist]

The thing is, even with brute force you still have to have a model of the plaintext data.

In addition you don't have enough letters in your plaintext. Because it's shorter than the keyspace, it's probable there's multiple valid plaintexts that could produce that encrypted output.

I know.
I also know I'm not the one who said " Most of them will fail in six memory lookups at the first hurdle."
So, show me how most of the zillion possibilities are excluded in 6 lookups.
Or accept that your assertion was- shall we say- optimistic.

It would also be instructive to see how many clock cycles it takes to actually "run" this
P'(W1'(W2'(W3'(R(W3(W2(W1(P(x))))))))))
I suspect it's over 1000

[wolfekeeper]

The thing is, even with brute force you still have to have a model of the plaintext data.

In addition you don't have enough letters in your plaintext. Because it's shorter than the keyspace, it's probable there's multiple valid plaintexts that could produce that encrypted output.

I know.
I also know I'm not the one who said " Most of them will fail in six memory lookups at the first hurdle."
So, show me how most of the zillion possibilities are excluded in 6 lookups.

The standard way that the Enigma was used was that the beginning of the plaintext was 3 characters, repeated.

So if you run a trial decrypt on the first and 4th character, and they aren't the same, then you've ruled out those settings and you can go onto the next.

Except when the rightmost wheel has rolled over and bumped the next wheel, which for the sake of this not being a cryptographic forum, only the rightmost wheel has moved.

So if: P'(W1'(W2'(W3'(R(W3(W2(W1(P(e1))))))))))  != P'(W1+4'(W2'(W3'(R(W3(W2(W1+4(P(e4))))))))))

Then you can stop immediately, and go onto the next wheel settings.

And that's the typical case: that they DON'T match. If they do match, you check the next letter of the station code, and only if they match do you check the third. That reduces the amount of work done per setting by thousands. If the result is a plausible station code then you can perform a much longer check on the rest of the alleged plaintext looking for plausible bigrams.

It would also be instructive to see how many clock cycles it takes to actually "run" this
P'(W1'(W2'(W3'(R(W3(W2(W1(P(x))))))))))
I suspect it's over 1000

Nah. It's 6 additions and 9 memory lookups, there's pipelining so the additions and lookups will happen in parallel, and the table lookups should fit in the on-chip caches. If they don't fit, then yes, it would be very slow, and you've picked the wrong processor for this workload. Also, processors these days are superscalar, so you can write the code to run several decode attempts running in parallel on different cores, this kind of thing parallelises really, really well.

[homebrewer]

Dear Wolfekeeper, respect for such an investigative and analytical mind... what a great effort.

I was born in Germany, and many students wanted to know how the Enigma code was broken, and to simulate the software on an IBM box. This was just a great fun part.

In reading about the Blechtley code people, they where the true Heros, using Relay logic, to do work which had never previously been done. Think, if their relay circuit was able to run at 1 hz per second, how long would your mainframe take with a similar clock rate.

What would you do, if you had to program your main frame with a patch panel, in machine code....?? You would be burning plenty of midnight oil...  even today.

[syhprum (OP)]

To be pendantic you don't run at 1 Hz per second Hz is the measure of frequency the per second is implied

[wolfekeeper]

It would also be instructive to see how many clock cycles it takes to actually "run" this
P'(W1'(W2'(W3'(R(W3(W2(W1(P(x))))))))))
I suspect it's over 1000

I coded it up in C and compiled it and ran it. It performed 1.76 billion encryptions in 44 seconds, which works out at about 25 nanoseconds per encryption on a single core. That's running on a shitty netbook Intel Atom processor with 1.4 Ghz clock speed.

This compares to the WWII bombes which could check up to 52 per second, and is 700,000 times faster, running single core, and should be nearly 3 million times faster multicore, but I couldn't be bothered to test that.

The two results are not entirely equivalent though, the bombe could be wired up using a diagonal board, and that should run a few times slower than this on a modern processor if you simulate that, but you wouldn't do that for a brute force attack.

[evan_au]

this not being a cryptographic forum

Could you post a link to a cryptographic forum, please - I am interested in how these cryptic brute forces spend their surplus cycles!

[evan_au]

with modern computers?

If you wanted the decryption algorithm to run even faster, you could compile the decryption code to an off-the-shelf programmable logic device like a gate array chip - ie put it in hardware. You can stack a lot of these chips in the space taken up by a general-purpose laptop.

If you had to do a lot of decryption using an established algorithm, you could produce a full-custom chip to implement the algorithm in hardware. The first one is more expensive than buying a commercial gate-array chip, but much faster for this one algorithm.