Debunking NIST's calculation of the Kyber-512 security level (2023)

Debunking NIST's calculation of the Kyber-512 security level (2023)(blog.cr.yp.to)

59 points by RA2lover 1 year ago | 21 comments

ggm 1 year ago |

You would expect a decent rebuttal if wrong, and an acknowledgement if correct.

I'm not aware of either. I'd love to know if NIST has formally accepted their arithmetic flaw. It's possible they did, and believe they are north of need supporting Kyber-512 irrespective.

zzo38computer 1 year ago |

I can see they say many problems with what NIST is doing. One question is: Does someone bribe (or otherwise coerce) them? If so, is that why they are being deceptive, and why they would not respond to (or explain) some things?

If a system has parameters, another issue is whether or not a different implementation is required due to the parameters being different. There are some reasons why a separate implementation might be desirable anyways in some cases, but sometimes it would be possible to change the parameters at run time.

Another consideration is patents; they should not recommend patented or secret algorithms. Cryptanalysis will be difficult if the specification is not freely available to anyone who wants to read it, and implementation can be a problem if patent licensing is required. Wikipedia says that NTRU is patented but "Security Innovation exempted open-source projects from having to get a patent license"; that might be good enough.

Wikipedia also says that Kyber is a key encapsulation mechanism but NTRU is a public key cryptosystem, so they would not be the same kind of things, anyways. However, you could also use a public key cryptosystem like a key encapsulation mechanism if you have another method of making up a key securely at random. But, Wikipedia says "it is easier to design and analyze a secure KEM than to design a secure public-key encryption scheme as a basis" (I do not know the details of the quoted part to judge this, but the unquoted part seems obvious to me).

Another alternative might be using multiple algorithms with independent keys (to be secure, the keys will have to be independent; however, you might have to be careful that they really will be independent), e.g. by using Kyber first and then encrypting the result with NTRU. But, that depends on what your requirements are.

As another comments (https://news.ycombinator.com/item?id=37756656) had mention, they may have different requirements than yours, such as hardware, so that is another issue.

None of that is an excuse for what NIST seems to be doing though (according to the article); they are additional concerns than those ones.

rurban 1 year ago | |

NIST is basically NSA and CIA. I wouldn't trust them a single bit.

wahern 1 year ago |

This stood out to me:

> For comparison, Bitcoin mining did only about 2^111 bit operations in 2022. ("Only"!)

Anyone have a source for this? Google results suggest in 2022 Bitcoin miners reached ~209 quintillion hashes (209 exahashes) per second. I don't know how many bit operations SHA-1 takes, but dividing 2^111 by 209 * 10^18 * 86400 * 365 gives 393891, which doesn't sound unreasonable for number of bit operations per SHA-1 hash.

Basically, it's fascinating that global compute is reaching those kinds of numbers. Even more fascinating is that it's just Bitcoin mining, so global total computations must be some multiple of that (3x? 10x? 100x?). These are numbers once considered (still considered?) unfathomable, let alone a quantity applicable to human endeavor. And that's 2022. Today the Bitcoin hash rate is 4.5x greater.

pbsd 1 year ago | |

This circuit [1] puts it at <=135k bit operations. Bitcoin uses SHA-256, not SHA-1.

[1] https://nigelsmart.github.io/MPC-Circuits/sha256.txt

nullc 1 year ago | | |

Bitcoin's proof of work uses SHA-256(SHA-256(x)). Combining that with your figures reduces the differences to well within minutia of how you count bit operations and exactly which tradeoff the circuits make.

kragen 1 year ago | |

It's hard to know what to count as "global compute". How many bit operations do we count for the clock propagation across your CPU? Two for each clock cycle per buffer? Even though the bit operation is just identity, or do we omit that? Does it change if you use inverting buffers, since NOT is a nontrivial operation? Did you know that in CMOS a normal buffer is made out of two inverters? Can you do twice as many bit operations just by using buffers that are half as big, so that you have to use twice as many? How about DRAM destructive read and refresh cycles? Do you count the bit operations in the TLB CAM and the caches to test if entries are already present? Then going to a higher associativity, like from two-way to four-way, doubles the bit operation count.

For power consumption I think the answer to all of these is "yes", except for the one where you split the clock buffers in half.

How about DNA replication in bacterial cells? Is that two bit operations per base? My pot of yogurt is 4 kg of mostly Lactobacillus casei, with a genome of about 2 million base pairs, 4 megabits, and a generation time of about 30 minutes, 2 kilobits per second of reproductive copying per bacterium, plus presumably a much higher transcription rate into mRNA. Each bacterium is about 5 cubic microns, so there are about 10¹⁴ bacteria in the pot, so about 10¹⁷ bit operations per second for reproduction, and maybe 10¹⁹ for mRNA, wildly guessing. That would make the pot of yogurt millions of times more computationally powerful than my CPU, though only for a few hours. Fortunately, the bacteria are more energy-efficient than AMD, or the yogurt would be exploding.

But none of those operations can be used directly for cracking a key, because they aren't programmable. What the paper says is sensible, because it's comparing two things that are very much alike. Even though you can't use Bitcoin mining ASICs for key cracking, you can build very similar key cracking ASICs for a very similar cost and energy consumption. But things get very vague when you start trying to quantify all compute.

fc417fc802 1 year ago | | |

Presumably "global compute" in this context refers to activities of similar complexity carried out with digital electronic devices that produce a similarly useful output. Obviously bitcoin is some fraction of global compute; it's interesting to wonder what the (approximate) total might be.

perching_aix 1 year ago |

That's pretty messed up, guess that's another sombering fact to the pile. I'd have expected that serious security stuff always involves mechanized math proofs every step of the way, making such silly mischaracterizations impossible. Not a fun thing to learn that this is not what happens.

I_dream_of_Geni 1 year ago | |

Not only messed up, but I am guessing that there are either politics involved (personal gain, friends of friends, etc), or somebody paid somebody to push Kyber over NTRU. Which is difficult or impossible to prove, ESPECIALLY if that "person" is senator or "other". (Since I failed civics, I have no idea what forces are involved in something like this, but it all sounds really fishy).

kragen 1 year ago | | |

Historically the NSA has sabotaged public cryptography standards so that it could crack them, while adversaries hopefully couldn't. It pays its employees to do this. It seems plausible that that's what's going on here, but even if so, whether that's because they know of a fatal weakness in NTRU they fear adversaries will exploit, or know of one in Kyber that they hope to exploit themselves, is anybody's guess.

drob518 1 year ago | | |

Senators can’t even spell crypto.

matthewdgreen 1 year ago | |

This has been discussed before on HN when it was first published. I don’t remember the resolution years later, but it was discussed on the PQC mailing lists. The missing context here is that many people had submissions and academic rivalries can be very bitter.

omoikane 1 year ago |

Previously:

https://news.ycombinator.com/item?id=37756656 - Debunking NIST's calculation of the Kyber-512 security level (2023-10-03, 201 comments)