Towards Backward-Compatible Post-Quantum Certificate Authentication

We have blogged about post-quantum cryptography before. Quantum computers would pose a threat to PKI algorithms and systems that we know today. Cisco, with our academic collaborators, has been focusing on quantum-resistant hash-based signatures for a few years now with LMS and SPHINCS+ and more. NIST’s PQ Project is also working on standardizing quantum-resistant algorithms that will be used to protect against the cryptographic challenges quantum computers would introduce.

How would quantum-resistant signatures be used on the Internet today? A very common usecase is authentication. For example, TLS uses X.509 certificates to authenticate servers today with traditional signature algorithms like RSA and ECDSA. When a new post-quantum algorithm gets standardized, how would it be used in X.509 certificates? By swapping traditional signature algorithm OIDs with post-quantum ones in X.509 certificates, we would introduce backwards compatibility problems. Clients that have not been upgraded to support the new algorithms would not be able to authenticate and communicate with the server.

It is clear that we would want a smooth transition that supports traditional and post-quantum signatures in X.509 for a long time until post-quantum support was ubiquitous, if that even was ever possible. To address these concerns, with our collaborators from ISARA and Entrust Datacard, we propose three new extensions in X.509 that would allow traditional and quantum-resistant algorithms to co-exist in certificates (hybrid certificates) and be used depending on which algorithm the verifier supports. These extensions are agnostic to the post-quantum algorithms (crypto agility) in them and allow a smoother transition to a post-quantum hybrid certificates. An example hybrid cert looks like:

Now, how about protocols that use these certificates? TLS is a great example. We wanted to test how TLS would operate with hybrid certificates and post-quantum signatures. We also wanted to investigate how these certs would be provisioned by using the crypto agile EST protocol (RFC7030). To demonstrate these scenarios, we worked with our partners at ISARA to come up with working code which is demonstrated in a public server, test-pqpki.com. test-pqpki.com adds postquantum signature support in TLS 1.2 by defining new ciphersuites and using hybrid certificates. Even though initially only LMS signatures are supported, in the future the server will support different algorithms (i.e SPHINCS+, Crystals-Dilithium) based on the server port the client is connecting to. Readers can test that post-quantum hybrid X.509 certs are backwards compatible with TLS clients that do not support these algorithms by connecting to the server using TLS. They can also use the code provided in order to patch OpenSSL and test post-quantum signatures in both the TLS handshake and X.509 hybrid certificates for TLS authentication.  Additionally, the server supports EST enrollment in order to get new hybrid certificates. As this is a demo server, we intend to investigate some more practical issues and challenges with the use of post-quantum signatures, which are described in the next steps section.

We want the industry to be ready to use PQ algorithms as soon as they are standardized by NIST. We encourage readers to visit the server and use the code patches in order to test it and provide feedback. For more information, visit http://test-pqpki.com

We want to thank ISARA for the great partnership in researching a practical quantum safe crypto world.