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

441–450 of 524 posts

Re: Announcing the first SHA-1 collision

#441

Post by photojosh »

nneonneo wrote: post #398
jwilk wrote: post #391

Earlier quoted context omitted.

Thanks! What tools did you use to analyse the JPEG?

I used Hachoir ( https://github.com/haypo/hachoir3 ), a Python library that I've contributed to. Hachoir disassembles files using a library of parsers, with the intent of describing the function of every single bit in the file. You can see the resulting disassemblies (rendered with the hachoir-wx GUI) here: http://imgur.com/a/F1cnV

What an incredible tool... I have a webapp that has as a small component the analysis of JPEG metadata, this will be very useful for future development.

Re: Announcing the first SHA-1 collision

#442

Post by aburan28 »

SamBam wrote: post #190

I'm confused by the "File Tester" at https://shattered.it/ It says "Upload any file to test if they are part of a collision attack." When I upload either of their two sample collision documents, it says they are "Safe."

This tool is simply testing whether or not the file has a disturbance vector that makes it a potential file with higher than usual probability to be in a collision

Re: Announcing the first SHA-1 collision

#443

Post by modalduality »

cjbprime wrote: post #247
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?

> How am I going to explain this to my wife? I don't know. What's your wife's background? If she already knows what one-way functions are, you could just explain that we've found collisions for the first time in an old one-way function that was used for file authenticity but isn't used much anymore because we knew ten years ago we were probably going to start finding collisions in it. If she doesn't know what one-way…

One-way functions are not cryptographic hash functions, which have the three properties preimage resistance, second preimage resistance, and collision resistance.

For example, say f(x) is a one-way function. Then define

g(0x) = f(x)

g(1x) = f(x)

Here given some z, it's easy to find another z that maps to the same output, just flip the first bit. However, g is still a one-way function:

Assume we could break g with non-negligible probability, that some program A(y) outputs x such that g(x) = y with probability p.

Then say someone gives us q = f(a) for some a. We can compute A(q) that will either give us 1a or 0a by the definition of g with probability p. In either case we can discard the first bit to find the preimage for a. By contradiction, g is a one-way function.

Re: Announcing the first SHA-1 collision

#444

Post by CGamesPlay »

nneonneo wrote: post #325

The visual description of the colliding files, at http://shattered.io/static/pdf_format.png , is not very helpful in understanding how they produced the PDFs, so I took apart the PDFs and worked it out. Basically, each PDF contains a single large (421,385-byte) JPG image, followed by a few PDF commands to display the JPG. The collision lives entirely in the JPG data - the PDF format is merely incidental here. Extract…

Great analysis. So why did Google choose to use PDFs instead of JPGs directly?

Re: Announcing the first SHA-1 collision

#445

Post by cesarb »

korethr wrote: post #413

So, since Git uses SHA-1, does this mean we're going to see a new major version number of Git that uses SHA-2 or SHA-3 in a few years? I don't expect one overnight. For one, as noted, this is a collision attack, one which took a large scale of power to achieve. In light of that, I don't think the integrity of git repos is in immediate danger. So I don't think it'd be an immediate concern of the the Git devs. Secondly…

> Secondly, wouldn't moving to SHA-2 or SHA-3 be a compatibility-breaking change?

If git allows for extra fields in commits and tags (I don't know if it's the case), one could have "tree3" and "parent3" entries on each commit, which point to a parallel sha-3 tree (with sha-3 nodes and leaves) and sha-3 of the parent commit(s). Old git would ignore these entries, new git would use them (and check they point to the same parents/blobs as their sha-1 equivalent). Hacky and ugly, but doable.

Re: Announcing the first SHA-1 collision

#446

Post by javajosh »

CGamesPlay wrote: post #444
nneonneo wrote: post #325

The visual description of the colliding files, at http://shattered.io/static/pdf_format.png , is not very helpful in understanding how they produced the PDFs, so I took apart the PDFs and worked it out. Basically, each PDF contains a single large (421,385-byte) JPG image, followed by a few PDF commands to display the JPG. The collision lives entirely in the JPG data - the PDF format is merely incidental here. Extract…

Great analysis. So why did Google choose to use PDFs instead of JPGs directly?

Perhaps to be taken more seriously by management. All things being equal, the content of PDFs (auditor reports) is more important than that of JPGs (cat memes).

Re: Announcing the first SHA-1 collision

#447

Post by maxmcd »

CGamesPlay wrote: post #444
nneonneo wrote: post #325

The visual description of the colliding files, at http://shattered.io/static/pdf_format.png , is not very helpful in understanding how they produced the PDFs, so I took apart the PDFs and worked it out. Basically, each PDF contains a single large (421,385-byte) JPG image, followed by a few PDF commands to display the JPG. The collision lives entirely in the JPG data - the PDF format is merely incidental here. Extract…

Great analysis. So why did Google choose to use PDFs instead of JPGs directly?

Maybe because JPG bytes or more likely to be manipulated when sending around the web?

Re: Announcing the first SHA-1 collision

#449

Post by joeyh »

rntz wrote: post #28
rocqua wrote: post #23

Earlier quoted context omitted.

What about git? This makes it technically possible to get a backdoored linux repo with the same commit hash. EDIT: this is wrong, it's not a second pre-image attack only a collision attack. That is, you can create 2 git repositories with the same commit hash, but not a git repo that matches an already existing repo. In other words, you can create 2 things with the same hash, but can't control what that hash actually…

EDIT: My original comment was wrong. Git commit signing apparently only signs the commit hash itself, so it's only as trustworthy as the integrity of the hash. However, see also other comments which point out that this isn't a pre-image attack; you can't find a collision for a given thing (in this case, the linux kernel); rather, you can generate from scratch two pieces of data which happen to collide. Still, this is…

When git signs a commit it pipes the entire commit, including the message at the end, and all headers to git. Then it goes back and adds the signature in a new gpgsig header.

I often see people getting this wrong in HN threads. Probably because that's how signed tags work.

Re: Announcing the first SHA-1 collision

#450

Post by WatchDog »

schoen wrote: post #405
schoen wrote: post #388

Earlier quoted context omitted.

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.

I was a bit surprised to see this because I thought there might be more constraints on it, but I tried adding arbitrary strings to the end of both PDFs and re-hashing, and the hashes continue to be the same after appending arbitrary arbitrary-length strings. I guess this is indeed a consequence of the length-extension attack; we can argue that if -- for this kind of hash -- H(X∥Y) always depends only on H(X), len(X),…

I suspect you would see the same behaviour even with a hash function that is not vulnerable to length extension attacks. My understanding is that protecting against length extension is about hiding the internal state of the cipher in the result hash, for the purposes of protecting a secret in the plaintext. But if the state is the same between each document, and you have access to the whole plaintexts, I don't see why length extension would play a role.
Post reply on HN