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

111–120 of 219 posts

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

#111

Post by lucb1e »

thadt wrote: post #67

The unfortunate reality of this is that while he may be right , it is difficult to classify the responses (or non-response) from the NIST people as deceptive vs just not wanting to engage with someone coming from such an adversarial position. NIST is staffed by normal people who probably view aggressively worded requests for clarification in the same way that most of us have probably fielded aggressively worded bug r…

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 understand the text in the first place.

I even got nerdsniped near the beginning into clicking on "That lawsuit has been gradually secret NIST documents, shedding some light on what was actually going on behind the scenes". That page (linked by the word ) is another 54000 words. Unaware, due to not having a scroll bar on mobile (my fault, I know), I started skimming it linearly to see what those revelations might be. Nothing really materialized. At some point I caught on that I seemed to have enrolled for a PhD research project and closed that tab to continue reading the original page...

Most HN readers, who are often smart and highly technical but in various fields, cannot reasonably weigh and interpret the techobabble evidence for "nist=bad". Being in an adjacent field, I would guess that I understand more than the average reader, but still don't feel qualified to judge this material without really giving it a thorough read. The page reasonably gives context and explains acronyms, but there's just so much of it that I can't imagine anyone who doesn't already know would want to bother with it. Not everyone understanding a submission is okay, but this is about accusations, and that makes me feel like it is not a good submission for HN.

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

#112

Post by [deleted] »

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…

[deleted]

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

#113

Post by lucb1e »

hn_throwaway_99 wrote: post #106
thadt wrote: post #67

The unfortunate reality of this is that while he may be right , it is difficult to classify the responses (or non-response) from the NIST people as deceptive vs just not wanting to engage with someone coming from such an adversarial position. NIST is staffed by normal people who probably view aggressively worded requests for clarification in the same way that most of us have probably fielded aggressively worded bug r…

Edit: Just realized the author is djb, Daniel Bernstein, which I guess is semi-ironic for me because I was recently praising him on HN for an old, well-read blog post on ipv6. Thus, I guess I may take back a bit of what I said below, or least perhaps it would be better to say that I can better understand the adversarial tone given djb's history with NIST recommendations (more info at https://en.wikipedia.org/wiki/Dan…

> 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? The latter can be expected to happen if there is actually something worthwhile in there.

This is objectively too long for casual reading, nothing to do with anyone's attention span.

(The 75-page estimate is based on: (1) a proficient reader doing about a page per minute in most books that I know of, so pages==minutes; (2) the submission being 17.6k words; (3) average reading speed is ~250 wpm, resulting in 17.6e3/250=70 minutes; (4) this is not an easy text, it has lots of acronyms and numbers, so conservatively pad to 75.)

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

#114

Post by hovav »

pclmulqdq wrote: post #57
tptacek wrote: post #48

Earlier quoted context omitted.

The problem with Dual EC isn't the sketchy "constants", but rather the structure of the construction, which is a random number generator that works by doing a public key transformation on its state. Imagine CTR-DRBG, but standardized with a constant AES key. You don't so much wonder about the provenance of the key so much as wonder why the fuck there's a key there at all. I don't know of any cryptographer or cryptogr…

I do know a few cryptographers who were suspicious of SHA-3 when it came out, but after some napkin math and no obvious hole was found, they were fine with it. The actual goal of that extra padding was to get extra one bits in the input to avoid possible pathological cases. My understanding of the Dual-EC problem may be different than yours. As I understand it, the construction is such that if you choose the two cons…

Even with a verifiably random key, Dual EC is still unacceptable.

First, because its output has unacceptable biases [1,2].

Second, because its presence allows an attacker to create a difficult-to-detect backdoor simply by replacing the key, as apparently happened with Juniper NetScreen devices [3,4].

--- [1] Kristian Gjøsteen, Comments on Dual-EC-DRBG/NIST SP 800-90, draft December 2005. Online: https://web.archive.org/web/20110525081912/https://www.math....

[2] Berry Schoenmakers and Andrey Sidorenko, Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator, May 2006. Online: https://eprint.iacr.org/2006/190.pdf

[3] Stephen Checkoway, Jacob Maskiewicz, Christina Garman, Joshua Fried, Shaanan Cohney, Matthew Green, Nadia Heninger, Ralf-Philipp Weinmann, Eric Rescorla, and Hovav Shacham, A Systematic Analysis of the Juniper Dual EC Incident, October 2016. Online: https://www.cs.utexas.edu/~hovav/dist/juniper.pdf

[4] Ben Buchanan, The Hacker and the State, chapter 3, Building a Backdoor. Harvard University Press, February 2020.

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

#115

Post by lucb1e »

kpdemetriou wrote: post #97
lucb1e wrote: post #89

Earlier quoted context omitted.

> Historically only the winners are adopted. Look at the AES competition Often, yes. But also consider the SHA-3 competition. BLAKE2 seems more widely used than what was chosen for SHA-3 (Keccak). What was submitted for the SHA-3 competition was BLAKE1 (it didn't have a number back then but I think this is clearer) so it's not like NIST said that Keccak is better than BLAKE2, they only said it's better than BLAKE1 (p…

Re: BLAKE2, I'm not sure it's fair to say that BLAKE2 is more widely used overall. But I do agree BLAKE2 is a bit of an outlier in terms of adoption. I think part of the reason is that SHA2 remains the go-to option, else I'd expect the ecosystem to consolidate around SHA3. Re: Serpent, there are many things to unpack here but, in summary, you don't know a priori how large of a security margin you need (given the prim…

> I'm not sure it's fair to say that BLAKE2 is more widely used overall

Ah, maybe my experience is biased then. I keep coming across BLAKE2 implementations, but rarely hear so much as people considering to use SHA-3 somewhere. If anyone has actual numbers on this, that would be interesting.

It would be good if SHA-3 is being used because then chip makers have a reason to bake it into their hardware, which is exactly where the biggest gain over SHA-2 is expected. If that happens, and all else being equal (no cracks appear in Keccak), I'd be surprised if BLAKE2 remains as popular!

> you don't know a priori how large of a security margin you need

True, so this can be argued to be an educated guess at first. But then confidence increases over time. It seems to be expected that, more than 20 years later, people aren't considering Serpent anymore. Is it because it wasn't chosen as AES? Certainly partially, but BLAKE2 (I'll admit it does seem like an outlier) likely will still be talked about in the future so standardization is not the only factor.

I didn't see actual benchmarks, but Serpent sounds at least three times slower than Rijndael for, by now, no tangible benefit. What would be interesting is if there were AES competitors that are also fully unbroken and are more efficient than Rijndael, or easier to implement, etc.

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

#116

Post by bsder »

zahllos wrote: post #85
kpdemetriou wrote: post #75

Earlier quoted context omitted.

Absolutely, but NIST ultimately choose the winners, giving them the option to pick (non-obviously) weak/weaker algorithms. Historically only the winners are adopted. Look at the AES competition - how often do you see Serpent being mentioned, despite it having a larger security margin than Rijndael by most accounts?

I fully admit to having a weak spot for Serpent - it is self-bitslicing (see the submission package or the linux kernel tree), which in hindsight makes constant time software easier to write, and it was faster in hardware even when measured at the time, which is where we have ended up putting AES anyway (e.g. AES-NI etc). BUT. On security margins, you could argue the Serpent designers were too conservative: https://e…

> BUT. On security margins, you could argue the Serpent designers were too conservative: https://eprint.iacr.org/2019/1492

Thanks for digging that paper out again. It is really telling that AES only gets a bit of a bump (10-30%) while the other ones gain like 2x or more.

I was about to comment that the competitors to AES were definitely too conservative, and it bit them because of how much slower it made them in software and larger in hardware.

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

#117

Post by ethbr1 »

Ar-Curunir wrote: post #102
f33d5173 wrote: post #66

Earlier quoted context omitted.

A hash function is a (CS)PRNG. It has the key property, namely of being indistinguishable from randomness while being generated deterministically.

That is not true. There is no such requirement for a hash function.

Thread is talking about cryptographic hash functions, given the context

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

#118

Post by ethbr1 »

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.

Stare into randomness for long enough, and you'll see something staring back. There's a reason I didn't go pure-math

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

#119

Post by ethbr1 »

10g1k wrote: post #99

Related note: Government employees (including military, intel) are just people, and worse, bureaucrats. They aren't magical wizards who can all do amazing things with mathematics and witchcraft. If they were good at what they do, they wouldn't need ever increasing funding and projects to fix things.

Cryptanalysis and encryption are somewhat of an exception to this. There are some extremely smart people who work in these areas for the government, precisely because funding and application is on a different scale.

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

#120

Post by kevin_thibedeau »

kpdemetriou wrote: post #75
tptacek wrote: post #20

An important detail you really want to understand before reading this is that NIST (and NSA) didn't come up with these algorithms; they refereed a competition, in which most of the analysis was done by competitors and other academics. The Kyber team was Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Gregor Seiler, Damien Stehlé, and also Peter Schwabe, a colla…

Absolutely, but NIST ultimately choose the winners, giving them the option to pick (non-obviously) weak/weaker algorithms. Historically only the winners are adopted. Look at the AES competition - how often do you see Serpent being mentioned, despite it having a larger security margin than Rijndael by most accounts?

Blowfish has a continuing existence as the basis for bcrypt.
Post reply on HN