If quantum computers were built, they would pose concerns for public key cryptography as we know it. Among other cryptographic techniques, they would jeopardize the use of PKI X.509 certificates (RSA, ECDSA) used today for authentication. To overcome the concern, new quantum secure signature schemes have been proposed in the literature and NIST's Post-Quantum (PQ) Crypto Project. Some will be standardized. Most of these schemes have significantly larger public key and/or signature sizes than the ones used today. There are concerns about the effect their size and processing cost would have on technologies using X.509 certificates today, like TLS and IKEv2. A recent publication provides an initial analysis of how these protocols would perform with PQ PKI certificates.
This page aims to investigate and demonstrate the viability of PQ hybrid X.509 certificates. A hybrid cert makes use of three non-critical extensions Subject-Alt-Public-Key-Info, Alt-Signature-Algorithm and Alt-Signature-Value that define the PQ public key and signature algorithms used in the cert. Below we can see example parts of a PQ cert that uses Leighton-Micali Signatures (LMS) and public key. A PQ hybrid cert can be verified traditionally (ignoring the extensions) by entities that cannot parse PQ algorithms. Entities that can make use of the PQ algorithms in the extensions will be able to verify the PQ key and signature in the certificate.
X.509 Certificate:
Data:
Version: 3 (0x2)
Serial Number: 4097 (0x1001)
Signature Algorithm: ecdsa-with-SHA256
Issuer: C=US, ST=NC, O=CISRA, CN=HSS-Hybrid-CACert-Test
[ ... omitted for brevity ... ]
Subject Public Key Info:
Public Key Algorithm: id-ecPublicKey
[ ... omitted for brevity ... ]
X509v3 extensions:
X509v3 Basic Constraints:
CA:FALSE
[ ... omitted for brevity ... ]
Alt-Signature-Algorithm:
hss-with-SHA512
Subject-Alt-Public-Key-Info:
Leighton-Micali Hierarchical Signature System
Public Key:
00:00:00:[ ... omitted for brevity ... ]
Winternitz Value: 8 (0x00000004)
Tree Height: 25 (0x00000009)
Alt-Signature-Value:
Signature:
04:82:07:90:[ ... omitted for brevity ... ]
Signature Algorithm: ecdsa-with-SHA256
30:45:02:21:[ ... omitted for brevity ... ]
This server listens on the ports used in the table below. It acts as a TLS 1.2 server that uses PQ certificates for authentication. In the TLS connection establishment it uses a new ciphersuite for the PQ signature algorithms. For example, when using LMS as the PQ signature algorithm the ciphersuite we define is ECDHE-HSS-WITH-AES-256-GCM-SHA384. It serves EST messages over TLS to enroll PQ certificates for entities that need a new PQ cert.
| Listening port | PQ Public Key and Signature algorithm used in Hybrid X.509 Certificates for TLS authentication and EST certificate enrollment. |
| 443 | Stateful LMS |
| 8443 | SPHINCS+ (coming later...) |
| 9443 | Other PQ signatures like CRYSTALS-DILITHIUM (coming later...) |
First let's download the root CA certificate that will be used by the client to authenticate the
server. The following command will retrieve the PQ hybrid public root certificate from the server.
Please note, in a web scenario, this root certificate will already be in your web browser's cert
store. But if you're using curl or openssl s_client as the TLS client, then you'll want to complete
this step to get a copy of the root certificate for the TLS connection.
cd ~
mkdir pqpki-poc
cd pqpki-poc
wget http://test-pqpki.com/<port#>-root.crt
You should verify the hash of this certificate to ensure it wasn't forged. The SHA-512 hash value for port 443 is
1cc979113cdf13f830980b4dc8693c3a76f7e0169e60ff59c93562e8f9b9d7d252b8e0c88eb5af8de3c85c786b69e8fe6c393
63aab3ff9f6ffd3797328e02fd6. Use command openssl sha512 ~/pqpki-poc/<port#>-root.crt to generate and verify the hash.
As mentioned above, the non-critical extensions in X.509 make these PQ certificates backward compatible with traditional entities that cannot use these algorithms. A traditional client would ignore these extensions and proceed to only verify the signatures in the traditional cert algorithms (ECDSA, RSA).
Use openssl or curl to ensure that clients that don't support PQ algorithms will still operate
by using the same certs. The following commands will connect to the test server by using the PQ hybrid root CA cert as their
root of trust.
openssl s_client -connect test-pqpki.com:<port#> -CAfile ~/pqpki-poc/<port#>-root.crt
curl https://test-pqpki.com:<port#> --cacert ~/pqpki-poc/<port#>-root.crt
Even though vanilla openssl and curl do not support PQ hybrid certificates, they were able
to transparently connect and authenticate the server by just using the "traditional" (non PQ) parts of the hybrid
CA root certificate. Note that the curl command returned a 400 Bad Request message because the server is not listening for that URI,
but the TLS handshake completed successfully.
Note that the openssl command could fail with stock OpenSSL in MacOS because it sometimes ships with old versions like 0.9.8.
First, we need to add PQ support to our client that we will test with. To do that, we provide a patched version of OpenSSL 1.0.2o. Then you install one more patch (test-pqpki-openssl.patch). Then you compile and install OpenSSL. It should be installed in a non-default location like /usr/local/. For convenience, that commands are
cd ~/pqpki-poc
git clone https://github.com/isaracorp/openssl.git -b test-pqpki-v1.0.0
git clone https://github.com/isaracorp/test-pqpki-patches.git
cd openssl
git apply ../test-pqpki-patches/v1.0.0/test-pqpki-openssl.patch
./config --prefix=/usr/local/pqpki-openssl1.0.2o --openssldir=/usr/local/pqpki-openssl1.0.2o shared && \
make && sudo make install
After patching OpenSSL, you can view the PQ hybrid CA certificate from Step 1 by using command
/usr/local/pqpki-openssl1.0.2o/bin/openssl x509 -engine qs_sig -in ~/pqpki-poc/<port#>-root.crt -text. The command will show
the hybrid X.509 extensions Alt-Signature-Algorithm, Subject-Alt-Public-Key-Info,
Alt-Signature-Value.
Now, connect to the server and show the hybrid certificate chain it provides
openssl s_client -connect test-pqpki.com:<port#> -showcerts.
If you view the cert details in the chain using the command in the previous paragraph, you will see
that the server and root cert (~/pqpki-poc/<port#>-root.crt) all include X.509 PQ extensions.
You will also see that the command was not able to
authenticate the server as we did not use the -CAfile option to provide a root of trust.
Now connect by trusting the root CA cert provided in Step 1:
/usr/local/pqpki-openssl1.0.2o/bin/openssl s_client -engine qs_sig -cipher ECDHE-HSS-AES256-GCM-SHA384 \
-connect test-pqpki.com:<port#> -CAfile ~/pqpki-poc/<port#>-root.crt
We can see that the client was able to authenticate the server by verifying the PQ signature on the cert and the PQ signatures in the TLS handshake.
Enrollment over Secure Transport (EST) is a certificate enrollment protocol that offers crypto agility and runs over HTTP over TLS.
We can use curl to pass HTTP messages over TLS to the EST server listening on port <port#>.
First we need a CSR for a PQ hybrid cert. You can download a PQ CSR request we have made available on the server with:
cd ~/pqpki-poc
wget http://test-pqpki.com/<port#>-pqpki.csr
You can view the CSR to see the PQ attributes in the CSR with /usr/local/pqpki-openssl1.0.2o/bin/openssl req -text -noout -verify -in ~/pqpki-poc/<port#>-pqpki.csr
Now, you can enroll the CSR and view the generated certificate with curl by using HTTP
basic authentication of the EST client. Please use the user ID of estuser and the password estpwd:
cd ~/pqpki-poc
curl https://test-pqpki.com:<port#>/.well-known/est/simpleenroll -u estuser:estpwd -s \
--cacert ~/pqpki-poc/<port#>-root.crt --data-binary @<port#>-pqpki.csr \
-H "Content-Type: application/pkcs10" --dump-header /tmp/resp.hdr -o /tmp/pqcert.pkcs7
The newly enrolled certificate is in the /tmp/pqcert.pkcs7 file. You can view the hybrid PQ certificate using
openssl base64 -d -in /tmp/pqcert.pkcs7 | openssl pkcs7 -inform DER -outform PEM -print_certs -out /tmp/pqcert.pem && /usr/local/pqpki-openssl1.0.2o/bin/openssl x509 -engine qs_sig -in /tmp/pqcert.pem -text.
Note that the above EST connection over TLS did not use PQ ciphersuites and authentication because curl was not patched to support it.
EST delivered the PQ certificate over TLS, but curl would need to be updated to support PQ TLS to declare the whole enrollment transaction PQ secure.
Also note that when enrolling the CSR on port 443, the certificate tree height is 15. The reason we chose that tree size by default was to reduce the key generation time. This key could sign only 215 messages.
Optionally, if we don't want to use curl (Step 4 above), we can enroll a PQ hybrid certificate with Enrollment over Secure Transport (EST) by using libEST. EST is a certificate enrollment protocol that offers crypto agility and runs over HTTP over TLS. libEST is an open-source implementation of EST.
First, we need to patch the open-source implementation of libEST. For convenience, the commands to install the patch are
cd ~/pqpki-poc
git clone https://github.com/cisco/libest.git -b rel-2.1.0
cd libest
git apply ../test-pqpki-patches/v1.0.0/test-pqpki-libest.patch
./configure --with-ssl-dir=/usr/local/pqpki-openssl1.0.2o && make
Then we can enroll a PQ hybrid certificate by using the EST server listening on this host by using HTTP
basic authentication of the EST client. Please use the user ID of estuser and the password estpwd.
The following commands generate an EST /simpleenroll operation and convert the newly issued cert to PEM format.
cd ~/pqpki-poc
export EST_OPENSSL_CACERT=<port#>-root.crt
export LD_LIBRARY_PATH=/usr/local/pqpki-openssl1.0.2o/lib/
./libest/example/client/estclient -v -e --common-name "Newly Enrolled PQ cert" -u estuser -h estpwd \
-s test-pqpki.com -p <port#> -o /tmp
After enrolling we can view the new certificate by using commands openssl base64 -d -in
/tmp/cert-0-0.pkcs7 | openssl pkcs7 -inform DER -outform PEM -print_certs -out /tmp/cert-0-0.pem &&
/usr/local/pqpki-openssl1.0.2o/bin/openssl x509 -engine qs_sig -in /tmp/cert-0-0.pem -text.
We can see that the enrolled cert is a PQ hybrid cert.
Note that when enrolling on port 443, the certificate tree height is 10. The reason we chose that tree size by default was to reduce the key generation time. This key could sign only 210 messages.
For stateful HBS signatures (port 443 on this server), reusing a private key could allow for a signature forgery. For the purpose of this demo, on the server listening on port 443 we are using a tree of height 25 for the root CA and the server public key. That means that the CA and the server can sign 225 certificates and TLS handshakes respectively. As this is a limited time demo server, we do not expect to run out of signatures for this server. The Winternitz parameter of the trees is 256 (W=8 in the LMS context) and the tree hash SHA256. For real world deployments the tree heights should be chosen carefully.
Additionally, for stateful HBS signatures (port 443 on this server) state needs to be managed carefully. In our reference implementation, the state is stored with the private key whenever a signature is created but before it is used. Thus, if there is a process crash during signing there's no way that a key is reused which could lead to forgery, unless the underlying filesystem does not sync the file changes immediately. The private key is also never copied, thereby preventing multiple copies of it. The private key gets updated with a call to OpenSSL's BIO_new_file followed by PEM_write_bio_PrivateKey. If the server crashes between or during these calls, the private key file could get corrupted. This can be mitigated by using a temporary key file. For real-world deployments, care must be taken to ensure that the private key is never reused or corrupted. Some techniques for proper state management are explained in ePrint Report 2016/357.
Hybrid post-quantum certificates are of decent size. The stateful HBS cert chain served over port 443 did not exceed 10KB, but depending on the postquantum algorithm used they could exceed 15KB which will add more packets and transmission time to the handshake. What is more, PQ algorithms are likely to be more computationally intensive that traditional algorithms which would burden the handshake as well. As explained in the Next Steps section, we plan to study the performance and the webpage's time-to-first byte to evaluate the impact of PQ certificates on web performance.
Finally, as it was correctly pointed out in IETF101, such certificates could exceed the 10MSS TCP congestion window in TCP Slow Start (initcwnd), which could lead to additional round-trips in order to transfer the certificate chain in TLS ServerHello message. Introducing more round trips for the ServerHello is an unwanted property for TLS. To alleviate that concern, we intend to study the options available as explained in the Next Steps section.
We intend to test various PQ signature algorithms. These include stateful HBS signatures, stateless and Lattice-based.
We also plan to investigate real-world parameters of a practical PKI with PQ cert chains of length equal to two or three with post-quantum OCSP responders/staples and Certificate Transparency logs.
This server has been deployed publicly to also allow us to test how middleboxes could behave with PQ certificate that they do not support yet. TLS 1.3 introduces encrypted certificates which would make this testing irrelevant, but for TLS 1.2 it would be worth to ensure that clients going through middleboxes are not affected by PQ certs.
We want to look into time-to-first byte for HTTP/2 pages that host external resources in order to see the impact of a more costly TLS handshakes, especially with certificates that may be exceeding the TCP Congestion Window while in Slow Start (initcwnd) as explained in the Caveats section.
Specifically for TLS, we plan to study alternatives discussed at IETF101 that could eliminate additional round-trips introduced by large certificates which exceed the initcwnd window (Caveats section). One such alternative could be to use new TLS extensions to negotiate and provide the PQ part of the certificate later in TLS handshake.