crypto: post-quantum support roadmap

[rolandshoemaker]

With the publication of the NIST PQ drafts FIPS 203, FIPS 204, and FIPS 205 and the beginnings of industry adoption of said algorithms (i.e. https://blog.cloudflare.com/post-quantum-for-all/, https://blog.chromium.org/2023/08/protecting-chrome-traffic-with-hybrid.html, etc), we are starting to look at what post-quantum support will look like in Go.

This issue is not going to propose any specific APIs, and is instead meant to lay out the way we intend to approach decisions about what algorithms we will adopt, and the manner in which we will adopt them.

Generally, we are quite conservative about what cryptographic algorithms we choose to support. In part this is because we have a significant maintenance burden once we adopt an algorithm, but also because we want algorithms that are stable (i.e. unlikely to significantly change in the future), and are already being actively used in the wider ecosystem. There are many PQ algorithms which are still experimental, or have found no wider industry adoption as of yet, which do not meet the bar to be included in the standard library, and make more sense being implemented in third-party modules.

When thinking about what PQ algorithms we want to provide support for, the first hurdle is whether that algorithm will actually be used in the standard library itself. What I mean by this is that, at least to begin with, we don't want to introduce support for algorithms which we will not be using ourselves. This means that our choices of initial algorithms are extremely likely to be driven by the adoption decisions made for the TLS protocol (and by extension the X509 web PKI).

Additionally our initial implementations are likely to only be available internally, at least to begin with (i.e. they will not be implemented in public facing libraries which users can directly use). This gives us the opportunity to gain experience with these new algorithms before we commit ourselves to an API design that we'll likely be stuck with for a significant amount of time. Once we are confident that we fully understand the ways users are expected to handle (and mishandle) these APIs we'll propose public APIs.

What's First

The first step in our PQ implementation plan is adding support to the now widely implemented hybrid X25519/Kyber (X25519Kyber768) KEM for TLS, or a successor version, hopefully in Go 1.23. This will provide TLS client/server interoperability with the other public implementations, and provide deployment experience with this new KEM.

This feature will be transparent to users, providing no public Kyber API, and likely will be gated behind a GODEBUG option.

cc @FiloSottile

[gopherbot]

Change https://go.dev/cl/550215 mentions this issue: crypto/internal/mlkem768: new package

[3052]

call me naive, but is this really something that needs to be in the standard library? I know Filippo and others are really passionate about crypto, I get and respect that. but one thing I DON'T want to see with Go is that is become the next Python, with a giant standard library (if its not already that). we have to draw the line somewhere, and in this case the proposed package(s) seem clearly on the "do not add" side (to me).

I invite counter arguments, I dont mind being proven wrong here, but I DON'T think it should just be assumed that this needs to be in the standard library. post-quantum crypto is in its infancy as I understand it.

[FiloSottile]

@3052 post-quantum key exchanges are necessary as soon as possible to prevent collect-now-decrypt-later attacks. There is a concerted industry-wide push to migrate to PQ, and we believe it's important for Go applications to enable that.

We are starting with internal packages, and initially probably only ML-KEM actually, probably until the final NIST specifications are published.

If you want to know more about how the implementation is following the Cryptography Principles, you might find https://words.filippo.io/mlkem768/ interesting.

[DemiMarie]

@FiloSottile What about the Streamlined NTRU Prime algorithm used by OpenSSH?

[UladzimirTrehubenka]

Wondering why only crypto/internal/mlkem768 has been added, what is the reason to skip mlkem512 and mlkem1024 described in FIPS 203? Don't think that this "partial" implementation which leads to use third party libraries instead built-in is a good idea.

[thequailman]

Also, when will the mlkem768 implementation be ready for use/be exposed outside of internal?

[crrodriguez]

In contrast, I strongly encourage to continue been opinionated and implement whatever you think it is the best/faster/safer now and not everything under the sun. And make hard choices of sane defaults, never let that to the application.

[UladzimirTrehubenka]

not everything under the sun

Don't you think that implement for example only AES-192 w/o AES-128 and AES-256 is a good idea?
And this is the same: implement mlkem768 w/o mlkem512 and mlkem1024.

the best/faster/safer

BTW I have another conversation regarding fast sha3/mlkem/mldsa implementation - see the issue.

[ctgowrie]

Thanks for work on this @FiloSottile. Appears the first standards were recently finalized 🙌

[maddin200]

Go could be helpful see:
https://eprint.iacr.org/2022/337

[torntrousers]

@FiloSottile What about the Streamlined NTRU Prime algorithm used by OpenSSH?

Curious about this too?

[FiloSottile]

We have no plans to implement any other PQ KEM than ML-KEM. Note that OpenSSH 9.9 added a ML-KEM hybrid, and we plan to support that in x/crypto/ssh soon.

[torntrousers]

We have no plans to implement any other PQ KEM than ML-KEM. Note that OpenSSH 9.9 added a ML-KEM hybrid, and we plan to support that in x/crypto/ssh soon.

@FiloSottile , by "soon" would that likely be Go1.24 which i suppose is around Feb 25?

[derekparker]

Hey, I wanted to just ping this thread on if there is an ETA for FIPS 204 and 205 as well, seeing as to how 203 is implemented.

[FiloSottile]

Signatures are lower on our priority list because they are not vulnerable to store-now-decrypt-later attacks and because it’s not as clear how and which to deploy, because none of the available ones are drop in replacements for every setting.

We plan to start with SLH-DSA (FIPS 205) because it is clearly optimal for some use cases: long-term conservative settings where small public keys are desirable and/or long signatures are acceptable, such as firmware signing. It will probably be implemented in Go 1.25 or Go 1.26.

It’s likely it will not be the only PQ signature we implement in the longer term, but we’ll decide also based on what ecosystems such as TLS and the WebPKI land on. (Note that NIST is running another competition for PQ signatures, too.)

[simo5]

I prefer SLH-DSA for document signing (including software/firmware) but currently CNSA 2.0 only lists ML-DSA among the algorithms I consider acceptable (stateful signatures is not something that should ever be implemented in software) for software/firmware signing.

Would be nice to see ML-DSA prioritized as well in case SLH-DSA does not get added to the list of valid algorithms as the clock is ticking. According to CNSA 2.0 software needs to be signed with PQ algorithms starting in 2025 ...

[torntrousers]

I'm super interested in something for firmware signing such as FIPS 205, so thats good news. Also still keen to know if ML-KEM will possibly be in Go1.24, can you give any hints @FiloSottile ?

[FiloSottile]

About ML-KEM, #70122 is the proposal for the public package, which we hope to land in Go 1.24, as well as crypto/tls support per #69985. x/crypto/ssh is not in the standard library, so it doesn't follow the release cycle and we have no precise ETA for ML-KEM support, but it should be available by the Go 1.24 release at the latest.

[FiloSottile]

Would be nice to see ML-DSA prioritized as well in case SLH-DSA does not get added to the list of valid algorithms as the clock is ticking. According to CNSA 2.0 software needs to be signed with PQ algorithms starting in 2025 ...

I'm afraid there's no chance we'll be able to add ML-DSA in Go 1.24, so we are definitely going to miss a 2025 deadline. Sounds like CNSA 2.0 is forcing some unfortunate choices here.

[DemiMarie]

Would be nice to see ML-DSA prioritized as well in case SLH-DSA does not get added to the list of valid algorithms as the clock is ticking. According to CNSA 2.0 software needs to be signed with PQ algorithms starting in 2025 ...

I'm afraid there's no chance we'll be able to add ML-DSA in Go 1.24, so we are definitely going to miss a 2025 deadline. Sounds like CNSA 2.0 is forcing some unfortunate choices here.

If CNSA is “Commercial National Security Algorithm”, wouldn’t those who need to use CNSA also likely need to use HSMs for code signing?

[simo5]

Would be nice to see ML-DSA prioritized as well in case SLH-DSA does not get added to the list of valid algorithms as the clock is ticking. According to CNSA 2.0 software needs to be signed with PQ algorithms starting in 2025 ...

I'm afraid there's no chance we'll be able to add ML-DSA in Go 1.24, so we are definitely going to miss a 2025 deadline. Sounds like CNSA 2.0 is forcing some unfortunate choices here.

If CNSA is “Commercial National Security Algorithm”, wouldn’t those who need to use CNSA also likely need to use HSMs for code signing?

You still need to verify the signatures, even if you use an HSM to generate them.

[Muzosh]

Happy New Year!

I stumbled upon this issue when I tried to PQ-ize (i.e. implement support for PQ algorithms) in several Go-written applications. Cloudflare's CIRCL is a wonderful library to do that.

However, most of these applications also use Go's standard x509 package, where pre-quantum algorithms are heavily hard-coded. I also found this phenomena in many other languages and libraries. That pushed me towards another question: why there is basically zero crypto-agility? Is it intended?

What are the arguments against having some "crypto-provider" mechanism/framework in everything that deals with cryptography?

Coming back to Go, if I want to parse DER-encoded x509 certificate signed with ML-DSA, I can either:

A) make a fork of Go and implement PQ crypto directly in x509 package myself

• which I don't want to maintain and keep updated with the upstream in order to just PQ-ize few apps

B) if an app encounters PQ algo, make a switch statement and direct the code into a place where I don't use Go's x509 package to parse a certificate

• do I have to develop this x509-package-alternative myself?
• if there is something available, is it compatible with x509.Certificate so I can use it for the rest of the app runtime?
• is it worth it if Go will eventually have capabilities to process ML-DSA certificates some time in the future?

C) implement crypto-provider-like structure/interface for Go so it use it for the current runtime in x509 package and parse my certificate

• this is currently not an option and my question is why?
• maybe something like Java's crypto providers? or re-use PKCS#11 but with SW?

Feel free to let me know this is a bad idea. Right now I can't think of any arguments against this.

[rolandshoemaker]

@Muzosh the answer to the implementation portion of your question is highly dependent on what you want to do. crypto/x509 will happily parse certificates that have unknown signature schemes or public key types, but all of the builtin verification methods etc obviously wont work (and this goes for all of the other packages which integrate with crypto/x509, like crypto/tls, etc.)

If you are just using crypto/x509 directly, you can implement the verification logic yourself (although I'd probably recommend against doing this, unless the certificate chains you plan on verifying are extremely simple) on top of certificates that use the PQ scheme you choose.

As for the philosophical portion of the question. For crypto/x509 in particular, we target the web PKI for compatibility, and since there are as of yet no standardized PQ signature schemes for X.509 that have been adopted, we have no plans to implement support. Once that changes, so will our support targets.

For pluggable crypto backends, this is something we are generally opposed to (there have been numerous discussions of this in the past.) While it offers a compelling feature for developers who wish to experiment, it requires an extremely complex implementation under the hood, and creates what can be a very painful support story (Java crypto providers are an example I'd actually provide of being extremely complex, requiring significant development overhead to support, and holding back the core implementations that the vast majority of people actually use.)

[Muzosh]

@rolandshoemaker Thank you for very insightful answer!

Implementation

The implementation portion is clear to me now. I already had some solutions in mind how to approach PQC implementation experiments. Your solution for x509 was added to the list. My next task is to select the one that has the least amount of "extra" work and will be easy to switch once the native support for PQC comes.

x509 package

When thinking about philosophical part (next subsection), I went back to this paragraph you wrote:

If you are just using crypto/x509 directly, you can implement the verification logic yourself (although I'd probably recommend against doing this, unless the certificate chains you plan on verifying are extremely simple) on top of certificates that use the PQ scheme you choose.

That got me to the question: why isn't there interface crypto.Verifier with a method Verify() same as there is crypto.Signer with Sign()? Wouldn't it be a little bit friendly towards crypto-agility without increasing much complexity?

For example, func checkSignature(algo SignatureAlgorithm, signed, signature []byte, publicKey crypto.PublicKey, allowSHA1 bool) (err error) in x509.go wouldn't require to have a hard-coded switch statement, but just call this new method, right? Am I missing something?

Philosophical part

I'm happy with the answer I got for the philosophical part. I wasn't aware of the complex crypto-provider implementation.

I have a follow up question: Would a language-independent, well-thoughtout, perfected-to-simplicity, crypto-agile defined API for crypto-providers solve something?

• I.e. developers would encounter exactly same structures/classes with same functionalitites when working with crypto libraries and they would be required to supply
• They don't have to implement those structures themselves, they could choose from pre-defined set (but they would have an option to extend that set)
• These structures and functionalities would "look" the same in every language.
• For example, wouldn't it be nice if exactly every language had something like crypto.Signer interface and every crypto operation accepted that interface?

P.s.: I know it's a big thing to ask the world for, probably impossible. I'm just extending the philosophical discussion.