My favourite book was Fermat’s
Last Theorem by Simon Singh. So when in 1999 I saw his new book - The Code Book - in shops I just had to
buy it, despite it being incredibly expensive (for a very poor student like myself). I then took my new
prize procession with me expectantly on the summer holiday. And when I reached the end of the book that
I discovered it contained a Cipher Challenge!
I
set about cracking the ciphers with gusto. By chance I happened to have my 286 computer with me, and my
hobby language of choice - Turbo Pascal 7.
I think I skipped the ADFGVX cipher, so
excited was I at the prospect of cracking the Enigma
stage 8 of the contest. Unfortunately, when I reached the Enigma, I was stumped. I couldn’t
make any headway with simulating the Enigma. I wrongly assumed that the message would begin with the
message key encrypted with the day key twice. But my biggest mistake was not understanding how rings
affected things. I didn’t understand how rings affected things because The Code Book didn’t
actually explain them! The book instructed the intrepid explorer to search the Internet for more
details and I didn’t take any heed of this because a) I couldn’t imagine the book
wouldn’t actually give me everything I needed to crack the challenge, and b) I didn’t
have any Internet. The Enigma I was trying to crack wasn’t even an accurate Enigma.
So
17 years later I find myself on a whim tacking the Enigma once again. And my computer is a bit faster
too. But I want to attack it my way, putting myself as much as possible in the shoes of my old self 17
years ago, only this time with Internet so I can double-check the correctness and completeness of my
implementation of the Engima cipher machine.
This is my attack on the Enigma. I will
describe my attack on an M3 Enigma (used by the army and air force) and then I will generalize it to
attack the M4 (used by the U-boats; what Alan Turing is famous for cracking).
A lot of people now think that Alan Turing cracked the Enigma. A lot of people like
to correct those people and say that it was the Poles who truly cracked the Enigma. So we really need
to correct everyone and set things straight, because it was far more nuanced than that, with far more
people involved, and different versions of Enigma were cracked even earlier. If you read enough about
code breaking you end up with a fuzzy timeline in your head pieced together from all the various
sources. Here’s what I’ve osmosed:
The settings for each rotor - its start position and ring setting - can actually be combined
into a single offset. This is perhaps why all the popular treatments of the subject just ignore the
impact of the rings on the number of combinations. In truth, their impact is hard to explain. The rings
change when rotors rotate, and do have an impact on the number of combinations, but many initial
starting positions are equivilent for short messages because the rings cancel out the rotor start
position and do not cause a rotation because the message is too short.
The M4 Enigma - as infamously used by the U-boats - is usually described as a ‘four
rotor’ machine. And that’s strictly true, I suppose, but I think I have a better way
of describing it:
The M4 was a normal 3-rotor M3 Enigma chassis. A new 'thin’ reflector design was
developed that could take a new, thinner 'greek’ non-rotating wheel. The thin greek wheel
could be placed in any of 26 positions and clicked into the thin reflector. This could then be placed in
the chassis in the normal reflector position.
So basically the M4 is an M3 Enigma with a configurable reflector.
I wrote the fast Enigma sim to serve as a basis of a statistical attack on the Enigma. In fact,
if you look at my test vectors, you’ll notice one of them is Simon Singh’s
Cipher Challenge Enigma stage 8, which I cracked using my statistical attack! More on that in
the next post :)
And here’s the code. As you can see, the vast majority of the code is just test
vectors to ensure its correctness:
It turns out my kids have been sending each other secret messages, enciphered with a
substitution cipher of their own invention! They only let me see the secret key when I agreed to help
them mix up a very complicated recipe for invisible ink:
This reawakened
fond memories of a young me getting a good way through Simon Singh’s The Code Book cipher challenge :) (Also, see
the Enigma
Spreadsheet my friend made a few years ago!)
So my mind raced considering
how fast todays laptops can brute-force, say, Enigma? Even non-brute-force attacks are on a different
scale if you have a computer. For example, with Enigma, can you ignore the plugboard and go through
every combination of day and message key, using a histogram to spot possible text that you then attack
as a substitution cipher?
First I needed an accurate Enigma simulator. To be honest,
I found most descriptions a bit light on detail. But I quickly found a paper Enigma, which I
made:
Back in the summer of 2009 a friend of mine read a few of my
books covering cryptography.
This is his interpretation of the Enigma cipher machine;
the distillation of a mental model he formed from reading those popular-science treatments of the
machine.
He is not a programmer or anything but he just proved his aptitude; and he’s
super-leet at Excel too!
I think we can all agree this is programming, even when done by someone
who is not a professional programmer and who has no formal programming education.
When I asked him if I could post his old Enigma spreadsheet, he was skeptical that anyone would
be interested. Outside the programming world, normal people think making complicated spreadsheets in
their spare time is creepy and to be suppressed ;)
Now the Internet is awash with Engima machines in Flash applets and such; none seem to agree
with any other, and this spreadsheet is no exception to that. So it would be most unlikely this is a
truly accurate representation of the real machine.
However, my friend is a good visual learner; I think if we could just get him to Bletchley Park he’d
refine and fix his mental model and build a better, more correct spreadsheet :)
I figure we all just have to give him encouragement - comments and code review and such - and
get his appetite whetted for doing more of this computer type of thing! So if you enjoy his work,
please say
see also:
