Slashdot Mirror
Google Has Demonstrated a Successful Practical Attack Against SHA-1 (googleblog.com)
Reader Artem Tashkinov writes: Ten years after of SHA-1 was first introduced, Google has announced the first practical technique for generating an SHA-1 collision. It required two years of research between the CWI Institute in Amsterdam and Google. As a proof of the attack, Google has released two PDF files that have identical SHA-1 hashes but different content. The amount of computations required to carry out the attack is staggering: nine quintillion (9,223,372,036,854,775,808) SHA1 computations in total which took 6,500 years of CPU computation to complete the attack first phase and 110 years of GPU computation to complete the second phase.
Google says that people should migrate to newer hashing algorithms like SHA-256 and SHA-3, however it's worth noting that there are currently no ways of finding a collision for both MD5 and SHA-1 hashes simultaneously which means that we still can use old proven hardware accelerated hash functions to be on the safe side.
Google says that people should migrate to newer hashing algorithms like SHA-256 and SHA-3, however it's worth noting that there are currently no ways of finding a collision for both MD5 and SHA-1 hashes simultaneously which means that we still can use old proven hardware accelerated hash functions to be on the safe side.
It is all about cost-benefit. CPU speeds continue to get faster, and renting CPU time on cloud providers become cheaper and cheaper.
Why is this significant? There are still major certificate authorities out there with intermediate certificates using SHA-1. Find a collision for these certificates, and you essentially become a new intermediate certificate authority with the ability to issue domain certs for basically anything you want and they'll validate in browsers.
Now thing of government agencies or crime syndicates that could afford the CPU/GPU time to do this. It is a highly practical attack vector now.
If one looks at the history of what happened the last time a major hash was broken, there was a large gap between when MD5 has its first collisions and when it became practical to detect collisions. There was about a little under a decade between when the first collisions were found and when it became easy to find collisions. The general expectation is that hash systems will fail gracefully in a similar way so we have a large amount of warning to switch over. Unfortunately, we've also seen that in practice people don't adopt new hash algorithms nearly as fast as they should. The second to last Yahoo security breach was so bad in part because the passwords were hashed with a completely unsalted MD5 https://nakedsecurity.sophos.com/2016/12/15/yahoo-breach-ive-closed-my-account-because-it-uses-md5-to-hash-my-password/. The lack of salting would have been by itself a problem even when MD5 was still considered insecure. That in 2015, a decade after MD5 was broken for almost all purposes, Yahoo was still using it, is appalling. Unfortunately, they likely aren't the only one. And I fully expect that if Slashdot is around in a decade we'll read about someone who has foolishly stored passwords using SHA-1.
If Google can do that, NSA can surely do that - maybe not right now but quite soon.
Also don't underestimate various botnets - right now they are mostly used for spamming/DDOS'ing/crypto currency mining (which in itself is ... hashing) but they can be used for finding collisions in SHA-1 as well.
Also don't forget that "practical" in this case means that an attack can be carried out using currently existing availble computational resources, vs. something purely theoretical which requires billions of CPUs/GPUs or quantum computers.
Any crypto geeks want to weigh in on the truth of this statement? I've often wondered about this. Wouldn't using two hash algorithms be easier and more effective over the long term than getting the whole world to upgrade to the Latest And Greatest Hash every ~10 years?
The key sequence to access my Slashdot bookmark in Firefox is Alt-B-S. I don't believe this is a coincidence.
Well, what exactly a time unit of CPU computation means isn't defined (it's like saying "This item cost me 500 monetary units", there's no context), but if we just take it to mean a literal amount of time on any random CPU...
6,500 years of CPU time potentially costs as little as ~$171k USD at Amazon, and compute costs are continuously falling.
Not a lot you can do?
Anything that requires signatures is vulnerable to forgery if the signer's certificate specifies SHA1.
An attacker could forge:
1. Software signatures - to slip malware into a software vendor's distribution channels.
2. SSL certificates - to MITM web connections to phish, steal data, or distribute malware.
3. Personal digital signatures - to fabricate documents, including emails, transaction, orders, etc that are normally trusted implicitly due to the signature
4. Subordinate CA certificates - to create trusted certificates which permit all of the above
The problem lies with #4. The real risk is not a one-off duplicate of John Doe's smart card. The real danger is the CAs signed with SHA1 who are still trusted by browsers, applications, and OSes around the world. If an attacker counterfeits one of their certificates, he can issue arbitrary certificates for any web site, any software publishers, or any user.
The only solution is to discontinue the use of SHA1 internally and to revoke trust for all CAs that still use SHA1. Better crypto has existed for a long time---the standard for SHA2 was finalized in 2001, well over a decade ago.
---
According to the latest ruleset, this post should be modded as Vorpal Flamebait +5.
A 10 million strong botnet would need +/- 3 years per key under ideal circumstances here.
Aren't you off by a few orders of magnitude there? 6,500 years of computation time divided by 10,000,000 bots would be about 5 hours and 42 minutes, not 3 years.
Even your hypothetical 10,000-strong botnet could do it in about 8 months, which might be well worth it if it meant being able to hijack a cert that could be leveraged in interesting ways (e.g. using it to sign your malware as an official update for the company).
I occasionally use a signed .jar in the company intranet. Reading TFA, I wondered what hash is used to sign that? It seems that jarsigner is not willing to divulge, so I had to write a little piece of code aaand ... yup, it's SHA1!
How common is this? Is loads of software now susceptible to attack by replacing a original code by a malware with the same SHA1?
The data was crafted in order to simplify attaining their goal. It would be far more damning if they could put together a document that results in the same SHA-1 hash as that of an externally specified document.
One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than kT, where T is the absolute temperature of the system and k is the Boltzman constant. (Stick with me; the physics lesson is almost over.)
Given that k = 1.38×10^-16 erg/Kelvin, and that the ambient temperature of the universe is 3.2 Kelvin, an ideal computer running at 3.2K would consume 4.4×10^-16 ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump.
Now, the annual energy output of our sun is about 1.21×10^41 ergs. This is enough to power about 2.7×10^56 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2^192. Of course, it wouldn't have the energy left over to perform any useful calculations with this counter.
But that's just one star, and a measly one at that. A typical supernova releases something like 10^51 ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.
These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.
I want crypto that has a good chance of outlasting the heat death of the universe even with a quantum computer. For symmetric key crypto this means you would need somewhere around a 601 bit keyspace IIRC before you exceed the mass energy of the universe.
Time to offend someone
I know you are trying to be funny, but you are inadvertently correct. Everyone here seems to be assuming they are using the definition which is the opposite of 'impractical', when they are actually using the definition meaning 'not just theoretical'.
Not a lot you can do?
Anything that requires signatures is vulnerable to forgery if the signer's certificate specifies SHA1.
An attacker could forge:
1. Software signatures - to slip malware into a software vendor's distribution channels.
That requires a second pre-image attack, not just a collision attack. (What gweihir called "two-sided" rather than "one-sided"... though that is not standard terminology).
2. SSL certificates - to MITM web connections to phish, steal data, or distribute malware.
Also requires a second pre-image attack.
3. Personal digital signatures - to fabricate documents, including emails, transaction, orders, etc that are normally trusted implicitly due to the signature
This one can be done with a collision attack. You generate two different documents which hash to the same value, but have different contents. The PDF format, unfortunately, make it pretty easy to generate documents which look sensible and have this property. It's not possible with more transparent formats (not without a second pre-image attack).
4. Subordinate CA certificates - to create trusted certificates which permit all of the above
The problem lies with #4.
This can only be done with a collision attack if the CA is really, really stupid. Proper CAs should include chain-length restrictions in their certificates. That way even if you can create two certificates which hash to the same value, one of which has the keyCertSign bit set to true (which the CA would refuse to sign) and one of which does not (which presumably you can get the CA to sign), it wouldn't matter because if you used the former to generate other certs, no one would accept them due to the fact that your chain is too long.
The only solution is to discontinue the use of SHA1 internally and to revoke trust for all CAs that still use SHA1.
I certainly agree that any CA still issuing certificates with SHA1 should not be trusted. Any existing certs based on SHA1 should be scrutinized, but most of them are still secure.
Better crypto has existed for a long time---the standard for SHA2 was finalized in 2001, well over a decade ago.
Absolutely. Of course, I say that as the maintainer (ish) of an open source crypto library that still uses SHA1. In systems that weren't originally designed for digest agility, it's often hard to retrofit. Today's news is a nice kick in the pants, though.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
This can only be done with a collision attack if the CA is really, really stupid. Proper CAs should include chain-length restrictions in their certificates.
Please correct me if I'm wrong, but it appears that most CAs are really, really stupid. Here's a list of the CAs included in Firefox: https://mozillacaprogram.secur... . I split the PEMs into a pile of files, and checked them:
$ for pem in * ; do openssl x509 -text -in $pem | grep pathlen ; done
CA:TRUE, pathlen:4
CA:TRUE, pathlen:1
CA:TRUE, pathlen:1
CA:TRUE, pathlen:7
CA:TRUE, pathlen:7
CA:TRUE, pathlen:3
CA:TRUE, pathlen:5
CA:TRUE, pathlen:12
CA:TRUE, pathlen:12
CA:TRUE, pathlen:12
CA:TRUE, pathlen:12
CA:TRUE, pathlen:3
CA:TRUE, pathlen:10
CA:TRUE, pathlen:3
So out of 172 root CAs only 14 include any path length restrictions, and even the ones who do still allow some chaining. This is what allowed the beautiful Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate to succeed.
I don't think the SHApocalypse will be tomorrow. This was an identical-prefix attack instead of a chosen-prefix which constrains the attacker considerably, and the computation required is much higher even to generate simple collisions. However, (again, please correct me if I'm missing something) it does seem plausible that that further weaknesses will be found which provide just enough leverage to forge a signature with one of those 172 CAs, and we may eventually see a rogue sha1WithRSAEncryption CA issued.
You can do it cheaper by using botnets rather than legitimate resources.