[myrion]

Here's my honest shot at it:

In between a bunch of conspiratorial hinting, djb argues that KYBER-512 is weaker than NIST claims.

To make that argument, he points out a fairly egregious math mistake (the whole "2^40+2^40" bit) and then shows that NIST was inconsistent in applying the rules of the contest it refereed.

He also offers an explanation for why NIST would be so inconsistent about it, namely that they were influenced to pick KYBER, even if it wasn't the best candidate.

--

My personal takeaway was that he was both being a sore loser but also that KYBER-512 is weaker than it should be, weaker than it is claimed to be and that for some reason NIST still wanted it to win.

Makes me skeptical about KYBER-512 (but not larger sizes) and reinforces my worry that NIST can be influenced to pick less-than-optimal algorithms.

But then, I'm not a cryptographer and in the lucky situation where for any application I encounter, I can just go for KYBER-768 or 1024 or NTRU and just be fine - I don't have to understand this situation perfectly.

Hope you get some value from this outside perspective.

[nmadden]

I’ve not followed the PQC competition very closely, but I don’t think djb’s arguments significantly impact whether you should use KYBER-512. From my reading, as someone with a decent amount of crypto knowledge, all the evidence suggests that it is more than secure enough. The rest of the stuff is at the level of “submit an erratum”, not “omg cancel the whole thing”.

If anything, this reinforces my belief that KYBER is a good design. If this is the best he can come up with to try and discredit it, then it must be pretty solid.

[myrion]

The last part I agree with - clearly KYBER isn't trivially broken if this is the best he can come up with.

What doesn't seem clear to me, and I'd appreciate if you could tell me why you think differently, is that KYBER-512 isn't as strong as it was targeted to be. I find djb's argument on this narrow point fairly convincing: KYBER-512 isn't as secure as AES-128 (by the methods used to measure "secure" in this competition).

Given that I already generally use AES-256, why shouldn't I treat this the same way as AES-128?

That is, "it's probably fine-ish, but if you have the power, just go one bigger".

[nmadden]

It’s possible that in the specific sense that NIST defined, KYBER-512 isn’t as strong as AES-128. However, that doesn’t mean that it’s less secure in general. E.g. DJB himself wrote a good article[1] on how even though 128-bit AES and 256-bit elliptic curve crypto are thought of as same “security level”, actually there are attacks against AES that just don’t apply to ECC when you consider multi-target security models (i.e., when you consider a population of users not just one). I wouldn’t be surprised if similar things applied to lattice-based crypto, but I don’t know enough about it. And even if we take the reduced security level given by DJB, it still seems big enough to be out of reach to any realistic attack.

But by all means feel free to go one bigger and pick KYBER-768, and I believe lots of people do recommend this. Obviously, there is a performance penalty (as there is when moving from AES 128 to 256), and for PQ schemes there is also more importantly also a big increase in the size of bytes on the wire when public keys have to be exchanged (e.g. in TLS) - in this case a jump from 800 bytes to 1,184 bytes (a 48% increase). (Compare this to ECC public keys which are typically around 32-65 bytes, depending on encoding).

[1]: https://blog.cr.yp.to/20151120-batchattacks.html

[myrion]

First off, thanks for the reply. It has since been pointed out to me elsewhere that there are now responses showing his central claim of a maths error to be false, which means all of this is now moot - KYBER is as secure as claimed.

It has also been pointed out to me that djb has been quietly ignoring another metric in which KYBER beats NTRU: implementation complexity.

Even accepting all other arguments about the tradeoffs between NTRU and KYBER (and I do take your point about size of keys being more important than CPU cycles), even then, KYBER is judged to have lower implementation complexity.

Having read about all the crypto libraries who produced broken output because they made a mistake in the implementation, that's something I immediately understand as a big benefit.

Again, thanks for the conversation and helping me understand!

[tptacek]

There's a valid point to be made about selecting key exchange parameters to match bulk encryption parameters, but before you gear up to make a stink about it, bear in mind that it's generally the case in modern cryptosystems (that aren't specifically designed to do that matching) that key exchange security levels are lower than those of block ciphers. The step functions for key exchange security levels are pretty abrupt, and you pay a pretty high price to select the next one up, so aiming for "roughly the vicinity" of 128 bits is pretty normal.