February 27, 2006 10:49 AM PST

Distributed computing cracks Enigma code

More than 60 years after the end of World War II, a distributed computing project has managed to crack a previously uncracked message that was encrypted using the Enigma machine.

The M4 Project began in early January, as an attempt to break three original Enigma messages that were intercepted in 1942 and are thought never to have been broken by the Allied forces.

These messages were encrypted using a four-rotor Enigma. That version was considered by Germany to be completely unbreakable, as it could be set up in any one of a vast number of ways (2 times 10 to the 145th power), each of which would encrypt a plain text message differently.

Cryptologists at Bletchley Park in the U.K. managed to break Enigma through their development of early computers, led by Alan Turing, and also by using intelligence to cut down the number of possible set-ups.

According to the organizers of M4, their open-source message-breaking application managed to crack one of the three messages early last week.

The translation of the message is as follows:

Radio signal 1851/19/252: "F T 1132/19 contents: Forced to submerge during attack. Depth charges. Last enemy position 0830h AJ 9863, (course]) 220 degrees, (speed) 8 knots. (I am) following (the enemy). (Barometer) falls 14 mb, (wind) nor-nor-east, (force) 4, visibility 10 (nautical miles)."

In breaking the first message, the project organizers used so-called brute force to test the encrypted message against all possible set-up configurations of the four-rotor Enigma. However, this configuration did not include the machine's plugboard, which allowed the operator to swap two letters around before they were processed by the machine's rotors.

The plugboard added much more complexity to the encryption process than any single rotor. To address this, the M4 Project used a "hill-climbing algorithm."

"Hill-climbing algorithms try to optimize an object, in this case the plugboard settings, by changing the object step by step. After each change the 'goodness' or 'fitness' of the new object has to be determined by a scoring function. Changes that lead to a 'better' object are retained. Here the changes lie in constantly trying out new wirings of the Enigma plugboard. After each change, the scoring function tests a new wiring by deciphering the message and trying to determine how closely the resulting plaintext matches the statistics of the natural language," the M4 Project explained.

With two messages still to break, the M4 Project is looking for computer users to download its application and help out.

Graeme Wearden of ZDNet UK reported from London.

See more CNET content tagged:
distributed computing, object, message, open source

34 comments

Join the conversation!
Add your comment
No U571 eh?
No U571, available to rescue hollywood style eh!
Posted by heystoopid (691 comments )
Reply Link Flag
Enigma?
Didn't the US steal the Enigma machine during WW2? Why are we reinventing the wheel? Just use the machine to crack the messages...
Posted by Gasaraki (183 comments )
Reply Link Flag
Did you read the story?
"...a previously uncracked message that was encrypted using the
Enigma machine."

You don't just "use" the machine to crack the message - you
need to know the daily key that was used to encode the message
in the first place.

And, as far as I remember (sure someone will correct me if I'm
wrong), us Brits actually got the machine... not you "Johnny
Come Lately's". :-)

RB
Posted by ross brown--2008 (57 comments )
Link Flag
Umm duh... they need the KEY to do that!
In order to decrypt the intercepted message on the Enigma, they need the KEY to set up the Enigma correctly. If they had the key, then they wouldn't have to brute force attack it.

You OBVIOUSLY know nothing about cryptography!
Posted by Anon-Y-mous (124 comments )
Link Flag
Recommended reading
Check out David Kahn's Seizing the Enigma for a good overview of
the difficulties in breaking Enigma.
Posted by Bert Dill (1 comment )
Reply Link Flag
No OS X Client?
The Unix client MIGHT work I guess. Pitty. I have this nice new dual core MacBook. . .Awww :-(
Posted by Jonathan (832 comments )
Reply Link Flag
The Little Computer That Could...
Apple Users: You hoo! When is the rest of the world going to recognize that we want to help too?!!!

Rest of the World: Yah, yah. We recognize that you Apple Users want soooo much to be a bigger part of the Computing industry. Well, the plain truth is, you're so insignificant to us, that we really don't want to waste anymore time even acknowledging that you exist.

Apple Users: Please please! Our computing platform is so much more stable and capable than your platform. We're really really powerful, just give us a chance to prove ourselves! Make some software for our OS!

Rest of the World: Yawn....

Apple Users: Hello? Isn't anybody listening...?
Posted by TMB333 (115 comments )
Link Flag
UNIX client for MacOSX
The UNIX client works just fine for Mac OSX. Just follow the instructions included with the tarball.
Posted by cnoyes72 (4 comments )
Link Flag
Where are all the code books?
Surely either the British or American government would have an appropriate code book for decrypting the message. The Alliance did vanquish Germany and occupy it after all. The Nazi couldn't have destroy every single copy ever printed.
Posted by Chung Leong (111 comments )
Reply Link Flag
Codebooks
But every submarine had their own combination(s) 1 copy kept at HQ and 1 in the sub. All it would take is the destruction of 2 pieces of paper. It was not a 'code' it was encypherment.

A code is a literal change of one item for another. Encypherment means that there are no literal changes from one to another.

i.e. code sample is morse code i.e.
a = .- c= -.-. and every message would use the same changes.

When encyphered each letter could have 26 possiblities (just using the latin alphabet), 36 with cyrillic)

With the Enigma the next letters encipherment would depend upon what the previous character was and this would begin with the original setting of the machine. Each code wheel had 26 letters plus the numbers 0-9. Each character would be wired to a different character on each wheel + you could change the possitioning of the wheels in any order, plus each wheel would rotate or step as each character was typed depending upon the wiring as to the number of steps it would rotate.

most of the time all but 1 wheels wiring would not be changed ever.

most cyphers are broken by language frequency (i.e english etionrish are the most common letters in that order (ever watch pat sajak and the wheel of fortune? and wonder why each contestant uses the same guess for the first 5 letters?). this is used to break transposition cyphers.

If the lenght of the cypher is longer than the maximum size of a message you will not get any repeated letters i.e. the letter a would not be the letter z ever again.. but if everyone started off the message the same way or if the format of the message was to be guessed i.e. like the format of an email message or a formal letter

from: name
to: emailaddy@?????.com (here .com .net .org) would also come up rather frequenty in approximately the same space.. in a simple cipher we might get 8 letters by frequency distribution a few more by placment in the message and after that its like looking at an unfinished crossword puzzle.

BTW the British government hired crossword champiions to be code (in this case cypher) breakers and they did a rather good job.

The biggest break was that one of the German Enigma machines was captured and turned over to the british which gave them a huge advantage.. The Army and Air Force just used the original machines BUT the submarine force after having destructive losses (due to HFDF and the fact that the messages were basically decrypted within minutes of being sent that anti-submarine forces could lay in wait of a submarine and destroy it because they were told where it was.

If you look at the article even if the position was not given the time speed of a convoy was plus the weather conditions.. Since the Allies knew where every convoy was and had weather reports from their own ships they could use this information as well to locate the lurking sub.

Sometimes the convoy would get a message to change course while the a-sub force would go after the waiting wolf pack.. thanks to the 'code breakers'..

When the Germans added the 2 extra wheels and the plug board the U-Boats enjoyed another "happy time" of sinking ships without being sunk until the british could counteract the new changes in the enigma machines.. this was done by a courageous sailor that boarded a sinking U-Boat (after surfacing to let off the crew) and capturing the device before it could be destroyed or sunk)..

Naval codebooks were usually weighted with lead covers to make them sink faster to prevent them from being captured (just toss it overboard matey)
Posted by davidj7738 (8 comments )
Link Flag
Codebooks
But every submarine had their own combination(s) 1 copy kept at HQ and 1 in the sub. All it would take is the destruction of 2 pieces of paper. It was not a 'code' it was encypherment.

A code is a literal change of one item for another. Encypherment means that there are no literal changes from one to another.

i.e. code sample is morse code i.e.
a = .- c= -.-. and every message would use the same changes.

When encyphered each letter could have 26 possiblities (just using the latin alphabet), 36 with cyrillic)

With the Enigma the next letters encipherment would depend upon what the previous character was and this would begin with the original setting of the machine. Each code wheel had 26 letters plus the numbers 0-9. Each character would be wired to a different character on each wheel + you could change the possitioning of the wheels in any order, plus each wheel would rotate or step as each character was typed depending upon the wiring as to the number of steps it would rotate.

most of the time all but 1 wheels wiring would not be changed ever.

most cyphers are broken by language frequency (i.e english etionrish are the most common letters in that order (ever watch pat sajak and the wheel of fortune? and wonder why each contestant uses the same guess for the first 5 letters?). this is used to break transposition cyphers.

If the lenght of the cypher is longer than the maximum size of a message you will not get any repeated letters i.e. the letter a would not be the letter z ever again.. but if everyone started off the message the same way or if the format of the message was to be guessed i.e. like the format of an email message or a formal letter

from: name
to: emailaddy@?????.com (here .com .net .org) would also come up rather frequenty in approximately the same space.. in a simple cipher we might get 8 letters by frequency distribution a few more by placment in the message and after that its like looking at an unfinished crossword puzzle.

BTW the British government hired crossword champiions to be code (in this case cypher) breakers and they did a rather good job.

The biggest break was that one of the German Enigma machines was captured and turned over to the british which gave them a huge advantage.. The Army and Air Force just used the original machines BUT the submarine force after having destructive losses (due to HFDF and the fact that the messages were basically decrypted within minutes of being sent that anti-submarine forces could lay in wait of a submarine and destroy it because they were told where it was.

If you look at the article even if the position was not given the time speed of a convoy was plus the weather conditions.. Since the Allies knew where every convoy was and had weather reports from their own ships they could use this information as well to locate the lurking sub.

Sometimes the convoy would get a message to change course while the a-sub force would go after the waiting wolf pack.. thanks to the 'code breakers'..

When the Germans added the 2 extra wheels and the plug board the U-Boats enjoyed another "happy time" of sinking ships without being sunk until the british could counteract the new changes in the enigma machines.. this was done by a courageous sailor that boarded a sinking U-Boat (after surfacing to let off the crew) and capturing the device before it could be destroyed or sunk)..

Naval codebooks were usually weighted with lead covers to make them sink faster to prevent them from being captured (just toss it overboard matey)
Posted by davidj7738 (8 comments )
Link Flag
Not that simple.
The system was very dynamic and you could not be sure of how many copies were retained. This is where some intel gathering was important. You had to know the source and destination of a transmission before you could narrow it down.
Posted by zaznet (1138 comments )
Link Flag
Codebooks
The Allies did find a number of old naval Enigma key lists after German surrendered. None have been released to the US or British archives. Most have probably been destroyed by now.

Although many wartime files on solving Enigma have been declassified, some are still classified Top Secret' by NSA.
Posted by querist (4 comments )
Link Flag
Safety is not free or safe
OK, I see safety is not free or safe today because cyber guys have access to computing about encryption and stuff that allows them to keep penetrating our software. So why depend on software on the web and why not just keep it off.

That's what I think anyway. Ciao now.
Posted by Iohagh (54 comments )
Reply Link Flag
Sour Grapes
Yes while the Pole did get the Enigma Machince.
And if you ever visit Bletchley you will Find many tribute to the Poles,the reason there is little reference to them is at the end of the war every single item relating to the operation there was destroyed even to the extent that little bit of paper use to bloke up hole that might stop the wind blowing in,were destroyed
And it is a fact there is a sculpture to thank them,
But the main point is miss here and that the actual code was broken by the team at Bletchley.
of the 1200 there were 300 American nere the end of the war,
Posted by Eddy Mac (1 comment )
Reply Link Flag
Britain captured enigma 13 times, US once Canada once, Poland BOUGHT 2
Yes we captured it 13 times. U-571, like Braveheart, like The Patriot, like Apocolypto, like 300 and like many more american films is full of crap..
Posted by andysykes (2 comments )
Reply Link Flag
 

Join the conversation

Add your comment

The posting of advertisements, profanity, or personal attacks is prohibited. Click here to review our Terms of Use.

What's Hot

Discussions

Shared

RSS Feeds

Add headlines from CNET News to your homepage or feedreader.