New collision attack relentless whipshake SHA1 algorithm, using SHA256's BTC to tremble?

Three years ago, Google announced the official death of the SHA1 cryptographic hash algorithm, and researchers successfully executed the world's first known collision attack against SHA1. On Tuesday, another group of researchers unveiled a new attack method, which is significantly more powerful, which caused SHA1, who had died once, to be ruthlessly whip.

This new collision method gives attackers more choice and flexibility. It makes it practical to create a PGP encryption key. According to data released by researchers on Tuesday, this attack only cost $ 45,000. In contrast, the attacks disclosed in 2017 did not allow forgery of certain predetermined document prefixes, and the cost of the attack at that time was expected to range from $ 110,000 to $ 560,000, depending on the speed of the attacker's execution.

(Picture from: John Adler)

• How accurate are people in the industry for the 2020 Bitcoin price prediction?
• 2019 Global Digital Asset Anti-Money Laundering (AML) Research Report
• Featured | Bitcoin's possible protocol upgrade in 2020; cryptocurrency industry issues in 2020

The new attack is significantly more powerful, achieving roughly 10 times the effect.

You might say that Google has announced that SHA1 is dead. Is anyone still using this hashing algorithm?

In fact, that's what happened. Although the usage of SHA1 has been getting lower and lower in the past five years, it is still far from being completely eliminated.

As of now, SHA1 is still the default hash function for verifying PGP keys in the 1.4 branch of GnuPG's legacy (GnuPG is an open source follow-up version of PGP applications, which is used to encrypt email 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 in New York this week, researchers warned that even if SHA1 usage is low or used only for backward compatibility, it will expose users to threats of attack, and they emphasized that they should be phased out as soon as possible SHA1 hash algorithm.

What is a hash function?

In a nutshell, a hash is an encrypted fingerprint of a message, file, or other type of digital input. Like traditional fingerprints, they should be unique. Hashing, also known as message digests, plays a vital role in ensuring that encryption keys, emails, and other types of messages belong to a particular person or entity, which prevents adversaries from creating forged inputs. These digital fingerprints come in the form of a fixed sequence of numbers and letters that are generated when a message is entered into a hash algorithm or function.

The overall security of a hash algorithm depends on whether two or more different inputs that produce the same fingerprint can be found. 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 , which significantly reduces the number of guesses required). Hash functions with sufficient bit length and collision resistance are safe because they require attackers to invest in impractical time and computing resources to perform collisions. If collisions can be found using less than 2 ^ (n / 2) attempts, we consider the hash function to be cracked.

The 128-bit MD5 hash function is an earlier and widely used hash function that has been cracked. Although researchers warned as early as 1996 that the flaws in MD5 made them 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 MD5 collisions to create an HTTPS certificate for their arbitrarily selected network. This demonstration eventually convinced certificate authorities trusted by browsers to abandon the MD5 hash function, but the algorithm is still widely used for other purposes.

SHA1 proved to follow a path similar to MD5. After the demise of MD5, SHA1 was proven to have collision defects by Professor Wang Xiaoyun and others in 2004, but it has better collision resistance and the difficulty of turning to new algorithms, which makes SHA1 still be used even after 2015. widely used.

SHA1 was hit by collision for the first time

In 2017, researchers demonstrated the world's first known collision attack against SHA1 . It comes in the form of two PDF files that have the same SHA1 hash, although they show different content. The researchers behind it said that the attack on Amazon's cloud computing platform only cost $ 110,000, at the time cryptographers called it a classic collision attack. This is also known as the same prefix collision attack, when two inputs have the same predetermined prefix or beginning, and subsequent different data, the same prefix collision occurs. Even if the two inputs are significantly different, they can hash to the same value if other data is appended to the file. In other words, for the 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. They are a fatal blow to the security of hash functions, but they have limited effect on attackers. A more powerful form of collision is called the chosen prefix attack , which made possible the MD5 attack against the HTTPS certificate system in 2008 and the MD5 attack against Microsoft's updated mechanism in 2012. Nick Sullivan, director of cryptography at the content delivery network Cloudflare , explained this selective prefix collision attack in detail in a 2015 article.

PGP / GnuPG select prefix collision attack simulation

The collision attack that occurred on Tuesday was the first known prefix collision attack against SHA1. In order to prove its effectiveness, researchers from INRIA in France and Nanyang Technological University in Singapore and Thomas Peyrin respectively used this collision. A PGP / GnuPG simulation attack was performed. In their thesis , they explained:

"The selection prefix corresponds to the headers of two PGP identity certificates with keys of different sizes, one RSA-8192 key and one RSA-6144 key. By leveraging the characteristics of the OpenPGP and JPEG formats, we can create two public keys: The key A with the victim's name and the key B with the attacker's name and picture, so that the identity certificate containing the attacker's key and picture has the same SHA- as the identity certificate containing the victim's key and name 1 hash. Therefore, an attacker can request the signature of its key and picture from a third party (from the trust network or CA) and transfer the signature to key A. Due to the collision, the signature is still valid and the attacker uses The victim's name controls key A and is signed by a third party. Therefore, an attacker can impersonate the victim and sign any document on his behalf. "

In an article that further demonstrated the attack, the researchers provided both message A and message B. Although different user ID prefixes are included, they all map to the same SHA1 hash value 8ac60ba76f1999a1ab70223f225aefdc78d4ddc0.

This significantly improves the efficiency of attacking the SHA1 hash algorithm with an acceleration factor of approximately 10. More precisely, when executed on a GTX 970 graphics processor, the new attack reduces the cost of the same prefix collision attack from 2^(64.7) to 2^(61.2) , and reduces the cost of choosing a prefix collision attack from 2^(67.1) reduced to 2^(63.4) .

It is reported that within two months, researchers attacked 900 Nvidia GTX 1060 GPU clusters they rented online.

They say rented clusters are a more economical option than Amazon Web Services and other competitors' cloud services. A few months ago, their attack cost $ 74,000, but with optimizations and computational costs continuing to fall, they now cost $ 45,000 to perform the same attack. According to estimates, by 2025, The cost of the attack will be reduced to $ 10,000. Therefore, their conclusion is that since 2009, selective prefix attacks against MD5 are now also applicable to SHA1 and will only become cheaper over time.

SHA1 can finally rest, what about the SHA 256 used by Bitcoin?

It is reported that the researchers privately reported their research results to the most affected software developers, including:

1. GnuPG, which responded that a countermeasure was implemented in November to invalidate SHA1-based identity signatures created after January 2019;
2. CAcert, a certificate authority that issues PGP keys, which acknowledges that SHA1 is still in use and plans to leave SHA1;
3. OpenSSL. Prior to this, the crypto library continued to accept SHA1 certificates, and the developers responded that they were considering disabling SHA1;

Considering that there are still many applications and protocols that rely on the SHA1 hash algorithm, researchers cannot reach all affected developers. To prevent the attack from being abused, they temporarily retained many collision details.

Matt Green, a professor of cryptography at Johns Hopkins University, commented that the results of this study are impressive, emphasizing the fact that the SHA1 algorithm is no longer secure, he said in an interview:

"For a safe hash function, an acceleration factor of 10 should not have much effect, but when you fall into a state that is very close to crashing, this efficiency improvement does have a great impact, especially When a lot of mining hardware existed, we knew that one shoe had fallen, and now it was the next shoe. "

Translator's comment: Bitcoin's current SHA 256 hash algorithm is still very secure, but one day, Bitcoin will also face the time to replace the hash algorithm. At that time, the cryptocurrency and developer community will soon reach Consistent, and then replaced SHA 256 with a more powerful hashing algorithm in the form of a hard fork (Note: Bitcoin code maintainer Pieter Wuille reposted the latest SHA1 collision research at the first moment. ) .

We will continue to update Blocking; if you have any questions or suggestions, please contact us!