Enigma Encryption Vs. Modern Computers?

wynlyndd asks: "The story about the recent theft of the Enigma machine has got me wondering. Right now we have a distributed network of machines trying to crack an encrypted message. This has taken hundreds of machines hundreds of days and we have hardly dented the available keyspace. How long would it take a modern desktop computer to solve the Enigma codes?" Most assuredly nowhere near as long as it will take to crack RC5...but I digress.

Cryptanalysis of Rotor Machines

[intuition]

First of all, people always speak of being able to brute force crypto algorithms. The real world feasibility of brute forcing a crypto algorithm is typically very low.

Consider Dk[C] = P : that is decryption function D using key K on ciphertext C to get plaintext P.

For every key K that you try in a brute force approach, you are going to produce a unique* plaintext P. All these stupid contests like distributed.net know what the beginning of the plaintext P should look like. Typically the beginning of plaintext P in a contest like the one previously mentioned is "The secret message is : "

Hopefully you see what I am getting at by now, every time in a brute force attack you try another key you are going to get another unique* plaintext. How are you going to check them all? Even if the plaintext is known to be ASCII english this is no trivial task. But what if plaintext P is just a number, for example a bank account #. Literally every possible key is going to produce a unique* number and there is not much to tell you which number is correct.

Anyways, I am just trying to put some perspective on these so called brute force attacks that have "cracked" certain algorithms.

As for the enigma rotor, I believe there is 5 rotors with 26 charachters each. 26^5 = 11,881,376 possible keys. Keeping in mind the limitations of brute force attacks, the only real method to crack this encryption is cryptanalysis.

D. Kahn wrote in "The Codebreakers: The Story of Secret Writing" :

"A period of that length (26^5) thwarts any practical possibility of a straightforward solution on the basis of letter frequency...The cipher text would have to be as long as all the speeches made on the floor of the Senate and the House of Representatives in three sucessive sessions of Congress."

Oh yeah about my * for unique, i meant relatively unique depending on the properties of the encryption function. Most are designed to have this property. (obviously)

William Stallings points out in Cryptography and Network Security principles and practice that the real modern day significance of the rotor machines was the implementation of using multiple rounds of encryption (i.e. multiple rotors) to strengthen the encryption. This is what DES does.

It is my belief that if you know enough about the workings of the rotor machine the problem becomes as simple or as hard as solving systems of linear equations.

So my final answer for a million dollars is :

(26^5) decryption cycles which can be done relatively quickly, but ~ 11 million possible decryptions which could be sifted through very slowly.

Brute Force

[Xamot]

Using the "Brute Force" method is an effective method of cryptanalysis. It just isn't a very good one. You will most likely get more than one possible solution and without some sort of crib you may not know which one is correct. This is what makes the One-Time Pad [everything2.com] effective.

These Distributed.net contests aren't that stupid. They do show what is possible if you do have a crib. Initialy Enigma [everything2.com] was broken by the Polish because they got a hold of the schematics and some german codebooks. They were able to find out that the first three letters were the same as the next three lettters and those were the rotator settings for the rest of the message. (the first enigma machines only had 3 wheels in use at one time) Because they knew this repetition existed they were able to create machines that could "Brute Force" those 6 letters. But they still had to look to see that they created a readable message. Turning took this information and many decrypted messages and figured out a way to decipher engima messages without this repetition because he knew the germans would eventually realize that it is a weekness. And they did! To crack these new messages Turning used cribs, guesses at what words would be where in the message. See Turing realized many messages the germans sent adhered to a strict standard format. IIRC especially some weather reports that were sent out at the same time everyday. Knowing the format of these messages and which messages (of the many messages that are sent during a war) turing was able to create a machine that could use these cribs to find the key to the message.

I haven't read Kahn's book yet, but I want to. I have read The Code Book [everything2.com] by S. Singh.

--

Silly...

[randombit]

Don't be ridiculous. Not only is the Enigma keyspace very small by modern standards (I don't see how it could possibly exceed 2**32 or even 2**24 keys...), but the algorithm is also very weak (by modern standards). The Enigma was broken in the 40s using lots of ciphertext and "guessed" plaintext (ie cribs). Any algorithm used today would be considered broken if the same were possible on them. Some can withstand attacks using 2**128 known plaintext/ciphertext pairs... Enigma is interesting historically, and even technologically (to see what the Allies had to do to break it, etc), but it's not something that useful today.

Recommended reading

[unitron]

Two other books of interest in this general subject area are "The American Black Chamber" by Herbert O. Yardley and "Piercing the Reich" by Joseph E. Persico. The first is about early 20th century U.S. codebreaking (and the idiots in the U.S. government who did their best to make it impossible) and the second is about the O.S.S. (Office of Strategic Services), World War II precursor to the CIA and NSA, and includes some pictures and info on the Enigma.

Breaking crypt(1) which is a modified Enigma

[fiji]

The crypt(1) command (not to be confused with the crypt function used for passwords) is a modified Engima. It is relatively easy to crack and there are toolkits[1] available for it. It is possible to make it more secure by compressing your plaintext thus transforming it from ASCII to binary and making it more difficult to detect a successful decryption. Spafford[2] talks about this in more detail.

-ben

[1] Crypt Breaker's Workbench: http://axion.physics.ubc.ca/cbw.html

[2] Practical Unix and Internet Security: http://secinf.net/info/misc/orelly/puis/ch06_06.ht m

Correction

[Xamot]

When I said Because they knew this repetition existed they were able to create machines that could "Brute Force" those 6 letters. But they still had to look to see that they created a readable message. I really should have said that those machines they created tried every initial wheel setting and combinations of wheels till they found ones that matched the ciphertext. (I'm leaving off the plug-board settings because I don't remember off hand how they worked those out, but I think they found a way to negate their effect) Since their was a possiblity for multiple keys and multiple decryptions of the 3 letters, they took each guess at the 3 letters and decrypt the rest of the message using the 3 letters as the key. If the message isn't giberish they take the original key and try to decrypt other messages with it to get their 3 letter keys followed by an attempt to decrypt the rest of those message with their own 3 letter key.

As you can see this is a lengthy process and can understand why it took so many people at Bletchley park to do it. Even with the help of machines it was difficult. And as somebody else pointed out the keyspace for Enigma is extremely small compared to today's standards.

Most recent advances in cryptography have come from Diffie-Hellman and RSA type advances (called public key encryption or asymmetric ciphers). Which deal more with key exchange then the mangling of the message itself. Even DES and other newer symmetric ciphers are still basically substitution ciphers. Where one thing is substituted for another. The algorithms to do the substitutions have gotten much more complex and the keyspaces have gotten larger, but the basic principle has stayed the same. The fact that the mangle(encryption) and de-mangle(decryption) could be different algorithms was a huge advancement, but unfortunately as of yet these are very slow algorithms to implement and so usually RSA is used to exchange a DES (or some other symmetric ciphers key) to do the encryption of the actual message with.

--