AI, Quantum Computing and Crypto – Not a Good Mix

Sorry, this is going to be a bit convoluted, so try to stay with me.

First we had encryption. Things were good. Encryption was based on mathematically hard problems and computers could not do the math, even in, potentially, a hundred thousand years.

Then came Quantum computing. Or at least it is coming. Or maybe it is here, but only to people with a lot of money like, say China. Or, maybe, the NSA.

So NIST, who is responsible for creating and vetting encryption algorithms for the government and industry, created some new encryption algorithms which would be quantum resistant (not quantum proof; more on that later).

Next comes AI. CRYSTALS-Kyber is one of the post-quantum algorithms recommended by NIST in 2022. Is is supposed to be quantum resistant. Unfortunately, maybe not.

Researchers from the KTH Royal Institute of Technology in Stockholm using AI combined with side channel attacks to, they say, break the algorithm.

They go on to say “Deep learning-based side-channel attacks,” say the researchers, “can overcome conventional countermeasures such as masking, shuffling, random delays insertion, constant-weight encoding, code polymorphism, and randomized clock”.

The researchers say that the technique can be applied to some other algorithms and even if it can’t be applied to all algorithms, they have opened up a whole new attack vector – one that does not even depend on having quantum computers.

NIST realized that developing secure algorithms in a quantum computing world might not be possible so they coined two terms.

Quantum safe encryption means it is safe until, well, it is no longer safe.

Quantum secure encryption means that it cannot be cracked using math. At least not with math that we understand today.

In building the post quantum encryption, they opted for quantum safe rather than quantum secure and it is coming back to haunt them even before the algorithms are even in use.

One researcher is complaining that the United States standards process requires someone who submits, say, an encryption algorithm, to be a proposed standard must give up the intellectual property rights to it. That is true, but there is nothing to stop someone from creating and selling an algorithm that is not a standard. If they think their stuff is so great, maybe the government won’t use it, but everyone else will. Therefore, while I understand the complaint, it is not that valid. That rule is unlikely to change. Researchers would like to be able to claim that the next encryption algorithm was invented by them.

So what comes next?

I am not sure who developed this model, possibly Apple, but there are five levels of encryption in this model. See the picture below:

Level 0 would be, for example, general email or text messages.

Level 1 might be iMessage, WhatsApp and other encrypted messaging apps. That is where we stop today in the pre-quantum computing encryption world.

Level 2 is what Signal messenger has announced. They call it Signal with PQXDH. It is a step towards post quantum secure communications, but not the end game.

Level 3 is the next level of post quantum encryption and Apple claims to have done it with what they call iMessage with PQ3 or post quantum level 3. Again it is not the end game, but they say, with constant rekeying, they will be able to limit the number of messages that are compromised. They also say that they will be implementing it this year in Apple products.

Of course, we thought Crystals was secure for four years until it is no longer secure.

PQ3, they say, is a combination of classic elliptic curve crypto with post quantum algorithms added in. It limits, according to Apple, the number of messages that are compromised when a single key is computed. If multiple keys are compromised, well, it is not as secure.

Again, a good step and an improvement, but we won’t know if the claims are valid for years. Until some other researcher says EUREKA! And then we move on to try and find the next generation of algorithms.

Finally, we have the level on the far right, which is whatever is next.

Point here is that this is going to be an arms race for the foreseeable future. Historically, encryption algorithms have had a life expectancy of decades. That version of fantasy is now history.

The challenge has been and is that it is really hard to rekey everything that has been encrypted in the past. We are going to have come up with a new reality and a new strategy for migrating to a new family of encryption algorithms every few years. This is not going to be easy. Right now we don’t know how to do that effectively but we will have to learn.

Credit: Security Week and Security Week

by