How to deduce enigma settings given a partial plaintext?

Assuming some large block of text is encrypted with an enigma machine and I only know a small subset of letters before and after encryption, how do I go about figuring out the enigma settings from this point?

-
Nice try, time traveling Alan Turing. –  Ethan Heilman Oct 28 '11 at 14:43
The first result I get when I search Google for "enigma cryptanalysis" is the Wikipedia article on Cryptanalysis of the Enigma. Do you have some specific question which it (or the other search results on the first page) don't answer? –  Ilmari Karonen Oct 28 '11 at 20:30

1 Answer

According to "Applied Cryptanalysis", the theoretical keyspace of Enigma is approximately $2^{366}$, but due to practical limitations, Enigma as used by the Germans only had a keyspace of approximately $2^{77}$. Given the power of some of the clouds out there (with GPUs and all), I bet you could do a brute-force attack of the 77-bit key space in a reasonable amount of time. Deep Crack could brute-force the 56-bit key space of DES in about 4.5 days. I'd think we could do much better than that today.

If you had a machine 100 times faster than Deep Crack, it would take about 265 years to do the brute force. If you had a thousand of these machines (not unrealistic given cloud computing), you could brute force it in 96 days (10000 machines would make it 9.6 days).

Since you are given a partial plaintext, however, I would think you could even do much better. Cryptanalysts during the war were able to do much better than brute force because of a protocol failure. The people enciphering messages would encrypt a session key with the daily key. They repeated the session key due to transmission errors. This allowed cryptanalysts to do statistical analysis once they had multiple messages captured from the same day. Without additional information from the OP though, it is unclear whether similar protocol weaknesses could be exploited.

-
@EthanHeilman, I hadn't plugged the number when I wrote my answer, so I wasn't completely sure. I did just run the numbers, however, and got 265 years. For my math, I did 4.5 days is s=388,800 seconds. So I took $ops = 2^{56}/s$ to get operations per second. I then did $2^{77}/(ops*100)$ to get the number of seconds for $2^{77}$ operations and assuming a machine 100 times faster. I then converted the answer to years. Am I doing something wrong? –  mikeazo Nov 1 '11 at 21:54
Yeah, my bad, I redid my calculations and ended up with the same answer as you. –  Ethan Heilman Nov 2 '11 at 15:36