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."
The paper noted that the collisions involved in the research are known as identical-prefix collisions, as opposed to the significantly more severe and costly chosen-prefix collisions at the heart of Flame's attack on Windows Update or the 2008 certificate authority impersonation. Identical-prefix collisions still allow signature forgeries, but their capabilities are far less flexible than chosen-prefix collisions.
Identical-prefix collisions, for example, allow for two different executable files that nonetheless generate the same digital signature. They also allow for colliding PDF documents that show different content. They also make it possible to generate colliding certificates, but those are only different in the public key, and not different in, say, the identities' name, so they can't be easily abused.
Kicking the can
Thursday's research showing SHA1 is weaker than previously thought comes as browser developers and certificate authorities are considering a proposal that would extend the permitted issuance of the SHA1-based HTTPS certificates by 12 months, that is through the end of 2016 rather than no later than January of that year. The proposal argued that some large organizations currently find it hard to move to a more secure hashing algorithm for their digital certificates and need the additional year to make the transition.
The paper was written by Marc Stevens, Pierre Karpman, and Thomas Peyrin. The new calculations, should they be confirmed by the researchers' peers, are likely to provide a strong argument for voting no and instead quickly migrating to use of SHA2, which is much more resistant to collisions.
reader comments
66