The Quantum Threat: Options for Migrating to Quantum Safe Cryptography

What are my quantum options?
And what has Goldilocks’ porridge got to do with it?

You’ve heard that eventually you’ll need to migrate to quantum-safe cryptography. Perhaps you’re raring to go. And yet, here I am, ready to tell you one thing: don’t do anything yet. 

Your options really depend on your quantum problem, but if you’re looking to migrate your cryptography today, you’re moving way too soon. You could stop reading right now, because that’s really the most important point here. (But do keep reading to learn more.)

Migrating now would mean rolling your own cryptography and implementation — which is never a good idea. Instead, the generally accepted wisdom is to wait for implemented and tested standards. While we do have some standards today, we are still some time away from these standards being implemented in popular protocols and libraries

(New to quantum cryptography? Read about quantum-safe cryptography standards & understand when quantum computers might actually become cryptographically relevant.)

Quantum migrations & Goldilocks’ porridge

Like porridge, you don’t want to be too hot or too cold on migration. But what is “just right”?

• Moving too soon will be challenging. You’ll be doing a lot of the implementation yourself, and you could be left without interoperability if you move before the ecosystem does.
• Moving too late, you could very well be vulnerable to the quantum threat.

Here’s what “just right” looks like to me: doing an assessment now, prioritising assets and being ready for a migration on your critical systems, products and data. And then doing nothing, except occasionally refreshing that assessment, and channelling your security energies elsewhere.

Told you it wasn’t glamorous — yet it is good security advice.

Planning a quantum migration

Now, if you are prioritising the quantum threat, then you should first plan a migration. And we can start by looking at which assets are vulnerable to quantum computers, in particular: Shor’s algorithm and Grover’s algorithm. 

Assets and data vulnerable to Shor’s algorithm 

To prepare these assets and data, here’s what to do: start by making an asset inventory, in which you prioritise those assets and data that use public-key cryptography methods — these methods are vulnerable to Shor’s algorithm, i.e. key establishment and signatures. 

When preparing this inventory, you can consider rolling to using ephemeral, per-connection keys, which will limit the exposure to the quantum threat: if an adversary cracks one key exchange, they get only one key. It’s better than nothing.

Within that inventory, you can prioritise even further. 

Unless you’re embedding signatures in products with a long lifespan, you can probably de-prioritise changing your signature schemes. This is because the validity of signature algorithms matters most at the time of signing and at the time of verification. And often, this lifetime is strictly controlled by policies e.g. in certificates, where the lifespan is typically 1 year or 90 days, but not 15 years.

Assets and data vulnerable to Grover’s algorithm 

For assets that are vulnerable to Grover’s algorithm (i.e. those using AES), you should make sure the key size is at least 128-bits. Grover’s algorithm provides a square-root reduction of work needed to break symmetric cryptography, so security is reduced by (at most) a square-root as a result. In a post-quantum world, we can say this:

• A 128-bit classical key size would still give 64-bits of post-quantum security. 
• A 256-bit classical key size would still give 128-bits of post-quantum security. 

This is absolutely loads. 64 bits is more than enough to be an impractical expensive cryptographic attack. (Basic security: every +1 bit doubles the work: so 64 bits is twice is much work as 63 bits.)

Always consider your threat model

Upping your key size is one of the easiest changes to make, but I urge you to think about your threat model.

An adversary is more likely to go ‘upstream’ and attack the key exchange method (RSA or ECDH) using Shor’s algorithm, than they are to attack AES using Grover’s algorithm. That’s because the key used for AES will likely have been exchanged using RSA or ECDH, both of which are vulnerable to Shor’s algorithm.

The work to crack RSA or ECDH is nearly 0 — while the work on Grover's is still quite hefty. So, if you had a quantum computer, you would attack the key exchange (RSA or ECDH) rather than AES.

Migrating to quantum-safe schemes: strategies & recommendations

If you’ve determined that the quantum threat is a top priority for your organisation, and you have some spare security effort floating around, you could start planning your migration.

I recommend this standard from ETSI, especially the annex, which breaks down the complex process into useful questions and these three simple steps:

1. Make an inventory of your assets and the cryptography they use. This has always been good security practice anyway.
2. Prepare the inventory, by understanding:
   • What to migrate: what needs to be end-of-lifed, and what needs to be migrated?
   • How to migrate: what will the new cryptography be?
   • When to migrate: prioritise the inventory.
3. Migrate.

When prioritising the inventory, you should prioritise key establishment mechanisms, then signatures, then symmetric cryptography (because of the relative threat).

Funnily enough, some older cryptographic technologies are already quantum-safe, e.g. IKEv1, because it uses a pre-shared key (PSK). Hilarious, right? Obviously I’m not suggesting that you roll back to IKEv1, but I can’t resist pointing out that quantum-safe cryptography is not always the latest and fanciest innovation.

Go hybrid…?

Hybrid sounds great when you’re talking about cars, but it’s just not the same for cryptography. Looking long-term, no-one wants to be stuck on a hybrid solution; the code complexity and combinatorial numbers of algorithms alone would be messy… no, thank you. 

So if you decide you want to go hybrid, make sure you have a genuine, actual, enforceable plan to roll onto pure quantum-safe cryptography (ideally soon) afterwards. 

I see your wry smile from here — how many times have you heard about “a stop-gap solution” that is years-old and now forms an integral part of the system? If you think such a transition plan cannot exist, then don’t do hybrid. Simple.

But, even if you have a transition plan to move away from a hybrid solution, challenge yourself: why are you transitioning to hybrid if you’re not sure about the cryptography you’re moving to? I mean, if you’re confident in it, you should move wholesale. 

If you’re not confident about it — why is that? Do you feel like not enough research has been done? If so, what are the (technical and legal) implications for the data you’ve encrypted with a hybrid solution that later turns out to be broken?

Finally, there’s no standard way to make a hybrid. Even how the key mixing should be done is a matter of discussion: there’s a chance that by doing your own solution, you’re introducing a weakness or extra performance burden into the system that is unnecessary.

If you feel like you can mitigate all these challenges, because it feels like the “safest” option, then you go for it.

Quantum migration quiz time

Test time! You should be able to tell me now:

• Why migrating to quantum-safe cryptography is like Goldilocks’ porridge.
• What to do with your quantum threat right now.