Back in time, Encryption used to be weak, plain, and simple. We can break those in couple of seconds with a normal PC over a brute-force attack. With the modern computing Grids, its possible to do much more than that.
Irony is, Today, three German ciphers are unsolved since World War II — They are now, finally being cracked, powered by thousands of home computers. The codes resisted the best efforts of the celebrated Allied cryptographers based at Bletchley Park during the war. The complex ciphers were encoded in 1942 by a new version of the German Enigma machine, and led to regular hits on Allied vessels by German U-boats.
The advancement in German encryption techniques led to significant Allied losses in the North Atlantic throughout 1942.
The three unsolved Enigma intercepts were published in a cryptography journal in 1995 and have intrigued enthusiasts ever since.
Many projects had been started to utilize the power of Idle CPU from Home PCs in various Open Research projects. These projects take power of few 100,000s of CPUs to do the complex computations. One such is Enigma@home.
Enigma@home is based on the M4 Project, an effort kick-started 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.”
Enigma@home provides access to the M4 Project using BOINC software for volunteer and grid 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]).”
Why It Isn’t Easy to Decipher this one?
During the war, teams of codebreakers based at Bletchley Park, in the UK, scrambled to unravel German communications in an attempt both to undermine the German war machine and to save the lives of soldiers and seamen.
Using early computers, Bletchley Park decoded thousands of intercepts in a knife-edge race to head off U-boat attacks.
German messages were encoded using the fearsome Enigma machine, which used a series of rotors, often augmented by a so-called “plugboard”, to scramble transmissions not meant for Allied eyes.
The machines used ever-changing rotor wheel combinations and electrical currents to produce unique coded messages.
Plugboards further complicated matters by swapping pairs of letters over during the encoding process, greatly increasing the numbers of possible encryptions.
Stefan Krah’s computerized codebreaking software uses a combination of “brute force” and algorithmic attempts to get at the truth.
The combined approach increases the chances of stumbling across a match by recreating possible combinations of plugboard swaps while methodically working through combinations of rotor settings.