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

SHA-1 'fully and practically broken' by new collision (2020)

duo.com

Post reply on HN
Print view View original

91–100 of 210 posts

Re: SHA-1 'fully and practically broken' by new collision (2020)

#91

Post by ganzuul »

contravariant wrote: post #61
ganzuul wrote: post #19

Earlier quoted context omitted.

Natural data is easily identifiable.

Only if you count all natural looking data of which there is way more than you could possibly imagine. It is of course likely that humanity hasn't yet created more than 2^100 (~10^30) files, so in theory given a registry of all files in existence you might be able to identify it by its hash. However while this is simple it's definitely not easy.

I can imagine the output of program space. That's pretty big. All possible universes in fact.

It's an issue of probability and bins. While natural data is infinite, there is vastly more unnatural data. At some point you have enough metadata (e.g. natural vs. random) to know that the original data came from Earth to pick out the right needle from the needle stack.

Unless the data is from a completely alien source, we are close enough to that source for our heuristics to be of a manageable size.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#92

Post by lvh »

danachow wrote: post #87
wcoenen wrote: post #58

Earlier quoted context omitted.

Surely signed tags and signed commits in git are supposed to be cryptographically secure? [0] Doesn't the security of those signatures depend on the security of the SHA-1 hashes that are being signed? [0] https://git-scm.com/book/en/v2/Git-Tools-Signing-Your-Work

No - after all, the most common use of digital signatures is to sign documents that can be easily tampered. All the security is in the signature, not the content being signed.

This makes no sense. Sure: you can generate an X.509 certificate that says whatever you want, but the point is that you can validate the signature and see that it's a forgery. In the case of a hash-addressed system like git, the problem is that the signature is over a collision, so it no longer certifies the thing its supposed to certify. Git uses the hash as a shorthand for a revision, including its entire history--so yes, it is using the hash that way.

By that logic, would MD5 be fine? MD4? CRC32?

Re: SHA-1 'fully and practically broken' by new collision (2020)

#93

Post by DSMan195276 »

noway421 wrote: post #56
outworlder wrote: post #41

Earlier quoted context omitted.

> presumably you can later substitute the initial commit with the other one without anybody being able to detect the substitution. How? Which operation would be involved? Will it not show anywhere else(reflog)?

`git push --force` I assume. In GitHub, this will leave a trail of events though - Webhook events and auditing.

I would think it's not that simple because `git push --force` doesn't do anything if it thinks the histories are the same, and in this case we've created a history that appears to be the same. You'd likely need a custom git client (which isn't a problem) but I don't know enough about the internals of a git push to know if the server would even accept objects if they match hashes of objects it already has (it may just go "I don't need that" and ignore it, because what's the point in doing anything with it?). Presumably it would depend on the exact server implementation whether you could get it to replace an existing object with a "new" one which is actually the same hash, but frankly I think that's unlikely because it would be pointless work from the view of the server. If it does happen I'm not sure what auditing you would actually be able to see, webhooks and such might not be triggered because the history didn't actually "change".

What you could do however is just host it yourself somewhere else, say put it on a fork. Or if you have access to the actual repository hosting the original version, you could just manually replace it yourself. git clients aren't going to just automatically pull the "new" version though so you'll have some combo of people with the old and people with the new, and it gets a little messier from there.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#94

Post by lamontcg »

ori_b wrote: post #53
cletus wrote: post #25

Git was created 16 years ago. The impending breakage of SHA-1 was known even at that time, just like how MD5 had been broken before it. I'm honestly still shocked that updating the hashing algorithm wasn't built into Git from day one. I really wonder why. Did people think this wouldn't happen? Were they so in love with the performance of C/C++ being able to pass around 20 byte hashes on the stack without worrying abo…

For someone to be able to break your repo using sha1 collisions, they need to be able to commit to it. If you don't trust someone, don't let them commit to your repo. > Were they so in love with the performance of C/C++ being able to pass around 20 byte hashes on the stack without worrying about a more complicated structure (eg a collection of variable length hashes)? The hashes show up everywhere. They're how every…

Yeah I don't think any of these proposed attacks work without write access to the repo, at which point the game is already pretty much over already.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#95

Post by wongarsu »

danachow wrote: post #87
wcoenen wrote: post #58

Earlier quoted context omitted.

Surely signed tags and signed commits in git are supposed to be cryptographically secure? [0] Doesn't the security of those signatures depend on the security of the SHA-1 hashes that are being signed? [0] https://git-scm.com/book/en/v2/Git-Tools-Signing-Your-Work

No - after all, the most common use of digital signatures is to sign documents that can be easily tampered. All the security is in the signature, not the content being signed.

A digital signature usually signs (~encrypts) a hash of the content. So asking what exactly signing a commit or tag entails is a very valid question. I would expect that signing a tag is only as strong as SHA-1, since a tag is essentially a label for a commit hash. For signing commits I have no clue, but would be quite interested as well.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#96

Post by dang »

Some past threads:

SHA-1 collisions now cost $45k [pdf] - https://news.ycombinator.com/item?id=23350223 - May 2020 (62 comments)

The first chosen-prefix collision for SHA-1 - https://news.ycombinator.com/item?id=21979333 - Jan 2020 (352 comments)

Abusing SHA-1 collisions for Chromium updates - https://news.ycombinator.com/item?id=20114809 - June 2019 (36 comments)

A SHA-1 chosen-prefix collision attack - https://news.ycombinator.com/item?id=19907127 - May 2019 (71 comments)

From Collisions to Chosen-Prefix Collisions Application to Full SHA-1 [pdf] - https://news.ycombinator.com/item?id=19878917 - May 2019 (18 comments)

SHA-1 Collision Detection on GitHub.com - https://news.ycombinator.com/item?id=13917990 - March 2017 (90 comments)

Linus' reply on Git and SHA-1 collision - https://news.ycombinator.com/item?id=13719368 - Feb 2017 (262 comments)

When Will We See Collisions for SHA-1? (2012) - https://news.ycombinator.com/item?id=13719079 - Feb 2017 (1 comment)

Announcing the first SHA-1 collision - https://news.ycombinator.com/item?id=13713480 - Feb 2017 (485 comments)

How would Git handle a SHA-1 collision on a blob? - https://news.ycombinator.com/item?id=13547348 - Feb 2017 (5 comments)

Why it’s harder to forge a SHA-1 certificate than to find a SHA-1 collision - https://news.ycombinator.com/item?id=10778773 - Dec 2015 (43 comments)

The Cost of Creating Collisions Using SHA-1 - https://news.ycombinator.com/item?id=8629906 - Nov 2014 (9 comments)

When Will We See Collisions for SHA-1? - https://news.ycombinator.com/item?id=4618069 - Oct 2012 (51 comments)

Re: SHA-1 'fully and practically broken' by new collision (2020)

#97

Post by musicale »

umvi wrote: post #79
simias wrote: post #62

Earlier quoted context omitted.

Honestly I find these rationalizations around the use of SHA-1 annoying and counter-productive. The rule is simple: don't use SHA-1. If you already use SHA-1 migrate away from it. You know that plenty of software out there that interfaces with git expecting that the commit hash will be unique. Is it a security risk? Maybe, maybe not. I don't care to find out. It doesn't matter until it starts mattering. If the Git de…

> You know that plenty of software out there that interfaces with git expecting that the commit hash will be unique You also know that plenty of software out there that interfaces with git has hardcoded assumptions (like, for example, the assumption that the commit hash will be exactly 40 characters long). Some tools parse the output of git log and other commit-bearing commands to make decisions. Will changing git to…

> New projects use git2, existing projects use git (or something like that). Otherwise confusion and backwards-compatibility breakage will abound.

Like uh, python2 and python3? ;-p

Re: SHA-1 'fully and practically broken' by new collision (2020)

#98

Post by ganzuul »

__s wrote: post #22
ganzuul wrote: post #19

Earlier quoted context omitted.

Natural data is easily identifiable.

That's because natural data has low entropy But let's say every paragraph only offers 1 bit of entropy. Then a 160 bit hash gives you fuzzy accuracy up to 160 paragraphs. After that you'll have to extend the hash with hints to guide which sequence of paragraphs you're looking for, & hints for where the typos are ofc, 100x compression of English text doesn't require this amount of compute to decompress: https://en.wik…

This is very abstract, but I believe that since both input and output are very close in program space compared to the total size of PS, the heuristics to map between them are going to be of a manageable size. This is based on an intuition about a single source for all activity in this universe.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#100

Post by sverhagen »

DSMan195276 wrote: post #93
noway421 wrote: post #56

Earlier quoted context omitted.

`git push --force` I assume. In GitHub, this will leave a trail of events though - Webhook events and auditing.

I would think it's not that simple because `git push --force` doesn't do anything if it thinks the histories are the same, and in this case we've created a history that appears to be the same. You'd likely need a custom git client (which isn't a problem) but I don't know enough about the internals of a git push to know if the server would even accept objects if they match hashes of objects it already has (it may just…

If you can force push, why would you then not push a different commit before pushing your updated commit with the same, original hash, or does that also not work?
Post reply on HN