Completing the Enigma Challenge
###############################

:date: 2012-07-22 13:30
:tags: Enigma, Py-Enigma, Cpp-Enigma, C++
:slug: completing-the-enigma-challenge
:author: Brian Neal

Since my last `blog post
<http://deathofagremmie.com/2012/06/06/introducing-py-enigma/>`_, I have spent
almost all my free time working on `Dirk Rijmenants' Enigma Challenge
<http://users.telenet.be/d.rijmenants/en/challenge.htm>`_. I'm very happy to
report that I cracked the last message on the evening of July 10. I thought it
might be interesting to summarize my experiences working on this challenge in a
blog post.

The first nine
--------------

I had a lot of fun building Py-Enigma_, an Enigma machine simulator library
written in Python_ based on the information I found on Dirk's `Technical Details
of the Enigma Machine`_ page. After I had built it and played with it for a
while, I discovered Dirk also had an `Enigma Challenge`_. I decided this would
be a good test for Py-Enigma_, and it may give me some ideas on how to improve
the library for breaking messages.

The first nine messages were pretty easy to solve using Py-Enigma_. Dirk gives
you most of the key information for each problem, and one can then write a small
program to brute force the missing information. I was able to solve the first
nine messages in a weekend. This was very enjoyable, as it did require some
thinking about how to simulate the problem and then executing it. I also learned
about `Python's itertools <http://docs.python.org/library/itertools.html>`_
library, which contains some very handy functions for generating permutations
and combinations for brute forcing a solution.

Dirk did a great job on the messages. They referenced actual events from World
War II and I ended up spending a fair amount of time on Wikipedia reading about
them. Translating the messages from German to English was a bit difficult, but I
relied heavily on `Google Translate <http://translate.google.com>`_.

Message 10
----------

But then I came to the last message. Here, Dirk doesn't give you any key
information, just ciphertext. Gulp. If you include 2 possible reflectors, the
Enigma machine's key space for message 10 is somewhere around 2 x 10\
:sup:`23` keys, so it is impossible to brute force every possible key, unless
you can afford to wait around for the heat death of the universe.

I then did some research, and learned about a technique for brute-forcing only
the rotor and message settings, and then performing a heuristic technique called
"hill-climbing" on the plugboard settings. I am deeply indepted to Frode Weierud
and Geoff Sullivan, who have published high level descriptions of this
technique. See Frode's `The Enigma Collection
<http://cryptocellar.org/Enigma/>`_ page and Geoff's `Crypto Barn
<http://www.hut-six.co.uk/>`_ for more information.

Python is too slow, or is it?
-----------------------------

After a week or so of studying and tinkering, I came up with a hill-climbing
algorithm in Python. I then started an attempt to break message 10, but after
running the program for a little over 24 hours, I realized it was too slow. I
did a "back of the envelope" calculation and determined I would need several
hundred years to hill-climb every rotor and message setting. This was a bit
disappointing, but I knew it was a possibility going in.

I then set out, somewhat reluctantly, to port Py-Enigma to C++. These days I
don't do any C++ at home, only at work. However I got much happier when I
decided this was an opportunity to try out some new C++11 features (the embedded
compiler we use at work has no support for C++11). Okay, things are fun again! I
have to say that C++11 is really quite enjoyable, and I made good use of the new
``auto`` style variable declarations, range-based for-loops, and brace-style
initialization for containers like ``vector`` and ``map``. 

C++ is too slow, or is it?
--------------------------

It took a fair amount of time to re-tool my code to C++11. I ensured all my unit
tests originally written in Python could pass in C++, and that I could solve
some of the previous messages. I then re-implemented my hill-climbing
algorithm in C++ and made another attempt at cracking message 10.

My C++ solution was indeed faster, but only by a factor of 8 or 9. I calculated
I would need about 35 years to hill-climb all rotor and message settings, and I
didn't really want to see if I could out-live my program. My morale was very low
at this point. I wasn't sure if I could ever solve this self-imposed problem.

Algorithms & Data Structures are key
------------------------------------

I had wanted to test myself with this problem and had avoided looking at anyone
else's source code. However, at this juncture, I needed some help. I turned to
Stephan Krah's `M4 Message Breaking Project
<http://www.bytereef.org/m4_project.html>`_. Stephan had started a distributed
computing attack on several 4-rotor naval Enigma machine messages. He had
graciously made his source code available. Perhaps I could get some hints by
looking at his code.

Indeed, Stephen's code provided the break I needed. I discovered a very cool
trick that Stephen was doing right before he started his hill-climb. He
pre-computed every path through the machine for every letter of the alphabet.
Since hill-climbing involves running the message through the machine roughly
600 to 1000 times, this proved to be a huge time saver. After borrowing this
idea, my hill-climbing times for one fixed rotor & message setting went down
from 250 milliseconds to 2! 

I immediately stopped looking at Stephen's code at this point; I didn't bother
to compare our hill-climbing algorithms. I believe both of us are influenced by
Weierud & Sullivan here. I was now convinced I had the speed-up I needed to make
a serious attempt at message 10 again.

This showed me how critically important it is to have the right data structure
and algorithm for a problem. However there were two other lessons I needed to
learn before I was successful.

Utilize all your computing resources
------------------------------------

Up to this point my cracking program was linear. It started at the first rotor
and message setting, then hill-climbed and noted the score I got. Then it
proceeded to the next message setting and hill-climbed, noting the score of that
attempt, and so on. There were two problems with this approach. 

I realized if I could do some sort of multi-processing, I could search the key
space faster. I thought about forking off multiple processes or maybe using
threads, but that was over-thinking it. In the end, I added command-line
arguments to the program to tell it where in the key space to start looking. I
could then simply run multiple instances of my program. My development laptop,
which runs Ubuntu, is from 2008, and it has 2 cores in it. My desktop PC (for
gaming), has 4 cores! I next spent a couple nights installing MinGW_ and getting
my application to build in that environment. I could now run 6 instances of my
cracking program. Hopefully this would pay off and shorten the time further.

(I didn't even attempt to commandeer my wife's and kids' computers. That
wouldn't have gone down so well.)

How do you know when you are done?
----------------------------------

The final problem that I had was determining when my cracking program had in
fact cracked the message. The hill-climbing attempts produced scores for each
key setting. Up to this point, based on running my program on messages 1 through
9, I had noticed that when I got a score divided by the message length of around
10 I had cracked the message. But my tests on messages 1 through 9 were
hill-climbing using the known ring settings. My message cracker was using a
shortcut: I was only searching ring settings on the "fast" rotor to save time.
This would let me get the first part of a message, but if the middle or
left-most rotor stepped at the wrong time the rest of the message would be
unintelligible. 

To verify my message cracking program, I ran it on some of the previous
messages. I was shooting for a score divided by message length of 10. Using this
heuristic, I was in fact able to crack some of the previous messages, but not
others. It took me a while to realize that not searching the middle rotor's ring
setting was causing this. The light bulb came on, and I realized that my
heuristic of 10 is only valid when I search all the ring settings. Instead I
should just keep track of the highest scores. When you get close enough, the
score will be significantly higher than average score. Thus I may not know when
I am done until I see a large spike in the score. I would then have to write
another program to refine the solution to search for the middle and left-most
ring setting. 

Success at last
---------------

It took a little over a month of evenings and weekends to get to this point.
I even had a false start where I ran my program on 6 cores for 1.5 days only to
realize I had a bug in my code and I was only searching ring setting 0 on the
fast ring. But once I had that worked out, I started a search on 6 cores on a
Sunday night. I checked the logs off and on Monday, but no significant spike in
the scores were noted. Before leaving for work on Tuesday I checked again, and
noticed that one instance of my program had found a score twice as high as any
other. Could that be it? I really wanted to stay and find out, but I had to go
to work! Needless to say I was a bit distracted at work that day.

After work, I ran the settings through my Python application and my heart
pounded as I recognized a few German words at the beginning of the message. In
fact I had gotten around 75% of the message, then some garbage, but then the
last few words were recognizable German. I then wrote another application to
search the middle ring setting space. Using the highest score from that program
allowed me to finally see the entire message. I cannot tell you how happy and
relieved I was at the same time!

Final thoughts
--------------

For a while I didn't think I was going to be smart enough or just plain up to
the task of solving message 10. Looking back on it, I see a nice progression of
trying things, experimenting, setbacks, and a few "a-ha" moments that lead to the
breakthrough. I am very grateful to Dirk Rijmenants for creating the challenge,
which was a lot of fun. And I also wish to thank Frode Weierud and Geoff
Sullivan for their hill-climbing algorithm description. Thanks again to Stephan
Krah for the key speedup that made my attempt possible.

For now I have decided not to publish my cracking program, since it is a tiny
bit specific to Dirk's challenge. I don't want to ruin his Enigma Challenge by
giving anything away. I don't believe my broad descriptions here have revealed
too much. Other people need to experience the challenge for themselves to fully
appreciate the thrill and hard work that go into code breaking.

I should also note that there are other ways of solving Dirk's challenge. You
could, with a bit of patience, solve messages 1 through 9 with one of the many
Enigma Machine GUI simulators (Dirk has a fine one). I'm not certain how
you could break message 10 using a GUI simulator and trial and error, however.

It is my understanding that this style of Enigma message breaking was not the
technique used by the allied code-breakers during the war. I believe they used
knowledge of certain key words, or "cribs", in messages received in weather
reports and other regular messages to find the key for the day. I look forward
to reading more about their efforts now.

Finally, I have published the C++11 port of Py-Enigma_, which I am calling
(rather unimaginatively) Cpp-Enigma_ on bitbucket. I hope Cpp-Enigma_ and
Py-Enigma_ are useful for other people who want to explore the fascinating world
of Enigma codes.

.. _Py-Enigma: https://bitbucket.org/bgneal/enigma
.. _Python: http://www.python.org
.. _Technical Details of the Enigma Machine: http://users.telenet.be/d.rijmenants/en/enigmatech.htm
.. _Enigma Challenge: http://users.telenet.be/d.rijmenants/en/challenge.htm
.. _Cpp-Enigma: https://bitbucket.org/bgneal/cpp-enigma
.. _MinGW: http://www.mingw.org/