SHA-1 Freestart Collision

There's a new cryptanalysis result against the hash function SHA-1:

Abstract: We present in this article a freestart collision example for SHA-1, i.e., a collision for its internal compression function. This is the first practical break of the full SHA-1, reaching all 80 out of 80 steps, while only 10 days of computation on a 64 GPU cluster were necessary to perform the attack. This work builds on a continuous series of cryptanalytic advancements on SHA-1 since the theoretical collision attack breakthrough in 2005. In particular, we extend the recent freestart collision work on reduced-round SHA-1 from CRYPTO 2015 that leverages the computational power of graphic cards and adapt it to allow the use of boomerang speed-up techniques. We also leverage the cryptanalytic techniques by Stevens from EUROCRYPT 2013 to obtain optimal attack conditions, which required further refinements for this work. Freestart collisions, like the one presented here, do not directly imply a collision for SHA-1.

However, this work is an important milestone towards an actual SHA-1 collision and it further shows how graphics cards can be used very efficiently for these kind of attacks. Based on the state-of-the-art collision attack on SHA-1 by Stevens from EUROCRYPT 2013, we are able to present new projections on the computational/financial cost required by a SHA-1 collision computation. These projections are significantly lower than previously anticipated by the industry, due to the use of the more cost efficient graphics cards compared to regular CPUs. We therefore recommend the industry, in particular Internet browser vendors and Certification Authorities, to retract SHA-1 soon. We hope the industry has learned from the events surrounding the cryptanalytic breaks of MD5 and will retract SHA-1 before example signature forgeries appear in the near future. With our new cost projections in mind, we strongly and urgently recommend against a recent proposal to extend the issuance of SHA-1 certificates by a year in the CAB/forum (the vote closes on October 16 2015 after a discussion period ending on October 9).

Especially note this bit: "Freestart collisions, like the one presented here, do not directly imply a collision for SHA-1. However, this work is an important milestone towards an actual SHA-1 collision and it further shows how graphics cards can be used very efficiently for these kind of attacks." In other words: don't panic, but prepare for a future panic.

This is not that unexpected. We've long known that SHA-1 is broken, at least theoretically. All the major browsers are planning to stop accepting SHA-1 signatures by 2017. Microsoft is retiring it on that same schedule. What's news is that our previous estimates may be too conservative.

There's a saying inside the NSA: "Attacks always get better; they never get worse." This is obviously true, but it's worth explaining why. Attacks get better for three reasons. One, Moore's Law means that computers are always getting faster, which means that any cryptanalytic attack gets faster. Two, we're forever making tweaks in existing attacks, which make them faster. (Note above: "...due to the use of the more cost efficient graphics cards compared to regular CPUs.") And three, we regularly invent new cryptanalytic attacks. The first of those is generally predictable, the second is somewhat predictable, and the third is not at all predictable.

Way back in 2004, I wrote: "It's time for us all to migrate away from SHA-1." Since then, we have developed an excellent replacement: SHA-3 has been agreed on since 2012, and just became a standard.

This new result is important right now:

Thursday's research showing SHA1 is weaker than previously thought comes as browser developers and certificate authorities are considering a proposal that would extend the permitted issuance of the SHA1-based HTTPS certificates by 12 months, that is through the end of 2016 rather than no later than January of that year. The proposal argued that some large organizations currently find it hard to move to a more secure hashing algorithm for their digital certificates and need the additional year to make the transition.

As the papers' authors note, approving this proposal is a bad idea.

More on the paper here.

Posted on October 8, 2015 at 11:44 AM • 14 Comments

Comments

AJWMOctober 8, 2015 1:07 PM

Not just GPUs instead of CPUs. If someone really wants to speed things up they could build custom hardware out of FPGAs or ASICs, like EFF's DES cracker of almost two decades ago, or Bitcoin mining engines today.

Which only reinforces the point.

GAZZAOctober 8, 2015 9:18 PM

Does this imply that RFC2898 (which is based on SHA-1 under the covers, at least in Microsoft's implementation) is also something we should be moving away from, perhaps to bcrypt?

metaschimaOctober 8, 2015 10:14 PM

Although SHA-1 may soon no longer be collision resistant, it can still be used as a one-way hash function, because AFAIK there are no practical full-round preimage attacks on SHA-1. So, it could still be used as a hash for a one-way password file and modification-detection encapsulated by encryption.

GweihirOctober 8, 2015 11:01 PM

@metaschima:

Yes. Also, for secure password storage, you iterate the hash (say, > 100'000 times), and use at least something like BPKDF2 and a salt in addition. That puts pre-image attacks so much out of reach compared to a single iteration, it is not even funny anymore.

curiousOctober 9, 2015 5:29 AM

I'd like to hear your opinion(s) about digital locking system called Iloq, which advertizes itself as secure and uses, surprise surprise, SHA-1.

http://www.iloq.com/
"Powerful encryption and security features."
"Proven communication and software technologies."
"The iLOQ S10 Locking system is managed via the Internet."
"Unique SHA-1 chip."


https://www.youtube.com/watch?v=empOqaqXHvQ
"Marc Tobias: Security_Alert_Iloq_2012"
after this video it was recommended to change ALL the locks, but resulted in basically none.. unless the individual customer him/herself asked for it.

https://www.youtube.com/watch?v=1KS7nbHIRcY
"See a ILOQ C10S Lock Get Broken into in Under a Minute"

https://www.youtube.com/watch?v=ALZn-NLif_Y
"iLOQ pwned"
and here's someone asking 120keur for keys to the kingdom..

AlexT October 9, 2015 6:05 AM

Wondering if Google knows something we don't... Their decision to press ahead with deprecating SHA-1 earlier this year might need to be revisited after reading this.

SJOctober 9, 2015 8:21 AM

Could one of those large companies be Micrsoft and related to use of WinXP with MSIE? Some asian countries (I think South Korea and parts of China) still have to relay on ActiveX in MSIE 6.0 (I think) for online banking.

I thought I heard that that newer SHA won't run on XP and hence that additional year is required.

Fascist NationOctober 9, 2015 10:47 AM

".... some large organizations currently find it hard to move to a more secure hashing algorithm for their digital certificates and need the additional year to make the transition." ....

I am so sick of complaining online, via e-mail and snail mail to IT, marketing depts. and CEOs of companies I do online purchases from when I try to carry out those transactions only to find myself being compelled to use an insecure (or in one case, US Air, non-existent) security protocol. RC4 or DHE, and now SHA-1 (though it still takes a fair amount of computing power). And a reluctance to upgrade encryption algorithms on servers.

All I get are assurances that they care and have the bestest, most secure interactions in the world when the links I provide prove otherwise. The airlines--which demand my security--are the worst. I don't buy from Monoprice anymore. I could go on listing businesses... but there are occasional ones that really shine on securing their connections. [How many people even check?]

CuriousOctober 10, 2015 4:06 AM

If I understood it correctly, someone on twitter seem to have pointed out that simply looking at the pricing for Amazon Elastic Compute Cloud (Amazon EC2) to calculate cost of computing power is a bad idea, when desktop GPU's with more power cost less.

"IOW if hash analysis is your thing, ignoring spot pricing, $1,890/mo for 4GPUs on ec2 gets you about 75% performance of a $340 desktop GPU."

I have no idea at all myself if those numbers are correct though.

rgaffOctober 10, 2015 7:04 PM

@Developer Francis

Sure. Right after the time machine that can let us see infinitely far into the future...

metaschimaOctober 11, 2015 11:29 PM

Well, technically the one-time pad is 100% future proof if done right. However, it is quite impractical. Still, cold war era messages are safe even today, and probably will be forever.

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of IBM Resilient.