This thread reminded me of a question I’ve wondered about for a while - using contemporary cryptographic methods and state-of-the-art hardware (and with an “infinite” supply of encoded messages to study), how long would it take to crack ‘Enigma’?
Your standard Enigma machine had three rotors with 26 positions each, which means a total keyspace of 26[sup]3[/sup] = 17,576 possible keys. The “bombe” machines used at Bletchley Park performed a simple brute-force attack, trying every possible key and saving the ones that produced results that looked like German.
To a modern computer, 17,576 keys is nothing. I’m not too familiar with the Enigma cipher, but I imagine you could test all the keys on a short message in less than ten seconds.
Actually upon further research it appears I was incorrect. The attack was not strictly brute-force - the cryptanalysts would provide candidate plaintext and see if any of the keys produced results that might match.
There are different levels of difficulty possible, depending on what sort of breaking (and what sort of Enigma machine) you have in mind. For every keystroke an Enigma machine sends a signal through a plugboard (implementing some number of character transpositions); then through some number of rotors (typically 3, but more in some cases), each of which implements an arbitrary permutation; then through a reflector, which implements a transposition of character pairs; and then backwards through the rotors and the plugboard. The rotor position is then adjusted in some way (originally in a way something like counting in base 26; some later machines had multiple carry notches) so that the next permutation will be different.
Each rotor implements one of 26! permutations (not even considering the carry notches). This is large enough to be out of reach of rapid brute-force search, even for a single rotor and considering specialized hardware. So brute-force search over the whole keyspace is infeasible. However, I believe that with more intelligent techniques this is still considered solvable.
But if you (like the Bletchley Park cryptanalysts–thank you, Poland!) have access to an Enigma machine, so that you know the permutations implemented by the rotors and reflector, you’ve vastly reduced the keyspace. What’s left is the choice of rotors and reflector (a fairly small number, for any number of rotors that would be reasonable for a portable hard-wired electric machine), the initial rotor positions (the settings friedo mentions), and the plugboard (“Stecker”) settings. This last factor is still quite large (~10[sup]14[/sup]) and not amenable to brute-force search on a general-purpose machine, though it would be possible on specialized hardware.
However, the Stecker permutation is constant over a message, so if messages (with the same Stecker settings) are sufficiently low-entropy, probable settings for the rotors can be guessed without knowing the Stecker settings. Then more intelligent techniques (much like a cryptogram) can be used to figure out the Stecker settings. This is quite feasible on a modern PC.
Here’s a previous thread on the exact same topic. Some good responses.
Somehow got the wrong link.
Try again.
http://boards.straightdope.com/sdmb/showthread.php?t=323603[/url
That’s better.
I just told my students about this all day yesterday. 17,576 is the period of the keystream, not the number of keys. The rotors can also be rearranged (6 choices with three available rotors, 24 with four like they used later on). Then there’s the plugboard, which chooses six pairs of letters to swap at the beginning and end of the encryption. That’s
((2625/2)(2423/2)(2221/2)(2019/2)(1817/2)(1615/2))/(654321) =
100,391,791,500
plugboard settings, for a total of
42,347,667,057,696,000
Which is actually not that far off from DES’ 2[sup]56[/sup], or
72,057,594,037,927,946
keys.
See, I’d consider the actual rotors in use to be part of the method, and thus a cryptanalyst knows them by Kerchoffs’ principle. Another thing I’d consider part of the method is weaknesses in implementation.
If you always encode every message with the day key, then a frequency attack can be mounted against the first letters of all the messages of a day, then the second letters, then the third, and so on. So, what the Germans did was pick three random letters. Say the day key was 2K3C1S, meaning that the second rotor in position K was on the left, the third in position C was in the middle, and the first in position S was on the right, as well as some plugbord setting. Then pick, say, “rfu”. First, the sender encodes RFU with the day key. Then he leaves the rotors in 2-3-1 order and leaves the plugboard alone, but sets the rotors to positions R, F, and U. Then he encodes the actual message.
Really, the sender encoded RFURFU, since a mistake in the message key would render the message completely useless. The problem is this: if the encrypted message begins VBOFDA, then we can tell that the initial settings’ permutation followed by the fourth character’s permutation sends V to F. Similarly, the second character’s followed by the fifth’s sends B to D, and the third’s followed by the sixth’s sends O to A. After gathering a lot of messages from a day you can figure out those three compositions (P[sub]1[/sub]P[sub]4[/sub], P[sub]2[/sub]P[sub]5[/sub], and P[sub]3[/sub]P[sub]6[/sub]) independently of the message keys. Now, it turns out that by finding the lengths of cycles making up each of those three you can narrow the day’s rotor settings down to 26. At that point it’s all the plugboard, which amounts to a relatively simple substitution cipher. So, find all 26 possibilities and attack each one like a substitution cipher. Simple.
Would that be Gaudere’s Coding Corollary?
Grim
Weren’t they using 5 rotors by the time the war started (with even more on Naval Enigmas)?
even with the fixed link, that links to this thread
I think the unit the polish govt supplied to the british govt had 3 rotors , the fourth one was added sometime in 1941/42 , but one of them had to do with weather stations for U-Boat purposes.
Declan
And of course the sheer number of keys isn’t necessarily a factor in how easy a cipher will be to break (unless you have a machine doing a brute force attack, not looking for patterns). A simple substitution cipher has 26! keys (4x10^26), many orders of magnitude higher than 2^56 (7.2x10^16) and I bet your students can break one in a short time with pencil and paper.
There were more choices than that. As grimpixie says, there were originally 5 rotors (3 chosen); some later Naval machines had 8-choose-4. (There was also a choice of reflector.) Also, I don’t think the plugboard was restricted to 6 pairs. The combinatorial maximum is at 11 pairs, but I think 10 pairs was more common.
For the original Enigma machines, I would mostly agree (though note that not all Enigma machines used the same wiring; if you are dealing with Enigma ciphers from various sources, this is not necessarily a trivial assumption). But in talking about an “Enigma class” of rotor cipher machines we could imagine reconfigurable rotors, perhaps changed periodically. (I’ve seen it stated that this was in fact done on later versions of the Enigma.) In that case it becomes part of the key and not part of the fixed algorithm. (Though I wasn’t very clear, this is what I meant by “what sort of Enigma machine” in my earlier post.)
Yes, those seem to be what kills most ciphers.
On this same subject, if my laptop were to be transported to 1930-something Britain, would it be useful in attacking the real Enigma?
I think you’ll find that it was cckerberos who said that, but now I’m kinda wishing it had been me… 
Grim
Are you assuming that the people back then would know how to use it to full advantage? I’m sure that it could provide valuable computational support to the already established code-breaking system. But as a device, it might only shorten some of the drudge-work rather than provide any new capabilities.
It sure would. I had a hard time finding a “speed” on the Bombe as it wasn’t a computer as we know them today with a CPU. It was a mechanical device and incorporated moving parts (lots of rotating drums mainly). Anything like that (moving mechanical parts) is going to be significantly slower than purely electronic means. If we assume that the guys back then could master modern programming languages (pretty smart guys so they probably could) then your laptop would have been an enormous help. Not only that, being able to re-write the program on a laptop is far easier to adapt and try different ideas of breaking the code than rewiring the rather complex Bombe. So yet another benefit.
As you can see below even an “old” computer running at 350Mhz would be 60x faster than the Bombe. I’ll let someone else figure how much faster a modern PC with, say, a 2Ghz processor would be.
[quote]
This high speed simulation of a Turing Bombe has been developed to enable the breaking of real Enigma intercepts in a reasonable time.
It has been written in compiled Modula 2 code and at maximum speed on a 350 MHz PC runs about 60 times faster than the original 1940’s Bombes. It takes about 20 minutes to go through the 60 wheel orders for the Army/Air Force set of 5 wheels. There may be faster simulations, but this one contains all the details required to exactly simulate and demonstrate the real Bombe.
SOURCE: Virtual Wartime Bletchley Park [//quote]