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

381–390 of 524 posts

Re: Announcing the first SHA-1 collision

#381

Post by timeal »

jakob223 wrote: post #255
problems wrote: post #242

Earlier quoted context omitted.

A few considerations though: - Google used GPUs, much of the Bitcoin network relies on fully custom ASICs now and mining without them isn't really profitable anymore - SHA1 hashes can also be computed over twice as fast as SHA256 even on GPUs, so if someone were to go out and build SHA1 ASICs, you could probably do this very, very fast. It's almost certain that intelligence agencies could invest this effort to say, b…

> say, break SHA1 SSL certs Maybe, and probably, but probably not within the scope of this attack. This attack relies on being able to have a large similar prefix and a lot of control over further internal data; SSL certs are somewhat more constrainted.

This attack is applicable to SSL certs. Not most CAs as they have deployed counter-measures (such as using a long, random serial number) after the publication of the colliding MD5 rogue CA (https://www.win.tue.nl/hashclash/rogue-ca/) but I'm sure there are tons of companies with IT department and internal CAs who don't follow best practices and could be attacked with SHA1 collisions.

Re: Announcing the first SHA-1 collision

#382

Post by jwilk »

schoen wrote: post #299
problems wrote: post #262

Earlier quoted context omitted.

Would a TLS certificate not offer such a large similar prefix? Just change the domain to a wildcard or something like the RapidSSL MD5 attack from a few years back.

In https://www.win.tue.nl/hashclash/rogue-ca/ , Sotirov et al. were able to use the ability to create MD5 collisions to create a pair of colliding certificates because the content of an about-to-be-issued certificate was almost completely predictable. In response to this, the industry added requirements for CAs to include unpredictable values (such as an unpredictable serial number) in certificates. For example, the…

Also, they used a chosen-prefix attack for creating colliding certificates.

The SHA-1 attack is identical-prefix, which gives you much less flexibility.

Re: Announcing the first SHA-1 collision

#384

Post by pornel »

udev wrote: post #283
Twirrim wrote: post #275

Earlier quoted context omitted.

The PDF example given is somewhat ridiculous. "For example, by crafting the two colliding PDF files as two rental agreements with different rent, it is possible to trick someone to create a valid signature for a high-rent contract by having him or her sign a low-rent contract. " Talk about ridiculous scenarios only people living in a tech bubble could come up with. How many landlords do you imagine know what sha-1 ch…

This is not as far fetched as you think. In UK, rental contracts are often digitally signed by the renter and landlord. I am sure in finance world many other types of contracts are signed digitally, also under the assumption that both parties sign the same thing.

The "signing" usually doesn't involve any cryptography. You just express your agreement, which can be as trivial as typing your initials in a box.

It's purely a legal, not technical thing, so if you cleverly forge the document using collisions, you'll be shouting "but the SHA-1 matched!" from behind the bars.

Re: Announcing the first SHA-1 collision

#385

Post by haberman »

btilly wrote: post #356
cbhl wrote: post #335

Earlier quoted context omitted.

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.…

> 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.

Is it really that simple? If that were the case, then you could take the two colliding blocks from Google's PDF and trivially use them to create an arbitrary number of colliding files. I would be really surprised if it was that easy.

Re: Announcing the first SHA-1 collision

#386

Post by gliptic »

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.

For that to be the case, in real hash functions, it would require you to be constrained to a certain number of possible preimages, not too many more than the number of possible hashes, so that it's likely that H^-1(H(x)) = x but there can still be a distinct y such that H(y) = H(x).

So I concede that this could be the case under very specific circumstances, but I doubt it makes much difference in the real world.

Re: Announcing the first SHA-1 collision

#387

Post by pfg »

timeal wrote: post #381
jakob223 wrote: post #255

Earlier quoted context omitted.

> say, break SHA1 SSL certs Maybe, and probably, but probably not within the scope of this attack. This attack relies on being able to have a large similar prefix and a lot of control over further internal data; SSL certs are somewhat more constrainted.

This attack is applicable to SSL certs. Not most CAs as they have deployed counter-measures (such as using a long, random serial number) after the publication of the colliding MD5 rogue CA ( https://www.win.tue.nl/hashclash/rogue-ca/ ) but I'm sure there are tons of companies with IT department and internal CAs who don't follow best practices and could be attacked with SHA1 collisions.

Even root CAs have been known to not comply with the randomized serial number requirement occasionally, see [1] for a recent example, with the most recent (SHA-1) certificate being issued in August of last year.

[1]: https://bugzilla.mozilla.org/show_bug.cgi?id=1267332#c5

Re: Announcing the first SHA-1 collision

#388

Post by schoen »

haberman wrote: post #385
btilly wrote: post #356

Earlier quoted context omitted.

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.…

> 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. Is it really that simple? If that were the case, then you could take the two colliding blocks from Google's PDF and trivially use them to create an arbitrary number of colliding files. I would be really surprised if it was that easy.

It may be a question about the implications of https://en.wikipedia.org/wiki/Length_extension_attack, which allows computing H(X∥Y) from H(X), len(X), and Y (without knowing X!). I'm not immediately sure how that applies or fails to apply in the case of a hash collision; that's an interesting thing to think through.

Re: Announcing the first SHA-1 collision

#389

Post by btilly »

haberman wrote: post #385
btilly wrote: post #356

Earlier quoted context omitted.

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.…

> 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. Is it really that simple? If that were the case, then you could take the two colliding blocks from Google's PDF and trivially use them to create an arbitrary number of colliding files. I would be really surprised if it was that easy.

Yes, it really is. You have to be careful where you put the colliding blocks, but everything else is open.

The same was true of MD5, and is true of any other block cipher.

Re: Announcing the first SHA-1 collision

#390

Post by matt_wulfeck »

> We then leveraged Google’s technical expertise and cloud infrastructure to compute the collision which is one of the largest computations ever completed.

And this, my friends, is why the big players (google, Amazon, etc) will win at the cloud offering game. When the instances are not purchased they can be used extensively internally.

Post reply on HN