Bruce Schneier

 
 

Schneier on Security

A blog covering security and security technology.

« Do-it-Yourself Keyboard Logger | Main | Friday Squid Blogging: Semi-Truck of Squid Overturns »

February 24, 2006

Distributed Enigma Cryptanalysis

And you can help:

The M4 Project is an effort to break 3 original Enigma messages with the help of distributed computing. The signals were intercepted in the North Atlantic in 1942 and are believed to be unbroken.

EDITED TO ADD (3/8): One message has been broken.

Posted on February 24, 2006 at 1:38 PM24 CommentsView Blog Reactions

To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.

Comments

I remember reading from applied crypto that enigma was broken. If that's the case how's there still unbroken messages lying around?

Posted by: Ari Heikkinen at February 24, 2006 2:16 PM


@Ari:

I believe the Allied decryption effort made extensive use of cribs -- stereotyped phrases, known message formatting, etc., which they used as presumptive plaintext. They did not perform ciphertext-only analysis, which is what is being attempted here.

Posted by: Carlo Graziani at February 24, 2006 2:24 PM


IIRC, the original enigma also used the previous day's key to encrypt the next day's--so breaking one day meant that all the following days were broken as well, for a particular operator at least, leading to long runs where all traffic was read.

Posted by: Justin at February 24, 2006 2:29 PM


"Seien Sie sicher, Ihr Ovaltine zu trinken"

Posted by: Andre LePlume at February 24, 2006 2:35 PM


@Ari

A code being broken is usually in reference to feasability rather than all messages necessarily having been decoded. For example, a 384 bit RSA key has been broken, proving that does not a reasonable level of security today. That doesn't mean every 384 bit RSA key ever created has been broken, but it could be with sufficient resources.

In this case, we certainly have the computing power available to break these messages today. What's being requested here is for people to volunteer computing power to break these specific messages.

Posted by: Mike Sherwood at February 24, 2006 2:44 PM


@Andre

Classic!

Posted by: Josh O at February 24, 2006 2:54 PM


Well, I've never studied enigma, all I know about it is that it was used by germans during WWII and those three words "enigma was broken" from applied crypto (that was good enough for me to convince the algorithm isn't secure for use).

As far as ciphers are concerned, I'm more or less satisfied being able to code a fast and reliable implementation of AES with C/C++ these days.

Anyways, I just checked the website and it's fascinating. Makes you appreciate the computing power we all have today in our homes for practically free.

Well, it's friday, so time to finish whatever vodka I've left and go to downtown..

Posted by: Ari Heikkinen at February 24, 2006 3:21 PM


Interesting; a manual botnet.

Posted by: bob at February 24, 2006 3:22 PM


@Andre

Seien Sie sicher, Ihre Ovomaltine zu trinken

Posted by: Jo_Jo_Mojo at February 24, 2006 3:33 PM


@Andre, @JoJo:

Or so the Germans would have you believe...

Posted by: David in Chicago at February 24, 2006 4:26 PM


The decrypt checks out on the Model "E" Enigma:

http://www.xat.nl/enigma-e/

I brought the kit home after visiting the Bletchley Park museum last summer. Awesome tour.

It was...interesting, though, to carry a box full of circuit boards and electronic components through airport security.

"Do you have a computer in your carry-on bag, sir? Sir, come this way, please."

Posted by: Joe Loughry at February 24, 2006 5:00 PM


Hey, at least someone didn't plant drugs on you in the airport, so that you ended up stuck in a Manilla jail, talking to a priest and hacking surreptitiously on your laptop...

Posted by: Jeremy at February 24, 2006 5:30 PM


If he'd had drugs planted on him at the Manila airport and had gotten caught and subsequently gone to jail with a priest, he'd eventually have become filthy rich with gold. He'd also possess a Crypt to hide digital information, as well as his own digital currency, in some country nobody knows, which is undeniably cool.

So I think the turn of events would have been good.

Posted by: Bob at February 24, 2006 5:56 PM


@ari:

The Germans had various "groups" (e.g. Atlantic Navy) which would all share daily Enigma keys. Bletchley Park would, each day, try to determine the daily key for each group. They didn't succeed for every group for every day - hence the existence of undecrypted messages.

Possible reasons for non-decryption include the possibility the group was of low priority, had insufficient traffic to analyse, or was at the time too difficult to break.

These are Atlantic Navy messages (U-boats) which were highest priority and intercepted in abundance - however, they had the best Enigma machines (4 rotors rather than 3, and chosen from a larger set of available rotors) and the best security procedures. There were significant periods of time during which the Naval Enigma were not being broken, but all other significant groups were.

Eventually (late 1942? I forget) they were broken and stayed broken. Had the Allies wanted to, they could have retroactively broken the messages from the "dark period", but presumably felt it was not worth the effort (which would have been great.)

Posted by: Filias Cupio at February 24, 2006 9:17 PM


@Jeremy & Bob
That'll never happen - unless your ancestors hang around with Newton.

(Sorry - I know Cryptonomicon references are on-topic for this blog, but the Baroque Cycle might be a bit of a stretch).

Posted by: Alan at February 24, 2006 11:44 PM


If you want to read more about Enigma but would find a history book dull, read Robert Harris's thriller Enigma. It was a best seller and for a good reason. It's a wonderful read and is more enjoyable if you're a techie because although it is a work of fiction, all of the Enigma and math elements are factually correct.

Posted by: Gruff at February 25, 2006 4:09 AM


Could this method be used to decrypt the unread VENONA messages (of which there are many)? NSA has the decrypted and translated VENONA messages on their website, but are the originals available anywhere, especially the undecoded ones?

http://www.nsa.gov/venona/venon00017.cfm

Posted by: Tinker Tailor at February 25, 2006 10:41 PM


Be aware that there are some slight errors in translation from the German of the recently cracked M4 message. I sent a correction.

Posted by: Stu Savory at February 26, 2006 11:19 AM


@Filias

"Had the Allies wanted to, they could have retroactively broken the messages from the "dark period", but presumably felt it was not worth the effort (which would have been great.)"

How would they have done this? Unless the new traffic revealed a crib to some older messages then surely they would have no more information to attack the messages retrospectively than they did at the time they were received.

During the war Enigma was never broken due to pure cryptanalysis, breaks required either a crib or were enabled due to poor practice by a German operator. The continued reading of naval Enigma following the initial break was primarily due to a heathly supply of cribs, perpetuated by continued reading of the traffic, not due to a new breakthrough that would have allowed retrospective reading of messages.

Posted by: Weasel at February 28, 2006 7:59 AM


I wonder how "secure" Enigma actually is, that is, how many "PC-weeks" of processing power does it take to brute force the entire keyspace?

Posted by: Grin-Mouse at February 28, 2006 9:27 AM


Enigma - was that a Turing machine?

Posted by: Anonymous at February 28, 2006 9:43 AM


"the Baroque Cycle might be a bit of a stretch."

There's an understatement ...

Posted by: Neal at March 8, 2006 11:03 PM


Help is still needed! The project has broken two messages. A third is being worked on but it looks like it may require more effort.

This project is tackling the problem of individual messages with a modified brute force attack. The allies exploited errors in procedure and bad practice. The machine's cipher key could be attacked in parts, making it easier to break messages in mass. They also used social engineering to help the Enigma operators make mistakes.

Good reading on the Allied efforts:

Codebreakers: the inside story of Bletchley Park, Hinsley and Strip (not to be confused with Kahn's book)

The Hut Six Story, Gordon Welchman

David

Posted by: David (Toronto) at March 14, 2006 5:00 PM


"During the war Enigma was never broken due to pure cryptanalysis, breaks required either a crib or were enabled due to poor practice by a German operator."
That is not quite so, even for naval Enigma.
Not all naval Enigma used the Kenngruppenbuch indicating system. Thus Seahorse (called Bertok by the Kriegsmarine) used doubly enciphered indicators for message keys for almost 5 years, even though the German army and air force abadoned them in May 1940.
This enabled Op-20-G to solve Seahorse, without cribs, using 'query menus' on its double bombes, if there were about 5 messages on any one day. Other naval 'throw-on' systems, such as Porpoise, required more messages. Bletchley Park also solved these systems, but query menus were hard on its bombes.
Why did the Kriegsmarine use such a flawed indicating system? No one knows.
For more, see 'Naval Enigma: Seahorse and other Kriegsmarine cipher blunders' in Cryptologia, 28 (2004) 211-241. Some of it may be on-line.

Posted by: Ralph E at March 15, 2006 3:54 AM


Post a comment



Real names aren't required, but please give us something to call you. Conversations among several people called "Anonymous" get too confusing.



E-mail is optional and will not be displayed on the site.


Remember Me?


Powered by Movable Type 3.36. Photo at top by Steve Woit.

Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.

 
Bruce Schneier