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.

Comments

Re:Practical?

[darkain]

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.

Re:Practical?

[Bob the Super Hamste]

Ever since I read this blurb from Applied Cryptography by Bruce Schneier years ago it has really put things into perspective when it comes to what is strong crypto and what isn't. I got the concept from him so it isn't my own idea even if I did simplify the explanation of it.:

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.