February 27, 2006 10:49 AM PST
Distributed computing cracks Enigma code
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.
34 commentsJoin the conversation! Add your comment