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.
Advertisement
A total of 69聽algorithms believed to be resistant to the increased code-breaking ability of quantum computers were submitted to聽. 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鈥檚 public key, which is made available聽to everyone.
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 鈥減rove鈥� they are someone else.
Beullens says that this kind of聽attack, detailed in a published by the International Association for Cryptologic Research, makes Rainbow 鈥渦seless鈥� 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.
鈥淚 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. 鈥淭he 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.
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.
鈥淲e want to change as little of our cryptography infrastructure as possible. So, things like secure internet connections, they can鈥檛 easily cope with incredibly large public keys,鈥� says Jones. 鈥淩ainbow already had larger keys. So in that sense, it was already perhaps not the strongest candidate.鈥�
at NIST told New 杏吧原创 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 .
