4 ms·

Reducing "gate" counts for Kyber-512 contradicting NIST's calculation

30 points by nabla9 3y ago

cedws 3y ago
There was a post recently about suspicion of NIST, specifically from Daniel Bernstein. We also have reason to believe there was funny business around Dual_EC_DRBG. If NIST really is up to no good on behalf of US intelligence agencies, it's reasonable to believe they'd be doing everything they can to prevent strong post-quantum crypto. Also, here's an idea I had: let's say you wrapped a plaintext in three different encryption algorithms authored in adversarial countries. Even if you assume all three are backdoored by their creators, you'd have something that could only be unwrapped if the three adversarial countries worked together. Is there anything out there that does this?
- imjonse 3y ago
  That would be very inefficient though even if more reassuring.
- twiss 3y ago
  This post is also by Daniel J. Bernstein, so DJB seems to be the only person with suspicions of NIST. Dual_EC_DRBG was created by the NSA, not NIST (who merely standardized it). NIST also merely standardises Kyber, they didn't create it. So there's no real reason to suspect "funny business" unless you believe the NSA is influencing the Kyber team.
- NavinF 3y ago
  Cascade encryption is pretty common. I remember using 3 ciphers with TrueCrypt in the 2000s. There are some theoretical issues that prevent you from using cipher1(cipher2(x)) though. See https://en.wikipedia.org/wiki/Multiple_encryption#Importance_of_the_first_layer https://en.wikipedia.org/wiki/Multiple_encryption#Importance... In practice post-quantum encryption is always combined with normal encryption so this sorta thing should become even more common in the future.
- nabla9 3y ago
  GSMK CryptoPhone protocol uses TwoFish-256 and AES-256 in parallel counter mode XOR'ed together.
FiloSottile 3y ago
For anyone that would like to catch up with this unfortunate saga, I recommend reading the following, that (partially due to being presented less inflammatorily and through the appropriate channels) are getting much less coverage. Ray Perlner (NIST PQC), Re: Kyber security level? https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/W2VOzy0wz_E/m/UGeTmPCqBAAJ https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/W2VO... Christopher J Peikert, Re: Kyber security level? https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/W2VOzy0wz_E/m/LjmQyMurBQAJ https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/W2VO... Matthew Green on Mastodon https://ioc.exchange/@matthew_d_green/111227593416987176 https://ioc.exchange/@matthew_d_green/111227593416987176 tptacek on HN https://news.ycombinator.com/item?id=37874682 https://news.ycombinator.com/item?id=37874682 Personally, I am woefully unqualified to judge the intricacies of attack cost estimation myself, but I have followed enough of the process to find some of the conspiracy claims risible. For example, that NIST made a graph a little smaller on a slide to "deemphasize" it (search for "thinner red bars" in https://blog.cr.yp.to/20231003-countcorrectly.html https://blog.cr.yp.to/20231003-countcorrectly.html). Moreover, I fail to understand why NIST would pick a weak algorithm (designed by independent researchers) to secure the data of US federal agencies and industry. This is critically different from Dual_EC_DRBG in that there is nowhere to hide a NOBUS (https://en.wikipedia.org/wiki/NOBUS https://en.wikipedia.org/wiki/NOBUS) backdoor, so it would be a ridiculous bet that no one else in the world will find the weakness in the next fifty years. The one bit of color I will add is that every community of cryptographers I am in has had enough of this, as far as I can tell, and is not taking Bernstein seriously anymore. The most common reactions are eyerolls and popcorns. As I said before (https://news.ycombinator.com/item?id=37868974 https://news.ycombinator.com/item?id=37868974), I am worried that Bernstein has increasingly argued in bad faith and alienated his peers (through spurious accusations, personal attacks, endless never-retracted arguments, and legal threats) to the point that they're unwilling to engage with him, which from the outside can look like his points are unrefutable. Like Matthew Green, I am worried about what that will do to confidence in modern cryptography, given Bernstein's following.
viraptor 3y ago
What's a reasonable time ratio these days (as in Intel gen 13 and quality ddr5) to assume between an addition of registers and access to L3 and to RAM? Also, they analyse gate times rather than ALU in estimations to account for someone producing a dedicated chip for cracking the cipher, right?

30 points by nabla9 3y ago

There was a post recently about suspicion of NIST, specifically from Daniel Bernstein. We also have reason to believe there was funny business around Dual_EC_DRBG. If NIST really is up to no good on behalf of US intelligence agencies, it's reasonable to believe they'd be doing everything they can to prevent strong post-quantum crypto. Also, here's an idea I had: let's say you wrapped a plaintext in three different encryption algorithms authored in adversarial countries. Even if you assume all three are backdoored by their creators, you'd have something that could only be unwrapped if the three adversarial countries worked together. Is there anything out there that does this?

imjonse 3y ago
That would be very inefficient though even if more reassuring.
twiss 3y ago
This post is also by Daniel J. Bernstein, so DJB seems to be the only person with suspicions of NIST. Dual_EC_DRBG was created by the NSA, not NIST (who merely standardized it). NIST also merely standardises Kyber, they didn't create it. So there's no real reason to suspect "funny business" unless you believe the NSA is influencing the Kyber team.
NavinF 3y ago
Cascade encryption is pretty common. I remember using 3 ciphers with TrueCrypt in the 2000s. There are some theoretical issues that prevent you from using cipher1(cipher2(x)) though. See https://en.wikipedia.org/wiki/Multiple_encryption#Importance_of_the_first_layer https://en.wikipedia.org/wiki/Multiple_encryption#Importance... In practice post-quantum encryption is always combined with normal encryption so this sorta thing should become even more common in the future.
nabla9 3y ago
GSMK CryptoPhone protocol uses TwoFish-256 and AES-256 in parallel counter mode XOR'ed together.

FiloSottile 3y ago

For anyone that would like to catch up with this unfortunate saga, I recommend reading the following, that (partially due to being presented less inflammatorily and through the appropriate channels) are getting much less coverage. Ray Perlner (NIST PQC), Re: Kyber security level? https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/W2VOzy0wz_E/m/UGeTmPCqBAAJ https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/W2VO... Christopher J Peikert, Re: Kyber security level? https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/W2VOzy0wz_E/m/LjmQyMurBQAJ https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/W2VO... Matthew Green on Mastodon https://ioc.exchange/@matthew_d_green/111227593416987176 https://ioc.exchange/@matthew_d_green/111227593416987176 tptacek on HN https://news.ycombinator.com/item?id=37874682 https://news.ycombinator.com/item?id=37874682 Personally, I am woefully unqualified to judge the intricacies of attack cost estimation myself, but I have followed enough of the process to find some of the conspiracy claims risible. For example, that NIST made a graph a little smaller on a slide to "deemphasize" it (search for "thinner red bars" in https://blog.cr.yp.to/20231003-countcorrectly.html https://blog.cr.yp.to/20231003-countcorrectly.html). Moreover, I fail to understand why NIST would pick a weak algorithm (designed by independent researchers) to secure the data of US federal agencies and industry. This is critically different from Dual_EC_DRBG in that there is nowhere to hide a NOBUS (https://en.wikipedia.org/wiki/NOBUS https://en.wikipedia.org/wiki/NOBUS) backdoor, so it would be a ridiculous bet that no one else in the world will find the weakness in the next fifty years. The one bit of color I will add is that every community of cryptographers I am in has had enough of this, as far as I can tell, and is not taking Bernstein seriously anymore. The most common reactions are eyerolls and popcorns. As I said before (https://news.ycombinator.com/item?id=37868974 https://news.ycombinator.com/item?id=37868974), I am worried that Bernstein has increasingly argued in bad faith and alienated his peers (through spurious accusations, personal attacks, endless never-retracted arguments, and legal threats) to the point that they're unwilling to engage with him, which from the outside can look like his points are unrefutable. Like Matthew Green, I am worried about what that will do to confidence in modern cryptography, given Bernstein's following.

viraptor 3y ago

What's a reasonable time ratio these days (as in Intel gen 13 and quality ddr5) to assume between an addition of registers and access to L3 and to RAM? Also, they analyse gate times rather than ALU in estimations to account for someone producing a dedicated chip for cracking the cipher, right?