Breaking Rainbow takes a weekend on a laptop
WhatsApp, just like many other secure messaging applications, relies on digital signature algorithms to authenticate digital messages. Digital signature algorithms are also used by internet browsers and e-commerce. Unfortunately, all digital signature algorithms that are in use today, such as RSA and ECDSA, require the mathematical problems of integer factorization or the discrete logarithm problem to be hard. However, these problems will be easy to crack by quantum computers. So 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 scenario, cryptographers have been working tirelessly to design new digital signature algorithms that are safe from attackers using quantum computers. NIST, the US National Institute of Standards and Technology, has been running a project to standardize quantum-safe digital signatures. On 5 July 2022, NIST announced the winners of a six-year-long competition to develop quantum-safe algorithms, a first step towards new post-quantum standards, expected to be finalized in two years. The CRYSTALS-Kyber algorithm won for general encryption, and CRYSTALS-Dilithium, FALCON and SPHINCS+ for digital signatures.
Originally, though, there was one more finalist in the NIST digital signatures category: Rainbow. And that’s where our work comes in. Our team unveiled a severe vulnerability in the Rainbow algorithm, allowing an attacker to break the algorithm in only 53 hours — one weekend — on a common laptop. Because of this work, Rainbow did not make the cut. 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 team found a new attack against the Rainbow signature scheme. The 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 53 hours on a laptop, showing that Rainbow is much less secure than anticipated and should not have been standardized by NIST.
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.
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. 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.