Breaking Rainbow Takes a Weekend on a Laptop
Abstract
This work introduces new key recovery attacks against the Rainbow signature scheme, which is one of the three finalist signature schemes still in the NIST Post-Quantum Cryptography standardization project. The new attacks outperform previously known attacks for all the parameter sets submitted to NIST and make a key-recovery practical for the SL 1 parameters. Concretely, given a Rainbow public key for the SL 1 parameters of the second-round submission, our attack returns the corresponding secret key after on average 53 hours (one weekend) of computation time on a standard laptop.
Author’s notes
Digital signature algorithms are a cryptographic mechanism to authenticate digital messages and entities. They are widely used by secure messaging applications, internet browsers, e-commerce, and many more. Unfortunately, all the digital signature algorithms that are in use today (RSA, and ECDSA for example) require the mathematical problems of integer factorization or the discrete logarithm problem to be hard.
However, we know these problems are easy for quantum computers. This means that when a sufficiently powerful quantum computer is built, it can be used to impersonate you on WhatsApp, serve you fake web pages, and send you malicious software updates. To avoid this catastrophe, cryptographers have been working tirelessly to design new digital signature algorithms that are safe from attackers with quantum computers. NIST, the US National Institute of Standards and Technology, is running a project to standardize quantum-safe digital signatures.
Rainbow
There were three finalists in the NIST project: CRYSTALS-Dilithium, Falcon, and Rainbow. This work unveiled a severe vulnerability in the Rainbow algorithm, which allows an attacker to break the algorithm in only 53 hours (one weekend) on a common laptop. Dilithium and Falcon, (both developed with the involvement of IBM researchers) are now selected for standardization.
Obviously, Rainbow did not make the cut, but the hash-based signature algorithm SPHINCS+ was selected for standardization instead. While we didn't find the pot of gold at the end of Rainbow, there was still some reward in the form of the “Best Early Career Researcher Paper” award at Crypto '22.
Our results
We found a new attack against the Rainbow signature scheme. Our attack exploits differentials to recover the secret key more efficiently. At the lowest security level, it was believed that to break Rainbow one would need to run an algorithm that does at least 2128 operations. Even if a billion computers had been working together, each doing a billion operations per second since the beginning of the universe 14 billion years ago they would still not have finished the attack today.
Our new attack is much more efficient and runs in only 53 hours (one weekend) on a normal laptop, which shows that Rainbow is much less secure than anticipated and should not be standardized by NIST.
What now?
It would be possible to fix Rainbow by changing the parameters. However, this would significantly increase the key sizes and slow down the signing and verification algorithms, which would make Rainbow less efficient than the so-called Oil-and-Vinegar scheme, a simpler algorithm that Rainbow was based on. Instead of reviving Rainbow, it would be better to use the related Oil-and-Vinegar scheme instead. Oil-and-Vinegar is simpler and better understood, so we have more confidence in its security.
Although our work has shown that powerful attacks can go undiscovered for many years, so we should still keep investigating Oil-and-Vinegar and looking for weaknesses more carefully. The only way to build confidence in the security of cryptographic algorithms is if many smart researchers try to find weaknesses and end up empty-handed.
Okay, so Rainbow is dead. What does this mean for the quantum-safe algorithms that NIST selected for standardization? Not very much.
Those other algorithms are based on completely different mathematics, so there is no chance that our techniques can be used to beak other algorithms. Moreover, Dilithium, Falcon, and SPHINCS+ have had a lot of scrutiny from the cryptographic community and there is strong theoretical evidence that they are secure, so it seems unlikely that anyone can come up with a practical attack on one of these signature algorithms.