Cracking Enigma in the Quantum Era

Every encryption specialist must have heard about Enigma, an encoding machine already developed in the twenties by a company called Chriffriermaschinen AG but mostly known by the use of the Nazi’s during World War II. Eventually, after almost six months of hard work Alan Turing and his team managed to crack the code used by the German forces. Since then, mankind has been striving for safer methods of encryption. However, with the dawning of quantum computing, will the existing encryption algorithms be sufficient for the coming years?

The question is becoming very relevant, since a number of universities and companies are on the verge of actually having a real quantum computer between 2025 and 2030. At the Technical University of Delft in the Netherlands, teams are even studying quantum connectivity using quantum teleportation. If you want quantum computers to communicate with each other at quantum speed, you need something quite different then the internet as we know it today.

AES

We rely these days on encryption to communicate safely, based on the symmetric encryption technology used in AES. The big question is how “safe” – as in: unreadable for unauthorized people – the data will be when we have this new quantum technology available. Basically there are two opinions in the field. The first one is that AES-256 is safe enough. Even quantum computers would not be able to solve this encryption in a reasonable time. However, the opposite opinion that a quantum computer might actually crack the algorithm in a reasonable time, has gained a lot of support over the last year.

Literature studies show ‘evidence’ for both opinions. Yet, if you read all these reports carefully, they do seem to agree at a certain level: AES is “safe”, yet could be decoded if one has enough time. One of the most recent studies is ‘Quantum Security Analysis of AES’ by Xavier Bonnetain, María Naya-Plasencia and André Schrottenloher of the Sorbonne University in Paris, France. According to their study AES-256 could be decoded using a quantum computer with as less as 1200 qubits, using Grover’s algorithm. The Grover algorithm was originally developed to issue searches in unstructured databases. To put it very simple: in a number of (infinite) iterations it calculates the one element that deviates from the state that all other elements in a specific system have. It makes the algorithm extremely suitable to decode AES.

How does it work? AES uses so-called S-Boxes. The algorithm calculates the byte ordering per S-box. The math as presented by Bonnetain and his colleagues shows that in seven rounds (iterations) Grover would be able to solve the byte ordering per S-box. The big trick is that using parallel computation – something only a quantum computer can do – it can run the algorithm on all boxes at the same time. It does not have to do this in sequence like a traditional computer would have to do. It would mean that AES-256 can be cracked. The only remaining question is: how much time would it take?

New methods

Hence, there’s a good reason for companies like IBM, Google, Microsoft and Fujitsu to explore new ways of encryption. NIST closed a second round of inventory on January the 30th, resulting in over twenty initiatives for new encryption methodologies. Most of these initiatives are based on lattice-based cryptography that eligibly has to be quantum safe. The problem with lattice-based cryptography is that it does produce a lot of overhead on traditional computer stacks, exactly the problem that we won’t have on quantum computers.

Back to Enigma one more time. It took Turing six months to solve the encoding algorithm of the Enigma-machine at that time. DigitalOcean ran a piece of single thread-Python code in 2017 on 2.000 virtual machines, cracking Enigma in 13 minutes at a 7,- USD cost. Nothing quantum here, but as we speak we have quantum simulation or annealing and it’s available for all of us. Microsoft offers quantum simulation in Azure, up to 40 qubits. It would take way, way less than a second to solve Enigma using Quantum Azure.

That would be just ‘playing around’, fair enough. It doesn’t prove anything in terms of concluding that existing encryption will be strong enough in the use of quantum computing. However, it does provide a tool to ‘practice’ calculations on encryption. The samples to explore Quantum Azure contain for instance Shor’s algorithm, that can be used to crack public keys like RSA.

Conclusion

We should explore. We should investigate. And we should invest. I do think that with quantum computers and quantum connectivity, existing encryption based on AES-256 can be cracked. Using Shor’s algorithm the public key RSA can be decoded in a couple of days using quantum. Where a number of scientists think that AES-256 is still safe to use, I’m more cautious – meaning that I don’t have reasons to assume that quantum computers will not be able to crack AES-256 and possibly much sooner than we think today. They can and I’m sure we will live to witness this.

Allow me to quote prof. dr. T. Lange of TU Delft here as conclusion: ,,Unless a large group of people have overlooked something, an attack based on Grover would result in 2128 operations on 256bit-AES. However, I would never call something quantum secure.”