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

51–60 of 219 posts

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

#51

Post by zahllos »

tptacek wrote: post #46
zahllos wrote: post #42

Earlier quoted context omitted.

This comment is factually incorrect on a number of levels. 1) single-handedly killed US government crypto export restrictions - Bernstein certainly litigated, but was not the sole actor in this fight. For example, Phil Zimmerman, the author of PGP, published the source code of PGP as a book to work around US export laws, which undoubtedly helped highlight the futility of labelling open source software as a munition:…

Dual EC is virtually certain to be a backdoor. I had the same take on Dual EC prior to Snowden. The big revelation with Snowden wasn't NSA involvement in Dual EC, but rather that (1) NSA had intervened to get Dual EC defaulted-on in RSA's BSAFE library, which was in the late 1990s the commercial standard for public key crypto, and (2) that major vendors of networking equipment were --- in defiance of all reason --- u…

DualEC: agree. Wanted to point out that it was a poor PRNG _anyway_ and point out that the NSA's attempt at backdooring the RNG wasn't that great - as you say, RSA BSAFE used it and it made no sense. We could also point out they went after the RNG rather than the algorithm directly, which is a less obvious strategy.

I'll believe he invented the term - I have a 2009 book so-named for which he was an editor surveying non-DLP/non-RSA algorithms. Still, the idea that he's "the only one who can produce the good algorithms" and literally everyone else on the pqc list (even if we subtract all the NIST people) is wrong is bonkers.

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

#52

Post by api »

tptacek wrote: post #29
aaomidi wrote: post #23

Earlier quoted context omitted.

> Why would they be willing to risk that here? Certain types of attacks basically make it so you need to have a specific private key to act as a backdoor. That's the current guess on what may be happening with the NIST ECC curves. If so, this can be effectively a US-only backdoor for a long, long time.

I don't believe that is anybody's guess on what may be happening with the NIST ECC curves. Ordinarily, when people on HN say things like this, they're confusing Dual EC, a public key random number generator, known to be backdoored, with the NIST curve standards.

Also: if the NIST ECC curves actually are backdoored then why would the NSA need to try to push a backdoored random number generator? Just exploit the already-backdoored curves.

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

#53

Post by tptacek »

sweis wrote: post #41
nmitchko wrote: post #2

Unfortunately, the NSA & NIST most likely is recommending a quantum-proof security that they've developed cryptanalysis against, either through high q-bit proprietary technology or specialized de-latticing algorithms . The NSA is very good at math, so I'm be thoroughly surprised if this analysis was error by mistake rather than error through intent.

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

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

#54

Post by mort96 »

tptacek wrote: post #39
mort96 wrote: post #35

Earlier quoted context omitted.

I don't think the "these finalist teams are trustworthy" argument is completely watertight. If the US wanted to make the world completely trust and embrace subtly-broken cryptography, a pretty solid way to do that would be to make competition where a whole bunch of great, independent teams of cryptography researchers can submit their algorithms, then have a team of excellent NSA cryptographers analyze them and pick a…

If the NSA has back-pocketed exploits on the LWE submission from the CRYSTALS authors, it's not likely that a purely academic competition would have fared better. The CRYSTALS authors are extraordinarily well-regarded. This is quite a bank-shot theory of OPSEC from NSA.

It's true that nothing is 100% safe. And to some degree, that makes the argument problematic; regardless of what happened, one could construct a way for US government to mess with things. If you had competition of the world's leading academic cryptographers with a winner selected by popular vote among peers, how do you know that the US hasn't just influenced enough cryptographers to push a subtly broken algorithm?

But we must also recognize a difference in degree. In a competition where the US has no official influence over the result, there has to be a huge conspiracy to affect which algorithm is chosen. But in the competition which actually happened, they may potentially just need a single plant on one of the strong teams, and if that plant is successful in introducing subtle brokenness into the algorithm without anyone noticing, the NIST can just declare that team's algorithm as the winner.

I think it's perfectly reasonable to dismiss this possibility. I also think it's reasonable to recognize the extreme untrustworthiness of the NIST and decide to not trust them if there's even a conceivable way that they might've messed with the outcome of their competition. I really can't know what the right choice is.

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

#55

Post by ziddoap »

zahllos wrote: post #51
tptacek wrote: post #46

Earlier quoted context omitted.

Dual EC is virtually certain to be a backdoor. I had the same take on Dual EC prior to Snowden. The big revelation with Snowden wasn't NSA involvement in Dual EC, but rather that (1) NSA had intervened to get Dual EC defaulted-on in RSA's BSAFE library, which was in the late 1990s the commercial standard for public key crypto, and (2) that major vendors of networking equipment were --- in defiance of all reason --- u…

DualEC: agree. Wanted to point out that it was a poor PRNG _anyway_ and point out that the NSA's attempt at backdooring the RNG wasn't that great - as you say, RSA BSAFE used it and it made no sense. We could also point out they went after the RNG rather than the algorithm directly, which is a less obvious strategy. I'll believe he invented the term - I have a 2009 book so-named for which he was an editor surveying n…

While I agree with a lot of what you have said,

>Still, the idea that he's "the only one who can produce the good algorithms"

The parent post did not, at all, make the claim that Bernstein is the only one.

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

#56

Post by throw0101a »

fefe23 wrote: post #15

If you have never heard of Bernstein, this may look like mad ramblings of a proto-Unabomber railing against THE MAN trying to oppress us. However, this man is one of the foremost cryptographers in the world, he has basically single-handedly killed US government crypto export restrictions back in the days, and (not least of all because of Snowden) we know that the NSA really is trying to sabotage cryptography. Also, h…

> If you have never heard of Bernstein, this may look like mad ramblings of a proto-Unabomber railing against THE MAN trying to oppress us.

> However, this man is one of the foremost cryptographers in the world […]

It's possible to be both (not saying Bernstein is).

Plenty of smart folks have 'jumped the shark' intellectually: Ted Kaczynski, the Unabomber, was very talented in mathematics before he went off the deep end.

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

#57

Post by pclmulqdq »

tptacek wrote: post #48
pclmulqdq wrote: post #43

Earlier quoted context omitted.

There is a final standardization step where NIST selects constants, and this is done without always consulting with the research team. Presumably, these are usually random, but the ones chosen for the Dual-EC DRBG algorithm seem to have been compromised. SHA-3 also had some suspicious constants/padding, but that wasn't shown to be vulnerable yet.

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 constants randomly, it's fine, but if you derived them from a known secret, the output was predictable for anyone who knows the secret. The NIST did not provide proof that the constants used were chosen randomly.

Random choice would be equivalent to encrypting with a public key corresponding to an unknown private key, while the current situation has some doubt about whether the private key is known or not.

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

#58

Post by tptacek »

mort96 wrote: post #54
tptacek wrote: post #39

Earlier quoted context omitted.

If the NSA has back-pocketed exploits on the LWE submission from the CRYSTALS authors, it's not likely that a purely academic competition would have fared better. The CRYSTALS authors are extraordinarily well-regarded. This is quite a bank-shot theory of OPSEC from NSA.

It's true that nothing is 100% safe. And to some degree, that makes the argument problematic; regardless of what happened, one could construct a way for US government to mess with things. If you had competition of the world's leading academic cryptographers with a winner selected by popular vote among peers, how do you know that the US hasn't just influenced enough cryptographers to push a subtly broken algorithm? Bu…

That's an argument that would prove too much. If you believe NSA can corrupt academic cryptographers, then you might as well give up on all of cryptography; whatever construction you settle on as trustworthy, they could have sabotaged through the authors. Who's to say they didn't do that to Bernstein directly? If I'd been suborned by NSA, I'd be writing posts like this too!

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

#59

Post by tptacek »

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…

Who were those cryptographers?

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

#60

Post by PeterisP »

api wrote: post #52
tptacek wrote: post #29

Earlier quoted context omitted.

I don't believe that is anybody's guess on what may be happening with the NIST ECC curves. Ordinarily, when people on HN say things like this, they're confusing Dual EC, a public key random number generator, known to be backdoored, with the NIST curve standards.

Also: if the NIST ECC curves actually are backdoored then why would the NSA need to try to push a backdoored random number generator? Just exploit the already-backdoored curves.

Redundancy, so if one backdoor is closed/fixed/avoided, you still have more.
Post reply on HN