Hash snag: Security shamans shame SHA-1 standard, confirm crucial collisions citing circa $45k chip cost

SHA-1 stands for Secure Hash Algorithm but version 1, developed in 1995, isn’t secure at all. It has been vulnerable in theory since 2004 though it took until 2017 for researchers at CWI Amsterdam and Google to demonstrate a practical if somewhat costly collision attack.

Last year, crypto-boffins Gaëtan Leurent, from Inria in France, and Thomas Peyrin, from Nanyang Technological University in Singapore, proposed [PDF] a more robust technique, a chosen-prefix collision attack.

And this week, at the Real World Crypto Symposium in the US, they described how they made it work.

“This more powerful attack allows to build colliding messages with two arbitrary prefixes, which is much more threatening for real protocols,” said Leurent and Peyrin in a paper, SHA-1 is a Shambles, presented at the conference.

A hash algorithm is a function that mathematically maps input data to another value of fixed length. Think of it as one-way encryption: you convert your input data, however long it is, into a summary or fingerprint that has a set size, with no way of recreating the original from this hash. Changing even a small part of the input data produces a significant change in hash, ideally. The hash is usually a lot smaller than the input.

Hashes are thus used for authentication and related applications: by comparing hashes, you can be sure data hasn’t been tampered with while in transit, for instance. A hash collision occurs when two separate inputs produce the same output – obviously not desirable if you’re checking, say, checking a stored hash of a password against a hash of a user-supplied password and you want only one specific password to provide access.

A chosen-prefix collision, because it allows the attacker to choose the prefixed content, represents a more serious threat.

Back in 2012, the same year America’s National Institute of Standards Technology (NIST) advised against using SHA-1 for applications that require collision resistance, cryptographer Bruce Schneier estimated that the cloud computing bill for carrying out a SHA-1 attack would be about $2.77m. And he projected the cost would fall to about $43,000 by 2021.

In their paper, Leurent and Peyrin put the theoretical cost at $11,000 for a SHA-1 collision and $45,000 for a chosen-prefix collision. To actually carry out their attack required two months of computation time using 900 Nvidia GTX 1060 GPUs. The boffins paid about $75,000 because GPU prices were higher at the time and because they wasted time during attack preparation.

Their attack involved creating a pair of PGP/GnuPG keys with different identities, but colliding SHA-1 certificates, allowing them to impersonate a victim and digitally sign documents in the victim’s name.

“Our work shows that SHA-1 is now fully and practically broken for use in digital signatures,” the researchers state in their paper. “GPU technology improvements and general computation cost decrease will quickly render our attack even cheaper, making it basically possible for any ill-intentioned attacker in the very near future.”

Much of the technical community has already taken action to avoid SHA-1 in vulnerable contexts. Web browsers like Chrome and Firefox stopped accepting SSL SHA-1 certificates in early 2017, followed by Edge and Internet Explorer a few months later.

In November last year, Apple said it would not longer trust SHA-1 certificates in macOS 10.15 and iOS 13. Microsoft took similar steps last year as well.

Usage of SHA-1 is low – Leurent and Peyrin claim about 1 per cent of website certificates still rely on it, down from 20 per cent in 2017. Nonetheless, SHA-1 signatures are still supported in many applications.

“SHA-1 is the default hash function used for certifying PGP keys in the legacy branch of GnuPG (v 1.4), and those signatures were accepted by the modern branch of GnuPG (v 2.2) before we reported our results,” they note. “Many non-web TLS clients also accept SHA-1 certificates, and SHA-1 is still allowed for in-protocol signatures in TLS and SSH.”

Leurent and Peyrin contacted several affected vendors in the spirit of responsible disclosure, but say they could not notify everyone. GnuPG patched the problem in its November 25, 2019 release so that SHA-1-based identity signatures created after 2019-01-19 are no longer valid.

The researchers note that even if SHA-1 usage is low, miscreant-in-the-middle attacks may downgrade connections to SHA-1. Also, SHA-1 continues to be the foundation of the Git version control system. CAcert, a Certificate Authority for PGP keys, has acknowledged the researchers’ concerns but not yet dealt with the issue. And OpenSSL developers, the researchers say, are considering disabling SHA-1 for the security level 1 setting, which calls for at least 80-bit security (SHA-1 produces a 160-bit hash value).

Back in 2017, Git creator Linus Torvalds dismissed concerns about attacks on Git SHA-1 hashes. GitHub, Microsoft’s hosted Git service, offered similar reassurance, noting in a blog post that it had implemented collusion detection for each hash it computes and that the open source Git project is developing a plan to move away from SHA-1.

GitHub did not immediately respond to a request for comment.

Evidence of efforts to implement SHA-256 can be seen on the Git mailing list, but the work appears to be ongoing. At the moment, Git developers advise using the collision detection library developed in 2017 and implemented by GitHub to check repo integrity. ®

READ MORE HERE