## Enigma Encryption Vs. Modern Computers? 6

Posted
by
Cliff

from the distributed.net's-next-project dept.

from the distributed.net's-next-project dept.

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 (Score:3)

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 (Score:2)

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... (Score:2)

## Recommended reading (Score:2)

## Breaking crypt(1) which is a modified Enigma (Score:2)

-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.h

## Correction (Score:2)

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

muchmore 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.--