Pierluigi Paganini February 24, 2017

Experts at Google and CWI conducted the first real world collision attack against popular SHA-1 hashing algorithm, so called shattered-attack.

Researchers at Google and Centrum Wiskunde & Informatica (CWI) in the Netherlands succeeded in conducting the first real world collision attack against popular SHA-1 hashing algorithm.

The researchers created two documents with different content but having the same SHA-1 hashes.

Google and CWI devised a hacking method dubbed ‘SHA-1 shattered’ or ‘SHAttered.’

“We were able to find this collision by combining many special cryptanalytic techniques in complex ways and improving upon previous work. In total the computational effort spent is equivalent to 2 63.1 SHA-1 compressions and took approximately 6 500 CPU years and 100 GPU years,” experts wrote in the research paper.

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.

In 2015 a group of researchers demonstrated that the cost of breaking the SHA-1 hash algorithm is lower than previously estimated.

The experts evaluated the economic effort requested to break the SHA1-1, experts in a range from $75,000 and $120,000 using Amazon’s EC2 cloud over a period of a few months.

According to the experts, the SHAttered attack is 100,000 times faster than a brute-force attack, it required nine quintillion (9,223,372,036,854,775,808) computations.

The SHAttered attack was composed of two phases:

• the first phase of the attack was run on a heterogeneous CPU cluster hosted by Google and spread across eight physical locations.
• the second phase of the attack was run on a heterogeneous cluster of K20, K40 and K80 GPUs hosted by Google.

The monetary cost of computing the second block of the attack by renting Amazon instances can be estimated from these various data. According to the experts, it would cost roughly $560,000 for the necessary 71 device years. It would be more economical for a patient attacker to wait for low “spot prices.”

The experts used two PDF files with different content for their PoC, the two documents had the same SHA-1 hash.

The researchers will release the code of the attack after 90 days.

The experts released a free online tool that scans for SHA-1 collisions in documents, it is available on the shattered.io website. Google has already introduction mitigation solutions in both Gmail and Google Drive services.

I suggest you give a look at this interesting infographic on the SHAttered attack.

[adrotate banner=”9″]

Pierluigi Paganini

(Security Affairs – SHAttered attack,  SHA-1)