[Sam Greydanus] created a neural network that can encode and decode messages just as Enigma did. For those who don’t know, the Enigma machine was most famously used by the Germans during World War II to encrypt and decrypt messages. Give the neural network some encrypted text, called the ciphertext, along with the three-letter key that was used to encrypt the text, and the network predicts what the original text, or plaintext, was with around 96-97% accuracy.
The type of neural network he used was a Long Short Term Memory (LSTM ) network, a type of Recurrent Neural Network (RNN) that we talked about in our article covering many of the different types of neural networks developed over the years. RNNs are Turing-complete, meaning they can approximate any function. [Sam] noticed the irony in this, namely that Alan Turing both came up with the concept of Turing-completeness as well as played a big part in breaking the Enigma used in World War II.
How did [Sam] do it?
One key to RNNs and LSTMs for this application is that they are good at learning from data that are in the form of sequences, in this case sequences of alphabetic characters. When being trained on whole documents of text, they learn about words, punctuation and sentence structure. In the case of the Enigma, [Sam] trained his LSTM on randomly generated plaintext, randomly generated keys, and the resulting ciphertext generated using a crypto-enigma Python API. From that training, the LSTM network then learned an approximation of the Enigma’s switchboard, wheels and cables. Note that it was trained on data encrypted using only a single cable configuration and wiring built into the wheels, though it can handle different keys, meaning that it can handle wheels turned to different positions. You can find the full code for the neural network on [Sam]’s GitHub page. As you can see from this article’s banner, with 96-97% accuracy it did pretty well when making predictions i.e. decoding.
At the end of World War II, most Enigma machines were destroyed but our [Brian Benchoff] was lucky enough to see some damaged and restored ones while attending a Vintage Computer Festival East. But of course, who can resist making one, an example being this one with 3D printed parts. And there are many more here for you to see.
Definitely a hack, using a neural network to essentially come up with a black-box implementation of a decryption routine. But I can’t help but point out that it’d be a lot more impressive if it managed to come up with the plaintext *without* also being given the decryption key…
I agree. The original team did not have the decoded messages to “train” themselves. If they had, I’m sure it would have been a much easier feat. But still, this is good work and very interesting.
They didn’t have keys, in the form of a working machine or the settings for it, not right away anyway, but the Enigma machine is heavily referenced on the Known-plaintext attack Wikipedia page. So they did have decoded messages to “train” themselves.
And from what I understand, the two main known plaintexts they used were the weather reports in the morning, and the fact that “Heil Hitler” was at the end of pretty much every message.
Which is why the RAF was told to stop sinking German ships reporting the weather …
Enigma was cracked because of an operator error. A message was sent but receipt was not acknowledged, so he sent the message again. The break was the second send was *not 100% identical* but the operator used the same key. Both sends were intercepted by Allied communications.
The people at Bletchley Park were able to use those two slightly different messages encrypted with the same key to at least partially decode them. That gave them a huge leg up on decoding other messages. When the British navy made the first capture of an Enigma machine, that made figuring out the rest all the easier.
Nope, you’re mixing up two different stories. The recent message story relates to how the allies cracked the Lorenz Cipher machine, aka tunny, used to transmit very important messages between branches of the German High command. Look up the work of Bill Tutte for more detail.
Enigma on the other hand had been worked out pretty completely by the Poles long before the war started, and the Brits weren’t a huge way behind them.
But they did have some decrypts from messages where various posts were reusing keys. Once they had those keys?
Interesting, as I believe reports within the past decade stated that there still is a backlog of undecoded WWII Enigma messages. Decoding them could spread an interesting light on history.
From: Obergefreiter Quartermaster
To: Unteroffizier OberQuartermaster
Request urgently
10 pairs woollen socks size S
12 pairs woollen socks size M
14 pairs woollen socks size L
In other words, I think they had a good idea what to look for and what to discard, the radio listening stations just copied everything, the decoders undoubtedly selected what they thought might be the most important, but yes they must have missed some things.
Nice try, but german is more than “VERBOTEN” and such. Sizes S,M and L, come on!
It were often used keywords like OBERKOMMANDODERWEHRMACHT or WETTERBERICHT.
In fact, some senders posted a daily weather report, reusing the same starting phrases every morning.
Those cribs alone would not have sufficed. It was a combination of several lucky circumstances. Polish crackers had already decoded one of the drum wirings (which astonishingly was “ABCDEFG…” !). Recurring phrases were prohibited, but the confidence in technological supremacy lead to levity. Some of the design decisions of the Enigma looked like a good idea but actually narrowed the key space (e.g. letters could not be coded as themselves).
I wonder how neuro nets perform with AES…
I assume that’s an example of the types of messages which you presume are undecoded, because the Bletchley folks figured from traffic analysis that it wasn’t likely to be important?
The original team had a commercial version of Enigma (for businesses that wanted to encrypt their telegraph or telex messages) before the war. They also had some luck because they grabbed encrypted messages sent by unexperienced operators, who didn’t follow procedure correctly. They also used statistical analysis of message prefixes to find both keys used and internal wiring of the machine.
They kind of did, though. Aside from the rare seized decrypted message, they also made good use of causality. If a bunch of messages in a short time contained the same string or pattern, and shortly thereafter So-and-So was attacked at 6 PM, the codebreakers could infer that the words “So-and-So” and “6 PM” were in those messages.
This is certainly less info than the neural net had to work with, but the codebreakers were certainly not shooting in the dark.
Enigma as used by the Germans during WWII had 26 letters on each encrypting wheel which means that there was no punctuation, no numerics, none of the extra diacritical German characters, and no space character. They overloaded the X by using it as the space between words. Late in the war the Germans went to a 4 wheel configuration and only generated 5 wheels that the changed the order of every day. I have written a software version of the Enigma Engine and allow the user to generate as many wheels as they would like, and encrypt with as many wheels as desired and each with different initial displacements. I have been testing it with million character strings of a single character and the resulting encryption is devoid of pattern. It also supports UTF-8. By using 7-bit ASCII while encrypting using 8-bit ASCII as a superset and the message comes back out just like it went in. This would give the neural network a challenge.
The Black Chamber.
If you can make it to Maryland, the NSA has Enigma machines you can try out.
https://www.nsa.gov/about/cryptologic-heritage/museum/exhibits/#enigma
There are a lot of other exhibits that are pretty interesting too!
Truly a really interesting hack Steven! I wished I understood it better. Maybe if I keep re-reading it a few times I’ll finally get it. :-)
I know what you said about history of these machines, and it’s true, however, the Nazis nor the Germans can claim fame to imaging this sort of intriguing and complex device. Some attribute the device’s first imagining to Germany’s Arthur Scherbius and 2 other parallel thinkers (Koch (Netherlands) and Damm (Sweden)) around 1918. However, a lesser known pre-Scherbius inventor was deliberately kept in the dark by US military intelligence community (of the time) was really the first person to think this up while in prison in US in 1908 for horse theft of all things! His name was Edward Hugh Hebern (April 23, 1869 – February 10, 1952) from Illinois (USA).
Apparently he thought this up in jail twiddling his thumbs trying to come up with using an electric typewriter style machine to cover up his alleged future potential criminal machinations from the LEO’s of the day. Leave it to a convict to think outside the box. Well the long and short of it a clever US government cryptologists who latter went onto work for the NSA in the 1950’s, figured out (albeit very difficult) how to break the method and use it to develop his own hardened system (i.e. SIGABA) the Americans secretly used during post WW1 & during WW2 while the Nazis were using a hardened version of Scherbius’ Enigma.
He later went to jail AGAIN for allegedly defrauding Uncle Sam, but was really just the cover story to keep this new gadget away from the press and ostensibly from Hitler and Tojo’s attention. So Hebern was the “mushroom” here and had to do more time to help maintain OPSEC (operational security). Albeit, he was never let in on the secret (hence the mushroom metaphor – kept in the dark and fed manure).
The SIGABA inventors allegedly went to Bletchley Park (authorized of course) to look at what Turing (et al) was doing and offered some technical insight on the matter. I think the Americans had a corporation already secretly manufacturing them before Enigma. Namely the famous NCR Corporation (still making cash registers etc. today). However, SIGABA was a behemoth unlike the small portable nature of Enigma.
So yes I do attribute TURING and crew for winning the war, however, there were other pioneers before him.
Check out Tatjavan’s version, She is so uber-cool:
http://www.tatjavanvark.nl/tvv1/pht10.html
Jeez, you guys really need to stop using Jimmy’s jerkapedia as a reference source.
There was no deep, dark conspiracy to keep encryption tools from the public or even the Germans.
We didn’t care during WWI and continued to trade with them up until 1917. During WWII, the State Department openly supported Germany against Britain – read Ambassador Kennedy’s writings from that time – while we continued to trade with both sides up until the attack on Pearl Harbor.
Hebern’s machine is relatively unknown because it’s own shortcomings. It was a single rotor design with the key physically embedded in the rotor amongst other things. The army bought a few but it was actually worse that what they were already using.
I wonder how it works on “purple” compared to enigma.
Another WW2 encryption puzzler is how Japan never caught on that we’d broken one of their main naval codes some time prior to their Dec. 7, 1941 attack. We had their list of targets but they’d made sure to never transmit the chosen target nor the date and time of the attack in any electrically interceptable way. I assume they delivered sealed orders by courier to Admiral Isoroku Yamamoto, with directions to sail to specific coordinates before opening them.
The US government did know in advance that Japan was planning an attack on some US territory or possession, but despite the fact that Pearl Harbor was the bleedin’ obvious choice for best chance to cripple the USA militarily, the FDR administration still had the fig leaf of not knowing exactly where and when. That’s most likely why the aircraft carriers were out of port that Sunday, and the missing carriers were likely why Yamamoto didn’t press the attack. He was a smart guy, likely figured that he’d best cut and run before we could get our carriers after his fleet. He had no idea where they might be, could’ve been hull down just over the horizon. He had plenty of time to recover the planes, rearm, refuel and send them back for a second go at destroying more stuff. Most of our planes were already damaged or destroyed on the ground.
Allowing Pearl to get hit would’ve been Step One in not tipping our hand to Japan about breaking their code. A prepared defense would (should!) have told them their code was cracked. ‘Course why they never caught on throughout the rest of the war as they ran into Allied forces time after time…
The cracking of Enigma was perhaps one of the greatest technological feats of WW2 which kind of makes me proud to be British however at the same time embarrassed of the post war treatment of Alan Turing. The man was a genius up there with the greats and was sadly left to kill himself because of his sexuality and British law at the time.
I know it was a different era then however the man saved possibly millions of lives and lost his because of the way our government treated him.