I was fascinated by the movie The Imitation Game, not just because it brings awareness of a great man that advanced our civilization tremendously, and the great injustice he suffered, but also because it presents the study of cryptanalysis, something that most people don’t even know it exists, but it’s incredibly important when dealing with information, specially in our modern day and age.
However, the Enigma machine to me was simply that; an enigma. I’m not a mechanic, so you put that thing in front of me, and it would take me forever to understand what it does, if I ever manage to find the interest to do so. I was happy thinking it was a magic box.
That was until Albert Still decided to write the code of the machine in Ruby (my favorite computer language), which he explained in a blog post. I’m a programmer, code I understand, and this was 30 lines, in a minute I understood the machine (literally).
I was blown away by the simplicity of it, and I thought: hey! anybody can understand this. And ultimately that’s the beauty of cryptography; it doesn’t matter if you know exactly how the algorithm works; you still cannot decrypt the message. This is what security today relies on; everybody knows the algorithms running in your web browser, yet you are secure accessing your bank account, because those algorithms are cryptographically secure. The phrase “cryptographically secure” might not mean much to most people, but it’s really important.
I will try to explain how the Enigma machine works in simple terms, if you are a programmer, you might be better off just reading the code.
You don’t need to understand this code, but it might help to understand the algorithm.
$reflector = Hash[*CHARS.to_a.shuffle] $reflector.merge!($reflector.invert)
So, what this means is that we pair each one of the 26 characters (A to Z) with another one randomly, so for example W is paired with L, which means that whenever we find a W, we switch it with an L, and when we find and L, we switch it with a W.
If we run this algorithm with the text HI, we get RF (H=>R, I=>F), pretty simple. The interesting thing is what happens when we feed this back to the algorithm; it becomes HI again (R=>H, F=>I). This is why it’s called a reflector.
This is actually so simple that you don’t even need a machine to do the conversion, you can even do it manually by looking to a piece of paper with the mapping. And there’s nothing cryptoraphic about this; if the Enigma machine only had this algorithm, you only need to steal one machine, and you could decypher every message immediately. It’s not cryptographically secure at all.
You intercept the message RFJWNH, you feed this to the machine, and you get HITLER. And that’s it.
Let’s put a cryptographic value to this algorithm: 0. It’s useful, but not for cryptographic reasons.
Let’s jump to something more complicated.
$rotor = Hash[CHARS.zip(CHARS.to_a.shuffle)]
This time each character gets another character, randomly, and there’s no reciprocity (A=>K, K=>V). This is the twist; here the rotor starts with K, however it could be configurable, so let’s say, tomorrow it starts with N, then the values associated rotate, and you get this:
Now it’s not so easy any more. You receive the message DGOKIP, but you can’t do anything with that unless you know which was the first value, or “key” (in this case it was E). The only alternative you have is to do what is called a brute force attack; you try every possibility. Fortunately there are only 26 possibilities, so soon enough you will stumble with the key E, and unlock the message: HITLER.
The value of this is: 26. It’s not much, but it’s better than zero.
The rotor, part two
We’ve managed to make things a bit difficult for our cyrptoanalysists, however if say, they notice the character G appearing too often in today’s messages, they’ll assume that perhaps G is actually a vowel, we need to make things mote difficult for them.
As right know, the message III would be encrypted into GGG; that’s too easy. Instead, what we can do is rotate the first part of the rotor each time a character is processed, so III, becomes GDM (I=>G, rotate, I=>D, rotate, I=>M)
This doesn’t really increase the possibilities to test, but makes their job harder.
The rotor, part three
Since the thing is already rotating it would make sense to start with something other than A. This starting position is also part of the key, and again, you need to get it right in order to decrypt the message properly.
So you have 26 ways to configure the rotor, and 26 ways to start it, now the value is: 676. This would take quite a bit of time to go through each and every possibility now.
This is where the fun begins.
$plugboard = Hash[*CHARS.to_a.shuffle.first(20)]
We take 20 random characters and we pair them to each other. In a way, this is similar to the reflector, except this is configurable, and this time we are not picking 1 out of 26, the combinations are many more than that.
The formula to find the number of ways to choose m pairs out of n objects is: n! /((n-2m)! m! 2m). We are picking 10 pairs out of 26 objects, so: 26! / (6! 10! 2^10). The result is: 150,738,274,937,250.
That would take a bit more to test :/
Each rotor needed 676 tries to brute force, why not add two more? That moves us up to 308,915,776.
While we are at it, make the order if the rotors part of the daily key, that’s 3 * 2 * 1: 6 possibilities.
And why not add two more to pick from, so every day you pick 3 out of 5; 5 * 4 * 3: 60 possibilities.
In total, that’s 18,534,946,560 just from the rotors.
And hey, make them rotate at different speeds to make the job of the analysts even harder.
Bring it home
Put everything together, and the process goes like this:
- Rotor 1
- Rotor 2
- Rotor 3
- Rotor 3
- Rotor 2
- Rotor 1
So, here is a simple message: YWXRVH. In order to decrypt it you need the full key: the whole plugboard, the configuration of the rotors, and their starting position. Even if I tell you the original message was HITLER, you would still need to do a lot of work.
For the record, this was the key used to generate that message:
I V III, BFR, SD HY GM EB UO LJ WZ QT AC FR, OIZ
If you try every key until you find it, you potentially would need 2,793,925,870,508,516,103,360,000 tries. Clearly, pure brute force is not the way to solve the problem :/
This is just the machine itself, on top of that there were many protocols to cypher the message even more, but let’s just leave it at that.
Back to the present
That is the power of cryptography; understanding the machine, understanding the algorithm gives you absolutely no leverage, that is the easy part. You are supposed to understand it, and still be unable to crack it.
The algorithm in Enigma is puny compared to modern algorithms which are incredibly complex and with a lot of research behind them. That’s what keeps the communication to your bank secure, and even though most people don’t know it, you can use these algorithms to send secure messages to anyone that in theory not even the government using the most powerful supercomputers can decrypt.
I think it’s time we stop saying “this is not rocket science”; rocket science is easy, we should be saying “this is not cryptanalysis”.