back to index
enigma-suite
M4 Project Client Install
M4 Project Results
M4 Project Statistics
M4 Project Mailing Lists
M4 Project Blog
M4 Project Wiki (external link)

Quick work unit overview:

Date Daily Completed Remaining
2009-11-15 10632 5694000 0

On May 28th 2008 we reverted to the middle part of the unbroken M4 message.
Please refer to the M4 Project Blog for details.


M4 Message Breaking Project


Status:

The first message has been broken on February 20th, 2006. The signal in question is the second of the intercepts in Erskine's letter. You can read the raw server logs as well as an interpretation and translation.

The second break has occurred on March 7th, 2006. The signal in question is the third of the intercepts in Erskine's letter. You can read the raw server logs as well as an interpretation and translation.

The remaining message has not been broken yet, so you are still welcome to download the client and participate.


About:

The M4 Project is an effort to break 3 original Enigma messages with the help of distributed computing. The signals were intercepted in the North Atlantic in 1942 and are believed to be unbroken. Ralph Erskine has presented the intercepts in a letter to the journal Cryptologia. The signals were presumably enciphered with the four rotor Enigma M4 - hence the name of the project.

This project has officially started as of January 9th, 2006. You can help out by donating idle time of your computer to the project. If you want to participate, please follow the client install instructions for your operating system:

M4 Project Client Install

Software:

The software used in this project is Open Source, so that you can see what is going on on your computer. The client is a Python script that tries to connect to the server to get a workunit (range of keys). When successful, it launches the message breaking program (written in C) to work on the range. The most promising result of that effort is submitted back to the server, after which the client gets a new workunit.

I have been running the client in the background on two Linux machines for almost two months, and I haven't experienced any stability problems whatsoever. The client runs at the lowest priority, which means that other programs you run on your machine will not be disturbed by it.

The client-server setup has been tested on some challenge messages presented by Geoff Sullivan and Frode Weierud. Messages 1, 3, 5 and 6 have been broken. Here are the raw server logs of break 5.

You can see that the server has been restarted due to a kernel upgrade. You can also see that the partial break has a lower score than the highest nonsense results. Here is a cleaned up version of break 5 with all parts of the key corrected.

News, current results and statistics:

You can read the latest news as well as additional information on the M4 Project Blog.

You can view the current server logs for the latest results. The logs are rotated, maximum size is 99 KB.

The statistics page shows how many workunits are processed per day. The average daily rate is calculated over the total running time.

Method:

The method in question is a ciphertext-only attack. This means that we don't need bits of guessed/known plaintext for a successful decryption.

The most simple ciphertext-only attack would use brute force. You would take every possible key, decrypt the message, and determine the likelihood of the resulting candidate plaintext. The enigma key space is too large for this approach.

The method used here is a mixture of brute force and a hill climbing algorithm:

The program iterates through all possible machine settings except the plugboard settings. This is a major shortcut since the plugboard settings form a huge portion of the key space. For each of these machine settings the program uses a hill climbing algorithm to find the optimal plugboard settings.

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 scoring function uses Sinkov Statistics.

Shortcuts:

The messages date from 25th November 1942, which rules out UKW C-Thin and Greek wheel Gamma. See Heinz Ulbricht's PhD Thesis, p9 (in German). The search space can be reduced further by only testing keys where the middle ring is in the 'A' position. Another shortcut is described in the software's documentation.

Runtime Estimates:

The key server hands out workunits of the size of 26^4 keys. With a ciphertext length of 180 letters, processing time is around 80min on a Celeron 1.2GHz.

The total search space consists of 7434 workunits. Based on the Celeron, 100 participants running the software 24/7 could walk through the search space in 4 days.

Easy messages break on the first walk through the search space. Tougher ones require more. Based on my experience with messages of this length, there should be a good chance that 1-10 walks will yield a break.

Mailing List:

I have set up a mailing list for anything related to the project.


Acknowledgements:

I was introduced to hill climbing algorithms by numerous usenet articles by Jim Gillogly. His Cryptologia paper "Ciphertext-Only Cryptanalysis of Enigma" is a great reference for anyone trying to solve classical ciphers using hill climbing or the Index of Coincidence.

In their Cryptologia paper "Breaking German Army Ciphers" Geoff Sullivan and Frode Weierud show a very efficient way of rewiring the plugboard during the hill climb. My program received a considerable speed-up after incorporating their method. Several shortcuts that reduce the search space can be found in the paper.

A special thanks goes to Geoff Sullivan for answering questions in sci.crypt, always revealing _exactly_ the right amount of information.

Online References:


Contact:

Stefan Krah <website @ bytereef.org>