What Does the Breaking of Rainbow Mean for Cybersecurity?
Computational complexity meets human ingenuity
A paper was released this week with the provocative title: Breaking Rainbow Takes a Weekend on a Laptop. The author is a cryptographic researcher, and the paper outlines an attack on Rainbow, a finalist of the NIST post-quantum cryptography (PQC) process. If the contents of the paper are correct, the implication is that Rainbow is no longer a good candidate for adoption.
This new attack provides a timely reminder that many aspects of cryptography rely on computational complexity arguments. Put simply, the security of an algorithm is derived from the fact that nobody has figured out a way to break it in a reasonable amount of time. If it takes three million years on a supercomputer to break a cryptographic algorithm, it’s probably safe for use today.
Most cryptographic algorithms have parameters that provide different levels of security. For instance, RSA keys can be generated in different sizes, depending on how secure the key needs to be. 512-bit RSA keys were once considered adequate for security, but now we know longer keys are needed to defend against improved attacks and increasing computing power. However, the longer we make the keys, the more impractical an algorithm becomes, so it’s important to balance practicality with security.
In the NIST selection process, each PQC algorithm is required to provide parameters that meet three increasing security levels (SL1, SL3 and SL5). In the paper, the author proposes an attack that can break the SL1 parameters, meaning that Rainbow cannot safely be used without increasing key lengths and signature sizes. These changes would make the algorithm far less attractive, since it would be more difficult to integrate it into existing systems. It’s plausible further breakthroughs would lead to more efficient attacks that render even these larger keys vulnerable to attack.
It’s not a surprise to see a PQC algorithm successfully attacked in this fashion. After all, humans are ingenious and computers are getting more powerful. Rainbow is far from the first algorithm to be found wanting by the selection process. You might argue, correctly, that the purpose of the process is to achieve this type of elimination. However, every time a new attack is discovered, we should reflect on whether we are on the right path, when it comes to securing our cybersecurity systems.
Unlike cybersecurity systems derived from computational complexity, quantum cybersecurity offers a range of tools that rely on the laws of physics. When we use quantum technologies to generate a cryptographic key, for instance, we are relying on quantum mechanics to ensure the key is strong. There is no algorithm that could be broken by smart thinking or a faster computer. It’s a fundamentally different approach. No advances in cryptanalysis or computing will result in the ability to predict how the universe behaves at such a basic level.
Computational complexity will continue to play its part, and we will always need classical algorithms to build security systems. However, this paper reminds us that new attacks can appear at any moment if you rely on complexity as your defence. Now that quantum cyber technology is a reality, companies should consider where they can switch from complexity-based thinking to defences built using the fundamental laws of nature.
Learn more about Cambridge Quantum’s cybersecurity products at https://cambridgequantum.com/our-technology/origin/.
Thanks to Matty Hoban and Peter Sigrist for their comments and edits.
