Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

blog.cr.yp.to

Post reply on HN
Print view View original

201–210 of 219 posts

Re: Debunking NIST's calculation of the Kyber-512 security level

#201

Post by hn_throwaway_99 »

pseg134 wrote: post #177
lucb1e wrote: post #113

Earlier quoted context omitted.

> I know people love to harp on "the Internet has killed our attention spans" Not just that. Give your parent or grandparent a 75-page booklet to read, full of accusations and snark, and let's say it's about something they care about and actually impacts their lives (maybe a local government agency, idk). What are the odds they are going to read that A-Z versus waiting for a summary or call-to-action to be put out? T…

People read it because of djb’s reputation. I’m the future, when someone smarter than you writes something it might benefit you to put aside your tone scolding and receive the information. It might be important.

Really smart people can be horrible writers. It's fair to call that out regardless of the reputation of the author.

Re: Debunking NIST's calculation of the Kyber-512 security level

#203

Post by wolf550e »

tptacek wrote: post #64
dfox wrote: post #63

Earlier quoted context omitted.

The issue with the NIST curves is that they were generated from a PRNG with some kind of completely random seed. The conspiracy theory there is that the seed was selected such as to make the curve exploitable for NSA and NSA only. Choosing such a seed is somewhat harder than complete break of the hash function (IIRC SHA-2) used in the PRNG that was used to derive the curve. On the other hand, there is a lot of reason…

It's very unlikely the seeds were random, and they weren't even ostensibly generated from a PRNG, as I understand it. Rather, they were passed through SHA1 (remember: this is the 1990s), as a means to destroy any possible structure in the original seed. The actual seeds themselves aren't my story to tell, but are a story that other people are talking about. For my part, I'll just point again to Koblitz and Menenzes o…

This seems to be all that is publicly known about the seeds: https://saweis.net/posts/nist-curve-seed-origins.html

Re: Debunking NIST's calculation of the Kyber-512 security level

#204

Post by crest »

bonzini wrote: post #147
tptacek wrote: post #130

Earlier quoted context omitted.

It works as a password hash for reasons having in part to do with why it isn’t a great general purpose cipher.

Can you expand, or link to an explanation?

The Blowfish key-schedule algorithm is equivalent to encrypting 4kB of data with it. This isn't a problem for some use-cases (e.g. transferring a large file over HTTPS), but terrible for others e.g. a encrypting lots of short messages using different keys without being able to cache > 30x larger result of the key-schedule result. To make it worse the cipher uses four large 256 x 32bit S-boxes with data (key and plaintext) dependent indexes making it very hard to implement fast without adding a timing side-channel on anything more complex than a simple microcontroller. It also does very little computation per memory access. Blowfish is a fast cipher on a very simple 32bit CPU with >= 4kiB of fast memory, but modern CPUs offer a lot more compute throughput than memory throughput. There is also very little opportunity to exploit for even the most expensive OoO CPUs because almost every depends on a data dependent memory access within a few instructions. For these reasons it's also expensive and relatively slow to implement in hardware.

Almost all of these downsides are helpful for password has validation function like bcrypt() because there is nothing to an attacker can to guess much faster than a desktop CPU.

Blowfish was a good cipher at a time when CPUs lacked dedicated trustworthy crypto engines, wide and deep OoO execution capability, and packed-SIMD support. AES and SHA1/2 are commonly implemented in hardware on modern server, desktop and mobile CPUs. Where hardware offloading isn't available ciphers can take advantage of OoO and SIMD to perform vastly more useful work per cycle than stalling on memory accesses.

Re: Debunking NIST's calculation of the Kyber-512 security level

#205

Post by tptacek »

cryptonector wrote: post #197
codeflo wrote: post #16

That's more of a diary than an article -- jargony, disorganized, running in circles, very hard to follow. But the information might be important regardless. There's a strong implication that NIST with help of the NSA intentionally standardized on a weak algorithm. We all know that's possible. But can someone who follows some of this stuff more closely explain what the play would be? I always assumed that weakening pu…

NSA weakened DES from 64-bit keys to 56-bit keys. The idea was that they could be ahead in breaking it, and that by the time 56-bit keys were too weak in general then something else would replace DES. Risky? Yes, but it worked out, for some value of "worked out". So I wouldn't assume something like that wouldn't happen again.

They did that openly. What they did in secret was to harden it against an incredibly powerful attack (it's still a basis for block and hash cryptanalysis today) that nobody else knew about.

Re: Debunking NIST's calculation of the Kyber-512 security level

#206

Post by lucb1e »

bjourne wrote: post #179
lucb1e wrote: post #111

Earlier quoted context omitted.

This is 100% in line my reading of the submission. Also noting that the page contains seventeen thousand words . That many words of harry potter take an average person 70 minutes to read. This text is no harry potter: it's chock-full of numbers, things to consider, and words and phrasings to weigh (like when quoting NIST), so you're not going to read it as fast as an average book, if you know enough about PQC to unde…

HN readers that don't want to read the piece in full can take solace in that PQC has not been proven viable. Thus, what algorithms we should use to protect ourselves once what we thought was intractable becomes tractable may be a moot point. Shor's algorithm is capable of factoring 21 into 7 x 3. That's a long way off from factoring the thousands of digits-long numbers used for modern cryptography.

> Shor's algorithm is capable of factoring 21 into 7 x 3. That's a long way off from factoring the thousands of digits-long numbers

That is quite misleading, per my understanding.

Today's or near-future quantum computers can do this level of arithmetic, but Shor's algorithm does not have hardware limitations because it's an algorithm and not a computer. You can apply it to a thousand digits as well as to one. Apparently the thousand digits requires a certain number of qubits, i.e. a big enough quantum computer, but that's kind of the point: many people expect that we will gain that capability (keeping enough qubits stable for long enough to do the computation) sooner or later. Security agencies are saying to expect it in about ten years from now. Maybe you know better, yes can be, but that is not where I am going to put my money.

There now exist algorithms that can mitigate this risk, might as well use them. Why try to convince people they shouldn't bother?

Re: Debunking NIST's calculation of the Kyber-512 security level

#207

Post by CyberDildonics »

codr7 wrote: post #62
wnevets wrote: post #36

Earlier quoted context omitted.

Correct me if I'm wrong, everything is also being done out in the open for everyone to see. The NIST aren't using some secret analysis to make any recommendations.

My rule of thumb in these situations is always: if they could, they would. I've seen enough blatant disregard for humanity to assume any kind of honesty in the powers that were.

Where is your evidence other than your gut feeling from other unrelated news articles?

Re: Debunking NIST's calculation of the Kyber-512 security level

#208

Post by arp242 »

Ar-Curunir wrote: post #104
ziddoap wrote: post #34

Earlier quoted context omitted.

> At this point, it feels quite strongly to me that he is trying to interpret every action in the most malicious way possible. Given the long and detailed history of various governments and government agencies purposefully attempting to limit the public from accessing strong cryptography, I tend to agree with the "assume malice by default" approach here. Assuming anything else, to me at least, seems pretty naive.

DJB has lost a ton of credibility already within the non-government cryptography community for his frankly unhinged rants on the PQC mailing list. If you read his posts there, it’s hard not to come away with the impression that he’s just upset his favourite scheme wasn’t chosen.

Hasn't djb always been rather difficult and ranty? That's certainly always been my impression of him.

Re: Debunking NIST's calculation of the Kyber-512 security level

#209

Post by arp242 »

denton-scratch wrote: post #184
ignoramous wrote: post #18

Earlier quoted context omitted.

An interesting set of comments (by tptacek) from a thread in 2022 (I wonder if they still hold the same opinion in light of this latest post on NIST-PQC by djb): > The point isn't that NIST is trustworthy. The point is that the PQC finalist teams are comprised of academic cryptographers from around the world with unimpeachable reputations, and it's ludicrous to suggest that NSA could have compromised them. The whole…

> actually a product of the Lizard People Nobody says that (not that I've seen). My reading is that he's a combative academic, railing against a standards body that refuses to say how they're working, with a deserved reputation for dishonesty and shenanigans.

I'm pretty sure that was a humorous exaggeration, and just means "conspiratorial bent". I don't think anyone really believes in Lizard People except David Icke.

Re: Debunking NIST's calculation of the Kyber-512 security level

#210

Post by feurenard »

greggsy wrote: post #50

It would be interesting to see Signal Sciences response to this Bernstein’s post

Signal seems to use Kyber-1024, which does meet the NIST contest's security criteria.

I wrote some more details here: https://community.signalusers.org/t/signal-blog-quantum-resi...

Post reply on HN