4 ms·

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 branc

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.

adrian_b 4y ago
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.
mongol 4y ago
Has there ever been a hash collision happening in git by pure chance?
- Groxx 4y ago
  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.
  - mongol 4y ago
    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.
    - Groxx 4y ago
      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.
      - mongol 4y ago
        Good to know, and knowing this, it underlines how much sense Linus' decision makes
        Groxx 4y ago
        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.
stouset 4y ago
> 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.
- wyoung2 4y ago
  All of which is why Fossil now uses SHA3-256 by default. How long is it going to take Git to follow?
  - tasuki 4y ago
    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?)
    - wyoung2 4y ago
      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. :)
  - yjftsjthsd-h 4y ago

adrian_b 4y ago

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.

mongol 4y ago

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

Groxx 4y ago
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.
- mongol 4y ago
  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.
  - Groxx 4y ago
    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.
    - mongol 4y ago
      Good to know, and knowing this, it underlines how much sense Linus' decision makes
      - Groxx 4y ago
        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.

stouset 4y ago

> 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.

wyoung2 4y ago
All of which is why Fossil now uses SHA3-256 by default. How long is it going to take Git to follow?
- tasuki 4y ago
  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?)
  - wyoung2 4y ago
    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. :)
- yjftsjthsd-h 4y ago