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

311–320 of 524 posts

Re: Announcing the first SHA-1 collision

#311

Post by grepthisab »

btilly wrote: post #307
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…

It's almost certain that intelligence agencies could invest this effort to say, break SHA1 SSL certs. To the contrary, it is unlikely that they can do so. 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". It gets harder still if you're trying to add constraints about the format of your text (such as making…

So the Birthday Problem, basically?[1]

https://en.wikipedia.org/wiki/Birthday_problem

Re: Announcing the first SHA-1 collision

#312

Post by 0x0 »

OJFord wrote: post #209
giovannibajo1 wrote: post #20

Earlier quoted context omitted.

This is not a pre-image attack, so you can't create a file that matches an existing SHA1. It's a collision attack, so you can create two files whose SHA1 is the same. So what I could potentially do (given a multi-million dollar budget) is create from scratch two git repositories with different content, whose HEAD is the same. This would allow me to serve different repositories to different users. What is currently st…

> What is currently still not feasible is to create a custom git repository whose HEAD matches that of the Linux kernel. Hang on, that doesn't matter though, does it? I was under the impression that git's SHAs were to be treated as repo-wise unique; not universally. There must non-adversarial 'collisions' across repositories already, surely? I thought this attack potentially allows creating two commits in the same re…

If there were collisions across repos you could just merge one into the other and you have a collision within one repo. It's previously unheard of.

Re: Announcing the first SHA-1 collision

#313

Post by jsolson »

problems wrote: post #308
btilly wrote: post #307

Earlier quoted context omitted.

It's almost certain that intelligence agencies could invest this effort to say, break SHA1 SSL certs. To the contrary, it is unlikely that they can do so. 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". It gets harder still if you're trying to add constraints about the format of your text (such as making…

> 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. I don't know the details of the attack, but a third possibility (as I read it) is that both PDF documents are modified in the process until they arrive at a collision.

PDF has the convenient property that you can inject arbitrary bogus data into the middle of it with a constant head and tail and it will still be valid. The tail of the file contains a trailer that points to the dictionary that describes where all of the resources in the file are located. The entire file need not be covered by the dictionary (and typically won't be for PDFs that have gone through several rounds of annotation/modification). This leaves the opportunity "dead chunks" that can be modified arbitrarily without changing the rendered result.

Re: Announcing the first SHA-1 collision

#314

Post by pfg »

goncalomb wrote: post #298

https://security.googleblog.com : "This website uses a weak security configuration (SHA-1 signatures), so your connection may not be private."

I get a SHA256 certificate for that site. What user agent are you using? Is there some kind of middlebox on your network, or do you use AV software that intercepts TLS connections?

Re: Announcing the first SHA-1 collision

#315

Post by xyzzyz »

stepik777 wrote: post #302
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…

> break SHA1 SSL certs. It's not possible to break existing SHA1 certificates because this attack is to generate collisions, not finding preimages.

You are thinking about this in a wrong way. It is in fact true that being able to generate collisions allows you to break SSL. What you do is this: generate two certificates with colliding hashes, one for google.com, the other for your own domain. Verisign will gladly sign the second one, since you own the domain, but since the hashes match, you can also use the same signature for the first one. Now you can impersonate google.com.

Of course, the real certificate issuance process is more complicated and has some extra precautions to protect from it, my point is that you don't need preimage, collisions should suffice for breaking SSL.

Re: Announcing the first SHA-1 collision

#316

Post by problems »

jsolson wrote: post #313
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. I don't know the details of the attack, but a third possibility (as I read it) is that both PDF documents are modified in the process until they arrive at a collision. PDF has the convenient property that you can inject arbitrary bogus data into the middle of it with a constant head and tail and it will still be valid. The tail of the file contains a trailer that points to the dictionary that describes where all…

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: Announcing the first SHA-1 collision

#317

Post by chrisper »

jgrahamc wrote: post #95

How am I going to explain this to my wife? Actually a serious question. How do we communicate something like this to the general public?

Assume there is a machine that is giving out unique numbers per person. If person A presses the button twice, they get the same number they got previously. If person B presses the button, they get a different unique number. Now, I searched for a long time to find a person who is not A, but will get the same unique number as A.

So now your wife can agree that the machine does not provide unique numbers per person and is, thus, broken.

Re: Announcing the first SHA-1 collision

#319

Post by jsolson »

problems wrote: post #316
jsolson wrote: post #313

Earlier quoted context omitted.

No. I don't know the details of the attack, but a third possibility (as I read it) is that both PDF documents are modified in the process until they arrive at a collision. PDF has the convenient property that you can inject arbitrary bogus data into the middle of it with a constant head and tail and it will still be valid. The tail of the file contains a trailer that points to the dictionary that describes where all…

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.

(also, should've mentioned in original post just for clarity -- I work for Google, but do not know any of the details of this work)

Re: Announcing the first SHA-1 collision

#320

Post by simias »

problems wrote: post #308
btilly wrote: post #307

Earlier quoted context omitted.

It's almost certain that intelligence agencies could invest this effort to say, break SHA1 SSL certs. To the contrary, it is unlikely that they can do so. 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". It gets harder still if you're trying to add constraints about the format of your text (such as making…

> 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 machine in the same internal state once processed.

Once the state machines are "synchronized" you can add whatever identical content you want to both files after that and it'll always hash up to the same value. You can't control that value however.

Post reply on HN