Since my last blog post, I have spent almost all my free time working on Dirk Rijmenants' Enigma Challenge. 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 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.

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 1023 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 page and Geoff's Crypto Barn 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. 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.


Comments

comments powered by Disqus