NIST Announces First Four Quantum-Resistant Cryptographic Algorithms (nist.gov) 56
jd writes: NIST has announced winners of its post-quantum cryptography battle of the giants.
CRYSTALS-Kyber has been chosen for standard encryption, CRYSTALS-Dilithium, Falcon, and SPHINCS+ were chosen for digital signatures. Falcon is recommended by NIST as a backup for Dilithium where shorter keys are needed, and SPHINCS+ uses a different mathematical technique than all of the other submissions, so if it is found that there's a flaw in the maths for the others, then there's something to fall back on.
There is still a final round for public key encryption algorithms. The remaining candidates are BIKE, Classic McEliece, HQC, and SIKE.
The mailing list members probably wish that they could use Slashdot's moderation system about now, as some of the discussions have been extremely heated. This was especially true for the signature system Rainbow, which is used by the ABC Mint crypto-currency, which was rejected after what was claimed to be a catastrophic flaw was reported, with allegations that it could be broken over a weekend on a laptop, followed by counter-allegations that many of the other algorithms had significant flaws in them also. (This is likely why SPHINCS+ is a backup.)
Another area that was hotly debated was CPU design flaws, particularly HertzBleed, which got the well-known crypto maestro Bernstein rather annoyed. As SIKE is a final round candidate, NIST seem to be satisfied with his explanation for why CPU design flaws should not be considered. It is to be seen how this debate progresses.
CRYSTALS-Kyber has been chosen for standard encryption, CRYSTALS-Dilithium, Falcon, and SPHINCS+ were chosen for digital signatures. Falcon is recommended by NIST as a backup for Dilithium where shorter keys are needed, and SPHINCS+ uses a different mathematical technique than all of the other submissions, so if it is found that there's a flaw in the maths for the others, then there's something to fall back on.
There is still a final round for public key encryption algorithms. The remaining candidates are BIKE, Classic McEliece, HQC, and SIKE.
The mailing list members probably wish that they could use Slashdot's moderation system about now, as some of the discussions have been extremely heated. This was especially true for the signature system Rainbow, which is used by the ABC Mint crypto-currency, which was rejected after what was claimed to be a catastrophic flaw was reported, with allegations that it could be broken over a weekend on a laptop, followed by counter-allegations that many of the other algorithms had significant flaws in them also. (This is likely why SPHINCS+ is a backup.)
Another area that was hotly debated was CPU design flaws, particularly HertzBleed, which got the well-known crypto maestro Bernstein rather annoyed. As SIKE is a final round candidate, NIST seem to be satisfied with his explanation for why CPU design flaws should not be considered. It is to be seen how this debate progresses.
Link to Falcon (Score:5, Informative)
My bad when checking. The definition of Falcon can be found at: https://falcon-sign.info/ [falcon-sign.info]
Signature lengths (Score:5, Informative)
The signature lengths in these schemes is... impressive. Falcon was recently congratulated for bringing the hash down to 410 bytes (not bits!), without compromising security, for their Falcon-512 algorithm. If you thought getting SHA-2 and SHA-3 into Git was bad, Falcon is going to be an absolute nightmare even with their reduced length. (I'm guessing here, but the pub size and sig size on their web page are therefore presumably bytes as well.)
This really is an improvement on the others. Dilithium reports a signature size of 2420 bytes and I believe SPHINCS+ produces one that is even longer.
You, too, can play with them, not only through the reference implementations but also through BouncyCastle, which has implementations of these algorithms. I wouldn't be surprised if they were being added to other standard crypto libraries, so expect some usage of them in the near future.
Re: (Score:3)
Well, 410 bytes is better than 410 kilo-bytes....Right?
In all seriousness though... 410 bytes is still CRAZY!!!
Re: (Score:2)
Ah, found SPHINCS+ sig lengths. The strongest version is 49k (49856 byte) signatures. It seems to be tied to SHA2 and similar hashes, but doesn't get defined with SHA3. I'm unsure what happens if SHA2 gets compromised, or whether you can use SHA3 as the regular hashing component.
(Pages 56-58 from https://sphincs.org/data/sphin... [sphincs.org])
Re: (Score:1)
Falcon is for signatures: Think PGP signatures. SHA2 and 3 are quantum resistant
Re: (Score:1)
Re: (Score:2)
Fair enough, so Falcon is of usable length, then. Dilithium is 5.9x longer, which is getting lengthy. Still haven't found SPHINCS+' digest length, but this may be the one that ends up used if the potential risk turns out to be an actual risk.
Re: Crypto Backdoor Culture Change? (Score:2)
Their support of SPHINCS+ as backup suggests they're trying to avoid flaws.
SIKE (Score:3)
It took me a while to comprehend SIKE. However after looking at it for a while, I've concluded that SIKE is my preferred candidate. While the mathematics for supersingular isogency graphs is a bit mind bending, implementing it is not too bad.
Re: (Score:3)
Re: (Score:2)
SIKE is mathematically intense; it's one of the slowest algorithms in the competition. Running it on embedded hardware is extremely painful... think in minutes rather than seconds to perform a key exchange.
My focus is hardware implementation of cryptographic stuff. It seems not to bad in that context. Your point is valid. I wouldn't try it on an 8052.
While I get the math mechanistically, I still have no real clue what a supersingular curve really is or why it is.
E.G. This enlightening blob of obfuscation from the internet, doesn't really
"A supersingular elliptic curve is an elliptic curve E/F with the property that the endomorphism ring (ring of homomorphisms from E to E) of E over the algebraic closure of F_
Symmetric encryption? (Score:2)
I thought symmetric algorithms like AE-256 weren't especially vulnerable to quantum attack; but the description of crystal, at least, implies otherwise. Was I misunderstanding the situation?
Tested, but not proven. (Score:3, Informative)
AES is believed to be secure against quantum attacks.
AES has stood up to attack attempts. It's not mathematically proven to the degree we'd like.
Kyber is mathematically proven (IND-CCA2), but hasn't been battle-tested like AES has.
A Kyber-based scheme will be used for asymmetric encryption. It is therefore convenient to also use Kyber for symmetric.
Bottom line - I'd continue using AES for the next couple of years, then switch to Kyber if things still look good.
Re:Tested, but not proven. (Score:4, Insightful)
Kyber is an asymmetric algorithm. It is not at all 'convenient to use it for symmetric', as it doesn't do that. Kyber is used to exchange AES keys, it is in no way a replacement for AES.
I mispoke (Score:3)
Thanks for adding the correct information re symmetric.
Re: (Score:2)
Amazing that incorrect information like this is modded informative.
Feel free to point out which of the claims is incorrect.
Re: (Score:2)
The parts that say Kyber can be used for symmetric encryption and that Kyber can replace AES at some point.
Re: (Score:2)
Yep. Joce may not have seen my acknowledgement of my error
https://slashdot.org/comments.... [slashdot.org]
Re: (Score:2)
AES has stood up to attack attempts.
So has every other crypto algorithm ever, because despite the twice-a-month announcement of quantum supremacy and billions of dollars spent, no-one has ever managed to build a quantum computer that's capable of attempting anything other than simple toy problems.
Almost all ciphers have fallen (Score:2)
> > AES has stood up to attack attempts.
> So has every other crypto algorithm ever, because despite the twice-a-month announcement of quantum supremacy and billions of dollars spent, no-one has ever managed to build a quantum computer that's capable of attempting anything other than simple toy problems.
It seems my message was unclear. I didn't say AES has stood up to QUANTUM attacks. It has survived all kinds of attacks, for a long time. That's very much NOT true of "every other crypto algorithm e
Re: (Score:1)
AES 256 is secure, but for Public Key encryption, you need to encapsulate the symmetric key in a Public Key Algorithm. CRYSTALS-Kyber is this encapsulation algorithm (Lookup KEM)
Re: (Score:2)
AES 128 is probably secure, too. The only known quantum attacks are on a reduced number of rounds.
Re: (Score:2)
I don't see anything in the description of CRYSTALS that implies AES is vulnerable. Kyber is a key encapsulation mechanism, intended only to encrypt a short message (i.e. an AES key). You wouldn't use it replace AES because encrypting just a 32 byte key results in a 1668 byte (if I remember correctly) output, and it is slow.
Re: (Score:2)
AES-256 or better is safe against quantum attacks (the best current algorithm for attacking it is still Grover's, which just cuts down the search space, making it effectively as secure as AES-128).
The asymmetric algorithms in the competition are all key exchange mechanisms. You use KEMs to securely agree on a shared secret, which you can use to derive keys for use with symmetric encryption like AES. Existing Diffie-Hellman key agreement schemes like ECDH can be "easily" cracked via Shor's algorithm (for val
Re: (Score:2)
I thought symmetric algorithms like AE-256 weren't especially vulnerable to quantum attack; but the description of crystal, at least, implies otherwise. Was I misunderstanding the situation?
They are not. Symmetric algorithms get their strength reduced to half the number of bits (worst case) and that only for a known-plain text attack. As even a 64 bit calculation (AES-128) is completely out of reach of any QC and will remain there for the foreseeable future, this whole thing is bogus.
Re: (Score:2)
This has nothing to do with AES or any other symmetric encryption, and nobody is claiming otherwise. This is only about the public key stuff used for key exchange and signature verification, specifically the ability to calculate the private key given the public key. And if the key exchange is compromised, then it doesn't matter how secure AES (or any other symmetric algorithm) is, because the attacker will possess the key.
Are their any quantum computers now that can do that? Probably not. Might there be
Re: (Score:2)
But it would be beyond stupid to just pretend the possibility does not exist, and do nothing to prepare for it.
Well, you certainly do not undertand risk management. Nobody pretends the possibility does not exist. What I say is that this is not a real threat anytime soon and it is still completely unclear whether it ever will be one. That the crypto-mathematicians can do some nice research here and then some additional nice research trying to attack what they have come up with is nice, but that is essentially it. There is no need to replace anything just yet. And there may never be any need for these things. Having t
SPHINCS+ (Score:2)
This algorithm used a regular hash as part of the code, but is only defined to work up to SHA2. Does anyone see any obvious reason it couldn't work with SHA3?
Re: (Score:2)
Ah, ok, that wasn't clear to me from the document. It working with any hash algorithm makes a lot more sense to me. I'd wondered if the reason it wasn't listed as one of the algorithms in their submitted document had to do with some sort of constraint on the number of bits that could be usefully processed, but if that's not the case, then that's fine.
(One reason for considering this is that the original SPHINCS was written a long time before SHA3 and therefore there would have been no obvious need for longe
Re: (Score:2)
What problem does SHA2 has for this use?
Re: (Score:2)
I don't know that it has for this use, but as Valerie Aurora pointed out in her scathing review of hash algorithms, that's not generally an acceptable line of reasoning. If there are any potential issues, then programmers tend to steer clear and what she refers to as Slashdotters (yes, us!) tend to sleepwalk into a crisis. The correct approach is to follow what she advocates for programmers, which is to always err on the side of caution and assume issues will get worse rapidly. We need to shake the image we
Re: (Score:2)
Are you referring to her comments on "compare by hash"? Because those simply demonstrate she has no clue what she is talking about and should never have been let anywhere near a kernel. I read them purely by accident a long time ago and having no idea who she was or what she was doing. And I was pretty shocked by the sheer level of arrogance and ineptitude expressed.
Re: (Score:2)
She's actually a very good programmer, her competence is extraordinary and your arrogance needs cutting down. Her views of Slashdotters are not unfounded.
Who cares? (Score:2)
Let's have QCs more powerful than my 30 year old programmable pocket calculator first. As things are going, that will require another 100 years or so.
Re: (Score:1)
Re: (Score:2)
Actually, it remains to be seen whether QCs able to tackle traditional cryptographic algorithms are feasible at all.
Indeed. But if they could get to what my old calculator can do, they might. Or not. If they cannot even get there (and they are very far removed from it), then we can forget about the whole thing.
Re: (Score:2)
Maybe so. But this line of thinking is entirely missing the possibility of a "store and decrypt later" attacker: /p>
It actually does not. The 2^64 effort for a QC to break, for example, AES128 is for a known-plaintext (!) attack. These only work in very limited contexts. 2^64 is not completely infeasible, but almost so. Now remember that they have to attack each key separately and that QCs are much, much, much slower than conventional computers as to operations per second. Hence for regular security needs, this attack is irrelevant. I really do not care if they could hijack my e-banking connection 10 years after it ended
Re: (Score:2)
Yes, possibly. Just that a Diffie-Hellman breaking QC will have to be massively larger than an AES breaking one. With a tech that scales like crap. And we currently have not even a tiny one that could break any cipher. Well, maybe they can do Rot13 by now.
Re: (Score:2)
And what leads you to this conclusion? There is no real discussion about QC being used to break AES (or other symmetric encryption), but there is plenty of discussion about how QC could be used (Shor's algorithm, for example) to break RSA and ECC. So how is it that YOU manage to know that a QC that can break RSA and ECC 'will have to be massively larger' than one used to break AES. Is it because you know nothing at all about the subject? Yep, I believe that is it.
Re: (Score:2)
There is no real discussion about QC being used to break AES (or other symmetric encryption),
That is because it is both trivial and useless. The effort for it is too high. You basically implement the cipher and brute force it and get quadratic speed-up. For factorization you get exponential speed-up on a QC and hence that gets discussed a lot.
Re: (Score:2)
Yep. Making it a few orders of magnitude _less_ feasible on the QC side. Also, this story is about the symmetric encryption and signatures. It is _not_ about public-key. That one is still ongoing. Seriously, there is no danger here. On the other hand, a cold, hard look at these new and "better" algorithms seems to be highly advisable. It seems some actual experts are not too impressed. Lets give it 5 to 10 years before we entrust anything to these algorithms.
Re: (Score:2)
You are completely, 100%, wrong. This story has NOTHING to do with symmetric encryption. Kyber is a Key Encapsulation Mechanism (KEM). It is NOT symmetric encryption. This is ENTIRELY about public key.
Re: (Score:2)
Actually, this is key creation. You may have missed the little part "There is still a final round for public key encryption algorithms." in the story.
Re: (Score:2)
Wrong again. It is not 'key creation', it is key encapsulation, as plainly stated in the first line of https://pq-crystals.org/kyber/ [pq-crystals.org]. The party with the public portion of the kyber key generates a random secret (RNG) and encrypts it with kyber. The party with the private portion decrypts the secret. If you are using only PQ stuff, the 'secret' can be the AES key itself. If you are using it in a hybrid mode, the 'secret' will be combined with the results of DH, then hashed to get the shared AES key.
In yo
Re: (Score:1)
"Key encapsulation" is not public key. It falls under the larger umbrella of "key creation". Well, I can see you are so desperate to be a know-it-all that you are not interested in facts anymore. Good luck with that.
Re: (Score:2)
Nope. Still wrong. OK, YOU are the one quoting the summary that "There is still a round for public key encryption algorithms". Are you still standing by that? Good. Now, what are the remaining candidates for 'public key encryption algorithms'? BIKE, Classic McEliece, HQC, and SIKE. So what do we know about those algorithms? Not too hard to find out, the summary itself has links to them.
BIKE - https://bikesuite.org/ [bikesuite.org] - "BIKE is a code-based key encapsulation mechanism based on QC-MDPC (Quasi-Cyclic M
Re: (Score:2)
Well, what can I say. I had crypto as elective on master level as a core subject and aced the exam, but that was 30 years ago. Yes, I missed that CRYSTALS-Kyber is actually the key exchange and not the symmetric encryption itself. I did not miss the comment "There is still a final round for public key encryption algorithms.".
My oversight is easily explained though: This is /. and I have basically stopped really looking at the post-quantum nonsense, because QCs that can solve real problems are pretty much a