It’s official. SHA-1 has been broken. As reported on pretty much every tech-focused news source and blog yesterday, two PDFs were created resulting in identical SHA-1 hashes. For years, security experts and cryptographers from industry to government, have warned against the use of SHA-1 as it was theoretically broken, just not practically (well…that we know of) – until yesterday. Why is this important? SHA-1 is used to verify, for instance, the authenticity of a website, message, or piece of software. When you log into to an HTTPS site, you trust that it is, e.g., your banks’ actual site. How do you know? Well, your browser verifies this for you by way of a third party’s digital signature. That is, you don’t trust a website based on its word, your trust it because a Certificate Authority like GoDaddy says you can. This attack now makes it theoretically possible to forge a signature (which is much harder than generating two files with meaningless content that collide), tricking your browser into thinking the page is safe when it is not. Chrome has already begun providing users with a notice if a site is signed with a SHA-1 certificate. After hearing the news, Firefox following suit TODAY. This example is trivially extended to message authentication (e.g., HMAC) and software validation (especially GIT).
SHA-1 Broken
SHA-1 is in the same algorithmic family as the broken MD5 (Merkle-Damgård). As a result, researchers have been weary about SHA-1 as MD5 attacks can threaten (and have now broken, in-part) SHA-1. SHA-2 is also in the same family and while it has no known vulnerabilities, it has already been replaced with SHA-3 (announced in FIPS PUB 202 in August 2015), which is based on an entirely different mathematical family (permutations).
According to the birthday paradox, a collision should occur in approximately 2number of bits/2 pair creation attempts. Since SHA-1 is 160 bits, that equates to roughly 280 cycles. That’s a huge number and considered safe (the current rule is 80+ is good). However, an attack was developed by researchers from Centrum Wiskunde and Informatica (CWI) in the Netherlands, Nanyang Technological University in Singapore, and INRIA in France, which would reduce the number considerably. CWI enlisted the assistance of Google to implement the attack because an immense amount of hardware was required to test their theory. Low and behold, they succeeded.
The details can be found on a dedicated website called “shattered.io“. While many of the specifics are being withheld for the customary 90-day period from announcement to full debriefing (to allow migration to new standards before attackers are given a blueprint for exploitation), they did provide some excellent stats. Let’s have a look:
- The attack required just a touch shy of 263.1 SHA-1 compressions – 9,223,372,036,854,775,808 – not something you can do on your laptop, but definitely in the realm of reason from a nation state.
- If executed on a single CPU, it would have taken approximately 6,500 years.
- If executed on a single GPU, it would have taken approximately 100 years.
- It would take 110 GPU’s 1 full year – sub-linear scaling due to communication overhead I presume; otherwise, their paper and infographic disagree.
- Bruteforcing the SHA-1 keyspace would have taken about 12,000,000 GPU’s to reach the same conclusion in a single year.
What should we use
The state-of-the-art is SHA-3. Unfortunately, it has not been around long enough to have made its way into some programming languages. For instance, Java 8 does not have a SHA-3 API as of yet. However, it is slated for Java 9 – JEP 287. Bouncy Castle (an excellent source of security API’s in general) does have a SHA-3 implementation available as a Jar. Other than SHA-3, SHA-256 (part of SHA-2) is perfectly safe at this point. There are no known attacks on the full key, so the best known attack is bound by the birthday paradox at 2128 – “safe”.