Live data from Hacker News

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

blog.cr.yp.to

71–80 of 219 posts

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

#71
post #53
post #41

Earlier quoted context omitted.

"High q-bit proprietary technology" and "specialized de-latticing algorithms" are made up terms that nobody uses.

I'm stuck on trying to work out what it would mean to de-lattice something. Would that transform a lattice basis into a standard vector space basis in R or something, or, like MOV, would it send the whole lattice to an element of some prime extension field? In my mind's eye, it's cooler: it's like, you render the ciphertext as a raster image, and then "de-lattice" it to reveal the underlying plaintext, scanline by sc…

i'm still working on understanding lattices better

but i can imagine, based on my own ignorance, creativity, and lack of correct understanding, would be some kind of factorization.

as I think while trying to better know what's a lattice, I imagine a lattice like a coordinate pair, but instead of each coordinate existing on a line, they exist on a binary tree (or some other directed graph explored from a root outwards without cycles)

which means you have two such binary-trees (not necessarily binary, but it's just easier to work with them seemingly)

and then you combine these into ONE lattice. so then, to de-lattice means to recover the binary trees.

but when I say binary tree I'm thinking about rational numbers (because stern broccott trees)

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

#72
post #64

Earlier quoted context omitted.

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…

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

In fact, `echo "This is my seed" | openssl sha -sha256` is not really a CSPRNG. Hash functions are the bases of many PRNGs. But I think you're abusing an ambiguity with the word "random" here. At any rate: we should be clear now on the point being made about the P-curve seeds.

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

#73
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…

You're making an assumption that the NSA cares about the efficacy of cryptography for other people. Why would they care about that?

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

#74
post #53

Earlier quoted context omitted.

I'm stuck on trying to work out what it would mean to de-lattice something. Would that transform a lattice basis into a standard vector space basis in R or something, or, like MOV, would it send the whole lattice to an element of some prime extension field? In my mind's eye, it's cooler: it's like, you render the ciphertext as a raster image, and then "de-lattice" it to reveal the underlying plaintext, scanline by sc…

i'm still working on understanding lattices better but i can imagine, based on my own ignorance, creativity, and lack of correct understanding, would be some kind of factorization. as I think while trying to better know what's a lattice, I imagine a lattice like a coordinate pair, but instead of each coordinate existing on a line, they exist on a binary tree (or some other directed graph explored from a root outwards…

A lattice is like a vector space, but with exclusively integer coefficients. It's not a coordinate pair. If you think of vectors as coordinate pairs, a vector space is a (possibly unbounded) set of coordinate pairs. If you haven't done any linear algebra, a decent intuition would be mathematical objects like "the even numbers" or "the odd numbers", but substituting vectors (fixed-sized tuples of numbers) for scalars.

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

#75
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?

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

#76
post #69
post #65

Earlier quoted context omitted.

You're still not recognizing the difference between corrupting a single academic cryptographer and corrupting a whole bunch of academic cryptographers. This isn't so black and white. For what it's worth, I do think the US government could corrupt academic cryptographers. If I was an academic cryptographer, and someone from the US government told me to do something immoral or else they would, say, kill my family, and…

As long as we're clear that your concern involves spy movie shit, and not mathematics or computer science, I'm pretty comfortable with where we've landed.

If your argument is: “assuming the US government wouldn’t be able to make someone act against their will and stay silent about it, the NIST recommendation is trustworthy”, I’m certainly more inclined to distrust this recommendation than I was before this conversation.

Note that the “forcing someone to comply” thing was just meant as one possibility among many, I don’t see why you completely dismiss the idea of someone who’s good at cryptography being in on the US’s mission to intercept people’s communications. I mean the NSA seems to be full of those kinds of people. You also dismiss the possibility that they just … picked the algorithm that they thought they could break after analysing it, with no participant being in on anything. But I get the feeling that you’re not really interested in engaging with this topic anymore, so I’ll leave it at that. It’s already late here.

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

#77

Notwithstanding DJB's importance to cryptography, and the fact that I'm ignorant of a large number of details here, there was a point where he lost a lot of credibility with me. Specifically, when he gets to the graphs, he says "NIST chose to deemphasize the bandwidth graph by using thinner red bars for it." That is just not proven by his evidence, and there is a very plausible explanation for it. The graph that has…

If you continue reading, you'll find that they aren't responding to requests for clarification on their hand-waving computations. Suspicion is definitely warranted.

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

#78
The NIST standardization process, appears to have a grey area particularly around the selection of constants.

The skepticism around standardization, advocating instead for direct adoption from cryptographers, sheds light on potential shortcomings in the current system.

There is definitely a need for a more transparent or open scrutiny in algorithm standardization to ensure security objectives are met.

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

#79

Love the narrative style of this writing second-guessing the erroneous thought processes. Are they deceptive? Who knows. What worries me is that it's neither malice nor incompetence, but that a new darker force has entered our world even at those tables with the highest stakes.... dispassion and indifference. It's hard to get good people these days. A lot of people stopped caring. Even amongst the young and eager. Wh…

The car is on fire and there is no driver at the wheel.

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

#80
post #34

Notwithstanding DJB's importance to cryptography, and the fact that I'm ignorant of a large number of details here, there was a point where he lost a lot of credibility with me. Specifically, when he gets to the graphs, he says "NIST chose to deemphasize the bandwidth graph by using thinner red bars for it." That is just not proven by his evidence, and there is a very plausible explanation for it. The graph that has…

> 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.

There's a meaningful difference between assuming an actor is malicious or untrustworthy and going out of your way to provide the maximally malicious interpretation of each of their actions. As a matter of rhetoric, the latter tends to give the impression of a personal vendetta.
Post reply on HN