Still trying to crack Nazi Enigma messages

You can donate your spare PC processing power to dozens of cool volunteer computing projects simply by downloading some software. Enigma@home is the one that called me.

Enigma@home is based on the M4 Project, an effort spearheaded by German-born violinist and encryption enthusiast Stefan Krah. The M4 Project was designed to break three original messages generated by a famed electro-mechanical Enigma machine and intercepted in the North Atlantic in 1942. (The project gets its name from the four-rotor Enigma M4 machine presumed to be used by the Germans for enciphering the signals during wartime.) The project's method for cracking the ciphers is described as "a mixture of brute force and a hill climbing algorithm."

Slideshow: 12 cool ways to donate your spare PC processing cycles

Enigma@home provides access to the M4 Project using BOINC software for volunteer and grid computing (FAQ: BOINC software for volunteer computing).

"The BOINC wrapper is very successful," Krah writes. "In fact most people prefer the BOINC client and the majority of work units is now submitted via BOINC."

The project, which started in January of 2006, succeeded in breaking the first two messages within the first couple of months (the first one read: "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]."

Enigma@home is still working on message No. 3. As for why it's such a tough one, Krah says there could be several reasons:

1. It could be a so-called Offizier message, part of which is doubly encrypted.

2. The message was badly intercepted and some letters are missing.

3. There are some messages that require the algorithm to be applied many times. This is pretty much what we are doing right now.

As for what sparked Krah's interest in breaking ciphers, he says that in 2005 he started solving the challenge messages of Simon Singh's Cipher Challenge - long after the actual challenge was over.

"The Enigma message in Singh's challenge is in many ways relatively easy to break and subsequently I improved the algorithm so that real world messages could be broken. In summer of 2005, a publication by Geoff Sullivan and Frode Weierud helped to refine the algorithm further.

"The three messages that are the target of the M4 Project were interesting for three main reasons: They were unbroken, published in a serious journal and encrypted by the M4 Enigma model. This model has the largest key space of all and breaking these messages pretty much requires a distributed computing project (unless you have pieces of guessed plain text, which is what they used in Bletchley Park in WWII [referring to the Allied codebreakers' headquarters, also known as Station X, in England])."

For more on Krah, this 2006 BBC story provides more background.