What is "quantum safe"?

[peter-h]

This is the latest thing in crypto... From the latest MbedTLS mailing:



Is it just huge RSA keys, etc?

The only defence against a fast computer has always been longer keys. It can't be different algorithms, otherwise why not use them right now? Well, except for the one time pad, but you have a key management issue there

[ataradov]

No, there is a whole new set of algorithms that have nothing to do with currently used algorithms.

https://www.nist.gov/news-events/news/2022/07/nist-announces-first-four-quantum-resistant-cryptographic-algorithms

You can't just use them 100% because they are still being tested. There were a few that passed initial rounds of testing and failed almost at the stage of approval. The ones that remain seem to be pretty solid.

Some implementations use both at the same time. Use classical stuff and then quantum resistant on top of it. If quantum breaks, no big deal, classical stuff will provide protection.

[Bud]

Do not bother, there will be no quantum computers capable of breaking existing public key scheme encryption for the next 15 years at least.

Edit: answering the question, quantum-safe means the algorithm is resistant to attacks using quantum computers, when they become viable (nobody knows when).

[helius]

Cryptologic algorithms that rely on the hardness of factoring or discrete logarithms have never been proven to be secure, because the hardness of these types of math problems is still unproven. It is completely possible that a non-quantum approach to factorization could break RSA. But a quantum algorithm for solving those problems in linear time was already published by Shor in 1994, which is exponentially faster than the best known classical algorithms based on the General Number Field Sieve, which have exponential complexity.

As to the timeframe when quantum computers that can actually apply the Shor algorithm might exist, you need to remember that some secrets need protection for a long time. If it's likely that a cryptosystem might fail 30 years from now, you should stop using it right now if your secrets are that important.

[Bud]

Just use symmetric AES 256, it is quantum safe.
For asymmetric key wrapping or signature, the new FIPS 203, 204 and 205 are certified as quantum safe.

[peter-h]

Cryptologic algorithms that rely on the hardness of factoring or discrete logarithms have never been proven to be secure

Surely very few algorithms are provably secure. But maybe the issue is that there is a fear that quantum computers will be able to do factorisation rapidly, which is definitely a way to crack RSA (and others).

[Siwastaja]

Do not bother, there will be no quantum computers capable of breaking existing public key scheme encryption for the next 15 years at least.

This brings us to the key deciding factor:

Is it important to keep recorded communications safe, and for how long?

This always isn't an issue at all. For example for our "smart heating controller" box, the threat factors are gaining unauthorized control, and thus authentication of the participants, and inability to alter the data, or record it and play it back, are the primary goals. For us it would not matter if someone recorded the data and were able to break it after 15.00001 years with a quantum computer, only to see how much power someone consumed 15 years ago and if their electric boiler relay was on.

Then again, someone else could be encrypting state secrets. Maybe names of agents whose life becomes threatened if the information leaks. Different outcome - "quantum safe" is needed already today.

[golden_labels]

Going post by post.

Post-quantum cryptography isn’t a “latest thing.” The problem is known for 30 years. The first viable algorithm was presented around that time too. In the past decade existing solutions reached sufficient maturity and people also realized it may be the right time to deploy them. Recent years see this trend surfacing. But it’s just the tip of a decades-deep iceberg.

For the entire thread it’s important to note that RSA is an ancient technology. Now we’re talking about ECC. It allows much better key space usage,⁽¹⁾ and offers different performance characteristics. But it is also vulnerable to quantum computing attacks and, similar to integer factorization, there is no proof of non-existence of a classical attacks.

It’s not a matter of longer keys. In both RSA and ECC the underlying problems are vulnerable. If big enough quantum computers become viable, these cryptography solutions will get their mathematical foundations shattered.

One of the reasons post-quantum algorithms were not deployed so far and their uptake is slow, is the need to ensure implementations are not considerably more expensive than ECC (or RSA). Time is also needed to recognize potential side-channel attacks. It doesn’t matter a quantum algorithm can’t break lattice-based cryptography in 2040, if in 2024 a script-kiddie armed with a laptop can send 10 GB of data to recover server’s key by observing timings.

I don’t understand the dismissive tone of “don’t bother.” A 15 years horizon is not an optimistic vision. Not sure about mentioning symmetric encryption (AES-256) either. It plays no role here, as the topic is only about the asymmetric cryptography.

The mention of proofs above was not about the encryption having a proof, but the underlying mathematical problem. We may have an algorithm, whose strength is based on a proven claim. Both RSA and ECC are based on the claim, that integer factorization and discrete logarithms are impossible to solve in polynomial time using classical algorithms. But we only believe this to be true: neither was ever proven. This is separate from any potential weakness affecting one of multiple features a cryptographic algorithm needs to offer. However, there are some hard truths based in physics. For example 128-bit keys⁽²⁾ can’t be brute-forced using any foreseeable technology. For 256-bit keys that becomes unconditional. There are also logical impossibilities. No encryption, even Caesar’s cipher(!), can fail its confidentiality promise without some knowledge about the plaintext.

⁽¹⁾ Higher entropy per key’s bit. RSA keys are represented as numbers. Only some of those numbers are suitable to be used for cryptography, leaving large areas of the space unused. ECC key space is denser, giving the same results for much shorter keys.
⁽²⁾ Actual keys’ entropy, not the number of bits used to store the key.

[peter-h]

a script-kiddie armed with a laptop can send 10 GB of data to recover server’s key by observing timings

That requirement may lead to hardware-only approaches as it did with e.g. DES whose software implementations mostly had key dependent timings.

Not sure about mentioning symmetric encryption (AES-256) either. It plays no role here, as the topic is only about the asymmetric cryptography.

Is it? Maybe it is but I was not aware.

Maybe names of agents whose life becomes threatened if the information leaks

I hope nobody is sending agent names in such a way Or identifying info. Yes I have read much about the Venona project, etc, so people have done it. But one hopes nobody does it today.

[Bud]

I don’t understand the dismissive tone of “don’t bother.” A 15 years horizon is not an optimistic vision.

OP's post came in the context of mbedTLS. I repeat - do not bother for mbedTLS. If someone is using mbedTLS to encrypt state secrets, he has a bigger problem.

[golden_labels]

a script-kiddie armed with a laptop can send 10 GB of data to recover server’s key by observing timings

That requirement may lead to hardware-only approaches as it did with e.g. DES whose software implementations mostly had key dependent timings.

Hardware implementations are as vulnerable. And much harder to fix.

Not sure about mentioning symmetric encryption (AES-256) either. It plays no role here, as the topic is only about the asymmetric cryptography.

Is it? Maybe it is but I was not aware.

Quantum computing is considered a threat primarily to asymmetric cryptography. Public keys reveal significant amount of information about the private (secret) key. You can almost directly calculate a matching private key from the public key. In fact any IT/CS student should be able to break RSA with a pen and paper. I myself had to do this on an exam. The catch: the amount of work needed grows quickly with key size. So while it’s trivial for small integers, doing so for 4096-bit values is prohibitively expensive.

With symmetric ciphers this isn’t the case. There isn’t any such clear relationship, no ready equations to calculate the key from anything, no way to easily verify the result. If either is possible, it’s a vulnerability and it has to be discovered. In that sense quantum computing may lead to some vulnerabilities being exploitable even in symmetric ciphers. But this is very different from asymmetric cryptography, where the way to break a cryptographic primitive is literally given along with its definition.

In either case, classic or post-quantum, asymmetric cryptography isn’t used to actually encrypt data. It would be too wasteful. Encryption is done with cheap symmetric ciphers (like AES) and asymmetric part is used only to negotiate the encryption key.

OP's post came in the context of mbedTLS. I repeat - do not bother for mbedTLS. If someone is using mbedTLS to encrypt state secrets, he has a bigger problem.

That’s an interesting claim. What is the vulnerability in mbedTLS, that leads to that conclusion?

I would also ask, how state secrets got involved in this, but I’ll skip that. Now I see Siwastaja sent a message with that phrase 21 seconds before my reply.

[radiolistener]

Do not bother, there will be no quantum computers capable of breaking existing public key scheme encryption for the next 15 years at least.

I think almost all approved algorithms are already compromised...
They are designed to protect against honest people who will not hack them.
So there is not a big difference if its quantum resistant or not.

[peter-h]

I repeat - do not bother for mbedTLS. If someone is using mbedTLS to encrypt state secrets, he has a bigger problem.

I just happen to be using MbedTLS and that extract in post 1 is from their mailing list. For sure nobody should be using an embedded product in some super secure application. The most likely scenario is the standard IoT stuff e.g. heating controllers, various telemetry stuff, etc. In the ref manual for my last project I tell people to only ever set it up as a client, never a server and never on an open port. You just can't be sure that 32F4 ETH + LWIP + MbedTLS is secure; there is insufficient deployment with open reporting going on.

Quantum computing is considered a threat primarily to asymmetric cryptography. Public keys reveal significant amount of information about the private (secret) key. You can almost directly calculate a matching private key from the public key. In fact any IT/CS student should be able to break RSA with a pen and paper. I myself had to do this on an exam. The catch: the amount of work needed grows quickly with key size. So while it’s trivial for small integers, doing so for 4096-bit values is prohibitively expensive.

OK - a good explanation!

[Siwastaja]

MBedTLS could be used for example on a IoT security camera, or smart lock / access logger. In such case, revealing that someone entered the home or had sex with someone would enable blackmailing or other nasty stuff even 15 years from now. Probably nothing of interest 100 years from now, though.

So I wouldn't rule out the question of "quantum safe" even in the context of small embedded systems.

[coppice]

Quantum safe means you are the smallest possible step away from being unsafe, so even the smallest improvement in attacks will kill you. 

[peter-h]

MBedTLS could be used for example on a IoT security camera, or smart lock / access logger. In such case, revealing that someone entered the home or had sex with someone would enable blackmailing or other nasty stuff even 15 years from now. Probably nothing of interest 100 years from now, though.

I know this is getting well off topic but for the above blackmail to work, the attacker would have to have been capturing the camera data for the 15 years, and then set about cracking it to see if there is something dodgy I guess that once the private key is calculated you can read all 15 years of traffic, but it will be a huge amount of video to go through.

The realistic attack surface will be way too small for this to work, and I suspect this will be true for nearly all IoT applications.

The security camera angle has already been well tested, with AXIS IP (ETH) cameras being sold with admin/admin config on HTTP, and quite a large following of perverts watching the videos, thanks to google having indexed up the cameras

A bigger problem might be cracking the private key of a high value product sold in vast numbers. An example is inkjet cartridges; the Canon private key was leaked from the factory.

[Siwastaja]

I know this is getting well off topic but for the above blackmail to work, the attacker would have to have been capturing the camera data for the 15 years, and then set about cracking it to see if there is something dodgy I guess that once the private key is calculated you can read all 15 years of traffic, but it will be a huge amount of video to go through.

Don't forget this camera could be in a home of a well-known politician or celebrity. Yellow media already goes to great lengths, some to illegal measures to spy on people like this. Imagine how difficult it is to be the president of any country. Or think about how princess Diana died.

Storing 15 years of any data that can be gathered about a "person of interest" is no big deal at all. It's not even "big data". Maybe just some hundreds of GB. Totally negligible effort and cost, if you are genuinely interested about someone. And celebrities always have bunch of those stalkers hanging around.

For the "average Joe" with nothing interesting going on with their life, pretty much the only risk is them being used in some sort of DDoS attack (internet activity, or think about heating controllers increasing power consumption all at the same time in an attempt to affect power grid); recovering data 15 years from now is not an issue to most.

But it doesn't mean this should be completely ignored either. Some small sub-% of people can realistically have secrets they don't want to leak even in 15 years, even in their IoT devices.

[peter-h]

Right but you still need to intercept the data.

Most likely route is monitoring somebody's WIFI and then you have WPA-PSK to deal with first. Is that also quantum-vulnerable? AIUI it is a shared key system.

[rteodor]

Veritasium video on the subject: How Quantum Computers Break The Internet... Starting Now.

Lattice based Q-resistant algorithms after 17:00

Later edit: correct link below in post #22.

[Siwastaja]

Right but you still need to intercept the data.

You can assume that part is already done. Anything else than end-to-end encrypted is known to break in the real world. If you are any kind of person of interest, that is.

For example, home routers are notoriously insecure, just some random Chinese crap cobbled together in a hurry and never any security updates applied to. (+ intentional backdoors, of course).

Or other IoT boxes in the same network leak. They have your wifi key configured and can listen to traffic. This is why the "safe firewalled / NATted internal network" idea is totally braindead. Everybody knows it even if you have hard time accepting it.

End-to-end encryption is really the only layer of security that can actually be made reliably safe. Not saying even that is obvious or easy, but it's possible.

I'm not saying every script kiddie can listen to your home network traffic, but anyone with enough time, motivation and maybe some good connections to the suitable experts can, it's not limited to top-notch NSA folks. A paparazzi can do it if they are sure enough that something they can make big headlines about happens in peter-h's house.

[peter-h]

rteodor that video has been taken down

[rteodor]

rteodor that video has been taken down

Damn, I'm too slow for this this internet thingie ...
And too bad as some of Derek graphical explanations are so good that directly imprint into memory.

[MK14]

rteodor that video has been taken down

Damn, I'm too slow for this this internet thingie ...
And too bad as some of Derek graphical explanations are so good that directly imprint into memory.

It seems to be here:

[peter-h]

Everybody knows it even if you have hard time accepting it.

Siwastaja, there is a shop near here

It seems to be here:

Thanks

[5U4GB]

Do not bother, there will be no quantum computers capable of breaking existing public key scheme encryption for the next 15 years at least.

According to someone who's actually done the math, it's not 15 years, it's 4,000 years.