Attacks on the SHA-1 hashing algorithm just got a lot more dangerous last week with the discovery of the first-ever “chosen-prefix collision attack,” a more practical version of the SHA-1 collision attack first carried out by Google two years ago.
What this means is that SHA-1 collision attacks can now be carried out with custom inputs, and they’re not just accidental mishaps anymore, allowing attackers to target certain files to duplicate and forge.
SHA-1 collision attacks
The SHA-1 hashing function was theoretically broken in 2005; however, the first successful collision attack in the real world was carried out in 2017.
Cryptographers predicted SHA-1 would be broken in a real-world scenario, but the SHAttered research came three years earlier than they expected, and also cost only $110,000 to execute using cloud-rented computing power, far less than what people thought it might cost.
SHA-1 chosen-prefix attacks
But last week, a team of academics from France and Singapore has taken the SHAttered research one step further by demonstrating the first-ever SHA-1 “chosen-prefix” collision attack, in a new research paper titled “From Collisions to Chosen-Prefix Collisions – Application to Full SHA-1.”
“Finding a practical collision attack breaks the hash function badly of course, but the actual damage that can be done with such a collision is somewhat limited as the attacker will have little to no control on the actual data that collides,” Thomas Peyrin, one of the researcher told ZDNet via email over the weekend.
“A much more interesting attack is to find a so-called ‘chosen-prefix collision,’ where the attacker can freely choose the prefix for the two colliding messages. Such collisions change everything in terms of threat because you can now consider having collisions with meaningful data inside (like names or identities in a digital certificate, etc).”
What this means is that SHA-1 collision attacks aren’t a game of roulette anymore, and now, threat actors can forge any SHA-1-signed documents they want, ranging from business documents to TLS certificates.
SHA-1 chosen-prefix collision attacks are now also cheap
But the work of Peyrin and his colleague –Gaetan Leurent– have done goes far beyond than proving SHA-1 chosen-prefix collision attacks are theoretically possible.
They also showed that such attacks are now cheap and in the budget of cybercrime and nation-state attackers.
“These chosen-prefix collisions are believed to be much harder to find than classical collisions. For SHA-1, the best previous search method required 2^77 SHA-1 evaluations, which remained out of reach in practice,” Peyrin told ZDNet.
“The novelty in our article is that we explain how to drastically reduce the cost of finding chosen-prefix collisions for SHA-1, down to almost the same cost as finding a classical collision,” he said.
“We are currently working on further improvements (unpublished yet), and we evaluate now that one can find a chosen-prefix collision for SHA-1 with a budget of less than $100,000, which is really practical.”
This is about the same cost as the original SHAttered research, yet, this version of the attack is what attackers would likely use if they’d ever want to attack SHA-1-protected data.
“We have tested all subcomponents of the attack, but we have not tried to compute a chosen-prefix collision example,” Peyrin said.
“Our initial estimations were $1 million to compute the chosen-prefix collision, which is an amount of money we simply don’t have. Thanks to our latest improvements, the cost went down below $100,000 and we are currently working on computing the first chosen-prefix collision for SHA-1.
“Hopefully, we will be able to announce new results soon,” the researcher said.
Moving away from SHA-1
Browser vendors have long ago started deprecating support for SHA-1-signed TLS traffic inside their products; however, other applications still rely on it.
“There are still many users with older browsers and many protocols and software that allow SHA-1 signatures. Concretely, it is still possible to buy an SHA-1 certificate from a trusted CA, and many email clients accept an SHA-1 certificate when opening a TLS connection,” Peyrin told us.
“SHA-1 is also widely supported to authenticate TLS and IKE handshake messages. Now, what protocol can be attacked and to what extent is hard to tell at the moment, because it needs careful scrutiny of the inner working of the protocol and how the digital signatures / certificates are used, etc..
“However, what we can say is that our attack put at possible risk products using digital signatures, or certificates based on SHA-1,” Peyrin said.
“The take-home message should really be that using SHA-1 for digital
signatures or certificates is very dangerous, and should not be allowed. People doing so are strongly advised to change to SHA-2 or SHA-3 now.”
What to use?
“The attacks against SHA-1 are only going to get better,” Scott Arciszewski, Chief Development Officer at Paragon Initiative Enterprises, and a leading cryptographer, told ZDNet in a separate email.
“Everyone should switch to (in order of preference):
- BLAKE2b / BLAKE2s
- Any other SHA2-family hash function as a last resort
“…unless they’re storing passwords! In which case, they should switch to (in order of preference):
- Argon2id with memory >= 32MiB, >= 2 rounds, and >= 2 parallelism
- scrypt / yescrypt with memory >= 32 MiB, >= 4 rounds, and >= 1 parellelism
- bcrypt (for PHP devs, password_hash() and password_verify() does the trick)
- PBKDF2-SHA512 with 85,000 iterations as a last resort
“But SHA1 should no longer be used anymore. No excuses,” Arciszewski said.