1. Introduction

Imagine a world where a hacker forge any trustchain in your OpenID Federation ecosystem, and thus make any malicious entity appear legitimately trusted. This is the threat of quantum computing. A cryptographically relevant quantum computer (CRQC) does not yet exist, but a lot of progress is being made. We don't know for sure when the first CRQC will be built, but it is wise to make our ecosystem quantum-resilient as soon as possible

In this document, we describe the road towards a post-quantum OpenID Federation Ecosystem:

We give some background on cryptography and the impact of quantum computers in Section 2.
We provide an overview of cryptography currently used in OpenID Federation in Section 3.
We assess the impact of quantum computing on OpenID Federation in Section 4.
In Section 5, we give an overview of post-quantum cryptographic algorithms that are relevant for OpenID Federation.
...

2. Background

Signatures can be used to cryptographically proof authenticity of a message. For example, Alice might create a signature of her message M called S using a secret key K. When Bob receives message M, he can verify that the message came from Alice by checking signature S with secret key K. Eve, wanting to forge a malicious message M', can not do so if she does possess secret key K.

Encryption can be used to provide confidentiality of a message. For example, Alice might encrypt her message M into ciphertext C using a secret key K. When Bob receives ciphertext C, he can decrypt the ciphertext back to message M using secret key K. Eve, who eavesdrops, sees ciphertext C but does not have the secret key K, can not decrypt ciphertext C and can thus not read the message M.

We can distinguish between asymmetric (public key) cryptography and symmetric (secret key) cryptography. Symmetric cryptography uses 1 key to both encrypt and decrypt, or sign and verify a message. Our examples above use symmetric cryptography, as there is only one key K. Asymmetric cryptography uses two keys: a public key (which, as the name implies, is public and can be read by anyone) and a private key. This has some benefits over secret key cryptography: for example, if Alice signs a message M with her private key a, then anyone can verify signature S with Alice's public key A, including Bob (and Eve). Moreover, Bob can send an encrypted message to Alice by encrypting M with Alice's public key A into ciphertext C. Now, only Alice who has her private key a can decrypt Bob's message.

A Cryptographically Relevant Quantum Computer (CRQC) is a quantum computing system powerful enough to break modern cryptographic algorithms that secure digital communications¹. This is possible because a CRQC allows us to run fundamentally different algorithms from traditional computing. The two main algorithms are Shor's algorithm and Grover's algorithm.

Shor's algorithm allows an attacker to efficiently compute integer factorization and the discrete logarithm problem. This pretty much breaks all traditional asymmetric cryptography (encryption and signatures) like RSA and ECDSA.

Grover's algorithm provides a large speed up to attacks against symmetric cryptography, but this can easily be mitigated by doubling the minimum allowed key size.

To summarize: symmetric cryptography like AES and hashing is pretty much safe from quantum computers, but asymmetric cryptography like RSA has to change dramatically. This is where post-quantum cryptography comes in: new asymmetric cryptographic algorithms that are safe against the threat of a CRQC. We discuss two main post-quantum cryptographic algorithms in the next section.

It is still very hard to predict when, if ever, a CRQC will exist. Quantum computing is however making significant progress in recent years. Because of this, Google and Cloudflare are setting 2029 as their deadline for their post-quantum cryptography migration²³. The EU sets the deadline later:

For high-risk use cases, quantum-vulnerable public-key mechanisms shall not be used stand-alone after the end of 2030, analogously after the end of 2035 for medium-risk use cases.⁴

High-risk use cases are mainly defined by the risk of store-now-decrypt-later attacks⁵. With these attacks, adversaries store large amounts of encrypted data and decrypt it years later when they obtain a CRQC. We estimate that the OpenID Federation ecosystem is a medium-risk use case, as this does not process encrypted confidential data that needs to remain confidential for more than 10 years.

3. Post-Quantum Cryptographic Algorithms

There are two main post-quantum cryptographic algorithms that were standardized by NIST: ML-KEM⁶ and ML-DSA⁷.

ML-KEM is a key encapsulation mechanism. It's main purpose is for two parties to agree on a symmetric key, which then can be used for encryption. The security of this KEM is based on the Module Learning With Errors (MLWE) problem, a problem. This is deemed to be secure even against adversaries with a CRQC.

ML-DSA is a digital signature algorithm. This algorithm allows parties to generate quantum-secure asymmetric signatures. It is also based on the Module Learning With Errors (MLWE) problem, but also the Module Short Integer Solution (MSIS).

While there exist no know attacks against ML-KEM and ML-DSA, the cryptographic schemes are still relatively immature compared to traditional algorithms like RSA or ECDSA. One could argue that this makes it risky to fully transition to them: new attacks might still be found in the future. That is why the EU recommends the use of hybrid schemes⁴: combinations of post-quantum schemes like ML-DSA and traditional schemes like ECDSA. The idea is that an attacker needs to break both schemes to break the hybrid scheme. Because e.g. ECDSA signatures are significantly smaller than ML-DSA signatures, you can relatively cheaply them in the mix. Hybrid schemes are also known as PQ/T (post-quantum/traditional).

4. Current Cryptography in the OpenID Federation Ecosystem

In our analysis, we found two main uses of cryptography in the OpenID Federation Ecosystem: JWS and JWE. Of these two, JWS is the only critical component.

JWS, JSON Web Signatures, are the main cryptographic component of OpenID Federation. It is used to verify trust chains and trust marks. JWS supports multiple algorithms, for OpenID Federation most common is RS256, which is based on RSA, but elliptic curve signature schemes like ES256 are also often supported.

JWE, JSON Web Encryption, is used in OpenID Federation to support encrypted request objects. It is not mandatory to encrypt request objects, so this is not really an essential part of the protocol. JWE also supports multiple algorithms.

Note that TLS is not required for OpenID Federation to be secure. If you still want to add post-quantum TLS, this can already easily be handled by reverse proxies today.

5. Impact of Quantum Computing on OpenID Federation

List JWS algorithms broken by quantum computing

List impact of signature forgery in OIDfed

What is the impact of a single entity in the trust chain not supporting a post-quantum algorithm?

Impact of signature forgery in OIDfed:

You can forge a trust chain and join a federation
You can forge ID tokens in OIDC in the implicit flow and impersonate other users or elevate privileges

6. Migration Strategies

I think you can just add the post-quantum algorithms as supported algorithms in id_token_signing_alg_values_supported in metadata at first.

Then deprecate classical signatures when the ecosystem supports it or the

7. Required Changes in the OpenID Federation Ecosystem

post-quantum signatures, JWS: https://datatracker.ietf.org/doc/rfc9964/ proposed standard

More mature hybrid signatures: https://datatracker.ietf.org/doc/draft-ietf-lamps-pq-composite-sigs/, but not tailored to JWS

Hybrid encryption: same idea, https://datatracker.ietf.org/doc/draft-ietf-jose-hpke-pq-pqt/01/, still subject to change.

Implement ML-DSA or hybrid schemes in JWT libraries used. There often already are libraries that implement ML-DSA, just not always for JWTs yet, so should not be too difficult.

Might be able to make a bridge to the go library? https://github.com/jwx-go/compsig or maybe some c library? not sure how negatively that affects performance

Then, add support for the new JWS algorithms in OIDfed implementations (lighthouse, shib, SSP, etc.)

Send update recommendation to NRENs when implementation supports post-quantum signatures. TODO: how do we know which NREN uses a specific OIDfed implementation?

Language	Implementations	PQ hybrid JWT	PQ JWT	PQ	Comment
Go	go-oidfed lighthouse, offa	https://github.com/jwx-go/compsig	https://github.com/lestrrat-go/jwx	-	Gabriel has update library
Rust	SUNET inmor	None?	https://github.com/MKSinghDev/pq-jwt-rust Could expand on https://github.com/hidekatsu-izuno/josekit-rs (used by Inmor)	RustCrypto: never audited, https://github.com/RustCrypto/signatures/tree/master/ml-dsa C bindings? https://github.com/rustpq/pqcrypto
Java	Shibboleth OIDC and OIDFed Plugin, Keycloak	None?	None, could expand on https://bitbucket.org/connect2id/nimbus-jose-jwt/src/master/ (used by Shib) Keycloak uses own JWT implementation: https://github.com/keycloak/keycloak/tree/main/core/src/main/java/org/keycloak/jose	Java 24+: native, https://openjdk.org/jeps/497 Java 17+: Bouncy Castle 1.79+: https://www.bouncycastle.org/resources/latest-nist-pqc-standards-and-more-bouncy-castle-java-1-79/
PHP	SSP OIDC and OIDFed module	None?	None, could expand on https://github.com/lcobucci/jwt (used by SSP)	PHP (non-audited): https://github.com/paragonie/pqcrypto_compat RustCrypto bindings (non-audited): https://github.com/paragonie/ext-pqcrypto
Python	Satosa	None?	https://github.com/eduardogiraudi/pqjwt/blob/master/python/pqjwt/README.md Could expand on https://github.com/IdentityPython/pyjwkest (used by Satosa), currently unmaintained	cryptography: https://cryptography.io/en/latest/hazmat/primitives/asymmetric/mldsa/

8. Interoperability Considerations

You can still support both post-quantum and classical signatures in the foreseeable future.

What about SAML?

9. Challenges and Risks

ML-DSA signatures are significantly larger (in 2kb range) What is the impact of this?

10. Recommendations

11. Roadmap for Migration

11.1. go-oidfed

go-oidfed - including LightHouse and OFFA - has added support for new signing algorithms including post quantum and hybrid algorithms. The following algorithms are now supported:

ECDSA