SHA1 algorithm securing e-commerce and software could break by year’s end

SHA1, one of the Internet’s most crucial cryptographic algorithms, is so weak to a newly refined attack that it may be broken by real-world hackers in the next three months, an international team of researchers warned Thursday.

SHA1 has long been considered theoretically broken, and all major browsers had already planned to stop accepting SHA1-based signatures starting in January 2017. Now, researchers with Centrum Wiskunde & Informatica in the Netherlands, Inria in France, and Nanyang Technological University in Singapore have released a paper that argues real-world attacks that compromise the algorithm will be possible well before the cut-off date. The results of real-world forgeries could be catastrophic since the researchers estimate SHA1 now underpins more than 28 percent of existing digital certificates.

Hashing it out

SHA1 is what’s known as a cryptographic hash function. Like all hash functions, it takes a collection of text, computer code, or other message input and generates a long string of letters and numbers that serve as a cryptographic fingerprint for that message. Even a tiny change, such as the addition or deletion of a single comma in a 5,000-word e-mail, will cause a vastly different hash to be produced. Like all fingerprints, the resulting hash is useful only as long as it’s unique. The moment two different message inputs produce the same hash, the so-called collision can open the door to signature forgeries that can be disastrous for the security of banking transactions, software downloads, and website communications.

A series of attacks on MD5, a hashing algorithm that’s much more collision-prone than SHA1, provides a glimpse at the dire results of collision attacks. The Flame espionage malware, which the US and Israel are reported to have unleashed to spy on sensitive Iranian networks, wielded such a collision attack to hijack Microsoft’s Windows Update mechanism so the malicious program could spread from computer to computer inside an infected network. Separately, in 2008, a team of computer scientists and security researchers used the technique to forge a master secure sockets layer certificate that could authenticate virtually any website of their choosing.

MD5 has since been largely abandoned for use in generating digital signatures, although it still remains viable in other cases. (Notably, MD5 is also unsuitable for cryptographically protecting passwords, but this has nothing to do with its susceptibility to collision attacks.) SHA1, by contrast, is considerably more resistant than MD5 to collisions, although it too has long been considered vulnerable. In 2012, cryptographers warned that the growing advances in computing made real-world collision attacks against SHA1 viable by 2018.

The 2012 warning was based on contemporaneous estimates from Bruce Schneier that it would cost $700,000 to perform a full-on collision attack on SHA1 by 2015 and, thanks to the ever-advancing speed of computers, just $173,000 by 2018. That latter amount, Schneier reasoned, was well within the budget of a well-financed criminal hacking group. Now, based on research completed last month, the international team of researchers believe that such an attack could be carried out this year for $75,000 to $120,000. The much lower cost is the result of efficiencies the researchers discovered in the way graphics cards can use a technique known as “boomeranging” to find SHA1 collisions.

The estimate was based on the researchers’ ability to carry out a successful collision attack on the SHA1 compression function. While not a collision on the actual SHA1 algorithm itself, the feat nonetheless invalidates the security proof upholding the algorithm and demonstrated the soundness of the new graphics-card technique.

“Our new GPU-based projections are now more accurate and they are significantly below Schneier’s estimations,” the researchers wrote in their paper. “More worrying, they are theoretically already within Schneier’s estimated resources of criminal syndicates as of today, almost two years earlier than previously expected, and one year before SHA-1 being marked as unsafe in modern Internet browsers. Therefore, we believe that migration from SHA-1 to the secure SHA-2 or SHA-3 hash algorithms should be done sooner than previously planned.”