7 ms·

Cryptographic Right Answers: Post Quantum Edition

109 points by lvh 2y ago

CodeVenturer 2y ago
[dead]
- hannob 2y ago
  What you got now as new standards is already the result of multiple iterations of improvements in key size reductions and performance improvements. But you'll likely not get drop-in replacements for existing public key crypto in post-quantum variations. It appears signatures are even more challenging regarding size than encryption in the post-quantum world. It may be worth noting that choosing the algorithms that are now chosen, which are primarily lattice-based, is already kinda a compromise. They're not the ones with the highest trust in security, which would've been McEliece and SPHINCS (though the latter has been standardized as a fallback). But those come with key and signature sizes that are entirely impractical for the most common use cases. It appears most of the crypto community came around thinking that the somewhat-smaller lattice algos are now "almost certainly secure". But surely there's at least one famous cryptographer raising his voice that he still has concerns.
- candiddevmike 2y ago
  AIUI part of the problem with size is due to hybrid setups. Size could probably be reduced if you only used a PQC algorithm instead of combining it with existing crypto.
- nmadden 2y ago
  Yes, Kyber (ML-KEM) ciphertexts can be compressed somewhat when you are sending the same message to multiple recipients. See https://csrc.nist.gov/csrc/media/Events/2024/fifth-pqc-standardization-conference/documents/papers/how-multi-recipient-kems.pdf https://csrc.nist.gov/csrc/media/Events/2024/fifth-pqc-stand... for details: > "Asymptotically, the size of an mKyber multi-recipient ciphertext is 16 times smaller than the sum of the sizes of N Kyber ciphertexts.” There’s a whole zoo of useful variants on the “KEM” idea, but sadly NIST decided to standardise the least flexible variant. See my blog from a few years ago for some background on the literature: https://neilmadden.blog/2021/02/16/when-a-kem-is-not-enough/ https://neilmadden.blog/2021/02/16/when-a-kem-is-not-enough/
kaliszad 2y ago
Thank you for the update. This is really useful. It would be really great, if you could commit to an update a few years down the road at the latest. E.g. "I will release an update no later than August 15th 2027". 3 years in the fast-changing world shouldn't be such a burden and it would help to settle many discussions somewhat reasonably with appeal to authority :-D No seriously, having something that can be considered current advice would be great.
- chupasaurus 2y ago
  Besides PQC only password handling has some changes from 2018, which I assume was made because of TLSv1.3 and ECC, so you get the idea.
- bigiain 2y ago
  There are a string of these posts going back to 2009. Not "updated every 3 years", but it looks to me like we get an update when important advice has changed at least. I may have missed some, but from my bookmarks I have: 2009: https://www.daemonology.net/blog/2009-06-11-cryptographic-right-answers.html https://www.daemonology.net/blog/2009-06-11-cryptographic-ri... 2015: https://gist.github.com/tqbf/be58d2d39690c3b366ad https://gist.github.com/tqbf/be58d2d39690c3b366ad 2018: https://www.latacora.com/blog/2018/04/03/cryptographic-right-answers/ https://www.latacora.com/blog/2018/04/03/cryptographic-right... 2024: https://www.latacora.com/blog/2024/07/29/crypto-right-answers-pq/ https://www.latacora.com/blog/2024/07/29/crypto-right-answer... So not every 3 years, but if you read through you'll notice a _lot_ of each update pretty much says "use the same advice as last time." It's not clear who wrote the most recent Latacora post, but it's Thomas Ptacek's company, and the original 2009 post was by Colin Percival. If you've been around here for a while you'll probably recognise those names, they's #1 and #60 here: https://news.ycombinator.com/leaders https://news.ycombinator.com/leaders At least in my head, both have serious credibility over many years in this subject space. The 2018 Latacora post says: "This content has been developed and updated by different people over a decade. We’ve kept what Colin Percival originally said in 2009, Thomas Ptacek said in 2015, and what we’re saying in 2018 for comparison. If you’re designing something today, just use the 2018 Latacora recommendation."
BoppreH 2y ago
Excellent post, I've always recommended people to this series. I'm curious what's the general opinion on the production-readiness of these solutions. Open Quantum Safe, for example, discourages it's use in production, and recompiling nginx to use PQC-BoringSSL feels risky since I'm not intimately familiar with both projects ("did I miss a --enable-security flag?"). > the PQ keys are 4 orders of magnitude larger For McEliece, perhaps, but the algorithms in the tables are "only" 2 orders of magnitude larger.
- stratom 2y ago
  The field is too young that we can be absolutely sure. That's why most suggest to use hybrid cryptography for now.
  - BoppreH 2y ago
    True, and hybrid cryptography is definitely the way to go. But there's more to it than just resistance to cryptanalysis: crashes, memory leaks, disabled security features (e.g., ASLR), irregular performance, supply chain attacks... PQC requires extra code, and every added instruction carries some risk.
- er4hn 2y ago
  One interesting thing is that if you look at what companies that want to prepare for Store Now Decrypt Later are doing (see links at bottom) they're pretty much all using the non-production ready OQS. If you believe in hybrid encryption this is mostly okay since a failure in the PQC portion should not cause a breakage in the classical portion. Assuming that OQS has implemented the hybrid protocol correctly. - https://www.microsoft.com/en-us/research/project/post-quantum-tls/ https://www.microsoft.com/en-us/research/project/post-quantu... - https://engineering.fb.com/2024/05/22/security/post-quantum-readiness-tls-pqr-meta/ https://engineering.fb.com/2024/05/22/security/post-quantum-... - https://blog.cloudflare.com/kemtls-post-quantum-tls-without-signatures https://blog.cloudflare.com/kemtls-post-quantum-tls-without-...
Ahmed_rza 2y ago
Great post! I was worried for a long time about this thing as I'm also working in DeFi field. It's great that governments are taking the quantum computer threat seriously
- deleted 2y ago
  [deleted]
michaelt 2y ago
I've always found it a bit disquieting how many times people feel the need to update these "cryptographic right answers" blog posts. This is what, a fourth or fifth version since 2009? Meanwhile everything from ubuntu's apt-get to my connection to HN is secured with 2048-bit RSA - an algorithm invented in 1977 and in widespread use since at least 1995. Am I getting crypto advice that will keep my data safe for 30+ years, if the advice changes every 3 years?
- deleted 2y ago
  [deleted]
- defrost 2y ago
  an algorithm publicly published in 1977. The Ellis, Cocks and Williamson algorithm has existed since at least 1973.
- Rhapso 2y ago
  On one side, there is good in "This is the best prediction of the future we have right now and we update it as our knowledge changes". They also have a consulting product to sell you. When you build your entire society on "greed as a virtue", it is reasonable to assume it as a primary motivation for a profit seeking entity.
- kientuong114 2y ago
  The right answer is not always about straight-out security: 2048-bit RSA is not broken and won't be broken for the foreseeable future, but we know that it is much less efficient and more error-prone than e.g. ECDH. So why suggest the former when the latter is a better alternative? You should consider these "right answers" as if the question were, "I want to develop a new product today. What cryptographic primitive should I use?"
  - SAI_Peregrinus 2y ago
    Even that is more subtle. RSASSA-2048-PKCS#1v1.5 is fine if leaking that you signed the same plaintext more than once isn't a threat. If that is a threat then you need RSASSA-2048-PKCS#1v2, (AKA RSA-PSS-2048). RSAES-2048-PKCS#1v1.5 has implementation-dependent security; implementations keep getting broken due to padding oracle attacks. RSA-KEM-2048 is fine, though slower than ECDH.
Rhapso 2y ago
There are tables at the end describing the algorithms key sizes. be mindful of "(Size in bytes)" not bits. They cover that these algorithms use bigger keys, but it is 4 kilobytes.
librasteve 2y ago
Good list of early supporters near the bottom of the post text - Chrome, OpenSSH and iMessage are relevant for me.
- dadrian 2y ago
  Hybrid kyber is actually enabled by default in Chrome on desktop, you don't need to go to chrome://flags to enable it.
throw0101d 2y ago
NIST announcement: * https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards https://www.nist.gov/news-events/news/2024/08/nist-releases-... See * FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard (ML-KEM / CRYSTALS-KYBER) * FIPS 204, Module-Lattice-Based Digital Signature Standard (ML-DSA / CRYSTALS-Dilithium) * FIPS 205, Stateless Hash-Based Digital Signature Standard (SLH-DSA / SPHINCS+) From: * https://csrc.nist.gov/News/2024/postquantum-cryptography-fips-approved https://csrc.nist.gov/News/2024/postquantum-cryptography-fip... * https://www.federalregister.gov/documents/2024/08/14/2024-17956/announcing-issuance-of-federal-information-processing-standards-fips-fips-203-module-lattice-based https://www.federalregister.gov/documents/2024/08/14/2024-17...
- deleted 2y ago
  [deleted]
ccppurcell 2y ago
As I understand it, the only reason pqc is of "practical" concern is the issue of "store now, decrypt later". Is it possible to defend against this attack in a classical way? Some sort of time limit on decryption? Or an argument that it's impossible?
- candiddevmike 2y ago
  Sneakernet or OTP
- red_admiral 2y ago
  The NSA has a copy of your ciphertexts on their disks today. What could stop them from trying to decrypt it in 5 years' time? It's not like they will be held back by any Terms & Conditions. The only way you can do any "not after X time" decryption even for honest-ish users is if the decryption involves getting extra key material from some server that erases it or shuts down at some point. But even that doesn't help if someone can break the crypto.
  - dogsledsleddog 2y ago
    I don't think that is true, current PFS algorithms are probably all just an inconvenience PQ, but I think they suggest strategies where one has to have a key at the time of a negotiation or even be part of a decision in a negotiation to ever have the session key as long as the parties discard it.
- thadt 2y ago
  Strong pre-shared keys will continue to remain secure, even against a quantum computer. Wireguard, for example, provides the ability to add a pre-shared key for endpoints, which it mixes in during key exchange. Wireguard sessions collected under such a configuration should remain safe when attacked by a future quantum computer, assuming that the shared keys remain secret. Pre-shared keys are just inconvenient to handle safely.
  - Panino 2y ago
upofadown 2y ago
>Avoid: HMAC-MD5, HMAC-SHA1 and such. The underlying hash function has to be safe. Interestingly enough, there is a proof out there that more or less states the opposite for HMAC-MD5 and HMAC-SHA1: * https://eprint.iacr.org/2006/043.pdf https://eprint.iacr.org/2006/043.pdf The issue here is that MD5 and SHA1 are broken for collisions. But no one could figure out an actual attack for HMACs based on them. The linked paper is an attempt to explain that.
- woodruffw 2y ago
  I think the phrasing in this post could be better, but the basic observation is sound: if the last use of a weak hash function in your codebase is in HMACs, then it’s better to upgrade to a stronger underlying hash function and apply a blanket ban to the weak ones. Similarly, in a greenfield codebase, there’s no reason to pick an HMAC construction based on a weaker hash when collision-resistant ones are universally available.
- deleted 2y ago
  [deleted]
- deleted 2y ago
  [deleted]
rgovostes 2y ago
“Classical cryptography” used to refer to historical ciphers, Vigenère and the like, tapering off after the World War 2-era cipher machines and definitely not used to describe asymmetric algorithms. There should be a different term for pre- (non-?) quantum cryptography from the modern era. We already suffered the redefinition of “crypto”.
- dlubarov 2y ago
  It's a reasonable point but this would probably be a losing battle; at this point terms like "classical security", "classical adversaries", etc. are common in the literature. To me what's worse is "zk" used to describe applications of verifiable computation with no secrets involved, but that seems like a losing battle also.
1oooqooq 2y ago
Hostly, most cryptographic vulnerability today are because things are stuck in the NIST and FIPS regulation. Most vulnerable building blocks are still shipped to have their certification to begin with. Why there's still excitement to their work?
- deleted 2y ago
  [deleted]

109 points by lvh 2y ago

CodeVenturer 2y ago

[dead]

hannob 2y ago
What you got now as new standards is already the result of multiple iterations of improvements in key size reductions and performance improvements. But you'll likely not get drop-in replacements for existing public key crypto in post-quantum variations. It appears signatures are even more challenging regarding size than encryption in the post-quantum world. It may be worth noting that choosing the algorithms that are now chosen, which are primarily lattice-based, is already kinda a compromise. They're not the ones with the highest trust in security, which would've been McEliece and SPHINCS (though the latter has been standardized as a fallback). But those come with key and signature sizes that are entirely impractical for the most common use cases. It appears most of the crypto community came around thinking that the somewhat-smaller lattice algos are now "almost certainly secure". But surely there's at least one famous cryptographer raising his voice that he still has concerns.
candiddevmike 2y ago
AIUI part of the problem with size is due to hybrid setups. Size could probably be reduced if you only used a PQC algorithm instead of combining it with existing crypto.
nmadden 2y ago
Yes, Kyber (ML-KEM) ciphertexts can be compressed somewhat when you are sending the same message to multiple recipients. See https://csrc.nist.gov/csrc/media/Events/2024/fifth-pqc-standardization-conference/documents/papers/how-multi-recipient-kems.pdf https://csrc.nist.gov/csrc/media/Events/2024/fifth-pqc-stand... for details: > "Asymptotically, the size of an mKyber multi-recipient ciphertext is 16 times smaller than the sum of the sizes of N Kyber ciphertexts.” There’s a whole zoo of useful variants on the “KEM” idea, but sadly NIST decided to standardise the least flexible variant. See my blog from a few years ago for some background on the literature: https://neilmadden.blog/2021/02/16/when-a-kem-is-not-enough/ https://neilmadden.blog/2021/02/16/when-a-kem-is-not-enough/

kaliszad 2y ago

Thank you for the update. This is really useful. It would be really great, if you could commit to an update a few years down the road at the latest. E.g. "I will release an update no later than August 15th 2027". 3 years in the fast-changing world shouldn't be such a burden and it would help to settle many discussions somewhat reasonably with appeal to authority :-D No seriously, having something that can be considered current advice would be great.

chupasaurus 2y ago
Besides PQC only password handling has some changes from 2018, which I assume was made because of TLSv1.3 and ECC, so you get the idea.
bigiain 2y ago
There are a string of these posts going back to 2009. Not "updated every 3 years", but it looks to me like we get an update when important advice has changed at least. I may have missed some, but from my bookmarks I have: 2009: https://www.daemonology.net/blog/2009-06-11-cryptographic-right-answers.html https://www.daemonology.net/blog/2009-06-11-cryptographic-ri... 2015: https://gist.github.com/tqbf/be58d2d39690c3b366ad https://gist.github.com/tqbf/be58d2d39690c3b366ad 2018: https://www.latacora.com/blog/2018/04/03/cryptographic-right-answers/ https://www.latacora.com/blog/2018/04/03/cryptographic-right... 2024: https://www.latacora.com/blog/2024/07/29/crypto-right-answers-pq/ https://www.latacora.com/blog/2024/07/29/crypto-right-answer... So not every 3 years, but if you read through you'll notice a _lot_ of each update pretty much says "use the same advice as last time." It's not clear who wrote the most recent Latacora post, but it's Thomas Ptacek's company, and the original 2009 post was by Colin Percival. If you've been around here for a while you'll probably recognise those names, they's #1 and #60 here: https://news.ycombinator.com/leaders https://news.ycombinator.com/leaders At least in my head, both have serious credibility over many years in this subject space. The 2018 Latacora post says: "This content has been developed and updated by different people over a decade. We’ve kept what Colin Percival originally said in 2009, Thomas Ptacek said in 2015, and what we’re saying in 2018 for comparison. If you’re designing something today, just use the 2018 Latacora recommendation."

BoppreH 2y ago

Excellent post, I've always recommended people to this series. I'm curious what's the general opinion on the production-readiness of these solutions. Open Quantum Safe, for example, discourages it's use in production, and recompiling nginx to use PQC-BoringSSL feels risky since I'm not intimately familiar with both projects ("did I miss a --enable-security flag?"). > the PQ keys are 4 orders of magnitude larger For McEliece, perhaps, but the algorithms in the tables are "only" 2 orders of magnitude larger.

stratom 2y ago
The field is too young that we can be absolutely sure. That's why most suggest to use hybrid cryptography for now.
- BoppreH 2y ago
  True, and hybrid cryptography is definitely the way to go. But there's more to it than just resistance to cryptanalysis: crashes, memory leaks, disabled security features (e.g., ASLR), irregular performance, supply chain attacks... PQC requires extra code, and every added instruction carries some risk.
er4hn 2y ago
One interesting thing is that if you look at what companies that want to prepare for Store Now Decrypt Later are doing (see links at bottom) they're pretty much all using the non-production ready OQS. If you believe in hybrid encryption this is mostly okay since a failure in the PQC portion should not cause a breakage in the classical portion. Assuming that OQS has implemented the hybrid protocol correctly. - https://www.microsoft.com/en-us/research/project/post-quantum-tls/ https://www.microsoft.com/en-us/research/project/post-quantu... - https://engineering.fb.com/2024/05/22/security/post-quantum-readiness-tls-pqr-meta/ https://engineering.fb.com/2024/05/22/security/post-quantum-... - https://blog.cloudflare.com/kemtls-post-quantum-tls-without-signatures https://blog.cloudflare.com/kemtls-post-quantum-tls-without-...

Ahmed_rza 2y ago

Great post! I was worried for a long time about this thing as I'm also working in DeFi field. It's great that governments are taking the quantum computer threat seriously

deleted 2y ago
[deleted]

michaelt 2y ago

I've always found it a bit disquieting how many times people feel the need to update these "cryptographic right answers" blog posts. This is what, a fourth or fifth version since 2009? Meanwhile everything from ubuntu's apt-get to my connection to HN is secured with 2048-bit RSA - an algorithm invented in 1977 and in widespread use since at least 1995. Am I getting crypto advice that will keep my data safe for 30+ years, if the advice changes every 3 years?

deleted 2y ago
[deleted]
defrost 2y ago
an algorithm publicly published in 1977. The Ellis, Cocks and Williamson algorithm has existed since at least 1973.
Rhapso 2y ago
On one side, there is good in "This is the best prediction of the future we have right now and we update it as our knowledge changes". They also have a consulting product to sell you. When you build your entire society on "greed as a virtue", it is reasonable to assume it as a primary motivation for a profit seeking entity.
kientuong114 2y ago
The right answer is not always about straight-out security: 2048-bit RSA is not broken and won't be broken for the foreseeable future, but we know that it is much less efficient and more error-prone than e.g. ECDH. So why suggest the former when the latter is a better alternative? You should consider these "right answers" as if the question were, "I want to develop a new product today. What cryptographic primitive should I use?"
- SAI_Peregrinus 2y ago
  Even that is more subtle. RSASSA-2048-PKCS#1v1.5 is fine if leaking that you signed the same plaintext more than once isn't a threat. If that is a threat then you need RSASSA-2048-PKCS#1v2, (AKA RSA-PSS-2048). RSAES-2048-PKCS#1v1.5 has implementation-dependent security; implementations keep getting broken due to padding oracle attacks. RSA-KEM-2048 is fine, though slower than ECDH.

Rhapso 2y ago

There are tables at the end describing the algorithms key sizes. be mindful of "(Size in bytes)" not bits. They cover that these algorithms use bigger keys, but it is 4 kilobytes.

librasteve 2y ago

Good list of early supporters near the bottom of the post text - Chrome, OpenSSH and iMessage are relevant for me.

dadrian 2y ago
Hybrid kyber is actually enabled by default in Chrome on desktop, you don't need to go to chrome://flags to enable it.

throw0101d 2y ago

NIST announcement: * https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards https://www.nist.gov/news-events/news/2024/08/nist-releases-... See * FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard (ML-KEM / CRYSTALS-KYBER) * FIPS 204, Module-Lattice-Based Digital Signature Standard (ML-DSA / CRYSTALS-Dilithium) * FIPS 205, Stateless Hash-Based Digital Signature Standard (SLH-DSA / SPHINCS+) From: * https://csrc.nist.gov/News/2024/postquantum-cryptography-fips-approved https://csrc.nist.gov/News/2024/postquantum-cryptography-fip... * https://www.federalregister.gov/documents/2024/08/14/2024-17956/announcing-issuance-of-federal-information-processing-standards-fips-fips-203-module-lattice-based https://www.federalregister.gov/documents/2024/08/14/2024-17...

deleted 2y ago
[deleted]

ccppurcell 2y ago

As I understand it, the only reason pqc is of "practical" concern is the issue of "store now, decrypt later". Is it possible to defend against this attack in a classical way? Some sort of time limit on decryption? Or an argument that it's impossible?

candiddevmike 2y ago
Sneakernet or OTP
red_admiral 2y ago
The NSA has a copy of your ciphertexts on their disks today. What could stop them from trying to decrypt it in 5 years' time? It's not like they will be held back by any Terms & Conditions. The only way you can do any "not after X time" decryption even for honest-ish users is if the decryption involves getting extra key material from some server that erases it or shuts down at some point. But even that doesn't help if someone can break the crypto.
- dogsledsleddog 2y ago
  I don't think that is true, current PFS algorithms are probably all just an inconvenience PQ, but I think they suggest strategies where one has to have a key at the time of a negotiation or even be part of a decision in a negotiation to ever have the session key as long as the parties discard it.
thadt 2y ago
Strong pre-shared keys will continue to remain secure, even against a quantum computer. Wireguard, for example, provides the ability to add a pre-shared key for endpoints, which it mixes in during key exchange. Wireguard sessions collected under such a configuration should remain safe when attacked by a future quantum computer, assuming that the shared keys remain secret. Pre-shared keys are just inconvenient to handle safely.
- Panino 2y ago

upofadown 2y ago

>Avoid: HMAC-MD5, HMAC-SHA1 and such. The underlying hash function has to be safe. Interestingly enough, there is a proof out there that more or less states the opposite for HMAC-MD5 and HMAC-SHA1: * https://eprint.iacr.org/2006/043.pdf https://eprint.iacr.org/2006/043.pdf The issue here is that MD5 and SHA1 are broken for collisions. But no one could figure out an actual attack for HMACs based on them. The linked paper is an attempt to explain that.

woodruffw 2y ago
I think the phrasing in this post could be better, but the basic observation is sound: if the last use of a weak hash function in your codebase is in HMACs, then it’s better to upgrade to a stronger underlying hash function and apply a blanket ban to the weak ones. Similarly, in a greenfield codebase, there’s no reason to pick an HMAC construction based on a weaker hash when collision-resistant ones are universally available.
deleted 2y ago
[deleted]
deleted 2y ago
[deleted]

rgovostes 2y ago

“Classical cryptography” used to refer to historical ciphers, Vigenère and the like, tapering off after the World War 2-era cipher machines and definitely not used to describe asymmetric algorithms. There should be a different term for pre- (non-?) quantum cryptography from the modern era. We already suffered the redefinition of “crypto”.

dlubarov 2y ago
It's a reasonable point but this would probably be a losing battle; at this point terms like "classical security", "classical adversaries", etc. are common in the literature. To me what's worse is "zk" used to describe applications of verifiable computation with no secrets involved, but that seems like a losing battle also.

1oooqooq 2y ago

Hostly, most cryptographic vulnerability today are because things are stuck in the NIST and FIPS regulation. Most vulnerable building blocks are still shipped to have their certification to begin with. Why there's still excitement to their work?

deleted 2y ago
[deleted]