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

181–190 of 210 posts

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

#181

Post by stevekemp »

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…

> If git were designed today it would probably use SHA2 or SHA3 but it's probably not going to change due to the massive install base.

There is some work going on to change this, but it's not an easy task:

https://lwn.net/Articles/811068/

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

#182

Post by swutas »

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.

But this is technically an invalid answer to the problem of file compression. An easy (!) way for data to be losslessly compressed would just be to have a registry of all files in existence, and to refer to each file by its index in the registry. (Like the prisoners who had told each other all their jokes so many times that now they could just quote them by number and everyone would laugh.) Data compression is supposed to be able to deal with novel but likely documents without needing to add them to a global registry.

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

#183

Post by Jensson »

Dylan16807 wrote: post #180
cortesoft wrote: post #150

Earlier quoted context omitted.

This is why I always get mad when people say something like "you are more likely to be struck by lightning than eaten by a shark!".... we'll, that REALLY depends on where you are.

> that REALLY depends on where you are There's only 10 fatal shark attacks per year. What's your calculation for the sharkiest area to live? It has to be something like 100+ times sharkier than average for your claim to be true. And keep in mind that half the US population can easily day trip to the ocean. Edit: Actually, that's using a number of 2000 lightning fatalities which might be 10x too low. And lightning inj…

You focused on the shark side and not on the lightning side. You will never get struck by lightning in a city, so there the probability is 0. Similarly if you go out swimming in the ocean on a sunny day the probability of getting struck by lightning is also 0, but the probability of getting eaten by a shark is not 0.

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

#184

Post by Dylan16807 »

Jensson wrote: post #183
Dylan16807 wrote: post #180

Earlier quoted context omitted.

> that REALLY depends on where you are There's only 10 fatal shark attacks per year. What's your calculation for the sharkiest area to live? It has to be something like 100+ times sharkier than average for your claim to be true. And keep in mind that half the US population can easily day trip to the ocean. Edit: Actually, that's using a number of 2000 lightning fatalities which might be 10x too low. And lightning inj…

You focused on the shark side and not on the lightning side. You will never get struck by lightning in a city, so there the probability is 0. Similarly if you go out swimming in the ocean on a sunny day the probability of getting struck by lightning is also 0, but the probability of getting eaten by a shark is not 0.

You're going too granular. This is about populations that live in certain areas, not specific people on specific days. "depends on where you are" when talking about an over-time risk ratio. The goal isn't to find some dude with weird habits.

And while a population that mostly stays inside a city has a reduced lightning chance, it also has a reduced shark chance. I don't think that's anywhere near the point of equalizing the rate.

If you have an idea for a factor that dramatically reduces lightning risk but doesn't reduce shark risk much, I'm interested.

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

#185

Post by radishingr »

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…

I believe it let's you substitute an entire chain of commits based on some starting commit.

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

#186

Post by rini17 »

deckard1 wrote: post #118
noway421 wrote: post #64

Earlier quoted context omitted.

The possible attack is to prepare 2 versions of a commit, both resulting in the same commit id. Then later on, after the project is successful/etc, swap out the commit with the second version, while keeping the other commits intact. Granted, the file that the commit touches would need to be not touched in other commits. That's not out of question in a typical software project - maybe a file in the utils folder which…

> swap out the commit What's the method for doing this? Does a "git push" replace objects with identical hashes on the remote? Or a "git pull" replace identical hashes on the local repo? I suspect finding a hash collision is only the first difficult part of actually pulling this off. You may need direct write access to the file system of the target. And even then everyone else that has already fetched the repo may no…

The history teaches us: If any system isn't hardened against something, we can assume it's possible. If Git server isn't specifically hardened against that, it might still be tricked to update the file by adversary client. Or attacker can temporarily add hooks that will replace the file on server. Or integration testing system might have write access to the server repo.

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

#187

Post by b3n »

zzo38computer wrote: post #155

Fortunately, Fossil can now use SHA3-256 as well as SHA-1 (even in the same repository if necessary, perhaps due to upgrading an older repository), and I think it also has a hard mode to detect if SHA-1 collisions seem likely. (I think git doesn't allow a repository to have multiple kind of hashes; from what I understand, only a single algorithm must be used.) Since SHA-1 and SHA3-256 have different hash length, you…

Unfortunately Fossil uses a fast SHA hash for the password hashes of user accounts in the database, rather than a key derivation function, which is disappointing.

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

#188

Post by RicoElectrico »

tialaramex wrote: post #67
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…

The defence used by GitHub specifically defends against these intentional collisions, not some mirage of random collisions. Basically you collide a hash like SHA-1 or MD5 by getting it into a state where transitions don't twiddle as many bits, and then smashing the remaining bits by brute force trial. But, such states are weird so from inside the hash algorithm you can notice "Huh, this is that weird state I care abo…

So, if I understand correctly: the patched SHA-1 code generates the same hash, but is has checks on the internal state so that it will flag inputs which are likely to be intentionally colliding?

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

#189

Post by gspr »

sirclueless wrote: post #141
dude187 wrote: post #126

Earlier quoted context omitted.

You'd also need the actual patch to survive future commits, especially without introducing any merge conflicts

Commits aren't patches. They contain the whole tree. Retroactively changing a commit can't possibly introduce conflicts with other commits on top of it, the worst it can do is introduce big funny-looking diffs.

> Commits aren't patches.

Indeed. I'd add that this is, in my, experience one of the biggest sources of misunderstanding for people new to git. It isn't helped by the fact that a lot of git introductions (well-meaningly) emphasize diffs between commits.

Darcs (http://darcs.net/) is an example of a truly patch-centric DVCS. While I think git is great and that its ubiquitousness has made the world better, I'm always a bit sad when reminded of what could have been with Darcs (for all its problems).

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

#190

Post by versteegen »

RicoElectrico wrote: post #188
tialaramex wrote: post #67

Earlier quoted context omitted.

The defence used by GitHub specifically defends against these intentional collisions, not some mirage of random collisions. Basically you collide a hash like SHA-1 or MD5 by getting it into a state where transitions don't twiddle as many bits, and then smashing the remaining bits by brute force trial. But, such states are weird so from inside the hash algorithm you can notice "Huh, this is that weird state I care abo…

So, if I understand correctly: the patched SHA-1 code generates the same hash, but is has checks on the internal state so that it will flag inputs which are likely to be intentionally colliding?

Yes. https://github.com/cr-marcstevens/sha1collisiondetection
Post reply on HN