Cost of Breaking SHA-1 decreases due to a new Collision Attack

A group of researchers has demonstrated that the cost of breaking the SHA-1 hash algorithm is lower than previously estimated.

The SHA-1 is still one of the most used cryptographic hash algorithm, but bad news for its supporters, a New Collision Attack Lowers Cost of Breaking it. The news is worrying, the cost and time necessary to break the SHA1 algorithm have fallen rapidly and could probably result in a definitive abandonment.

The SHA-1 algorithm was designed in 1995 by the National Security Agency (NSA) as a part of the Digital Signature Algorithm, as we have already explained in the past hashing functions converts any input message to a string of numbers and letters of fixed length. This string is theoretically unique and is normally used as a cryptographic fingerprint for that message.

If two different messages generate the same digest we are in the presence of a collision, this circumstance opens the door to hackers. A successful collision attack could be exploited by hackers to forge digital signatures.

The process is not reversible, this means that known the message digest and the hashing function used, it is not possible to retrieve the original message.

According to a group of researchers, the SHA-1 algorithm is so weak that it may be compromised by hackers very soon.

The research team is composed of experts from from the Centrum Wiskunde & Informatica in the Netherlands, Inria in France, and Nanyang Technological University in Singapore. They have published a paper that demonstrates that the SHA-1 algorithm is vulnerable to collision attacks. The experts named the attack Freestart Collision.

The evaluation of the economic effort requested to break the SHA1-1, experts estimated that currently it ranges from $75,000 and $120,000.

“However, as remarked in [KPS15] and now further improved in this article thanks to the use of boomerang speed-up techniques [JP07], graphics cards are much faster for this type of attacks (compared to CPUs) and we now precisely estimate that a full SHA-1 collision will cost between 75,000 and 120,000 US$ renting Amazon EC2 cloud over a few months today, in early autumn 2015.” states the research paper.

These numbers could give no information is not compared from an estimation provided in the past. Back in 2012, for example, the popular security expert Bruce Schneier estimated that it would cost $700,000 to carry out a collision attack on SHA1 by 2015, and just $173,000 by 2018.

The findings of this recent study provide a worse scenario for the SHA-1, the cost to break it is dramatically decreased respect the forecast of the experts. The efficiency of the attacks has been improved by the adoption of a new graphics-card technique known as “boomeranging” that allows experts to find SHA-1 collisions. The Researchers managed to perform an attack in 10 days by using the computational capability offered by a 64-GPU cluster.

“Our new GPU-based projections are now more accurate, and they are significant below Schneier’s estimations,” continues the research paper. “More worrying, they are theoretically already within Schneier estimated resources of criminal syndicates as of today, almost 2 years earlier than previously expected and 1 year before SHA-1 being marked as unsafe.”

What to do?

In 2012, the National Institute of Standards and Technology (NIST) recommended that SHA1 digital certificates should not be trusted starting with 2014. Despite the NIST’s advisory, the SHA1 is still widely adopted.

What about the IT giants?

Microsoft announced in 2013, its intention to force the use of the SHA2 algorithm in code signing and SSL certificates from 2014. In September 2014 Google and Mozilla announced that their browsers would stop accepting SHA1-based certificates after January 1, 2017.

It is likely that there will not be an immediate danger for Internet users, anyway, it is important to encourage the migration to more robust hash algorithms, including SHA-2 (developed by the NSA) or SHA-3 (developed by a group of independent researchers).

It is strongly suggested to start thinking to the future, administrators should consider the impact SHA-1 would have in their infrastructure. This means that IT administrators have to consider the migration to hardware and software compatible with SHA-2/SHA-3.

[adrotate banner=”9″]

Pierluigi Paganini

(Security Affairs – hash,  SHA-1)

[adrotate banner=”12″]