3 ms·

The forged hash collision will always be a weak point. Things will get worse with cost reduction of processing power. It's a loosing battle. The only way to de

by chmike 10y ago

The forged hash collision will always be a weak point. Things will get worse with cost reduction of processing power. It's a loosing battle. The only way to detect without error two identical files is by comparing the files. This comparison can be speed up by comparing compressed version of the files. The other functionality of hashes is to build a presumably unique file identifier. The byte sequence of the compressed file could serve as identifer. So instead of using the file system as index with the sha1 name as file name, we would have to build a specific database organized as a set whose values (compressed files) would be the keys. A hash index could be used to speed up the search and equality test. Here a very fast hash would do the trick. Sha1 or a faster hash would be ok. The file system could then be used to organize the hash buckets as does git. File comparision would of course first compare compressed and uncompressed file size. Or use other hashes or longer hash values to detect different files. When all these values are identical, then a file comparison must be performed to detect if we have a collision. File compression can only get better and faster. So basically git would only need to add hash collision detection and the capacity to support different objects with the same hash identifier.

vbezhenar 10y ago
With reasonably long cryptographically strong hashes it's not a weak point (or you could call almost all cryptography a weak point). Weak point is hard-coded algorithms and sizes into Git (if I understood the problem correctly). Software should be written with more generic approach, so algorithms could be changed and migrated when necessary. SHA-1 is considered weak for many years, git should've migrated from it already.
- DougBTX 10y ago
  Git could have been written with a pluggable hash system, but for something that needs to be changed let's say once every ten years, is the up front cost really worth it?
  - adrianN 10y ago
    How hard is it to introduce a global constant for the number of bits in your hash instead of writing char hash[40] everywhere?
    - pilif 10y ago
      That's not good enough though if you need to work with repositories that were made with previous releases. Just converting them is one thing, but what if you need to stay compatible indefinitely. And what about old releases that encounter a new repo? And what about URLs and emails that reference commit hashes? Think archives of mailing lists that suddenly become useless unless there's a way to keep both hashes around. Yes. These are all solvable problems (maybe not the old-release needing to handle new-style repo gracefully), but the complexity is much higher than upgrading a global constant.
      - adrianN 10y ago
        I think you could solve most problems by just enabling a different hash function with no backwards compatibility. Repositories have a format-version somewhere, and migrating from git to git-with-new-hash should be a fairly simple operation. You can always edit commit messages to add "corresponds to commit <sha1> in <old repo>". This is of course not as nice as full backwards compatibility, but it gets rid of the security problem for relatively cheap.
    - emn13 10y ago
      The problem isn't the number of bits (yet). The problem is the choice of hash. A truncated sha2 would still be fine for years to come (barring a sha2 break, which doesn't look imminent). 160bits may not be a huge margin, but it's still enough.
- hvidgaard 10y ago
  > With reasonably long cryptographically strong hashes it's not a weak point (or you could call almost all cryptography a weak point). We do not yet know if one way functions truly exists, so from a theoretical standpoint, any hash function is a weakpoint if you do not properly handle malicious collisions. > SHA-1 is considered weak for many years, git should've migrated from it already. Linus addressed this many years ago, when de was working on the first version of Git. It was chosen, despite the fact that it was known to be weakened. I don't know if they lost sight of this, or the geniuenly still believe that malicious colliding hashes are not a problem. I do not know enough about the intimate details of Git to comment on that fact.
adrianN 10y ago
If you use a strong hash with say 256 bits, it's not a weak point. Random collisions are less likely than cosmic rays flipping bits in your programs and unless you don't believe in strong cryptography attackers can't do much better.

by chmike 10y ago

vbezhenar 10y ago

With reasonably long cryptographically strong hashes it's not a weak point (or you could call almost all cryptography a weak point). Weak point is hard-coded algorithms and sizes into Git (if I understood the problem correctly). Software should be written with more generic approach, so algorithms could be changed and migrated when necessary. SHA-1 is considered weak for many years, git should've migrated from it already.

DougBTX 10y ago
Git could have been written with a pluggable hash system, but for something that needs to be changed let's say once every ten years, is the up front cost really worth it?
- adrianN 10y ago
  How hard is it to introduce a global constant for the number of bits in your hash instead of writing char hash[40] everywhere?
  - pilif 10y ago
    That's not good enough though if you need to work with repositories that were made with previous releases. Just converting them is one thing, but what if you need to stay compatible indefinitely. And what about old releases that encounter a new repo? And what about URLs and emails that reference commit hashes? Think archives of mailing lists that suddenly become useless unless there's a way to keep both hashes around. Yes. These are all solvable problems (maybe not the old-release needing to handle new-style repo gracefully), but the complexity is much higher than upgrading a global constant.
    - adrianN 10y ago
      I think you could solve most problems by just enabling a different hash function with no backwards compatibility. Repositories have a format-version somewhere, and migrating from git to git-with-new-hash should be a fairly simple operation. You can always edit commit messages to add "corresponds to commit <sha1> in <old repo>". This is of course not as nice as full backwards compatibility, but it gets rid of the security problem for relatively cheap.
  - emn13 10y ago
    The problem isn't the number of bits (yet). The problem is the choice of hash. A truncated sha2 would still be fine for years to come (barring a sha2 break, which doesn't look imminent). 160bits may not be a huge margin, but it's still enough.
hvidgaard 10y ago
> With reasonably long cryptographically strong hashes it's not a weak point (or you could call almost all cryptography a weak point). We do not yet know if one way functions truly exists, so from a theoretical standpoint, any hash function is a weakpoint if you do not properly handle malicious collisions. > SHA-1 is considered weak for many years, git should've migrated from it already. Linus addressed this many years ago, when de was working on the first version of Git. It was chosen, despite the fact that it was known to be weakened. I don't know if they lost sight of this, or the geniuenly still believe that malicious colliding hashes are not a problem. I do not know enough about the intimate details of Git to comment on that fact.

adrianN 10y ago

If you use a strong hash with say 256 bits, it's not a weak point. Random collisions are less likely than cosmic rays flipping bits in your programs and unless you don't believe in strong cryptography attackers can't do much better.