The Tacoma Narrows suspension bridge- which spanned the Puget Sound in Washington state, USA – opened to the public in July 1940, and suffered a catastrophic collapse after only five months. This event had a profound effect on the fields of science and engineering. The bridge collapsed due to aeroelastic flutter, a type of self-sustaining structural oscillation that was not well understood at the time, and resulted in considerable research into the fields of aerodynamics and aeroelastics.
Fast forward 81 years and today we have another branch of science, quantum physics and its application in quantum computers – that is expected to be particularly disruptive in the field of cryptography. However, now we have ways of predicting the effects of quantum computers – before they can disrupt established cryptographic practices. This will allow us to be better prepared as we build new solutions that may impacted by advances in quantum computing.
The expectation is that quantum computing will render the strong cryptographic algorithms we use today ineffective through brute force attacks by dramatically speeding up the time it would take to break an encryption algorithm.
So what will the post-quantum world look like? There are a handful of theories, principles and algorithms you need to be familiar with – or at least be able to name drop into a conversation!
Postulated in 1994 by American mathematician Peter Shor, Shor’s algorithm is a polynomial-time quantum computer algorithm yield exponential speedup when solving factoring. Large complex mathematical problems, like cryptographic algorithms, could thus be solved quickly using quantum computers – putting commonly used public-key cryptography schemes based on asymmetric algorithms such as RSA and elliptic curves at risk.
Grover’s algorithm could weaken symmetric algorithms like AES. It suggests that an attacker with access to a quantum computer might be able to attack a symmetric cipher with a key up to twice as long as could be attacked with access only to standard computers. However, the National Institute for Standards and Technology (NIST) has considered Grover’s algorithm and noted that, aside from the anticipated greater expense of quantum computing, to obtain the full quadratic speedup, all the steps of Grover’s algorithm would have to be performed in series. This means that the ‘speedup’ might not be as impressive in comparison to massively parallel systems. NIST reports “it is quite likely that Grover’s algorithm will provide little or no advantage in attacking AES, and AES 128 will remain secure for decades to come.” The full response from NIST can be read here.
Named for Canadian Michele Mosca, Mosca’s theorem tackles the thorny topic of migration to a quantum safe eco-system, and is designed to measure risk based on an organization’s response to three questions:
- How long do you need your cryptographic keys to be remain secure? This is denoted as x, the security shelf life.
- How long will it take to deploy a set of tools that are quantum-safe? This is denoted as y, the migration time.
- How long will it be before a quantum computer, or some other method, breaks the currently deployed public-key cryptography tools? This is denoted as z, the collapse time.
Mosca expresses those questions in a simple formula determining if x+y>z “we have a serious problem.” It’s worth exploring these ideas in detail.
Security Shelf life (x)
While some crypto keys in use today are ephemeral with a truly short life, many others, such as those used in public key infrastructure, need to be in use and secure for five, 10 or even 20 years or longer before it needs to be rotated. This is a non-trivial amount of time.
Another consideration is the “store-now, decrypt later” attack. A well-resourced attacker could target encrypted communications between two parties, and then hold the data for decryption when a quantum computer becomes available – this extends ‘x’
Migration Time (y)
Migration time isn’t simply how long it takes for an organization to migrate their entire crypto ecosystem to quantum safe algorithms. It also needs to reflect the time for quantum safe algorithms to be established and fully accepted by industry and academics alike, reviewed, refined and thoroughly tested before being used real life situations. That can easily take 3-5 years. So adding x and y yields say worse-case scenario (20 +5) 25 years.
Collapse Time (z)
Collapse time for the Tacoma Narrow’s bridge was a mere five months – a disastrous turn of events. Academics and enterprise alike now speculate that quantum computers will have enough qubits to allow them to break the classic cryptographic algorithms in 15-20 years.
Figure 1: Illustration of Mosca’s theorem
So back to the formula, as illustrated in figure 1, we have achieved x+y>z – Houston we have a problem! Mosca’s theorem serves as a stark reminder of why organizations need to start applying due diligence in the Post Quantum area now. NIST recently published a migration paper that serves as a statement of intent, outlining their plans to develop a set of tools that will in part address migration time (y). NIST is seeking comments from industry and academia, so if this is on your radar you can download the paper here.
Why Should I Care?
So you might be thinking, should this be keeping me awake at night? Are we facing a Tacoma Narrows situation? Predicting the collapse of classical cryptographic algorithms is currently very much in the crystal ball domain, but we do have time to plan and implement steps to make sure we are best prepared for when it happens. Fortunately, there is time to adopt some best practice steps:
- Ensure your organization has a Post Quantum Strategy in place. Lobby your Chief Security Officer to make it happen.
- Keep abreast of the emerging Post Quantum algorithms from NIST. Develop a plan to test and deploy them.
- Develop a crypto-agile mind set. Where possible, don’t hardwire specific pre-quantum algorithms into your certificates and code. Make sure you have the ability to upgrade when required, adopting new Post Quantum algorithms as and when they become ratified.
- Until Post Quantum safe algorithms are available, use a hybrid approach of currently available Post Quantum resistant algorithms in conjunction with existing asymmetric algorithms.
- Use longer Symmetric keys and algorithms.
Right now, there is time to get ready. In a few years, that may not be the case. With these steps, you can get your organization on the right path to cross that bridge into a post quantum world.