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

Unsafe hashing algorithm really is unsafe

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.

Weapon of the information wars from Shutterstock

Dev writes Ethereum code for insecure SHA-1 crypto hash function


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. ®

Other stories you might like

  • Google sours on legacy G Suite freeloaders, demands fee or flee

    Free incarnation of online app package, which became Workplace, is going away

    Google has served eviction notices to its legacy G Suite squatters: the free service will no longer be available in four months and existing users can either pay for a Google Workspace subscription or export their data and take their not particularly valuable businesses elsewhere.

    "If you have the G Suite legacy free edition, you need to upgrade to a paid Google Workspace subscription to keep your services," the company said in a recently revised support document. "The G Suite legacy free edition will no longer be available starting May 1, 2022."

    Continue reading
  • SpaceX Starlink sat streaks now present in nearly a fifth of all astronomical images snapped by Caltech telescope

    Annoying, maybe – but totally ruining this science, maybe not

    SpaceX’s Starlink satellites appear in about a fifth of all images snapped by the Zwicky Transient Facility (ZTF), a camera attached to the Samuel Oschin Telescope in California, which is used by astronomers to study supernovae, gamma ray bursts, asteroids, and suchlike.

    A study led by Przemek Mróz, a former postdoctoral scholar at the California Institute of Technology (Caltech) and now a researcher at the University of Warsaw in Poland, analysed the current and future effects of Starlink satellites on the ZTF. The telescope and camera are housed at the Palomar Observatory, which is operated by Caltech.

    The team of astronomers found 5,301 streaks leftover from the moving satellites in images taken by the instrument between November 2019 and September 2021, according to their paper on the subject, published in the Astrophysical Journal Letters this week.

    Continue reading
  • AI tool finds hundreds of genes related to human motor neuron disease

    Breakthrough could lead to development of drugs to target illness

    A machine-learning algorithm has helped scientists find 690 human genes associated with a higher risk of developing motor neuron disease, according to research published in Cell this week.

    Neuronal cells in the central nervous system and brain break down and die in people with motor neuron disease, like amyotrophic lateral sclerosis (ALS) more commonly known as Lou Gehrig's disease, named after the baseball player who developed it. They lose control over their bodies, and as the disease progresses patients become completely paralyzed. There is currently no verified cure for ALS.

    Motor neuron disease typically affects people in old age and its causes are unknown. Johnathan Cooper-Knock, a clinical lecturer at the University of Sheffield in England and leader of Project MinE, an ambitious effort to perform whole genome sequencing of ALS, believes that understanding how genes affect cellular function could help scientists develop new drugs to treat the disease.

    Continue reading

Biting the hand that feeds IT © 1998–2022