Engineering

How 2,000 Droplets Broke the Enigma Code in 13 Minutes

Posted: June 22, 20188 min read

In late 2017, at the Imperial War Museum in London, developers applied modern artificial intelligence (AI) techniques to break the “unbreakable” Enigma machine used by the Nazis to encrypt their correspondences in World War II. Using AI processes across 2,000 DigitalOcean servers, engineers at Enigma Pattern accomplished in 13 minutes what took Alan Turing years to do—and at a cost of just $7.

I have long been fascinated by the Enigma machine and its impact on World War II. Aside from being a huge history geek, my father-in-law went over to Normandy on D+3 (three days after the Omaha beachhead was established). He served in an advance corps, finding ways for the army to move across the country, and as such, they were the first to come across one of the concentration camps and liberate it. None of that would have been possible without Enigma.

The Enigma Machine

The Enigma machine is a complicated apparatus consisting of a keyboard, a set of rotors, an alphabet ring, and plug connections, all configurable by the operator. For the message to be both encrypted and decrypted, both operators had to know two sets of codes. A daily base code, changed every 24 hours, was published monthly by the Germans. Then, each operator created an individual setting used only for that message. The key to the individual code was sent in the first characters of the message, coded in the base code. This created over 53 billion possible combinations, changing every 24 hours. Because of this, the machine was widely considered unbreakable.

Marian Rejewsky, working with other mathematicians at the Polish Cipher Bureau, cracked an early version of the Enigma machine in 1932 by the tried-and-true method of stealing a few machines and reverse engineering the mechanism. It took him just under a year to figure out the general principle of the German military’s double message setting and the wiring of the rotors, and another year to catalog the settings. After all of that, daily keys could be obtained in under 20 minutes.

But as Germany revved up its war machine, the Nazi navy made the machine more complex with the addition of plugs and more rotors, making it impossible for humans to work through the billions of possible combinations. Enter Bletchley Park in rural England, where Alan Turing, a brilliant English mathematician, gathered a team of cryptographers, puzzle solvers, linguists, and mathematicians in 1939 with the mission of breaking the German codes.

“Enigma gave the foundation to Alan Turing to develop the computer,” explained Rafal Janczyk, a Polish mathematician and CEO and co-founder of Enigma Pattern.

Rejewsky and his team smuggled their cracked Enigma machines out of Poland, and worked their way to Bletchley Park where they donated the machines and their expertise to Turing. Building on Rejewsky’s work, Turing was able to automate the cryptography that could crack the daily code. It took the better part of a year to decrypt their first message. They called their work the Bombe, and it’s widely considered to be the first computer.

But it was more elaborate than simply breaking the code. Because the Nazis changed the rotor settings every 24 hours, each new day brought a new set of 15,354,393,600 password variants that had to be decrypted. Many times they worked through the night only to fail to break the code and have to start over the next day.

It was an exhausting, near-impossible task. And, seven decades later, Enigma Pattern wondered how modern technology like AI could change things, and if they could break the code in a fraction of the time.

Geeking out: Breaking Enigma with Modern AI

“The project started from the question, ‘What would Alan Turing be able to do nowadays if he had the current computing power and all the development around AI,’” said Janczyk. Since AI is still such a new discipline, the company allows their employees to spend 20 percent of their time on side projects of their choice that encourage out-of-the-box uses of AI.

Retracing Turing’s footsteps was a pet project of Lukasz Kuncewicz, Enigma’s Head of Data Science (and another Polish mathematician co-founder). Kuncewicz chose this project to refer to the common history of Brits and Poles using human intelligence to overcome the biggest obstacles of the Second World War. (Their third co-founder, Mike Gibbons, is British).

Kuncewicz decided to recreate the Nazi navy’s version of the machine, which was the most sophisticated. His team started by recreating the machine, rotors, and plugs in Python. Initially, they tried to teach their AI to decode the Enigma code itself, but it didn’t work. Neither did Lambda functions from Amazon.

The problem, he said, was with the amount of computations. “Since the Lambda function from AWS is not very quick, and has some limits regarding execution time, the number of concurrent Lambda calculations was very high. So high that we actually spent more than a week going from one AWS department to another, trying to squeeze a decision from them regarding extending our limit.”

Enter DigitalOcean. “We only use [DigitalOcean] for quick ‘bish bash bosh’ needs—they are very good when we need to have a bigger server run for a few hours,” he said. Enigma Pattern uses DigitalOcean for a variety of things—from learning environments, to quick compute tasks where results will be stored on their internal computers, to prototyping projects when they’re not sure yet how many machines will be needed.

When Enigma mentioned the project, DigitalOcean quickly agreed to provide the ML 1-Click Droplets. It fit the company’s developer focus, said Mark Mims, the R&D Engineer who designed the ML 1-Click that launched last year, and demonstrated the ease of use, as an ML 1-Click Droplet can be spun up in a few minutes with (you guessed it) one click. “But if you’re looking to spin up 2,000 servers, you won’t be using the web UI,” said Mims. “That takes a call to the help desk.” Within half a day, DigitalOcean had hydrated the 1,000 droplets used in the testing phase.

The next step for Kuncewicz and his team was training an algorithm to recognize German, which they did by using Grimms Fairy Tales, including Hansel & Gretel, Rapunzel, Cinderella, and Rumpelstiltskin; 200 tales in all. Why children’s stories? Well, it’s not like the AI had to decrypt German philosophy, but instead military telegraphs, which use as few words as possible. Fairy tales are also written in simple language, so it makes sense. And it worked. Interestingly, in the end the AI could not understand German. But it did what machine learning does best: recognize patterns.

Fairytales

It took two weeks for the team to train the machines and create the Python code, and another two weeks for the first successful attempt to decrypt a message. But in order to copy Turing’s success, a successful decryption had to be done in less than 24 hours.

Then they decided to try to break it by using sheer computing power, adding another 1,000 Droplets. I’ll let Kuncewicz explain the details:

“First,” he said, “one has to accept the fact, that even if you have 2,000 Droplets, you still have billions of combinations to be checked. And the neural network that we used, however good at spotting the German language, is not a speed demon.

“It’s because it uses recurrence, which gives you this boost when dealing with languages, but you pay with the calculation time. So the idea is, you need to separate the wheat from the chaff, and use the network only to check the best possible candidates.

“So for the AI to shine, we actually use 2,000 minions that do the tedious work. Everybody praises AI, but it’s actually the minions that do the 99% of work. Life, right?”

“We wrote one minion in Python, and DigitalOcean has this very nice API for storing images. So you create one minion, say ‘DigitalOcean, please save it as an image,’ and then you say ‘DigitalOcean, please create 2,000 copies of it and make them run,’ and you have them.

“The code is really simple. It connects to the bus and gets a first not-yet-taken assignment. The assignment is a package of the gibberish text (the encoded message) and combinations of passwords to run on it. It checks the gibberish against every password, checks if the decoded message sounds like German, and if so, sends it through the same bus for more detailed inspection by the AI.

“And this is exactly what the Droplets do. They get their share of password combinations from RabbitMQ, they take a few letters of the gibberish they need to decode, they decode it using the given passwords, and apply a very crude (but very quick) check if at the end of this pipeline we have something that resembles German.”

If the code looks like German, it’s pushed back to the main server where the AI works its magic.

“The job is not coordinated in any way, each minion doesn’t know anything about others—they are fully autonomic. This is great, because it means that we can have 200, 2,000, or 20,000 of them if we like (and if DigitalOcean allows). The more we have, the less time will pass before breaking the Enigma code.”

The 2,000 virtual servers ran through 41 million combinations per second. After 13 minutes of minion work, boom! The new Bombe had broken the code.

AI uses

Enigma Pattern: Who are these People?

“AI is being called the new electricity,” said Janczyk, “because it will be in everything.” Enigma Pattern works with companies that already collect big data but are unsure of the ways to harness its power. “You would be surprised at how many companies store big data but don’t know how to put it to use,” he said. “For example, a coffee chain would rather throw up a new store than delve through the data to determine how to optimize the stores they already have, because they know how to open a new store and don’t know how to dig through the data.”

One of their clients has a fleet of over 10,000 cars on which they collect a variety of raw data. Janczyk and his team sat down with the client to discuss the pain points of the business, how they might use the data they already had to help ease the pain, and how AI could help.

Tires are a significant business cost. In addition to the price of the tires is the cost of maintenance and driver downtime. If you don’t change the tires in time, you’re endangering the life of your drivers. Change them too often, and you lose money. It turns out, you can teach a machine to hear the level of wear on a tire.

“Out of the sound of the spinning tire, we were able to teach the machine the level of wear of the tire,” Janczyk said. “Now the company is able to change tires based on the sound of the wear and automatically schedule downtime to which saves lives and money.”

“With AI and ML, there is such an unlimited amount of possibility, which is what makes it so exciting,” said Janczyk. “That’s what makes my work fascinating,” he said, "finding new uses for AI.”

Who knows what mysteries AI will solve in the future? By appreciating the problems that Enigma presented to previous generations and applying modern techniques, we can expand our vision for what AI can accomplish in today’s world.

To see how Enigma functioned, check out this link or watch it in action on YouTube.

To learn more about Alan Turing and the work done at Bletchley Park, check out Andrew Hodges’ acclaimed biography of the computing legend, titled “Alan Turing: The Enigma.”

You can check out Enigma Pattern’s code on GitHub, with a warning from Kuncewicz that it’s a bit messy.

TC Currie is a journalist, storyteller, data geek, poet, body positive activist and occasional lingerie model. After spending 25 years in software development working with data movement and accessibility, she wrote her first novel during National Novel Writing Month and fell in love with writing.

Share

Try DigitalOcean for free

Click below to sign up and get $200 of credit to try our products over 60 days!Sign up

Related Articles

Dolphin: Mastering the Art of Automated Droplet Movement
engineering

Dolphin: Mastering the Art of Automated Droplet Movement

January 23, 20243 min read

DigitalOcean's journey to Python Client generation
engineering

DigitalOcean's journey to Python Client generation

January 26, 20233 min read

How DigitalOcean uses Let’s Encrypt
engineering

How DigitalOcean uses Let’s Encrypt

November 28, 20223 min read