Hacker News Reader

Comment by williamstein | Hacker News Reader

A really critical sneaky trick that Linus pulled in the implementation of Git was to just pretend like Sha1 hashes never collide, which helped make "cheap branching, robust conflict management, and offline workflows" possible. This (false but convenient) assumption massively reduced the complexity of many algorithms, and allowed Git to efficiently do things that other source control systems couldn't do. I personally switched from Darcs to Git about 15 years ago entirely due to performance issues.

View on HN

> A… sneaky trick that Linus pulled… was to just pretend like Sha1 hashes never collide. This (false but convenient) assumption…

As an infosec engineer, this is a bit disingenuous. From a statistical perspective, you can pretty much assume that it's impossible to create colliding SHA-1 hashes.

In the intervening years we've discovered security flaws in SHA-1 that allow attackers to create collisions under certain circumstances. That's not great, and now we have ways to migrate repositories to SHA-256 hashes (although it's not yet the default).

But this decision wasn't "sneaky". Cryptographers everywhere routinely build systems under the assumption that hash collisions can't happen, because that's an explicit design goal of hash functions. If we ever find a way that this doesn't hold true, the answer isn't to design the system around the possibility of a collision, it's to switch to a better hash.

All of which is why Fossil now uses SHA3-256 by default.

How long is it going to take Git to follow?

Have hash collisions in Git ever been a problem for you?

What is the exact scenario in which a hash collision would be dangerous? (Like, you give some random person push access to your repository and... I'm really getting lost here... they override some commit with a different commit with the same hash? And that's somehow worse than them just creating a new commit with a different hash, which you would notice for sure? And the only reason you won't notice their Evil Change is because they sneaked it in inside a hash collision?)

We don't know how to push bad artifacts into a Merkle tree by exploiting SHA-1's weaknesses. The thing is, though, we didn't want to be pushed into scrambling for a better hash algorithm after some clever bastard works that trick out. :)

It appears that git currently has experimental, non-backward-compatible support for sha256, so I'd guess "as soon as they finish fixing any issues and figure out a nice upgrade path", with the caveat that there's little pressure because it's not actually a practical problem yet and isn't expected to be one in the foreseeable future.

Fossil's method is backwards-compatible, and we published the method for it five years ago (2017-03-05): https://fossil-scm.org/home/doc/trunk/www/hashpolicy.wiki

The assumption that with an 160-bit hash you will not get collisions is pretty safe.

I have actually searched for collisions by hashing several tens of millions of files with various hashes.

With shorter hashes I have seen collisions, but even with an 128-bit good hash there were no collisions, much less with an 160-bit hash.

Unless you hash many billions of things, the chances of SHA-1 collisions are negligible.

Has there ever been a hash collision happening in git by pure chance?

I suspect the answer is "probably yes", since SHA-1 collisions do exist, and practical ways to generate collisions are known.

Which doesn't mean it's currently risky, I'm not sure how you'd turn a collision into an attack without leaning on external systems (like code review that approves by SHA, and allows you to push later). But if MD5's history is any clue, that will not be true in the long run.

The time to begin moving to a new algorithm was several years ago, when those collisions were demonstrated. Git is unambiguously lagging behind basic security practices here, though that's likely currently fine. The question is for how long that will remain true, and that's something that can only be answered after it has already become unsafe.

I was thinking collision due to a new commit causing a hash that equals an already existing hash. Just by chance, but in the course of normal use.

Yeah. I think it's still "probably has happened", but it is very very easy to work around: just try again. The timestamp (and thus the hash) will have changed.

Or if I'm wrong about the timestamp being part of the computed checksum: add a space to your commit message. Very simple.

Good to know, and knowing this, it underlines how much sense Linus' decision makes

Yeah, the non-malicious failure mode is extremely reasonable, and overall I think it's a good choice... minus not building in support for changing the algorithm from the beginning. Checksum algorithms somewhat regularly need changing. This was completely foreseeable.

The malicious failure modes... I don't know. No doubt something is possible, particularly when you account for common surrounding-system usage patterns.

Reply on news.ycombinator.com