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 PM • 25 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
Ari Heikkinen • February 24, 2006 2:16 PM
I remember reading from applied crypto that enigma was broken. If that's the case how's there still unbroken messages lying around?
Carlo Graziani • February 24, 2006 2:24 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.
Justin • February 24, 2006 2:29 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.
Mike Sherwood • February 24, 2006 2:44 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.
Ari Heikkinen • February 24, 2006 3:21 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..
David in Chicago • February 24, 2006 4:26 PM
@Andre, @JoJo:
Or so the Germans would have you believe...
Joe Loughry • February 24, 2006 5:00 PM
The decrypt checks out on the Model "E" Enigma:
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."
Jeremy • February 24, 2006 5:30 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...
Bob • February 24, 2006 5:56 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.
Filias Cupio • February 24, 2006 9:17 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.)
Alan • February 24, 2006 11:44 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).
Gruff • February 25, 2006 4:09 AM
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.
Tinker Tailor • February 25, 2006 10:41 PM
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?
Stu Savory • February 26, 2006 11:19 AM
Be aware that there are some slight errors in translation from the German of the recently cracked M4 message. I sent a correction.
Weasel • February 28, 2006 7:59 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.
Grin-Mouse • February 28, 2006 9:27 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?
Neal • March 8, 2006 11:03 PM
"the Baroque Cycle might be a bit of a stretch."
There's an understatement ...
David (Toronto) • March 14, 2006 5:00 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
Ralph E • March 15, 2006 3:54 AM
"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.
Paulomus • February 8, 2010 6:29 PM
Not a cryptographer, but my understanding (from the books I've read), is that the Enigma machines had a keyspace that was thought to be large enough to be completely secure, but in reality was just on the edge of what was technically feasible to attack. The British had a limited number of machines capable of brute forcing a section of the keyspace. They used a combination of cribs, known insecurities and quirks and advanced mathematics to bring the keyspace down into something they were capable of breaking with the resources at hand. Sometimes (frequently) they didn't get there. With the development of better machines and American industrial capacity, their "processing power" improved to the extent that they were able to routinely break traffic that would have previously been difficult or impossible. I don't really understand the details, but I know the basic problem with the Enigma design to be underestimating the cryptological and technical resources available to the other side, plus numerous "security through obscurity" measures that only made things worse.
Subscribe to comments on this entry
Post a comment
Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.
|
| Subscribe |
Subscribe via Kindle |
| Blog Menu |
SearchPowered by DuckDuckGoBlog Home Page
Archives by Date2013 J F M A M J
Tags  |
| Latest Book |
more books by Bruce Schneier |
Comments