Monkey see, monkey patch...Frank Breedijk
Every now and then there is major new in the world of cryptography, or in this case the world of breaking cryptography. This month a team from CWI (Centrum voor Wiskunde en Informatica) and Google announced that they have created a practical attack, called SHAttered, on the SHA-1 hashing algorithm.
What is SHA-1?
SHA-1 stands for Secure Hashing Algorithm – 1. As the name suggests it is a hashing algorithm. A hashing algorithm can be used to transfer a block of data into a single value that is unique for that file, a so-called digest. In order for a hashing algorithm to be secure it must be computationally infeasible to generate a second message that has the same digest. This property allows digests to function as proof that a message has not been altered. If I have a message and its original digests, you can compute a new digest of the message and if these two digests are the same the message has nog been altered.
Hashing algorithms are the work horses of cryptography, they are used to sign messages, to store passwords securely, to exchange keys and various other uses.
Dove Cote a CC SA image by Craig Chew-Moulding (https://www.flickr.com/photos/69037709@N00/6372028137/)
All hashing algorithms suffer a common problem. This problem is commonly described as a pigeonhole problem. For practical reasons the size of a digest is limited. Since SHA-1 produces a digest of 160 bits (20 bytes) long there are a lot of possible combinations. It can be calculated as follows: 2160 » 1.461 * 1048. A very large number of possibilities. It is e.g. larger than the estimated number of stars in the universe (1022) or the number nanoseconds that has passed since the big bag (» 4.339 x 1026), but smaller than the estimated number of atoms in the universe (1081). However, any messages that is longer than the 20 bytes used for the digest has a number of possible combinations that is larger than the number of available digests. Just as having a pigeon flock bigger that the number of pigeonholes in your dovecote means that two pigeons have to share the same hole. Having more possible messages than possible digests means that there must be at least two messages that share the same digest.
In an ideal world, the pigeons in a dovecote would distribute themselves evenly over the available pigeonholes. But, not all pigeonholes are created equally and thus some pigeonholes are more popular than others. This means that doves will start fighting over pigeonholes even before the flock is larger than the number of available pigeonholes. The same is true for hashing algorithms. Ideally, messages would be mapped evenly over digests. Thus, flipping a random bit in the message would lead to a completely new and unpredictable digest.
SHA-1 is not perfect, and this has been known for quite a while. In February 2005 researchers Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu where able to create a method to find collisions (two messages having the same digest) in SHA-1 in a more economical fashion than simply trying out all possible combinations until a collision occurs (known as a brute force attack). This resulted in NIST officially deprecating SHA-1 in 2011.
So, what is SHAttered?
SHAttered is the first attack against the SHA-1 algorithm that has demonstrated that it is “practically” possible to generate two PDF documents with visually different content and an identical SHA-1 digest. SHAttered cleverly abuses the fact that the SHA-1 of the first block of a file is used as a starting value for the second black, the SHA-1 of the second block is then used as imput for the SHA-1 of the third block, etc, etc. They figured out a way to change the first block and then change the second block to compensate for the changes made in the first block.
This attack was hard to compute; it took them 9,223,372,036,854,775,808 SHA-1 computations to compute this collision. Which is equivalent of having a cluster of 110 GPUs processing for a single year (in contrast a brute force attack would have taken a 12,000,000 GPU cluster a full year).
But, now that the ghost is out of the lamp, everybody can create two differently looking PDFs with an identical SHA-1 digest. The project has promised to release tools which can do this after the 24th of May 2017.
But, but, why?
Stamp letter Y – A CC NC SA image by Leon Reynolds (https://www.flickr.com/photos/49968232@N00/19433535236/)
The saying “Attacks always get better; they never get worse” is most commonly attributed to the NSA. This means that once an algorithm is shown to be weak, it will at some point be too weak to use it. Since MD5 was proven to be insecure, SHA-1 has been the workhorse of cryptography and replacing is going to take a lot of effort.
Before SHAttered, people could/would claim that attacks against SHA-1 were merely theoretical. SHAttered has shown that these attacks are practical and that SHA-1 is in fact broken for people that can effort it (Amazon spot prices are near USD1.6/hour for 16 GPUs, which puts this attack at around USD 60k).
Because SHA-1 is everywhere it is expected to take a long time to phase it out in favour e.g. SHA-256. What is happening to SHA-1 is similar to what happened to MD5. When it was created in 1990 as MD4 and later on improved as MD5 in 1992 it was known to have weaknesses in the underlying compression function. It was officially banned from use in the HTTPS security system in 2008, yet today in 2017 there are still issues in deprecating it for signatures.
So, what can we do about it?
Stop using SHA-1. As of January 17th , Google Chrome will treat sites that have a certificate with a SHA-1 signature in the chain as insecure. Firefox has done the same as of the 24th of February following the release of SHAttered. Microsoft implemented a change in the Windows 10 Anniversary Update (August 2016) that no longer marks sites with a SHA-1 certificate as secure and the current plan is to deprecate SHA-1 support “mid 2017” (I was unable to find an updated plan for SHA-1 deprication).
There is good news: it is possible to detect this attack. If you are in possession of a file that you feel might be tampered with using this attack you can upload it to https://shattered.io and have it tested. The code for this test has been publicly released, so that it can be built into products. To set an example Google has included detection routines into Gmail and Google Drive.
Monkey See, Monkey Patch?
Now that the world has seen that SHA-1 is indeed broken, there is a lot of work to do fixing it. The Schuberg Philis’ security team is fully aware and helping people with the replacement of SHA-1 based certificates should we still encounter them.