[HN Gopher] NIST announces first PQC algoritms to be standardized
___________________________________________________________________
NIST announces first PQC algoritms to be standardized
Author : isido
Score : 128 points
Date : 2022-07-05 16:25 UTC (6 hours ago)
(HTM) web link (groups.google.com)
(TXT) w3m dump (groups.google.com)
| RcouF1uZ4gsC wrote:
| HN 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?
| ghaff wrote:
| It's worth noting that the relevant timeframe to implement PQC
| isn't just when quantum computers become sufficiently fast to
| break current crypto (assuming the answer isn't never). It can
| take a decade or longer to re-encrypt data and/or to update
| cryptographic infrastructure.
|
| Given that (varied) expert option on quantum computing being
| able to break current public key cryptography seems to mostly
| fall in the 10-20 year range, there is some, at least mild,
| urgency to start using PQC for the most sensitive data
| relatively soon.
| NavinF wrote:
| "When will 256 bit ECC become insecure?" :
| https://www.metaculus.com/questions/8169/?invite=GpV2Dc
|
| The community prediction is 22% by 2032 which seems way too
| high IMO. I predict 5% due to advances in automated algorithm
| search and 0% due to quantum computers in that time frame.
| marcosdumay wrote:
| Why would a croudsoursing site know that? This is the kind of
| question where 1 expert will fare better than the average of
| 90% of the people.
| IncRnd wrote:
| I think what you are asking may better be answered by ignoring
| PQC and following CNSA recommendations for up to TOP SECRET.
| The crypto is likely what you already use, but it defines how
| to get enough bits of security from an algorithm.
|
| There is a table of transition algorithms on the second or
| third page, depending on your screen size. [1]
|
| [1] https://apps.nsa.gov/iaarchive/programs/iad-
| initiatives/cnsa...
| upofadown wrote:
| We have not been able to implement even a single logical qubit
| of the sort required to run Shor's algorithm (we would need
| thousands). It is impossible to extrapolate from zero.
| bawolff wrote:
| https://xkcd.com/678/
|
| Any predictions on these time scales are pretty much pointless.
| Asraelite wrote:
| I want to see these actually being implemented in current
| software ASAP (layered with traditional crypto). As-is it's
| possible to capture encrypted traffic out of the air, store it
| for however many decades are needed, and then decrypt it in
| future.
| danuker wrote:
| I expect you'd see a large increase in Bitcoin Days Destroyed,
| perhaps unrelated to market volume, should someone break ECDSA.
|
| Bitcoin uses ECDSA to validate whether coins were spent by the
| owner of an address.
|
| https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_...
| jleahy wrote:
| The modern wallets don't publish the public key though, so
| this is not likely to help.
| rvz wrote:
| Well good thing that some of the cryptographers that created
| Falcon [0][1] (the ones who developed Algorand) for post-
| quantum cryptography for digital signatures use cases is
| considered to be _' standardised'_ as such.
|
| This tells me that Algorand is one of the more serious
| blockchain projects out there with top cryptographers as
| evidenced by Falcon.
|
| [0] https://falcon-sign.info
|
| [1] https://github.com/algorand/falcon
| kvathupo wrote:
| Not an expert, but you should upgrade now to prevent attackers
| from stealing your encrypted data today, and decrypting it
| later. That said, you'll have to determine if your data is
| worth stealing.
| hannob wrote:
| 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 possibility that they're too
| big to overcome.
| chasil wrote:
| 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.
| ..
| latenightcoding wrote:
| Quantum Annealing is not a threat for cryptography. You can
| safely dismiss these sort of articles.
| krastanov wrote:
| 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.
| bwesterb wrote:
| It's hard to say. Here is a great paper that tries to answer
| this question.
|
| https://arxiv.org/pdf/2009.05045v1.pdf
|
| See Figure 11. Optimistically 15 years. Pessimistically 35
| years. But anything can happen.
| Zamicol wrote:
| The linked study is about RSA, not elliptical curve
| cryptography
| krastanov wrote:
| Does that matter? Both are based on some hidden subgroup
| problem and both are breakable in a similar way.
| upofadown wrote:
| It is generally accepted that elliptical curge cryptography
| is a bit easier to break with Shor's algorithm than RSA.
| Something like half as hard, but it probably would not make
| any real difference in practice. So the paper is directly
| applicable to elliptic curves to the extent that it is
| applicable to anything.
| adastra22 wrote:
| 10-20 years. As soon as we have atomically precise
| manufacturing, there are multiple approaches to making stable,
| scalable quantum computers that work. I see APM being possible
| on that time horizon. One company, Zyvex, has already
| prototyped those capability in the lab.
| jjice wrote:
| Been 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 :)
| isido wrote:
| A link to the report:
| https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413.pdf
| ENOTTY wrote:
| What'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 wrote:
| NIST 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 wrote:
| Just 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")
| formerly_proven wrote:
| Crypto that requires royalties won't be widely implemented, so
| you basically don't need to bother standardizing it.
| rdpintqogeogsaa wrote:
| Key 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 exuect 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.
| madars wrote:
| > If the agreements are not executed by the end of 2022, NIST
| may consider selecting NTRU instead of KYBER.
|
| It is especially interesting that NTRU (nor NTRU Prime, a
| different proposal) is _not_ advancing to the 4th round.
| Wouldn't you want to encourage more analysis for your (implied)
| runner-up?
| oconnore wrote:
| > 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 wrote:
| Some people believe you can generalize Shor's algorithm to
| attack lattice-based cryptography.
| bawolff wrote:
| 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
| hinkley wrote:
| Particularly sha-3 vs sha-512, which turned out to have
| issues.
| adastra22 wrote:
| SHA-512 doesn't have any issues.
| hinkley wrote:
| 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.
| adastra22 wrote:
| 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-Damgard
| 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.
| oconnore wrote:
| 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.
| Spooky23 wrote:
| 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.
| runjake wrote:
| They aren't publishing until 2024 at the earliest. This is
| just a head's up that they _will_ be publishing in the
| future.
|
| Presumably, they'll have a better idea by then.
| adastra22 wrote:
| Non-cryptographers should not be implementing NIST
| standards. You should be using higher level APIs written by
| cryptographers which do employ NIST standards in the
| details.
| kickling wrote:
| Well, 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 wrote:
| 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)
| adastra22 wrote:
| 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.
| bawolff wrote:
| 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)
| oconnore wrote:
| Maybe it safeguards them from looking like they've
| screwed this up, but in terms of providing a concrete
| recommendation to system implementers, how does this
| safeguard anything? How does offering multiple algorithms
| in the PQC category help me make systems safer? What am I
| actually supposed to do here (how do I reflect this hedge
| in a system design)?
|
| They didn't feel the need to provide multiple
| recommendations during the AES, or the SHA-3 process,
| even though Rijndael and Keccak used different
| constructions relative to RC6/TwoFish and SHA-2/Blake2.
| Why now?
| gdavisson wrote:
| The recommendations look clear to me: you should use
| CRYSTALS-Dilithium (unless you need smaller signatures,
| in which case use FALCON), but you should also be
| prepared to switch to SPHINCS+ on short notice if someone
| breaks CRYSTALS-Dilithium (or structured lattices in
| general).
|
| So best practice would seem to be to implement both
| CRYSTALS-Dilithium and SPHINCS+, set CRYSTALS-Dilithium
| as the default, and provide a switch (config setting,
| whatever) to switch to SPHINCS+. If you have long-term
| keys, you should have both forms set up & ready to use.
| bawolff wrote:
| > They didn't feel the need to provide multiple
| recommendations during the AES, or the SHA-3 process,
| even though Rijndael and Keccak used different
| constructions relative to RC6/TwoFish and SHA-2/Blake2.
| Why now?
|
| SHA-3 was explicitly alternative reccomendation. The
| entire point was to come up with something that was not
| based on sha-2, because they were worried that the
| attacks on md5/sha1 could be extended to sha2 (which
| didn't really happen the way people were worried about).
| Even to this day, general advice is not to use sha3.
|
| Less clear cut for aes, but at time of standardization
| (and even now afaik), triple des was considered secure,
| so its not like there wasn't a secure alternative.
|
| These standards arent meant as implementation guides. You
| still need cryptography knowledge to securely use them.
| bawolff wrote:
| 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.
| [deleted]
| Beldin wrote:
| 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.
| upofadown wrote:
| 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.
| kvathupo wrote:
| A point rendering the choice even more curious: Germany and the
| Netherlands have recommended the use of encryption not relying
| on the shortest vector problem [1]. The two suggestions of
| FrodoKEM (relying on hardness of the learning with errors
| problem) and Classic McEliece (relying on hardness of decoding
| random codes?) aren't lattice-based apparently.
|
| Perhaps NIST knows something we don't ; ^ )
|
| [1] - https://twitter.com/CJTjhai/status/1544398903591796736
| nullc wrote:
| The security story for lattices hasn't been very stable.
|
| Consider the graph in the Classic McEliece marketing materials,
| showing the exponent in the attack costs for lattice-based
| crypto:
|
| https://classic.mceliece.org/comparison.html
|
| Because of communication cost considerations the lattice
| candidates use problems small enough that another substantial
| improvement in attacks could leave them vulnerable (no shock
| that they use small problems: if you're really not
| communication cost constrained use McEliece and don't worry
| about it).
|
| If you do use lattice key agreement, be sure to use it in a
| hybrid configuration (combined with ECC like ed25519 or
| Curve448) to avoid the (small but hard to assess) risk that
| your security upgrade could actually be a security downgrade.
| elromulous wrote:
| PQC = post quantum cryptography
| haggy wrote:
| Ah thank you. I figured the 'Q' stood for quantum but you saved
| me a fair amount of googling :)
| capableweb wrote:
| "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 ;)
| chrispeel wrote:
| Crystals-Kyber website: https://pq-crystals.org/kyber/
|
| Press release: https://techxplore.com/news/2022-07-nist-quantum-
| resistant-c...
|
| Github: https://github.com/pq-crystals/kyber
| bwesterb wrote:
| And a Go implementation I wrote for Cloudflare.
| https://github.com/cloudflare/circl/tree/main/kem/kyber
| dsp wrote:
| Obligatory djb warnings: https://ntruprime.cr.yp.to/warnings.html
| code_biologist wrote:
| Here'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.
| 0des wrote:
| should really be higher up.
| kzrdude wrote:
| Is djb involved in any of the standardized algorithms here by
| the way?
| bawolff wrote:
| Isn't that the point of having "hybrid" mode?
| api wrote:
| HMAC(pqc_shared_secret, ecc_shared_secret)
| [deleted]
| mixedmath wrote:
| What does "djb" mean here?
| Retr0id wrote:
| https://en.wikipedia.org/wiki/Daniel_J._Bernstein
| forty wrote:
| What's the "obligatory djb warnings"? Something like "any
| crypto that's not mine isn't great"? ;)
| sterlind wrote:
| 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.
| markschultz wrote:
| Cyclotomic 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 wrote:
| My understanding is that he worked on NTRU Prime, which
| would have somehow benefited from NTRU being choosen.
| chasil wrote:
| OpenSSH 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/
| layer8 wrote:
| OpenSSH has merely chosen that as its current default. Surely
| multiple algorithms will be supported in the future as they
| have in the past.
| chasil wrote:
| 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.
| google234123 wrote:
| Bernstein seems to be involved in never ending drama. Maybe
| the problem is him?
| bwesterb wrote:
| NTRU-Prime, NTRU, Kyber and SABER are all great KEMs. NIST
| could've chosen any one of them. NIST never standardised
| Ed25519 and OpenSSH still uses it, which is perfectly fine.
| Zamicol wrote:
| Ed25519 is in the draft standard, as well as Ed25519ph: https
| ://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5-draft...
| CircleSpokes wrote:
| I imagine they would add support for the standardized
| algorithms and still support the ones they are currently using
| too.
| sbf501 wrote:
| Waiting for the ELI5 sites to explain Kyber and LWE. :)
| markschultz wrote:
| 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.
| sbf501 wrote:
| 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!
| forty wrote:
| Coincidentally, we have just published this today, if you want to
| play with PQ crypto in JavaScript
| https://github.com/Dashlane/pqc.js
| buu700 wrote:
| 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!)
| forty wrote:
| Apparently yes! I'm told we did use your other older project
| ntru.js as mentioned in the readme :) thanks for sharing your
| code!
___________________________________________________________________
(page generated 2022-07-05 23:00 UTC)