Debunking NIST's calculation of the Kyber-512 security level (2023)
1–10 of 22 posts
Re: Debunking NIST's calculation of the Kyber-512 security level (2023)
#2That'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.
Re: Debunking NIST's calculation of the Kyber-512 security level (2023)
#3That'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.
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).
Re: Debunking NIST's calculation of the Kyber-512 security level (2023)
#4This 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.
Re: Debunking NIST's calculation of the Kyber-512 security level (2023)
#5Previously:
https://news.ycombinator.com/item?id=37756656 - Debunking NIST's calculation of the Kyber-512 security level (2023-10-03, 201 comments)
Re: Debunking NIST's calculation of the Kyber-512 security level (2023)
#6That'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.
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).
Senators can’t even spell crypto.
Re: Debunking NIST's calculation of the Kyber-512 security level (2023)
#7This 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…
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.
Re: Debunking NIST's calculation of the Kyber-512 security level (2023)
#8You 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.
Re: Debunking NIST's calculation of the Kyber-512 security level (2023)
#9This 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…
This circuit [1] puts it at [1] https://nigelsmart.github.io/MPC-Circuits/sha256.txt
Re: Debunking NIST's calculation of the Kyber-512 security level (2023)
#10That'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.
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).
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.