Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Announcing the first SHA-1 collision

security.googleblog.com

Post reply on HN
Print view View original

371–380 of 524 posts

Re: Announcing the first SHA-1 collision

#371

Post by rocqua »

kuschkufan wrote: post #222
cesarb wrote: post #119

On a quick scroll of the comments, I haven't seen this posted so far: http://valerieaurora.org/hash.html We're at the "First collision found" stage, where the programmer reaction is "Gather around a co-worker's computer, comparing the colliding inputs and running the hash function on them", and the non-expert reaction is "Explain why a simple collision attack is still useless, it's really the second pre-image attack…

Love this page. Someone should remind her to update the table for sha1 now.

It seems to have been updated already.

Re: Announcing the first SHA-1 collision

#372

Post by pfg »

Lord_Yoda wrote: post #364

As I consumer how do I identify sites which are vulnerable? What should I do to protect my data?

Recent versions of Chrome will show a warning if you try to browse to a site that uses a SHA-1 certificate. Mozilla is doing the same thing as of Firefox 51, but they're enabling this gradually to measure impact. Microsoft has an update ready to disable SHA-1 support in their browsers - I think it was delayed a few days ago due to some issues (not sure if they were related to disabling SHA-1).

You can use [1] to test how your browser behaves.

Technically, the sites cannot be said to be vulnerable because of their SHA-1 usage. Rather, continuing issuance of SHA-1 certificates by publicly-trusted CAs increases the risk that someone obtains a certificate that collides with a certificate for a different domain or for a certificate that could be used to sign other certificates for sites the attacker does not own. [2] does a good job of explaining this. The mitigation for this is to use a browser that disables (or warns about) SHA-1 certificates. Publicly-trusted CAs are also not supposed to continue issuing these certificates, but there have been quite a number of cases where they did so anyway - most notably WoSign.

Of course, a site might use SHA-1 for other things behind the scenes. There's really no way to detect that in general.

[1]: https://sha1-2017.badssl.com/

[2]: https://news.ycombinator.com/item?id=13715717

Re: Announcing the first SHA-1 collision

#373

Post by shawabawa3 »

ddlatham wrote: post #365
Gankro wrote: post #358

Earlier quoted context omitted.

You seem to be mistaking or misreading something here. * Collision attack: find X and Y such that hash(X) = hash(Y) * Second-preimage: given X, find Y such that hash(X) = hash(Y) * First-preimage: given hash(X), find Y such that hash(X) = hash(Y) > If you have an encrypted message that you hashed/signed _before_ encrypting, and Eve wants to know what you said, first-preimage would be worse, and second-preimage wouldn…

You're missing something in your definition of a second-preimage attack, which is that Y != X.

That's kind of implicit.

If X = Y, it's not an attack, it's the primary purpose of hashing

Re: Announcing the first SHA-1 collision

#374

Post by rocqua »

mike_hearn wrote: post #340
fivesigma wrote: post #54

Earlier quoted context omitted.

None of what you mentioned is affected since this is a collision attack. They purposely created 2 files with the same hash. Creating a file with the same hash as legit file is a preimage attack and is much more difficult to perform (many orders of magnitude more difficult). This still doesn't mean that SHA-1 isn't dogshit however. It should have been phased out years ago.

anilgulecha is correct. Consider the following attack: You wish to undermine the security of an important codebase managed by git. You write a valuable and useful contribution to the code. You also create another version of the commit that has the same SHA-1 as the first, which breaks the security of that code. You submit the first commit, it is accepted and merged. Now you wait for your target to do a git clone on t…

You need enough leeway in the first commit though. As this is a collision attack, you need to be able to tweak both commits in order to get their hashes to collide.

The mangling in the first commit is probably going to look mighty-suspicious. You might be able to handle this if you get to mangle e.g. code comments. In any case, you need something similar like PDFs malleability where you can change one document without the change being noticeable.

Re: Announcing the first SHA-1 collision

#375

Post by Strom »

alfalfasprout wrote: post #189
raphaelj wrote: post #47

Earlier quoted context omitted.

They provide an estimate in their paper: > The monetary cost of computing the second block of the > attack by renting Amazon instances can be estimated from > these various data. Using a p2.16xlarge instance, > featuring 16 K80 GPUs and nominally costing > US$ 14.4 per hour would cost US$ 560 K for the > necessary 71 device years. It would be more economical > for a patient attacker to wait for low “spot prices” of >…

Eh, at that point you may as well buy the servers yourself and let them run on-premises. Even with power, etc. that cost could easily come down 50% or more. Once you own the servers, additional tasks just cost power.

In addition, as any bitcoin miner knows, AMD GPUs are actually far more efficient at calculating hashes.

Re: Announcing the first SHA-1 collision

#376

Post by lilyball »

ddlatham wrote: post #366
gliptic wrote: post #338

Earlier quoted context omitted.

If you can do a first-preimage attack, you can do a second-preimage attack. Just hash the document you have. Therefore a first-preimage attack is strictly more severe.

Not if the second-preimage attack is properly defined to find a second distinct document with the same hash as the first.

If you can do a first-preimage attack, then just keep doing it until you get a distinct document. I'm not sure what sort of first-preimage attack you have in mind that is only capable of producing a single preimage for any hash.

Re: Announcing the first SHA-1 collision

#377

Post by eridius »

mikegerwitz wrote: post #354
palunon wrote: post #349

Earlier quoted context omitted.

But if you have a first preimage atack, you could then use it on the hash to get (presumably) another document...

A first-preimage attack just means you have H(P), find preimage P (where H is SHA1). If you found preimage P and wanted another document that hashes into it (so, H(P) = H(P')), you'd have to perform a second-preimage attack and brute-force one. An "ideal" hash function is one where the only way to compute a second-preimage is through brute force. Due to the pidgeonhole principle, there will always be a second preimag…

> Due to the pidgeonhole principle, there will always be a second preimage

It's trivial to construct a hash function where this isn't true. However, it should be true for any cryptographically secure hash.

Re: Announcing the first SHA-1 collision

#378

Post by jwilk »

simias wrote: post #320
problems wrote: post #308

Earlier quoted context omitted.

> There is a world of difference between "come up with two things that hash to the same value" and "come up with something that hashes to a particular known value". Doesn't the PDF on their site pretty much prove they can do both of these - at least, in a way? They were able to change the color without impacting the contents of the PDF and get the same SHA1. They probably have a fair bit of garbage data to work with…

No, they can't chose the hash value. Or, to put it an other way, they can't find a collision for an arbitrary file, they can only craft two particular files that happen to collide. See this image: http://shattered.it/static/pdf_format.png The "collision blocks" is where the magic happen, given the two different prefixes (with the different colors) they have to craft two sequences of bits that will put the SHA1 state…

> given the two different prefixes (with the different colors) they have to craft two sequences of bits that will put the SHA1 state machine in the same internal state once processed.

No, this is an identical-prefix attack.

Re: Announcing the first SHA-1 collision

#379

Post by pornel »

mysterydip wrote: post #355

Forgive my ignorance, but it seems a solution to collision worries is to just use two hashing algorithms instead of one. We have two factor authentication for logins, why not the equivalent for hashed things? Give me the sha1 and md5, rather than one or the other. Am I wrong in thinking even if one or both are broken individually, having both broken for the same data is an order of magnitude more complex?

You're effectively creating a new hashing algorithm, which is twice as long and twice as slow, and is built using constructs known to be weak.

Re: Announcing the first SHA-1 collision

#380

Post by eridius »

jsolson wrote: post #319
problems wrote: post #316

Earlier quoted context omitted.

Ah, okay. Yeah, that does seem quite possible. They are saying "HTTPS Certificates" are potentially impacted - but they're probably just trying to push people away from SHA1 as fast as possible.

Re-reading it and checking out the demo on https://shattered.io/ it looks like it's even stranger -- some PDFs are "safe", so it may be that it requires the original document (and hash) to have certain properties to be able to generate a collision (but if it has those properties they may be able to generate them arbitrarily). It sounds like this is going to be reaaaalllly interesting when the 90 day window passes. (a…

It's entirely possible that "dangerous" PDFs are simply ones with a dead chunk containing image data in in the middle of it, and if there's no dead chunks, or if the dead chunks don't allow for arbitrary garbage data, then it's "safe".
Post reply on HN