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

41–50 of 210 posts

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

#41

Post by outworlder »

adrian_b wrote: post #39
api wrote: post #7

Earlier quoted context omitted.

Random collisions in 160-bit space are incredibly unlikely. This is talking about intentional collision, and means that it's entirely feasible for someone with significant compute power to create a git commit that has the exact same hash as another git commit. This could allow someone to silently modify a git commit history to e.g. inject malware or a known "bug" into a piece of software. The modified repository woul…

It is not yet possible "to create a git commit that has the exact same hash as another git commit" in the sense that if someone else has already done a commit you can make another commit with the same hash. What is possible now is something that is much easier: if you have enough money and time, you can create 2 commits with the same hash, which start with some different parts, which may be chosen arbitrarily, then t…

> 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)?

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

#42

Post by tantalor »

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…

> going to cause pain

What kind of attack on a git repo are you worried about?

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

#43

Post by asdfman123 »

api wrote: post #7
ImJasonH wrote: post #3

Reminder that GitHub has blocked Git commit collisions since 2017, and as far as anybody is aware hasn't seen one in the wild. https://github.blog/2017-03-20-sha-1-collision-detection-on-...

Random collisions in 160-bit space are incredibly unlikely. This is talking about intentional collision, and means that it's entirely feasible for someone with significant compute power to create a git commit that has the exact same hash as another git commit. This could allow someone to silently modify a git commit history to e.g. inject malware or a known "bug" into a piece of software. The modified repository woul…

> Random collisions in 160-bit space are incredibly unlikely

Just for fun: to get a 5% chance of a hash collision between ANY two numbers in an 160 bit space, you'd have to generate 3.9e23 hashes.

So you'd have to generate 1000 hashes per second for *12 trillion years.*

Formula:

n = sqrt(2 * 2^160 * ln(1/(1-0.05))

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

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

#44

Post by __s »

AnimalMuppet wrote: post #32
__s wrote: post #22

Earlier quoted context omitted.

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…

"Paragraph" is highly optimistic. IIRC, each English character has about 1 bit of entropy.

Shannon estimated 0.6 to 1.3: https://cs.fit.edu/~mmahoney/dissertation/entropy1.html

For the sake of argument I figured I'd be highly optimistic. The linked prize shows practical evidence of 1GB of Wikipedia being compressed below 1 bit per character (& that's with a limit of 50 hours cpu time, 10GB memory, & 100GB disk)

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

#45

Post by tantalor »

ImJasonH wrote: post #3

Reminder that GitHub has blocked Git commit collisions since 2017, and as far as anybody is aware hasn't seen one in the wild. https://github.blog/2017-03-20-sha-1-collision-detection-on-...

> A higher probability exists that every member of your programming team will be attacked and killed by wolves in unrelated incidents on the same night.

- Scott Chacon

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

#46

Post by umvi »

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…

"We note that classical collisions and chosen-prefix collisions do not threaten all usages of SHA-1."

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

#47

Post by asdfman123 »

tantalor wrote: post #45
ImJasonH wrote: post #3

Reminder that GitHub has blocked Git commit collisions since 2017, and as far as anybody is aware hasn't seen one in the wild. https://github.blog/2017-03-20-sha-1-collision-detection-on-...

> A higher probability exists that every member of your programming team will be attacked and killed by wolves in unrelated incidents on the same night. - Scott Chacon

That's even true if you make your developers commute into Yellowstone National Park by ski every day

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

#49

Post by snovv_crash »

tantalor wrote: post #42
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…

> going to cause pain What kind of attack on a git repo are you worried about?

Subrepo hash substitution could enable a supply-chain attack

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

#50

Post by noway421 »

api wrote: post #7
ImJasonH wrote: post #3

Reminder that GitHub has blocked Git commit collisions since 2017, and as far as anybody is aware hasn't seen one in the wild. https://github.blog/2017-03-20-sha-1-collision-detection-on-...

Random collisions in 160-bit space are incredibly unlikely. This is talking about intentional collision, and means that it's entirely feasible for someone with significant compute power to create a git commit that has the exact same hash as another git commit. This could allow someone to silently modify a git commit history to e.g. inject malware or a known "bug" into a piece of software. The modified repository woul…

From a practical point of view, how would injecting malware happen? If you're trying to insert a malicious diff somewhere deep in the git history, you would need to recompute all the other commits after the injected commit - which would most certainly change their commit ids too if they are touching the same file. When other commit ids change, the malicious change becomes detectable.

There's also the case for auditing: force pushing into an existing repo triggers an event in GitHub and is logged. While the logging event can be missed, it leaves a paper trail.

With things like reproduce-able builds, this also becomes harder. Distributing (through a means of a fork, or putting it up on a website mytotallylegitgitrepos.com) source code which builds into a binary which doesn't match upstream hash is suspicious.

Post reply on HN