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ās 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 āproveā they are someone else.
Beullens says that this kind ofĀ attack, detailed in a 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.
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.ā
at NIST told Ā鶹“«Ć½ 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 .
