On July 5, 2022, NIST announced the first group of winners from its six-year competition.
| Type | PKE/KEM | Signature |
| Lattice | CRYSTALS-Kyber | CRYSTALS-DILITHIUM Falcon |
| Hash Based | SPHINCS+ |
The Quantum Threat to Cybersecurity
There are a number of risk vectors that malicious attackers can exploit. With cryptography being used ubiquitously in our systems, there are three areas that highlight the need for urgent action today:
• Harvest & Decrypt: communications can be harvested today and decrypted later using a large-scale quantum computer
• Roots of Trust: public keys based on classic cryptography which are embedded in long-lived devices (such as connected vehicles, critical infrastructure and military equipment) cannot be trusted to authenticate software updates after a large-scale quantum computer arrives
• Crypto Agility in PKI: organizations and governments rely on complex PKIs to support information and communication technology (ICT) systems that often require several years to a decade to migrate.
To determine the negative impact to your organization, you’ll need to consider the probability of attack for each particular area. This blog focuses on the impact to your PKI and options avaialable to your organisation.
Attacks on PKIs are much more cost effective for an attacker than harvest and decrypt. When deploying harvest and decrypt, the attacker must run Shor’s algorithm for each communication session, where the algorithm may need to be executed a number of times on a stream of sessions to fully obtain what is desired. After all that effort, an attacker receives past information, which depending on its type (i.e. state or military secrets) can be of significant value but not as a matter of course.
Now, when attacking a PKI system, only a single instance of Shor’s algorithm is needed. Note that the public key of the root certificate authority (CA) is known to everyone by design. Therefore, virtually no effort is required to obtain such a public key. With the public key of the root CA in hand, running Shor’s algorithm only once is enough to obtain the root CA’s private key. And once root CA’s private key is obtained, the attacker can produce just about any digital certificate for any entity, existing or new. Since certificate issuance is typically an off-line process, it is extremely difficult to detect the malicious issuance of a false or impersonating certificate. In essence, the attack is nearly undetectable while the root CA’s public key is trusted.
This is an incredibly powerful attack that can be perpetrated by adversaries with access to a large-scale quantum computer. This means that if the PKI is used for access control, the attacker can obtain access to any classified information. And if the PKI is used for financial transactions, the attacker can steal any amount of money since fraudulent transactions will appear to execute legitimately.
Migrating to Post Quantum PKI
Aside from the algorithm selection and standardization outlined above, there are significant additional concerns which organizations must take into account to plan a transition to a quantum-safe PKI.
- Duplicating the existing classical PKI with a parallel quantum-safe version is required in order to migrate organizations’ ICT systems and users. This is an incredibly expensive, resource intensive, and cumbersome (to users and administrators) proposition.
- With both a classical PKI and a quantum-safe PKI in place, transitioning users, systems and services in stages is logistically extremely challenging as legacy and upgraded systems must continue to interoperate.
a. Will systems need to be modified/replaced/duplicated to support backwards compatibility?
b. Will applications require updates/changes to support backwards compatibility? - Maintaining service levels for users, services and systems while minimizing downtime will be critical for this transition to be a success.
a. Can end users tolerate and correctly use multiple sets of certificates?
Taken as a whole, these concerns must be addressed, and their impact minimized for an orderly and efficient migration to quantum-safe cryptography to be possible. In other words, a solution that provides cryptographic agility, or crypto-agility, is required.
Options:
Hybrid Certificates
The current universally adopted design for X.509 digital certificates used in PKI’s are standardized to employ a single cryptographic algorithm, making duplication of a PKI system the only means by which multiple algorithms can be supported.
pqPKI’s crypto-agile certificate technology creates the ability to support two cryptographic algorithms within a single X.509 certificate in such a way that it is fully compatible with systems that are unaware of the second cryptographic algorithm. This allows for the existing PKI to be upgraded with the ability to issue new crypto-agile certificates without the duplication of resources.
A crypto-agile certificate allows for backward compatibility between systems that only recognize classical algorithms and those that are upgraded to recognize quantum-safe algorithms. In this case an updated system can communicate with a legacy one using crypto-agile certificates, as the legacy system will only process the classical cryptographic primitives and ignore the quantum-safe equivalents without any modification. This makes migration of these dependent systems in phases not only possible but practical as the complexity of staged migrations is greatly reduced since backwards compatibility is maintained.
Users will not need to manage multiple sets of certificates during the migration process, to them their crypto-agile certificate is all they need to access the systems and services they require. The support burden on the IT team is greatly reduced as a result.