4 ms·

> Just a few years ago, two of the four finalists of the NIST PQC were broken so badly that you could break production key sizes in hours with a 10 year old Mac

> Just a few years ago, two of the four finalists of the NIST PQC were broken so badly that you could break production key sizes in hours with a 10 year old Mac mini. SIKE was not a Finalist, it was a Round 4 candidate. Candidates being broken before the process finishes is a sign of the process working.

thesz 2y ago
https://cacm.acm.org/news/nist-post-quantum-cryptography-candidate-cracked/ https://cacm.acm.org/news/nist-post-quantum-cryptography-can... "Belgian researchers have cracked the SIKE cryptographic algorithm, a fourth and final-round candidate that the U.S. National Institute of Standards and Technology (NIST) was evaluating for its Post-Quantum Cryptography (PQC) standard." SIKE was a finalist, it entered final round.
- pclmulqdq 2y ago
  SIKE was probably the most exciting PQC algorithm available, if it hadn't been broken. It made it to the finals for a relatively brief time. CRYSTALS also now has a possible attack proposed by a recent paper on a similar algorithm, so time will tell if any more of these algorithms is broken.
  - tptacek 2y ago
    But SIKE was also broken in, like, a theatrical fashion. It was an explosive break! It feels like there's some dancing around happening here, where the subtext is that where an algorithm is in a NIST contest process isn't determinative on it's own, and that there are external reasons we tend to trust the lattice stuff (because it's been studied for decades, &c).
    - adastra22 2y ago
      Even with lattice stuff, the parameters keep having to be changed to ensure security. It may not be explosive breaks, but the cryptanalysis is advancing at stunning speeds. This stuff is no where near prime time ready.
      - tptacek 2y ago
        I think we are agreeing, directionally. I don't have a strong opinion in either direction and wouldn't be qualified to express one. I'm a vulnerability researcher with a little bit of cryptography to me, so I tend always to err on the side of utterly skeeved out. I assume, regardless of what national standards bodies recommend, this stuff will all be run hybrid for the foreseeable future, but who knows? I don't think anybody can easily shut down the argument that it's too early for lattice PQC to simply replace ECDLP cryptography.
        adastra22 2y ago
        There is not any reason to NOT run hybrid cryptography schemes right now, when the use case allows for it. I do worry though that early standardization might lock us into a bad standard, and current PQC systems are too inflexible to allow for many use cases. The latter point means that if you want PQC, you might have to give up some features. E.g. multikey signature schemes, zero knowledge proofs, etc.
        CiPHPerCoder 2y ago
        > There is not any reason to NOT run hybrid cryptography schemes right now, when the use case allows for it. This is reasonable, but runs contrary to the stance taken by CNSA 2.0.
        adastra22 2y ago
        Gee, I wonder why.
        pclmulqdq 2y ago
        There is a very good reason: efficiency. Do you want to have servers carry an extra megabyte of otherwise-useless key material for each incoming connection? What about the extra ~100-1000 microseconds of CPU time for each key exchange? Now multiply that by 100,000 live connections and 10,000 per second, and you'll see that there's a big problem here. A lot of cryptography arguments forget that people don't place unlimited value on cryptography (or even security in a general sense). These algorithms are costly, and if they do nothing, should not be used.
    - pclmulqdq 2y ago
      Yeah the break of SIKE was pretty spectacular. The attacks on lattice-based crypto are less so. Still, the math is a lot more complicated than ECC or RSA, so it's plausible that it's also fundamentally broken, but we just haven't found out how. At this point the only PQC algorithm I would trust with my data on its own is good old McEliece.
      - tptacek 2y ago
        I'm not as convinced that the math on RSA is so simple compared to LWE cryptography. You'll see reputable cryptographers (well, one of them at least) confidently opining how we'll never break SHA2 and AES. I've never seen that for RSA or any ECDLP construction. SIKE, sure, all bets are off.
        adastra22 2y ago
        The math for RSA is dead simple. But the theoretical foundations are not well established, no. It should be said though that SHA2 and AES also have unproven foundations for their security model. In a very strict sense both RSA and AES are equally vulnerable. But I think people would be more surprised if AES was catastrophically broken, and most surprised if SHA2 were, though there is little more than mathematical intuition underlying this.

thesz 2y ago

https://cacm.acm.org/news/nist-post-quantum-cryptography-candidate-cracked/ https://cacm.acm.org/news/nist-post-quantum-cryptography-can... "Belgian researchers have cracked the SIKE cryptographic algorithm, a fourth and final-round candidate that the U.S. National Institute of Standards and Technology (NIST) was evaluating for its Post-Quantum Cryptography (PQC) standard." SIKE was a finalist, it entered final round.

pclmulqdq 2y ago
SIKE was probably the most exciting PQC algorithm available, if it hadn't been broken. It made it to the finals for a relatively brief time. CRYSTALS also now has a possible attack proposed by a recent paper on a similar algorithm, so time will tell if any more of these algorithms is broken.
- tptacek 2y ago
  But SIKE was also broken in, like, a theatrical fashion. It was an explosive break! It feels like there's some dancing around happening here, where the subtext is that where an algorithm is in a NIST contest process isn't determinative on it's own, and that there are external reasons we tend to trust the lattice stuff (because it's been studied for decades, &c).
  - adastra22 2y ago
    Even with lattice stuff, the parameters keep having to be changed to ensure security. It may not be explosive breaks, but the cryptanalysis is advancing at stunning speeds. This stuff is no where near prime time ready.
    - tptacek 2y ago
      I think we are agreeing, directionally. I don't have a strong opinion in either direction and wouldn't be qualified to express one. I'm a vulnerability researcher with a little bit of cryptography to me, so I tend always to err on the side of utterly skeeved out. I assume, regardless of what national standards bodies recommend, this stuff will all be run hybrid for the foreseeable future, but who knows? I don't think anybody can easily shut down the argument that it's too early for lattice PQC to simply replace ECDLP cryptography.
      - adastra22 2y ago
        There is not any reason to NOT run hybrid cryptography schemes right now, when the use case allows for it. I do worry though that early standardization might lock us into a bad standard, and current PQC systems are too inflexible to allow for many use cases. The latter point means that if you want PQC, you might have to give up some features. E.g. multikey signature schemes, zero knowledge proofs, etc.
        CiPHPerCoder 2y ago
        > There is not any reason to NOT run hybrid cryptography schemes right now, when the use case allows for it. This is reasonable, but runs contrary to the stance taken by CNSA 2.0.
        adastra22 2y ago
        Gee, I wonder why.
        pclmulqdq 2y ago
        There is a very good reason: efficiency. Do you want to have servers carry an extra megabyte of otherwise-useless key material for each incoming connection? What about the extra ~100-1000 microseconds of CPU time for each key exchange? Now multiply that by 100,000 live connections and 10,000 per second, and you'll see that there's a big problem here. A lot of cryptography arguments forget that people don't place unlimited value on cryptography (or even security in a general sense). These algorithms are costly, and if they do nothing, should not be used.
  - pclmulqdq 2y ago
    Yeah the break of SIKE was pretty spectacular. The attacks on lattice-based crypto are less so. Still, the math is a lot more complicated than ECC or RSA, so it's plausible that it's also fundamentally broken, but we just haven't found out how. At this point the only PQC algorithm I would trust with my data on its own is good old McEliece.
    - tptacek 2y ago
      I'm not as convinced that the math on RSA is so simple compared to LWE cryptography. You'll see reputable cryptographers (well, one of them at least) confidently opining how we'll never break SHA2 and AES. I've never seen that for RSA or any ECDLP construction. SIKE, sure, all bets are off.
      - adastra22 2y ago
        The math for RSA is dead simple. But the theoretical foundations are not well established, no. It should be said though that SHA2 and AES also have unproven foundations for their security model. In a very strict sense both RSA and AES are equally vulnerable. But I think people would be more surprised if AES was catastrophically broken, and most surprised if SHA2 were, though there is little more than mathematical intuition underlying this.