NIST announces first PQC algoritms to be standardized • Hacker News Board

Re: NIST announces first PQC algoritms to be standardized

#71

Post by adastra22 » Tue, Jul 05, 2022, 9:14 PM UTC

hinkley wrote: post #63

adastra22 wrote: post #55

Earlier quoted context omitted.

SHA-512 doesn’t have any issues.

The selection criteria for SHA-3 included internal state being greater than the output size. SHA-1 and SHA-2 both repeat this mistake of MD5. SHA-2 has variants that don't have this problem, but sha-256 and sha-512 aren't among them. I'm having trouble finding it now but I recall someone complaining about the constants for 512 leaving something to be desired.

This isn’t a mistake per se, it’s how that class of hash functions—and really, almost every hash function ever—is implemented. It’s called the Merkle-Damgård construction. It adds some very good properties and is the basis for how hash functions can be used in hash tree constructions and such.

But proving that the input state is evenly mixed among the output state is THE hard thing to prove (the hash function equivalent of the difficulty of factoring integers), so for the sake of ecosystem diversity NIST chose a hash function based on different principles for SHA-3. It’s not a criticism of SHA-2 that the difference was called out.

The constants are the fractional bits of of successive cube roots. This is effectively a nothing-up-my-sleeve random number selection. If there are problems with this, that in itself would be a serious cryptographic result.

Re: NIST announces first PQC algoritms to be standardized

#72

Post by bawolff » Tue, Jul 05, 2022, 9:20 PM UTC

adastra22 wrote: post #58

bawolff wrote: post #43

Earlier quoted context omitted.

To nitpick, afaik, its not that they cannot be proven, its that they have not been, and look very hard to prove, which is slightly different (not my area of expertise, but i assume this would be tied to p vs np)

I it not tied to P vs NP as far as I’m aware. But it is the same sort of situation: number theory assumptions that are completely unproven despite many attempts.

I was thinking, if you could definitively prove these assumptions are hard, that would prove P != NP, because if P=NP that would imply there would be an algorithm to solve these types of problems, since they are the type of thing that can be solved in polynomial time with the key, but cannot without a key. (I'm a bit out of my depth here)

Re: NIST announces first PQC algoritms to be standardized

#73

Post by forty » Tue, Jul 05, 2022, 9:28 PM UTC

buu700 wrote: post #39

forty wrote: post #21

Coincidentally, we have just published this today, if you want to play with PQ crypto in JavaScript https://github.com/Dashlane/pqc.js

Similarly, I just published this a few days ago: https://github.com/cyph/pqcrypto.js Edit: lol, actually it looks like you guys borrowed some of my code for that. (Which is totally fine and part of the point of open source!)

Apparently yes! I'm told we did use your other older project ntru.js as mentioned in the readme :) thanks for sharing your code!

Re: NIST announces first PQC algoritms to be standardized

#74

Post by Beldin » Tue, Jul 05, 2022, 9:33 PM UTC

bawolff wrote: post #41

oconnore wrote: post #36

Earlier quoted context omitted.

If NIST feels the need to hedge their bets, why are they publishing at all? The whole point of these recommendations is so that I, a non-expert, don't have to reason about cryptographic bets.

Life's hard and the world is uncertain. If NIST could make an algorithm that they could prove was 100% safe with no possibility of future cryptoanalytical breakthroughs, i am sure they would, but that is beyond current state of the art.

You mean like a one-time pad? I'm sure the folks at NIST know about it; it is completely unbreakable and had been around for a while. Use is not really practical though, so typically reserved for very specific use cases.

Re: NIST announces first PQC algoritms to be standardized

#75

Post by forty » Tue, Jul 05, 2022, 9:39 PM UTC

sterlind wrote: post #26

forty wrote: post #20

Earlier quoted context omitted.

What's the "obligatory djb warnings"? Something like "any crypto that's not mine isn't great"? ;)

from skimming it, his main argument is that Kyber relies on many constructions (e.g. cyclotomic polynomials) that are actively under attack - researchers have been successfully chipping away at them and show no signs of stopping. he also alleges that NIST have been moving the goal posts to favor Kyber, and they've been duplicitous in their narrative. he favors NTRU, which iirc isn't his.

My understanding is that he worked on NTRU Prime, which would have somehow benefited from NTRU being choosen.

Re: NIST announces first PQC algoritms to be standardized

#76

Post by Spooky23 » Tue, Jul 05, 2022, 9:43 PM UTC

oconnore wrote: post #36

bawolff wrote: post #33

Earlier quoted context omitted.

Presumably to hedge their bets. If suddenly someone finds a major problem with latices, its good to have an alternative waiting in the wings. See also sha-3 vs sha-256

If NIST feels the need to hedge their bets, why are they publishing at all? The whole point of these recommendations is so that I, a non-expert, don't have to reason about cryptographic bets.

Perhaps they want industry to start working on software or hardware to leverage these algorithms?

Cryptography is driven by defense applications. For all us civilian types know, these algorithms have been around for 30 years.

Re: NIST announces first PQC algoritms to be standardized

#77

Post by sbf501 » Tue, Jul 05, 2022, 9:59 PM UTC

markschultz wrote: post #62

sbf501 wrote: post #18

Waiting for the ELI5 sites to explain Kyber and LWE. :)

I wrote up an introduction to a (severely unoptimized for pedagogical purposes) version of FrodoKEM https://mark-schultz.github.io/nist-standard-out/ It's the same base scheme as Saber/Kyber, although as Saber/Kyber are over algebraically structured lattices they are significantly more efficient.

Thanks for taking the time to write this up. But, woof, it's a bit more than ELI5. :) The python code makes it a little more clear since I'm not familiar with some of the notation. However, it does seem kind of magic that 'e' is derived during the encryption and then sort of vanishes. I also don't quite get the bounded vs uniform vector sampling calls (one for s and the other for chi). But this at least greases the wheels so to speak, so thanks!

Re: NIST announces first PQC algoritms to be standardized

#78

Post by google234123 » Tue, Jul 05, 2022, 10:00 PM UTC

chasil wrote: post #35

layer8 wrote: post #22

Earlier quoted context omitted.

OpenSSH has merely chosen that as its current default. Surely multiple algorithms will be supported in the future as they have in the past.

There was considerable strife for Daniel J. Bernstein during this competition. https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&c... It would not surprise me if OpenSSH only chooses to add SPHINCS+ and refuses the others.

Bernstein seems to be involved in never ending drama. Maybe the problem is him?

Re: NIST announces first PQC algoritms to be standardized

#79

Post by krastanov » Tue, Jul 05, 2022, 10:06 PM UTC

chasil wrote: post #42

hannob wrote: post #19

Earlier quoted context omitted.

I've been following this space for a while and this is a good question, but I think the answer is really a "ranges from 10 years to never". There's a lot of investment currently in the quantum computer space (+ a lot of hype and scams). Yet this is still all very early research and far away from any practical use. The challenges to really build a QC that can break cryptography are enormous - and it is absolutely a po…

This article asserts that D-Wave and other quantum annealing devices will be able to mount attacks long before a machine exists that can run Shor's algorithm with error-corrected qubits in sufficient quantity. https://www.forbes.com/sites/arthurherman/2021/06/07/q-day-i...

To second what the sibling comment has said, "quantum annealing" claims by DWave are considered fairly overblown (on some rare occasions even misleading/scammy). If the claims of this article held, they would have been much better known in the field and published in much more popular venues.

Re: NIST announces first PQC algoritms to be standardized

#80

Post by upofadown » Tue, Jul 05, 2022, 10:10 PM UTC

Beldin wrote: post #74

bawolff wrote: post #41

Earlier quoted context omitted.

Life's hard and the world is uncertain. If NIST could make an algorithm that they could prove was 100% safe with no possibility of future cryptoanalytical breakthroughs, i am sure they would, but that is beyond current state of the art.

You mean like a one-time pad? I'm sure the folks at NIST know about it; it is completely unbreakable and had been around for a while. Use is not really practical though, so typically reserved for very specific use cases.

One time pads fall into the symmetrical encryption category. There is no huge issue with symmetrical encryption with respect to the possibility someone might invent a quantum computer. The things people are working on for a post quantum world and NIST is attempting to standardize are in the asymmetrical encryption category.