13 ms·
NIST announces first PQC algoritms to be standardized
- isido 4y agoA link to the report: https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413.pdf https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413.pdf
- dsp 4y agoObligatory djb warnings: https://ntruprime.cr.yp.to/warnings.html https://ntruprime.cr.yp.to/warnings.html
- deleted 4y ago[deleted]
- 0des 4y agoshould really be higher up.
- bawolff 4y agoIsn't that the point of having "hybrid" mode?
- api 4y agoHMAC(pqc_shared_secret, ecc_shared_secret)
- mixedmath 4y agoWhat does "djb" mean here?
- Retr0id 4y agohttps://en.wikipedia.org/wiki/Daniel_J._Bernstein https://en.wikipedia.org/wiki/Daniel_J._Bernstein
- forty 4y agoWhat's the "obligatory djb warnings"? Something like "any crypto that's not mine isn't great"? ;)
- sterlind 4y agofrom 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.
- markschultz 4y agoCyclotomic polynomials are incredibly standard in the field. The only researcher I know of who has issues with them is DJB, and there has not been significant advances in cryptanalysis due to usage of cyclotomics (with the exception of problems not used by NIST candidates, meaning the whole SOLIQUAY thing)
- forty 4y agoMy understanding is that he worked on NTRU Prime, which would have somehow benefited from NTRU being choosen.
- mti 4y agoNTRU also relies on cyclotomic rings, so if distrust in cyclotomics was a good reason to reject Kyber, it would apply to NTRU too.
- code_biologist 4y agoHere's the warning: Lattice-based cryptography is much more risky than commonly acknowledged. This applies, in particular, to lattice KEMs under consideration within the NIST Post-Quantum Cryptography Standardization Project (NISTPQC) as of October 2021. The above document... There's a linked PDF paper with more detail.
- kzrdude 4y agoIs djb involved in any of the standardized algorithms here by the way?
- markschultz 4y agoYes, many. I believe he's on the SPHINCS+ team (was standardized), Classic McCliece (round 3, not standardized), and NTRU_PRIME (round 3, passed over for Kyber). Perhaps more, but he has significant skin in the game.
- chasil 4y agoOpenSSH has already chosen NTRU-Prime. Will there be a retrofit of CRYSTALS-KYBER? Or has the market already chosen? DJB is an author on the SPHINCS+ team; glad to see that his work will be part of the standard. https://sphincs.org/ https://sphincs.org/
- layer8 4y agoOpenSSH has merely chosen that as its current default. Surely multiple algorithms will be supported in the future as they have in the past.
- chasil 4y agoThere was considerable strife for Daniel J. Bernstein during this competition. https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwj6ivHQv-L4AhXxbDABHVUHByEQFnoECAYQAQ&url=https%3A%2F%2Fgroups.google.com%2Fa%2Flist.nist.gov%2Fgroup%2Fpqc-forum%2Fattach%2F6f5422d4f193d%2Fcomplaint-re-apon.pdf%3Fpart%3D0.0.1&usg=AOvVaw3UwJgXrLQb6wKLKEjBC_nX 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.
- google234123 4y agoBernstein seems to be involved in never ending drama. Maybe the problem is him?
- TedDoesntTalk 4y agoCan you summarize? That’s a PDF I can’t read.
- simcop2387 4y agoThere's some technical details that I'm not good enough to summarize, but a large gist of it seems to be that the NISTPQC seems to have gone back on it's word about being transparent through the standardization process and only ever solicited private input after round 2 and round 3 and used that non-published input to make claims about the strength of at least one contender for the standardization. And the way they've done this appears to reek of Dual EC style manipulation again from what DJB brings up? at least as far as how the process is working. I don't believe he's claiming that there's any NSA back doors but alluding to there being a private party that is steering things in ways that might not be good. Along with also apparently some possible remarks about DJB doing something wrong also (I couldn't tell from this at least what it was. I haven't done any complete readings yet).
- chrispeel 4y agoCrystals-Kyber website: https://pq-crystals.org/kyber/ https://pq-crystals.org/kyber/ Press release: https://techxplore.com/news/2022-07-nist-quantum-resistant-cryptographic-algorithms.html https://techxplore.com/news/2022-07-nist-quantum-resistant-c... Github: https://github.com/pq-crystals/kyber https://github.com/pq-crystals/kyber
- bwesterb 4y agoAnd a Go implementation I wrote for Cloudflare. https://github.com/cloudflare/circl/tree/main/kem/kyber https://github.com/cloudflare/circl/tree/main/kem/kyber
- elromulous 4y agoPQC = post quantum cryptography
- haggy 4y agoAh thank you. I figured the 'Q' stood for quantum but you saved me a fair amount of googling :)
- capableweb 4y ago"fair amount of googling"? Not sure what browser you use, but in most you can select what you wanna search for, click "Search on $searchEngine for $term" and there you go! For PQC, I get Wikipedia link with "PQC can refer to: Post-quantum cryptography" in the description as the 3rd result on Google. Not sure what classifies as "fair amount", but for me it took about 1-2 seconds to find the Wikipedia link ;)
- johndough 4y agoI agree that it is not a lot of work for a single person, but if you add it up over 100,000 readers (just a ballpark guess, I am sure dang can tell us exact numbers), it sums up to at least 2 days of cumulative wasted time, assuming that everyone looked it up. Obviously, not everyone will look it up because of laziness or indifference, but those readers will not understand what the title is about, which is not an ideal situation either. A similar situation arises with trains, where it is often better to not hold open the door for someone who is late by a few seconds, as the cumulative delay for everyone else in the train exceeds the waiting period of the single person for the next train.
- cpeterso 4y agoLooks like the name “CRYSTALS-KYBER” is a Star Wars reference (kyber crystals). At least one of the authors of CRYSTALS-KYBER (Peter Schwabe) published an earlier PQC algorithm called “NewHope”, another Star Wars reference. And “CRYSTALS-DILITHIUM” is, obviously, a Star Trek reference. :)
- ENOTTY 4y agoWhat's up with this? > In addition, NIST has engaged with third parties that own various patents directed to cryptography, and NIST acknowledges cooperation of ISARA, Philippe Gaborit, Carlos Aguilar Melchor, the laboratory XLIM, the French National Center for Scientific Research (CNRS), the University of Limoges, and Dr. Jintai Ding. NIST and these third parties are finalizing agreements such that the patents owned by the third parties will not be asserted against implementers (or end-users) of a standard for the selected cryptographic algorithm and > NIST expects to execute the various agreements prior to publishing the standard. If the agreements are not executed by the end of 2022, NIST may consider selecting NTRU instead of KYBER. NTRU was proposed in 1996, and U.S. patents were dedicated to the public in 2007.
- hn_throwaway_99 4y agoNIST is going the proper route to ensure that any standards they publish can be freely implemented without implementers having to pay patent royalties. That's the reason for your second quote - if KYBER patent holders don't want to agree, they should know that NIST won't choose them for the standard.
- nullc 4y agoJust to clarify: My understanding is that the authors of Kyber aren't the patent holders in question-- rather a third party has patents which may read on Kyber and several other of the NIST finalists. It's really unfortunate the the licensing terms weren't announced at the same time: Depending on how they're written the result may still be unattractive to use, and since they've already announced the selection NIST probably just lost some amount of negotiating leverage. (As the obvious negotiation would be "agree to these terms we find reasonable, or we just select NTRU prime")
- rdpintqogeogsaa 4y agoKey part here is "are finalizing". It's still possible for at least some of the deals to fall through. I guess NTRU is the backup plan just in case and/or a method to apply pressure by saying the public is now aware there's a plan B. I exüect this passage to imply at least one negotiation has been going poorly. It would probably be interesting to look up who of these people also has patents outside of the USA. If there really is someone being particularly stubborn, one might reasonably expect them to enforce the non-US patent variant outside of the USA.
- jjice 4y agoBeen waiting on this announcement for a while. As someone who took a crypto class in college, but isn't a crypto expert (just knows the basics and basic theory), this is very neat to see. I'm looking forward to never implementing it myself :)
- RcouF1uZ4gsC 4y agoHN Crypto and Quantum Experts. What is your prediction when classical public key encryption using elliptical curve cryptographic becomes practically vulnerable to quantum computers, such that we would need these PQC algorithms. 10 years out? 20 years out? 50 years out? 100 years out?
- hannob 4y agoI'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 possibility that they're too big to overcome.
- chasil 4y agoThis 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-is-coming-sooner-than-we-think/?sh=1a7676f83f5d https://www.forbes.com/sites/arthurherman/2021/06/07/q-day-i...
- latenightcoding 4y agoQuantum Annealing is not a threat for cryptography. You can safely dismiss these sort of articles.
- krastanov 4y agoTo 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.
- Asraelite 4y ago
- sbf501 4y agoWaiting for the ELI5 sites to explain Kyber and LWE. :)
- markschultz 4y agoI wrote up an introduction to a (severely unoptimized for pedagogical purposes) version of FrodoKEM https://mark-schultz.github.io/nist-standard-out/ 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.
- sbf501 4y agoThanks 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!
- markschultz 4y agoThanks for the feedback! Roughly speaking, that all has to do with making e vanish later, so perhaps I need to revisit that section. Quickly (cause I probably won't for a few days), (q//2)m can be seen as a form of error correction. You can check (either pen+paper or programmatically) that, provided |e| < q/4, if noisy_m = (q//2) m + e, then round(noisy_m / (q/4)) = m. So e vanishes because it is bounded (not uniform), + we encode m as (q//2)*m (i.e. in the "most significant bits" of the number).
- baby 4y agoI wrote a chapter containing explanations on these here: https://livebook.manning.com/book/real-world-cryptography/chapter-14/70 https://livebook.manning.com/book/real-world-cryptography/ch...
- forty 4y agoCoincidentally, we have just published this today, if you want to play with PQ crypto in JavaScript https://github.com/Dashlane/pqc.js https://github.com/Dashlane/pqc.js
- buu700 4y agoSimilarly, I just published this a few days ago: https://github.com/cyph/pqcrypto.js 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!)
- forty 4y agoApparently yes! I'm told we did use your other older project ntru.js as mentioned in the readme :) thanks for sharing your code!
- oconnore 4y ago> Additionally, SPHINCS+ will be standardized to avoid only relying on the security of lattices for signatures > Both BIKE and HQC are based on structured codes, and either would be suitable as a general-purpose KEM that is not based on lattices What's up with this caveat? Why would the standard require algorithms not based on lattices assuming there is confidence in the lattice based approach? Is this a security concern, or is there some performance (ops/sec or size) related trade-off?
- latenightcoding 4y agoSome people believe you can generalize Shor's algorithm to attack lattice-based cryptography.
- bawolff 4y agoPresumably 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
- oconnore 4y agoIf 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.
- kickling 4y agoWell, most modern cryptography is based on assumptions that can not be proven, so having different standards based on different assumptions is probably the only way to safeguard against if one of the assumptions would be proven false in the future.
- bawolff 4y agoTo 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)
- kragen 4y agoPresumably since Dual_EC_DRBG it is counterproductive to rely on NIST's recommendations for secure cryptography. What should we rely on instead?
- bioemerl 4y agoSomething that worries me, if someone cracks our current encryption using quantum computers couldn't they be logging everything we say right now and everything we say right now is actually unsecure to someone 10 years in the future?
- tptacek 4y agoYes. That's, for instance, why people say the KEM problem has more urgency than the signature problem; a PQC KEM is what you need today if you're worried that someone's archiving your TLS sessions so they can break them with the quantum computer their government promised them for Christmas in 2034. Even if your KEX involves a signature, your adversary can't time-travel back to 2022 to break it with their 2034 scooty-puff quantum edition. But if all you've got is classical ECC and RSA, you're in trouble. If you assume the PQC KEM doesn't interact with classical ECDH, you might want to get some kind of PQC KEM rolled out as quickly as you can, in a dual construction with ECDH; the worst that happens is, your new KEM isn't quantum-safe (or anything-safe), but your ECDH holds up. But that's (if you believe in quantum attacks on crypto) still better than no PQC KEM at all.
- snapetom 4y agoYes. This is why the work is being done now, and there will be an urgency in moving PQC algorithms from academia to commercial use. Everything that has been stolen in data breaches up until then will be broken once QC are viable. Good news is that we are likely more than 10 years away from QCs being useful enough to do this.
- baby 4y agoShameless plug: I wrote about all these schemes in Chapter 14 on post-quantum cryptography of Real-World Cryptography https://www.manning.com/books/real-world-cryptography?a_aid=Realworldcrypto&a_bid=ad500e09 https://www.manning.com/books/real-world-cryptography?a_aid=... These are meant as a gentle introduction to the ideas and intuitions behind the schemes. The book is recent but some of that stuff (hash-based signatures) I started writing back in 2015 and is available on my blog: https://cryptologie.net/article/306/one-time-signatures/ https://cryptologie.net/article/306/one-time-signatures/ At the time the schemes had not yet been chosen, fortunately I picked the right ones :) don't have to rewrite that chapter (yet).
- carride 4y agoSome news analysis https://news.ycombinator.com/item?id=31997362 https://news.ycombinator.com/item?id=31997362