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

351–360 of 524 posts

Re: Announcing the first SHA-1 collision

#351

Post by xamuel »

gliptic wrote: post #338
mikegerwitz wrote: post #324

Earlier quoted context omitted.

The severity between the preimage attacks depends on context. For Git, for example, a first-preimage attack won't buy you anything, but a second-preimage could be potentially devastating depending on how lucky you get. If Mallory wanted to make it look like you signed a document you didn't, second-preimage would be devestating. And with the demonstration of two PDFs sharing the same hash, this is a pretty severe one:…

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.

mikegerwitz is technically right. As an illuminating example, consider a hash-algorithm in which there's at least one hash that occurs precisely once. Then a 2nd-preimage attack is formally impossible no matter how much computational power you have (assuming by "second" you meant "distinct second"). But a 1st-preimage attack is formally possible.

Re: Announcing the first SHA-1 collision

#352

Post by [deleted] »

jwilk wrote: post #292
refulgentis wrote: post #268

Earlier quoted context omitted.

One can insert arbitrary data into JPGs. Given that, the researchers embedded a JPG in a PDF, and manipulated the arbitrary data until it resulted in a collision.

Sure, but you don't end up with two images that differ only in background of top half by accident...

[deleted]

Re: Announcing the first SHA-1 collision

#353

Post by TheGrumpyBrit »

dwaltrip wrote: post #282
m3ta wrote: post #144

To put things into perspective, let the Bitcoin network hashrate (double SHA256 per second) = B and the number of SHA1 hashes calculated in shattered = G. B = 3,116,899,000,000,000,000 G = 9,223,372,036,854,775,808 Every three seconds the Bitcoin mining network brute-forces the same amount of hashes as Google did to perform this attack. Of course, the brute-force approach will always take longer than a strategic appr…

This says more about the Bitcoin network than it does about the ease with which one can create a SHA-1 collision. From the article: Nine quintillion (9,223,372,036,854,775,808) SHA1 computations in total. 6,500 years of CPU computation for 1st phase of attack. 110 years of GPU computation for 2nd phase of attack.

It certainly raises an interesting question. The go-to response when anybody discusses brute forcing bitcoin is that the sheer number of possibilities makes finding a collision infinitesimally small. And that's true. Same for .onion certificates.

But Google certainly haven't been attacking this for the last 6,500 years. With a sufficiently obscene amount of resources, it IS feasible to create an index of every possible public/private keypair. It's not profitable to do so just for the purpose of plundering bitcoin wallets, but if you're a government doing it for other reasons, it might be worthwhile.

Re: Announcing the first SHA-1 collision

#354

Post by mikegerwitz »

palunon wrote: post #349
mikegerwitz wrote: post #346

Earlier quoted context omitted.

Getting the first-preimage of the document and hashing that same preimage just gives you back the original hash---it's like an identity function. It doesn't give you a second document. Edit: I misinterpreted your message. I added "same" above to convey what I thought you were saying.

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 preimage---it's just whether it's computational feasible to compute it.

Re: Announcing the first SHA-1 collision

#355

Post by mysterydip »

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?

Re: Announcing the first SHA-1 collision

#356

Post by btilly »

cbhl wrote: post #335
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…

I haven't seen the actual PDFs, but the way my crypto prof taught me about this attack in college is that you generate a PDF of the form if (x == a) { // display good content } else { // display bad content } You have to craft this PDF file in such a way that given a SHA1 collision (a, b) that the file with x = a and the file with x = b have the same SHA1. (There are some nuances about aligning to block boundaries, I…

Exactly the right idea.

More technically, the reason why this is possible is that this is a block cipher. You take the file, and proceed block by block. So if two files are identical except for one block, and those differing blocks generates the same SHA-1, then the whole files will generate the same SHA-1. You can make it look like any pair of documents, but the actual content of the source includes both documents.

This trick works better with some document formats than others. PDF is great. Plain text, not so much.

This trick is absolutely useless unless you control both documents. But if you already control a certificate, then you have no need to try to switch to a fake one

Re: Announcing the first SHA-1 collision

#357

Post by lisper »

xamuel wrote: post #351
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.

mikegerwitz is technically right. As an illuminating example, consider a hash-algorithm in which there's at least one hash that occurs precisely once. Then a 2nd-preimage attack is formally impossible no matter how much computational power you have (assuming by "second" you meant "distinct second"). But a 1st-preimage attack is formally possible.

One of the requirements for a hash to be cryptographically secure is that all possible values are equally likely. So yes, it is possible (in fact trivial) to construct a hash of the sort you describe, but such a hash would not be cryptographically secure to begin with.

Re: Announcing the first SHA-1 collision

#358

Post by Gankro »

mikegerwitz wrote: post #346
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.

Getting the first-preimage of the document and hashing that same preimage just gives you back the original hash---it's like an identity function. It doesn't give you a second document. Edit: I misinterpreted your message. I added "same" above to convey what I thought you were saying.

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't buy you anything.

first-preimage doesn't do anything here. It gets you some text that matches the hash. It's overwhelmingly unlikely to be the original message, and if it's not the exact original message, it won't have any similarity to it. Unless you can enumerate all hash collisions for a value efficiently, which is a much a stronger claim, this isn't any better than brute-force guessing the text.

> Getting the preimage of the document and hashing that preimage just gives you back the original hash---it's like an identity function. It doesn't give you a second document.

The second-preimage attack supposes you have X, the first-preimage attack supposes you have hash(X). If "all" you have is a first-preimage attack, then it's trivial convert it into a second-preimage attack. You hash(X) and feed it into your attack.

Re: Announcing the first SHA-1 collision

#359

Post by AlexandrB »

anderskaseorg wrote: post #287
AlexandrB wrote: post #256

Earlier quoted context omitted.

As someone who knows only the very basics of cryptography - would verifying hashes of a file using SHA-1 and a "weak" hash function like MD5 provide any additional protection over just SHA-1? I.e. how much harder would be it be to create a collision in both SHA-1 and MD5 than in just SHA-1? My common sense intuition is that it would be a lot harder, but I'm guessing theoretically/mathematically it's only a little bit…

It’s actually not much harder at all, as first noted by Joux, “Multicollisions in iterated hash functions. Application to cascaded constructions”, 2004. https://www.iacr.org/archive/crypto2004/31520306/multicollis...

Thanks, this is fascinating!

Re: Announcing the first SHA-1 collision

#360

Post by tlb »

xamuel wrote: post #351
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.

mikegerwitz is technically right. As an illuminating example, consider a hash-algorithm in which there's at least one hash that occurs precisely once. Then a 2nd-preimage attack is formally impossible no matter how much computational power you have (assuming by "second" you meant "distinct second"). But a 1st-preimage attack is formally possible.

A 'good' hash function (exhibiting uniformity) that converts arbitrary-sized documents to finite-sized hashes should not have any hashes that occur precisely once.

This can occur with ill-conceived hash functions, for example if it bundles the length of the document with the hash, so there would be only 256 distinct hashes with length=1.

Post reply on HN