NIST Announces Post-Quantum Cryptography Standards

https://spectrum.ieee.org/post-quantum-cryptography-2668949802

87 32 2 years ago

spectrum.ieee.org

tromp• 2 years ago

Old standards like RSA and ECDSA re based on the presumed classical hardness of the discrete log / hiddden subgroup problem, which is known to be quantum easy. New ones are based on lattice shortest vector problems, which are presumed to be both classical and quantum hard. But there's a risk that they turn out to be easy for both.

Is there support in the standards for combining the strength of old and new methods, so that successful attacks requires breaking both types of problems?

shandor2• 2 years ago

I think you can mostly achieve this by using the ciphertext from the quantum algorithm as the plaintext to the classical algorithm (or vice versa).

I wouldn’t trust any solution that combines the algos in some more ”clever” way, as the whole point like you say is to guard against the risk of unproven new algorithms.

mplewis9z2• 2 years ago

Please do not advocate rolling your own crypto - there are tons of pitfalls in nesting encryption algorithms like what you've just suggested. Besides, symmetric encryption algorithms aren't the biggest target of quantum computers, and in modern systems like TLS we really only use asymmetric encryption to exchange a symmetric key, and there are safe algorithms implemented by people who know what they're doing already available in most libraries.

mplewis9z2• 2 years ago

Yep, that's the approach being taken by companies like Cloudflare[^cloudflare] and Google[^google], but notably the NSA recommends _against_ that approach[^nsa] (though the cybersecurity community at large thinks that may be because using hybrids now is disadvantageous to them breaking communications in the future).

[^cloudflare]: https://blog.cloudflare.com/post-quantum-for-all/

[^google]: https://blog.chromium.org/2023/08/protecting-chrome-traffic-...

[^nsa]: https://news.ycombinator.com/item?id=38844117

zimmerfrei• 2 years ago

Yes, there are methods to combine multiple, different key exchange algorithms so that you need to break all, like in:

https://datatracker.ietf.org/doc/rfc9370/

https://datatracker.ietf.org/doc/draft-ounsworth-cfrg-kem-co...

https://www.etsi.org/deliver/etsi_ts/103700_103799/103744/01...

For other security mechanisms, like PKI, things are more complicated (and inefficient).

And one can argue that even if in theory the above gives you better security margin, the whole system becomes more complicated, and it may be practically less secure because of the additional moving parts. That is why there is no unanimous consensus: agencies in Europe recommend it, but the NSA does not.

Finally, note that the the 3rd standard (SLH-DSA), is PQC but it is based on old and well-understood standards (SHA2/SHA3), so it can arguably be used by itself.

Retr0id2• 2 years ago

FIPS 205 (SLH-DSA) relies only on the security of hashing - but that's just for signing, not key exchange/encapsulation.

(and as others have pointed out, classic/post-quantum hybrid schemes exist)

mbStavola• 2 years ago

Kyber was a great name, a bit sad we can't preserve a little bit of fun in standardization. FIPS 203 just doesn't hit the same!

bongodongobob• 2 years ago

Looking forward to our security team wanting to implement this to justify their usefulness.

modeless• 2 years ago

How are people supposed to choose which one of the four to use?

Vecr3• 2 years ago

Not Kyber-512, because of questionable long-term security. I'd say the strongest one your application can tolerate (a level 5 if you can tolerate it, otherwise a level 3), but other people have other priorities.

Edit: but don't use a level 5 alone if you can use a level 3 hybrid. The risk's still too high to use these algorithms alone.

charlieyu1• 2 years ago

Interesting question. RSA was the only option back then, then we have ECC that is a clear winner.

But this time there doesn't seem to be a clearly superior option and it may well end up with everyone choosing their own

feverzsj• 2 years ago

With post-quantum back doors?

lvh2• 2 years ago

These standards are developed out in the open.

Are you suggesting a true backdoor, or just "the NSA knows something about lattice algorithms the rest of us don't"?

nabla9• 2 years ago

For maximum post-quantum security KEM Classic McEliece has the strongest security track record.

https://mceliece.org/

https://classic.mceliece.org/

The large key size may be a problem for some uses.

bayindirh2• 2 years ago

I wonder whether we will find (un)intentional weak points in these algorithms down the road, too.

After reading Crypto AG scandal, I can't trust anyone easily.

dogma11382• 2 years ago

The IBM/NSA teams discovering differential cryptanalysis and sitting on it until Biham and Shamir independently discovered it a decade later is a better example.

And even then they did use that knowledge to make DES more resistant to it rather than simply ignoring it. It wasn’t made public because at the time - early to mid 70’s it would’ve made most other block ciphers very beakeable. DES wasn’t broken until the late 90’s.

CryptoAG was about backdooring an implementation not an algorithm or finding a novel attack.

bayindirh2• 2 years ago

I know the difference, and I'm aware that Crypto AG scandal is not the same thing as not selecting better curves or withholding new techniques or exploits.

On the other hand, the end result is the same: lower security. It's irrelevant whether you backdoor an implementation (it was actually weakening the algorithm itself), design something with backdoors, tap dark fibers or lobby politicians for escrow laws.

It's about the spirit of the motivation, not how you achieve it.

kanbrtka• 2 years ago

They did make DES more resistant (but for all we know they had another method of breaking it). But they tried to foist Dual_EC_DRBG on everyone:

https://en.wikipedia.org/wiki/Dual_EC_DRBG

benreesman• 2 years ago

I have no idea how one person could have this much sophistication in their evening/weekend work on their dots: but for an example of some hard core BQP as daily driver:

https://github.com/xddxdd

lvh2• 2 years ago

We did an updated version of the Cryptographic Right Answers for PQC. Given how quick the field is moving, I'm sure we're going to have to edit it a bunch :)

https://www.latacora.com/blog/2024/07/29/crypto-right-answer...

udev40962• 2 years ago

Is ed25519 resistant to quantum computers?

Vecr3• 2 years ago

Less resistant than 4096 bit RSA, so not really. Depending on what speedups pan out in real hardware.

udev40962• 2 years ago

From https://ed25519.cr.yp.to/:

High security level. This system has a 2^128 security target; breaking it has similar difficulty to breaking NIST P-256, RSA with ~3000-bit keys, strong 128-bit block ciphers, etc.

ramchip• 2 years ago

No. EdDSA (with any curve) relies on the ECDLP for security, which is broken by Shor's algorithm on quantum computers.

NIST Announces Post-Quantum Cryptography Standards

Related Stories