Regular readers of this blog will have listened to me talking about crypto-agility and quantum safety quite a bit.
Luckily our cryptographic foundations are quite safe for several years before Quantum Computers are powerful enough to be a threat. The bad news though is that virtually all enterprises I visit have serious gaps for the crypto-agility part.
As I’ve argued before, cryptography has always been evolving. We always had algorithms that we thought were safe and then they were broken and we moved to new ones… So what makes the move to Quantum Safe alternatives so hard?
MD5 is a hashing algorithm. It is a one-way function that produces a short 16-byte text that is supposed to be different for each input. Hashing functions are used everywhere from cryptocurrencies, password verification, integrity checking and much more.
Various attacks to MD5 appeared and in 1996 NIST recommends using SHA-1 instead of MD5 (since 2013 this can be attacked in just seconds on regular computers).
However in 2019 one quarter of widely used content-management-systems still use the vulnerable MD5 for password hashing (https://www.zdnet.com/article/a-quarter-of-major-cmss-use-outdated-md5-as-the-default-password-hashing-scheme/).
To fix this, a simple move to a different hashing algorithm is all that is required. The newer hashing algorithms are even much faster than MD5 (!). The only downside is that newer hashing algorithms produce a longer text.
See e.g. (from https://blake2.net/) where both SHA-1 and BLAKE2b are much faster than MD5 (while SHA-256 is slower)
And that really begs the question. We know since 1996 that MD5 needs to be replaced. We have alternatives that are much faster and still in 2019 you can find MD5 everywhere…
So, we had 25 years to do something about it and we are still in really bad shape. That doesn’t give us much confidence that any upgrade to more fundamental cryptographic algorithms (like public key cryptography) is going to happen anytime soon.
Now that Google has achieved quantum supremacy (although for a completely non-relevant problem), nobody is questioning that the time-frame we have to transition to quantum safe data protection alternatives is less than 25 years.
To make things worse, we don’t really know what we should replace our current crypto infrastructure with… NIST is still running its competition for the successor for Public Key Cryptography and Signatures. Currently lattice-based cryptosystems seems to be everybody’s favorite pick, however researchers are already working on Quantum Algorithms to attack lattice-based cryptosystems. David Joseph, Alexandros Ghionis, Cong Ling and Florian Mintert from the Imperial and King’s College in London just published their research “Not-so-adiabatic quantum computation for the shortest vector problem” (https://arxiv.org/abs/1910.10462v2). These may be early days and Quantum Annealing algorithms don’t yet necessarily provide an exponential speedup, but we don’t know what’s coming next. We don’t want to put all of our eggs into one basket where we don’t know whether its safe, particularly when we consider that none of the quantum-safe alternatives come with a proof that they are uncrackable. In 1993, everybody thought that RSA encryption was uncrackable, and just one year later Peter Shor came up with his algorithms and suddenly the world has turned upside down. Let’s make sure history doesn’t repeat itself.
But even if we would know what the replacement would be, recent experiments show the massive impact post-quantum algorithms will have in practice. It’s simply not as easy as “just” replace the thing with another.
Amazon did a study on what the impact post quantum algorithms would have to their systems ( https://aws.amazon.com/blogs/security/post-quantum-tls-now-supported-in-aws-kms/) and they are massive. Instead of completing the whole TLS handshake in 1.19 ms, the handshake now takes 155.08 ms for the SIKE algorithm (which is an algorithm under consideration by NIST to be standardized as quantum safe).
This is massive and can be considered an eternity in the scheme of things. From 1 second to 155 seconds (!)
If these numbers don’t mean anything to you,
These numbers were from 10 years ago. Today it is more widely accepted the reduction in sales to be more around the 7% – 10% mark!
Cloudflare also ran various post-quantum experiments and they noted that “Nevertheless, our results show that SIKE incurred a significant overhead for every connection, especially on devices with weaker processors” (https://blog.cloudflare.com/the-tls-post-quantum-experiment/)
Think what impact this would have to the 30 billion IoT devices that all support HTTPS (and therefore TLS encryption), but the vast majority won’t have the CPU power to cope with post quantum algorithms. Not that we have figured out a way of updating all of these yet!
I hope I have provided you with some practical information on why post-quantum is more than just “I don’t have to worry about it and just replace one algorithm with another…” and we really must combine crypto-agility with post-quantum strategically and call on every enterprise in the world to take this issue seriously. Google has just proven all pessimists wrong by showing that they can scale up their quantum processor. IBM has been offering Quantum Computers publicly for years and Microsoft just pushed Quantum into their Azure backend. This revolution is coming whether we are ready or not, so let’s make sure we are ready.