Enigma@Home

Enigma@Home
A four rotor Kriegsmarine Enigma M4, the machine type whose original wartime radio traffic Enigma@Home tried to decipher
Project
Status	Completed
Category	Mathematics, Cryptography
Compute	CPU & GPU
Requires	None for the CPU client; the GPU application required CUDA or OpenCL drivers
Development
Developer	Stefan Krah
Author	Stefan Krah
Sponsor	None (independent volunteer effort)
Maintainer	Inactive
Initial release	January 9, 2006  (20 years ago)
Completed	Yes
Repository	https://github.com/jbo-85/enigma-suite
Software
Written in	C, Python
Operating system	Windows, Linux, macOS, Android
BOINC statistics
Stats as of	July 17, 2019  (7 years ago)
Performance	20079.27 GigaFLOPS
Active users	302
Total users	69,398
Active hosts	938
Total hosts	152,157
Metadata
Website	http://www.enigmaathome.net/
License	GPL-2.0

Enigma@Home was a BOINC volunteer computing project that attacked genuine, unsolved Enigma M4 cipher messages from the Second World War using a combination of brute force search and hill climbing cryptanalysis. The project was a BOINC "wrapper" around Stefan Krah's M4 Project (also called the M4 Message Breaking Project), which was launched independently in January 2006 before being ported to the BOINC platform to draw on a much larger pool of volunteered computer time. Over the project's lifetime, volunteers helped recover the plaintext of several authentic Kriegsmarine radio messages that had defeated Allied codebreakers at Bletchley Park during the war and had remained unbroken ever since.

History

Origins: the M4 Project

The three original ciphertexts targeted by the project were intercepted by the British destroyer HMS Hurricane in the North Atlantic on 25 November 1942, during the ten month period the British called the "black-out", when Bletchley Park's Naval Enigma section could not read Kriegsmarine traffic enciphered with the newly introduced four rotor Enigma M4. The intercepts were published by historian Ralph Erskine in a 1996 letter to the journal Cryptologia and were widely assumed to be permanently unbreakable, since a ciphertext-only attack on the M4 has to search a key space of roughly

$N=1344\times 676\times 439,400\times 150,738,274,937,250\approx 6.02\times 10^{25}$

possible machine settings, a figure corresponding to a key length of almost 86 bits once the choice of rotors, ring settings, rotor start positions, and plugboard wiring are all combined. The project was catalogued on the official BOINC project wiki under the "Mathematics and Games Projects" category.

In January 2006, Stefan Krah, a German-born violinist and cryptography hobbyist, wrote a message-breaking program and began recruiting volunteers on internet newsgroups, attracting around 45 participants in the project's first weeks. Krah named the effort the M4 Project, after the four rotor machine. Rather than attempting the full plugboard search, the client software brute forced only the rotor choice, ring settings, and rotor start positions, a much smaller space of

$N_{\text{search}}=1344\times 676\times 439,400\approx 3.99\times 10^{11}$

candidate settings, and used a hill climbing algorithm to recover the plugboard wiring for each candidate, scoring decrypted candidate plaintext against Sinkov statistics of German language text.

Breaking the Erskine messages

The first of the three 1942 messages was broken on 20 February 2006, only about six weeks after the project began. It proved to be a routine contact report sent by Hartwig Looks, commander of the German submarine U-264, describing a depth charge attack and giving the U-boat's position, course, speed, and local weather. A second message from the same batch was broken on 7 March 2006. The third message resisted brute-force hill climbing for several more years; it is believed to have been partly enciphered as an "Offizier" message, meaning it was doubly encrypted with an additional, officer-only substitution before being enciphered a second time on the M4 itself, which defeats a straightforward attack. It was finally solved on 14 January 2013, not through raw distributed brute force but after cryptanalyst Daniel J. Girard and Michael Hörenberg, working independently of the BOINC client, located a usable crib during a joint search of U-boat war diaries; the crib let Girard's own bombe-simulator and hillclimbing software recover the plaintext directly.

The Norrköping messages

After the original three Erskine messages had all been solved, researchers located a further cache of Enigma intercepts made by the Swedish security police at Norrköping between December 1939 and April 1940, comprising more than twenty additional naval intercepts along with a handful of Army and Luftwaffe messages. Enigma@Home's BOINC infrastructure turned its distributed computing power to this archive, breaking a message referred to on the project's forums as "FNYG MXHU" in June 2013, and, following a further burst of activity after new intercepts surfaced in mid-2017, the messages code-named "KLDIO" on 2 August 2017 and "FTNBK" on 15 September 2017. Around the same period the project added a Gridcoin-compatible GPU application, encouraging cryptocurrency mining teams to contribute additional compute power, and released CUDA and OpenCL builds capable of running on graphics cards from the Fermi generation onward.

The improved hill climbing and partial plugboard exhaustion techniques developed and tested during this later phase of the project were subsequently documented in the peer-reviewed literature by Olaf Ostwald and Frode Weierud.

Cryptanalytic method

Close-up of the rotor windows of a four rotor Naval Enigma, the component whose settings formed the bulk of the search space attacked by the project's client software

Enigma@Home's client combined two complementary techniques rather than a single brute force pass over the entire M4 key space:

• Exhaustive search of the rotor order, ring settings, and rotor starting positions, since these form a comparatively small, enumerable space of roughly 4 × 10¹¹ combinations once the plugboard is set aside.
• Hill climbing over the plugboard wiring for each candidate machine setting: starting from an empty or partially filled plugboard, the algorithm repeatedly tried swapping plug connections, scored the resulting candidate plaintext against expected German letter and bigram statistics, and kept only changes that improved the score, iterating until no further improvement could be found.

The key server distributed work in fixed-size batches of 26⁴ keys; on a single Celeron processor of the era a batch took roughly 80 minutes to process, and the entire search space for one message comprised several thousand such batches. Later versions of the client also implemented a "partial exhaustion" refinement of the plugboard search, described by Ostwald and Weierud, which combined limited brute forcing of a few plug pairs with hill climbing over the remainder, improving success rates on short or heavily garbled ciphertexts.

Software and technical details

A surviving Enigma M4, of the type captured intact from German submarine U-505 in 1944

The cryptanalytic core of the client, enigma-suite, was written in C by Stefan Krah and released under the GNU General Public License, version 2. The BOINC wrapper and scheduling logic around it were written in Python. The BOINC-hosted version supported Windows, Linux, macOS, and Android clients, distributing work through a conventional BOINC scheduler and awarding credit for completed workunits. A CUDA-accelerated GPU application, based on the enigma-suite algorithm with additional optimizations, was later made available for GPUs of Nvidia Fermi compute capability (2.0) or newer, and an OpenCL build offered comparable support for AMD graphics cards. Because the underlying source code was published under the GPL, independent forks and optimized builds of the client circulated within the BOINC community throughout the project's active years.

Publications

The following papers are listed for Enigma@Home on the official BOINC publications page.

1. Girard, Daniel J. Breaking "Tirpitz": Cryptanalysis of the Japanese-German joint naval cipher. Cryptologia (2016). This paper gives the solutions of the only four surviving messages from the previously unbroken Japanese-German joint naval cipher known as "Tirpitz", which used a specially built model T Enigma; the article's author biography credits its methods, and the earlier break of the third Erskine message, to techniques and collaborations that grew out of the M4 Project and Enigma@Home cryptanalytic community.
2. Campbell, MacGregor. Uncrackable codes: The second world war's last Enigma. New Scientist (2011). A general-audience feature on the still-unsolved third Erskine message and the crowdsourced Enigma@Home effort to recover it, published two years before that message was finally broken.

See also

• BOINC
• HashClash
• NumberFields@Home
• Enigma machine
• Cryptanalysis of the Enigma