Post Quantum Cryptography Migration: Time to Get Going

Quantum computing is advancing rapidly. Innovations from Google, Microsoft, IBM and others are pushing the boundaries of not just the numbers of qubits but also their quality. We are well on our way to quantum computing being practical for real world problems. This also means we are also on the path to the existence of cryptanalytically relevant quantum computers (CRQCs) that can break a number of the algorithms much of modern security depends on. 

Opinions vary on the timeline of when a CRQC will be available. Many estimates fall in the 2035 time frame, give or take. But, there are many variables that could bring this forward including innovations in hardware, in error correction or many other aspects. It’s reasonable to expect significant engineering advances that bring this date forward, but we should not underestimate the sheer scale of the challenge to get a machine with the millions of physical qubits to make up the many thousands or more logical qubits needed to create a CRQC. 

So, let’s assume we are dealing with a 2032 - 2040 range. In other words, if we are to be pessimistic (or optimistic depending on your use case) we have 7 years to deal with this. That’s a relatively long time, so why worry about this now?

1. Store now and decrypt later attacks. This is the notion that adversaries are already capturing large amounts of data encrypted under keys in turn protected by keys that would be vulnerable to a CRQC. So, when a CRQC is available to those adversaries they will start going through that potential goldmine of data. This is a real threat, but I think it is massively overblown. Most organizations simply don’t have the long term secrets that are worth collecting, but even if they are an adversary is not necessarily going to prioritize the breaking of those keys vs. all the keys from other more obvious targets (defense, intelligence, serious intellectual property (IP) etc.). Remember, even if a CRQC exists they will not, for years after, exist in large numbers. Also, despite being able to break keys in a time frame beyond, by definition, the capabilities of conventional computers, it will still take time to break a key. Hence, even with one or more CRQCs, adversaries will use them as scarce resources. So, unless you have immensely valuable long term IP, national security data, long term sensitive communications (typically national security related), or have a cryptographic architecture where small numbers of keys can unlock all previously encrypted data then you likely don’t have to be concerned about store now and decrypt later attacks. Attackers will be just as likely to focus their efforts on breaking keys that give them exploitation capabilities (authentication for human and machine identities, software validation, etc.) rather than communications interception or media decryption. 

2. Long migration. The migration will take time and will be more complex than people think. This is actually the driver. Even though 7 - 10 years sounds a long time away, in reality the extent of the work needed might mean you are already too late. 

So the answer, no matter what your perspective, is to get going now. The rest of this blog post intends to serve two purposes, (1) How to get going and what scope to include and, (2) Useful links to much more detailed work on how to run a PQC migration program for when you do get going. 

Objectives and Scope of the Program

The objective of the overall program is to decrease your scope of potential harm from an attack by an adversary equipped with a CRQC. A secondary, perhaps obvious, objective is to ensure continued reliable operation of all your systems that depend on cryptographic controls. In other words, upgrade your crypto but don’t break your organization. 

• Develop an Inventory. Identify where you have cryptography that needs to be updated. This is harder than it sounds - and it probably already sounds pretty hard. In reality finding the libraries, toolkits, embedded crypto in other software and hardware, and looking across your supply chain is difficult. Naturally, don’t just focus on key exchanges for encryption, it’s likely your most critical keys will be for signing and authentication. 

• Set New Bars. Introduce new procurement standards such that new purchases validate either PQC conformance or a high assurance roadmap to achieve that within the goals of your overall migration program. In other words, from now on don’t add to your problem. 

• Assume Hybrid Operation. Plan for PQC coexistence / hybrid operation with existing cryptographic technologies for the foreseeable future. This can be part of an overall crypto-agility program, but in essence it is in case there is a severe break in one or more PQC algorithms before the threat from a CRQC is credible so that you will still remain protected by the current suite of cryptographic algorithms.  

• Scope Broadly. This isn’t just about any core cryptographic toolkits you might have. Cryptographic technologies are everywhere. Worse, the nature of some of these changes have potential knock on effects to how other layers in the technology stack operate (e.g. authentication protocol exchanges using PQC might blow assumptions of how much of those can fit in one TCP frame which might inadvertently break vendor middle boxes that have made bad design assumptions). The scope for crypto migration or post-migration testing should include at least:
  

  • Core cryptographic toolkits and services. 

  • Communications protocols. 

  • Middleware, database and other layers. 

  • Authentication services.

  • Software signing services. 

  • Applications (e.g. that might hardcode assumptions of signature sizes).

  • Extended enterprise - downstream to suppliers and services.

  • Extended enterprise - upstream to customers, APIs and AI agents.

  • Hardware.

• The 4Ps - Power, Performance, Parameters and Portability. Include assessments of certain application/system/protocol sensitivities to the potential performance implications of PQC, consequent power implications (e.g. for mobile devices), knock-on effects from larger key and signature sizes and the implications for portability when interfacing with older systems. 

• Embedded Keys and Signatures.  Look out for application and database layer dependencies. In particular, fixed assumptions about how key or signature sizes, certificates or other PQC output might be different such that changes are needed to application protocols, databases, applications fields and so on. Think Y2K-like changes all over again. 

• Historical Transactions - Store and Repudiate Later. Store and Decrypt Later issues might not be a risk for your organization but Store and Repudiate Later might be. For example, do any of your long term transactions, records, bills of materials, or contracts require re-signing or additionally signing under PQC. 

• Lead Times. Some items, for example hardware, will have a long lead time to become PQC equipped and may take longer again to upgrade or replace in the field. So, your prioritization may need to adjust and account for that. 

• Plan for Crypto Agility. See next section. 

Importance of Crypto Agility 

There are many definitions of crypto-agility. But in simple terms this is about making sure that you do your migration under the assumption that further changes might be needed in the future. Specifically, that if further changes are needed then it’s a matter of routine to adjust that without going through a whole new migration. While many algorithms in post quantum cryptography are quite well studied there are others, despite intense scrutiny, that may well succumb to cryptanalysis. The remediation for this might be to increase key sizes or change other algorithm parameters. If doing this requires the same effort as your original PQC migration then you're in trouble, not just because of the work effort but also because you might not have the time if the reason for the change is due to imminent threat. 

So look at the following questions and ask if your PQC migration is going to deliver not just PQC but also agility in the face of these issues: 

• What happens if one of the NIST algorithms has to be changed after implementation?

• What happens if algorithm parameters have to change e.g. key sizes?

• What happens if output needs to change e.g. signature sizes?

• If key and signature sizes change does that mean further application layer protocol changes and can you accommodate that? 

• Does this work for hardware as well as software i.e. have you thought about field upgradability? 

I'm not suggesting that all aspects of crypto-agility are covered at the expense of a timely PQC migration. You will likely need to prioritize which aspects of crypto-agility to focus on in your program. 

Forming and Sustaining the Team 

Running a PQC migration program will be similar to all your other major enterprise-wide programs and, as mentioned, will be reminiscent of things like Y2K if you have anyone around that remembers that. This will include:

1. Program Team. Build a program team. Small at first, but plan for it to grow. 

2. Federate. Federate the work into business units. So this is more like a program of programs. 

3. Governance. Build an overall governance process (executive sponsors, Board agreement) and a long term budget with some growth projections. 

4. Targets. Set annual targets projected out over at least 5 years e.g. Year 1 inventory, Year 2 migrate core tool kits, etc. 

5. Sector Coordination. Establish sector/industry wide coordination especially where industry standards, common utilities or other shared resources need to be upgraded in synchrony with other organizations. 

6. Supplier Standards. Set and communicate higher expectations on your suppliers/service providers to evidence they have an active PQC migration program in place. 

7. Principles. Define, agree and communicate a set of principles and standards in relation to hybrid expectations, prioritization approach and the extent to which extra work will be done to meet crypto-agility goals. 

8. OKRs. Define short term and long term Objectives and Key Results.

9. Partner. Team up with other organizations, intra- or inter-sector to get help and share experiences e.g. Post Quantum Cryptography Alliance, an ISAC etc. 

PQ(2K)C - An Important Emphasis 

It’s hard not to draw an analogy with the old Y2K programs most companies in the 1990’s ran in readiness for the Year 2000 date change. Y2K programs overall were a resounding success and a lot of work for many organizations. The fact that there were so few issues is often ascribed to the problem being overhyped as opposed to the reality of it being fixed in time. 

PQC migration programs have similarities to Y2K in that inventories need to be examined, suppliers questioned and upstream dependencies managed to look for crypto in need of upgrades. This is not where the analogy stops. There are many application or application protocol layer assumptions about signature and key sizes which will require database field, middleware protocol encoding or application layer software changes. Many of these changes will need to be done in synchrony across an entire organization or industry to ensure reliability. Sadly, this might be even more complex than Y2K. 

What Not to Do

• Fall for the snake-oil. There are a few companies out there selling proprietary, or standard-variant implementations of PQC algorithms that have not gone through a full vetting process as the NIST standards have. Some of the sales pitches of these companies is to get ahead of NIST standards implementation by large companies or to improve on performance. 

• Think QKD is the answer. Quantum key distribution (QKD) or quantum cryptography overall, as distinct from Post Quantum Cryptography, is touted as a (or even the) answer to the risks from CRQCs. While there are uses for QKD in certain quantum communications situations the reality is that QKD has implementation issues (despite its theoretical soundness). But the main issue is the nature of how it is deployable means it is not in any way a viable replacement for conventional crypto. All of this is well covered by NSA, GCHQ and ETH Zurich. 

Resources

• US DHS/CISA Guides to Post Quantum Cryptography

• US National Security Agency Post Quantum Cybersecurity Resources

• NIST PQC Migration Framework

• Google’s Enterprise PQC Migration Resources

• Post Quantum Migration : Nature

• The PQC Migration Handbook

• Post Quantum Cryptography Alliance 

Bottom line: Cryptanalytically Relevant Quantum Computers (CRQCs) are coming. Perhaps sooner than we think, but we can conservatively (and usefully) assume in the 2032 - 2040 time frame. It’s going to be more complex to migrate to Post Quantum Cryptography than many organizations expect and so getting started now is vital. Adopting crypto-agility practices will mitigate the risk of further wide-scale changes as PQC standards inevitably evolve. Beware the snake-oil of non-standard solutions.