New collision attack mercilessly whips the SHA1 algorithm. Is BTC using SHA256 trembling?

Three years ago, Google declared the SHA1 cryptographic hash algorithm officially dead, and researchers successfully performed the world's first known collision attack on SHA1. On Tuesday, another group of researchers announced a new attack method that is significantly more powerful, which has mercilessly whipped the corpse of SHA1, which has already died once.

The new collision method gives attackers more options and flexibility, making it feasible to create PGP encryption keys, and the data released by the researchers on Tuesday showed that the attack only cost $45,000. In contrast, the attack disclosed in 2017 did not allow forging specific predetermined document prefixes, and the cost of the attack at that time was estimated to range from $110,000 to $560,000, depending on the attacker's execution speed.

(Photo credit: John Adler)

The new attack is significantly more powerful, roughly 10 times more effective.

You might say, Google has announced that SHA1 is dead, so why are people still using this hash algorithm?

In fact, that's still the case. Although SHA1's usage has been declining over the past five years, it is still a long way from being completely eliminated.

As of now, SHA1 remains the default hash function for verifying PGP keys in the legacy 1.4 branch of GnuPG (GnuPG is the open source successor to the PGP application, which is used to encrypt emails and files).

Git, a widely used management software system, still relies on SHA1 to ensure data integrity. Many non-web applications that rely on HTTPS encryption still accept SHA1 certificates.

No wonder, at a cryptography seminar held in New York this week, researchers warned that even if SHA1 is used very little or only for backward compatibility, it will expose users to attack threats, and they emphasized that the SHA1 hash algorithm should be completely phased out as soon as possible.

What is a hash function?

In a nutshell, a hash is a cryptographic fingerprint of a message, file, or other type of digital input, and like traditional fingerprints, they should be unique. Also known as a message digest, hashes play a vital role in ensuring that encryption keys, emails, and other types of messages belong to a specific person or entity, which prevents adversaries from creating forged inputs. These digital fingerprints appear in the form of a fixed sequence of numbers and letters that are generated when a message is input into a hashing algorithm or function.

The entire security of a hash algorithm depends on being able to find two or more different inputs that produce the same fingerprint. A function of bit length n should require a brute force attacker to test 2^(n/2) inputs before finding a collision (a mathematical concept known as the birthday paradox that significantly reduces the number of guesses required). Hash functions with sufficient bit length and collision resistance are secure because they require an attacker to invest an infeasible amount of time and computational resources to produce a collision. If a collision can be found using fewer than 2^(n/2) attempts, the hash function is considered broken.

The 128-bit MD5 hash function is an early widely used hash function that has been cracked. Although researchers warned as early as 1996 that MD5's flaws made it vulnerable to collisions, the MD5 hash function has remained a key part of software and web authentication for more than 20 years.

Then, in 2008, researchers used an MD5 collision to create an HTTPS certificate for a network of their choice. This demonstration eventually convinced browser-trusted certificate authorities to abandon the MD5 hash function, but the algorithm is still widely used for other purposes.

SHA1 has been shown to follow a path that is strikingly similar to MD5. After the demise of MD5, SHA1 was proven to have collision flaws by Professor Wang Xiaoyun and others in 2004, but its better collision resistance and the difficulty of switching to a new algorithm have made SHA1 still widely used even after 2015.

SHA1 was attacked by collision for the first time

In 2017, researchers demonstrated the world's first known collision attack against SHA1. It came in the form of two PDF files that had the same SHA1 hash despite showing different content. The researchers behind it said the attack, which was carried out on Amazon's cloud computing platform, cost only $110,000, and cryptographers at the time called it a classic collision attack. This is also known as an identical prefix collision attack, and an identical prefix collision occurs when two inputs have the same predetermined prefix or beginning, followed by different data. Even if the two inputs are obviously different, they can hash to the same value if additional data is attached to the file. In other words, for a hash function H, two different messages M1 and M2 will result in the same hash output: H(M1) = H(M2).

Identical prefix collision attacks are very powerful, and they are fatal to the security of hash functions, but they also have limited effects on attackers. A more powerful form of collision is called a chosen prefix attack, which made the MD5 attack against the HTTPS certificate system in 2008 and the MD5 attack against Microsoft's update mechanism in 2012 possible. Nick Sullivan, head of cryptography at content delivery network Cloudflare, explained this chosen prefix collision attack in detail in a 2015 article.

PGP/GnuPG chosen prefix collision attack simulation

The collision attack on Tuesday was the first known chosen-prefix collision attack against SHA1. To prove its effectiveness, researchers Gaëtan Leurent and Thomas Peyrin from INRIA in France and Nanyang Technological University in Singapore respectively used this collision method to simulate PGP/GnuPG attacks. In their paper, they explained:

"The prefixes are chosen to correspond to the headers of two PGP identities with keys of different sizes, one RSA-8192 and one RSA-6144. By exploiting the characteristics of OpenPGP and the JPEG format, we can create two public keys: key A with the victim's name and key B with the attacker's name and image, such that the identity certificate containing the attacker's key and image has the same SHA-1 hash as the identity certificate containing the victim's key and name. As a result, the attacker can request a signature of his key and image from a third party (from the web of trust or a CA) and transfer the signature to key A. The signature is still valid due to the collision, while the attacker controls key A using the victim's name and it was signed by a third party. As a result, the attacker can impersonate the victim and sign any document in the victim's name."

In a paper that further demonstrates the attack, the researchers provided both Message A and Message B. Despite containing different user ID prefixes, they both mapped to the same SHA1 hash 8ac60ba76f1999a1ab70223f225aefdc78d4ddc0.

This significantly improves the efficiency of attacks on the SHA1 hash algorithm by a speedup factor of about 10. More precisely, when executed on a GTX 970 GPU, the new attack reduces the cost of a same-prefix collision attack from 2^(64.7) to 2^(61.2) and the cost of a chosen-prefix collision attack from 2^(67.1) to 2^(63.4).

The researchers reportedly carried out the attack over a two-month period on a cluster of 900 Nvidia GTX 1060 GPUs that they rented online.

They say that renting a cluster is a more economical option compared to Amazon Web Services and other competing cloud services. A few months ago, the attack they performed cost $74,000, but with optimizations implemented and computing costs continuing to fall, they can now perform the same attack for only $45,000, and according to estimates, the cost of performing the attack will drop to $10,000 by 2025. Therefore, they conclude that the chosen-prefix attack against MD5, which has been available since 2009, now also applies to SHA1, and will only get cheaper over time.

SHA1 can finally rest in peace, but what about SHA 256 used by Bitcoin?

The researchers privately reported their findings to the software developers most affected, including:

1. GnuPG, which responded by implementing a countermeasure in November that invalidates SHA1-based identity signatures created after January 2019;

2. CAcert, a certificate authority that issues PGP keys, admitted that it is still using SHA1 and plans to move away from it.

3. OpenSSL, the cryptographic library continued to accept SHA1 certificates, and the developers responded that they were considering disabling SHA1;

Given that there are still many applications and protocols that rely on the SHA1 hash algorithm, the researchers were unable to contact all affected developers. To prevent the attack from being abused, they temporarily withheld many collision details.

Matt Green, a cryptography professor at Johns Hopkins University, commented that the findings are impressive and highlight the fact that the SHA1 algorithm is no longer secure. He said in an interview:

“For a secure hash function, a speedup factor of 10 shouldn’t have much of an impact, but when you get into a state extremely close to collapse, this efficiency gain does have a large impact, especially when there is a lot of mining hardware out there. We know that one shoe has dropped, and now it’s the next shoe.”

Translator’s comment: The SHA 256 hash algorithm currently used by Bitcoin is still very secure, but one day, Bitcoin will also face the time to change its hash algorithm. At that time, the cryptocurrency and developer communities will quickly reach a consensus and then replace SHA 256 with a more powerful hash algorithm through a hard fork (Note: Bitcoin code maintainer Pieter Wuille forwarded the latest SHA1 collision research at the first moment, which shows that developers are very concerned).