Modern Computers and WWII Codes

Last March, during vacation in England I got to seeAn Enigma Machine. It was the German encryption system for their armed forces but was broken wide open by the allies which contributed heavily to the allied victory.

My question is how quickly and easily do you think it would be for a modern, one Gigahertz processor to crack and decode enigma transmissions, starting from nothing? No previously decoded materials or other references than the actual coded transmissions. Assuming that this would be attempted by an expert crypto-analyst who could properly program and operate the computer.

I’m interested in the answer to this, too. I think it would be harder than you think, because if one literally had no clues, then there are a large number of different ways that the message could be encoded, and you have to check all of them. Enigma is particularly annoying in this respect, as the encryption setting changes for each letter depending on what the previous letter was (if I recall correctly).

I believe that the Allies fairly rapidly got their hands on the Army-issue Enigma machine (around 1939), which gave them various helpful hints. It was only after this that the computing machines came into anything, as they were used to decode captured messages using a small range of possible key settings determined from other data. I am not a crypt-analyst, though, so let’s hope one happens along soon.

I’m thinking that the pure speed of the 1 gig system would be able to bull its way through many of the possibilities through sheer dogged trial and error rather quickly. At least it could narrow down the possible encoding techniques by determining some of the ones that are not used.

from This site

Blimey! I’m guessing that the original code breaking computers were very specialised, you could possibly regard them as code breaking hardware I don’t think you programmed them as such, you recofigured the wiring to fit the current problem/job.

"a modern Pentium PC programmed to do the same decoding task took twice as long to break the code. "

I don’t know, but that is an unsupported statement. No specifications about speed of the processor (yes it’s a pentium. But how fast?) Or just how it was programmed. If you took out much of the crap built into an operating system and had the processor working just on the code breaking the results might be very different.

On the other hand, there is something to be said for parallel processing, even at primitive levels. A couple of slow 486 chips operating in parallel can perform things like digital image processing faster than a single uber-chip. Code breaking might be similar in that it is a (long) series of simple repetitions.

If I remember correctly, the codebreakers had several clues.

I think one German transmitter used to regularly repeat each message, which is a real bonus.
Plus the Brits recovered a code book from a German submarine (which of course Hollywood turned into a film with an American hero :rolleyes: )

Without these to help, you would presumably try all combinations of codes until you hit some German words.
Bear in mind the wartime ‘computing’ was incredible slow by modern standards.

Spot-on. Not only were the cryptanalytic “bombes” hardware, they were electro-mechanical. The early ones used motors and rotors - not too dissimilar in concept from a motorized Enigma. Later ones were developed by Bell Labs and were based on telephone switching relays. Oddly, the relay-based Bombes were much slower than the rotor-based ones.

Other useful goofs by the Germans - one particular operator persisted in using he girlfriend’s name - Cillie - for his message keys. Messages keyed with silly keys like CILLIE, HITLER or BERLIN came to be known as “Cillies”

Head over to http://www.nsa.gov/history/histo00007.cfm to find more info on Enigma in the WWII section.

But they weren’t starting from scratch.gotpasswords and glee pointed out a couple of major helpful hints. Also the machine itself was the product of a line of research aimed at producing exactly the result it did. A modern pentium is built for a lot of things (well, gaming mostly) but cracking codes isn’t any of them.

hold on there though, the OP specifically stated that it would programmed for crypto work, so in essence you’d have a very powerful processor specifically TASKED for the job so its not like you’d be using generic off the shelf programs.
Given that, wouldn’t it be more likely that the modern machine would be doing the same thing (decoding-wise) as the old machines, only much much faster?

I’m not a programmer, but would it be possible to take the encoded German messages and try to decode them using a dedicated program on a modern PC?

There’s a very good chapter on this in “The Code Book” by Simon Singh (“The Mechanisation of Secrecy” and “Cracking the Enigma”).

The Poles were the real heroes in initially cracking this code. The design of the Enigma was betrayed to them by a German traitor (via the French), but of course they didn’t have the so-called “day-keys” from which the Enigmas would be initialised. Their most important code-breaker (Rejewski) used the fact that the German operators always sent a so-called message-key twice as the start of their transmission, which the recipient was intended to decode with the day-key and re-initialise the machine.

From many messages each day (and each sharing the same day-key) Rejewski was able to determine the decryption required, and could read all Enigma traffic until 1938, when the Germans upgraded the design. In 1939 their methods and a replica Enigma machine were transferred to the British.

Initially the British just used more resources and refined the Polish methods (effectively making systematic use of better guesses of the message-keys). Soon they moved to methods that didn’t depend on the repeated message keys, but used patterns that arose from the known design of the enigma and the expected presence of certain encrypted words.

Code-books were stolen from the Germans to assist in cracking the more complex version of the Enigma codes used by their navy - and I guess the lifting of a naval enigma from a u boat was part of that story.

Anyhow, really this was just a roundabout way of recommending a really good book that covers the history of codes and cyphers from the 16th Century through to PGP and quantum cryptography.

Yeah, the purely mathematical process is what I was interested in. However, it is interesting that the real defects in any cryptographic enterprise are always the human ones. The “Cillies,” stolen books, traitors, and human procedures provide the cracks for the mathmatical crowbars to exploit.

I am wondering just how fast a modern computer could crack that Enigma, though. I’m speculating that the actual math and codebreaking application would be simpler than one might suppose. Just a whole lot of simple, repetitive iterations. Hmmmmm. This might make an interesting thesis for computer programming doctorals. Too bad I don’t know jack about this kind of thing.

This paper suggests that Enigma is relatively easy to crack with modern software.

I don’t know any hard numbers for the Enigma system, so let’s make some assumptions.
First, let’s assume that the mechanism for the code was known. This could be deduced from the capture of a single Enigma machine (encoder or decoder, if there’s a difference). You should never rely on your opponent being ignorant of your encoding scheme, for this and other reasons.
Second, I’ll assume that the modern-day Nazis (or whoever’s sending the messages we want to crack) is following the custom of repeating the message.
Third, I’ll assume that the repeated message is approximately 1000 characters long.
Fourth, I assume that given the key and the encoded text, one could reproduce the plaintext with no further information.
Fifth, I’ll assume that the alphabet for Enigma consisted of 36 characters (26 letters and 10 digits).
Sixth, I’ll assume, given the examples of “CILLIE”, “HITLER”, and “BERLIN”, that the keyspace consisted of six-character words.
And seventh, I’ll assume that each character in a message would require a small number of basic operations to decrypt.

Now, then. The simplest method of attack would be to systematically test every possible key, and look for one which duplicates the message. There are 36[sup]6[/sup] different keys, or 2.18 billion. For each key, I’ll have to decrypt the entire first copy of the message, but it’ll quickly become apparent if the second message is not a copy after only a few characters, so I’ll only need to decrypt just over 1000 characters on average. And I’ll be conservative and say that it takes 3 clock cycles per character (though most modern processors can do several basic operations per clock cycle). This comes to 6.53*10[sup]12[/sup] clock cycles. Assuming a 2 GHz processor, this is less than an hour.

Now consider: First of all, the average time will be half of this, since sometimes you’ll find the right key more quickly than others. Second, this algorithm will parallelize very smoothly (just divide up the keyspace between your computers), so if you have two computers, it’d be a maximum of half an hour, ten computers will be a maximum of six minutes, sixty computers would take less than one minute, etc. Third, this is a very simplistic algorithm, and you could speed it up in a number of ways (searching German words first in the keyspace, checking for German words as opposed to gibberish in the plaintext candidate, etc., as well as any special tricks which might be made possible by a detailed understanding of the code). And an hour is probably not too shabby, anyway.

I understand from the book to which I referred that the “simple” (non-navy) version of enigma generated 159 000 000 000 000 000 000 scrambler settings to check.

You’re right about the power of computers to help of course: that’s exactly what they evantually did with Colossus, which I think was the first programmable electronic computer, but they needed mathematicians like Turing to devise ways of making the problem tractable.

I guess I agree really, but I just wanted to mention that the problem was bigger than 2.18 billion keys to check in practice (I think that the cillies were only 3 letters, by the way).

Chronos,

You’re my hero.

Well, this is not exactly the same but I had to crack my sisters Win XP or 2000 password. She set it to a 20 some odd character alpha-numeric-charcter password and promptly forgot it. Using a brute force cracking program it calculated that it would have taken like a number of months*. This was on a PII. This was using the full character set a-z, A-Z, 0-9 and all the special charcters like $%^&.

Brute force would take a while but it would depend, I think, on how many segments you had for the program to use for comparison. But I could be wrong.

Slee

I don’t remember exactly how long but it was way over a month, more like 6. I got into the machine in about 30 mnutes. It took 25 minutes to find a utiliy that would overwrite the password in the sam, five minutes to get in reset the password to dumba* and to repair the destop file which it inadvertently hosed up.

Adjust your thoughts upward. A lot. From the NSA, the total number of possible Enigma configurations is approximately 3 × 10[sup]114[/sup]

The full explanation is in The Cryptographic Mathematics of Enigma. The short explanation is that there were as many as eight rotors to pick from, three or four slots to put them in, 26 starting positions to put them in, and a 26-jack plugboard that was used with anywhere from 0 to 13 cables. In operation, the rotors move, but not in the simple one full revolution kicks the adjacent rotor up by one like a car’s odometer.

Also, serving to make cracking harder, messages were supposed to be 200 characters or less, but this rule was frequently ignored.

We’re just lucky that the Allied forces were able to capture some hardware and that the operators made some poor choices when using these machines.

Enigma is pretty easy to simulate. I’ve got a partial program (written in [url-http://www.rapideuphoria.com]Euphoria) floating around on an old backup CD somewhere. I never finished it because it was rather disappointingly easy to simulate and in searching out information on the hardware, I discovered that everyone and their brother seems to have written the same program.

It wouldn’t be that hard to to make a program to crank through possible keys. It would be a bit more difficult to write a program to identify when you were finally cranking out the plaintext. You could do what they did in WW2 and have hundreds of people read the output until they got something that wasn’t gibberish.

Yeah, I’ve written one too, though as far as I know my brother has not.

That part is a little more subtle, but not too hard for English (or similar language) plaintext. The entropy of the true plaintext will typically be much lower than for an incorrectly-decoded text. If you know what language it’s in you can guess at the proper letter and digraph frequencies, and compare the two distributions, or even use a dictionary to look for likely words. An even easier test is counting the maximum-length consonant substring, which is usually ~6-8 for English but is likely to be noticeably larger for long random alphabetic strings.

On another note, if I remember correctly from when I was playing with it, the large keyspace of Enigma is somewhat deceiving. There is noticeable structure to many almost-correctly-decoded strings. For example, a single missing (or extra) plugboard pair will affect only about 1/13 of the characters in the message, giving both a partially readable message and some good clues as to what the plugboard pair ought to be. A misaligned carry notch will also only affect some characters in the message (between where the carry should have happened and when it did happen). Also (as noted in the analysis linked above) most of that huge number (a factor of about 5E92 of the 3E114) comes from computing the number of possible rotor and reflector wiring configurations. For the original Enigma machines, rather than choose any conceivable configuration (for a total of 26![sup]3[/sup] possibilities) the operator would choose three rotors from a small collection of supplied rotors, usually something like 8, for a total of 876=336 possibilities. This whittles down the effective raw keyspace (once the wiring of the supplied rotors and reflector are known) to about 2E24: still too big for exhaustive search on a PC, but reaching feasibility for a modern massively-parallel attack. (Most of that keyspace is in the plugboard settings.)