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.