ONE of three cryptography algorithms vying to become a global standard against the looming security threat posed by quantum computers has been cracked in a weekend using a standard laptop. The algorithm is now widely believed to be unfit for purpose.
A range of algorithms for encryption – the process of bundling data up into impenetrable files for safe transmission – are currently verified and approved as secure by the US National Institute of Standards and Technology (NIST), and consequently they are used around the world. But these algorithms are set to be made obsolete in coming years by the arrival of quantum computers.
Once developed, these machines promise to vastly exceed the power of classical computers at certain types of problems. One example is quickly finding the prime factors that serve as the multiplicative building blocks of a number – for instance, 3 and 7 are the prime factors of 21. This seemingly innocuous ability will fundamentally break encryption currently used in email, banking and cryptocurrencies.
A total of 69 algorithms believed to be resistant to the increased code-breaking ability of quantum computers were submitted to NIST’s Post-Quantum Cryptography competition. These have now been whittled down to four finalists for the task of encryption and three for signing signatures, which are used to verify identity, for example when making a financial transaction.
Rainbow is one of the final three signature algorithms. A signature scheme is used to mark a message using a secret key known only to that person. It can then be verified as a legitimate message by a recipient using the sender’s public key, which is made available to everyone.
Ward Beullens at IBM Research Zurich in Switzerland was able to take a Rainbow public key and discover the corresponding secret key in just 53 hours using a standard laptop. This weakness would allow an attacker to falsely “prove” they are someone else.
Beullens says that this kind of attack, detailed in a study published by the International Association for Cryptologic Research, makes Rainbow “useless” as a method to verify messages. He had previously developed less serious attacks against Rainbow, to which the creators responded by increasing the complexity of the private and public keys at the expense of efficiency, he says.
“I think my previous attack was also quite serious, and I think it was already obvious that Rainbow was not going to be standardised,” says Beullens. “The common feeling among cryptographers seems to be that [the other two finalists in the signature competition] are much more secure.”
Current algorithms use public keys, secret keys and signatures that are just a handful of bytes, allowing cryptography to be added onto all sorts of protocols without much additional overhead.
Duncan Jones at Cambridge Quantum says that while all cryptographic algorithms can eventually be broken, there are varying levels of efficiency. Some algorithms require more data to store a public key and secure private key, while others do it using less. Rainbow had already been one of the less efficient algorithms, he says.
“We want to change as little of our cryptography infrastructure as possible. So, things like secure internet connections, they can’t easily cope with incredibly large public keys,” says Jones. “Rainbow already had larger keys. So in that sense, it was already perhaps not the strongest candidate.”
Dustin Moody at NIST told New Scientist that the attack against Rainbow had been verified and that it is now unlikely to be chosen as the final signature algorithm when a decision is made later this month. Unfortunately, it has already seen limited real-world use, including by a cryptocurrency called ABCMint.