5 ms·

Given that the only way to reuse it is to duplicate the tree and commit metadata exactly, or find an sha1 collision, I think it's pretty safe. :) I wonder if t

by CUViper 12y ago

Given that the only way to reuse it is to duplicate the tree and commit metadata exactly, or find an sha1 collision, I think it's pretty safe. :) I wonder if there are any git sha1 collisions out there in aggregate, say across all of github. Would they even notice if there were?

meowface 12y ago
>I wonder if there are any git sha1 collisions out there in aggregate, say across all of github. Despite the incredibly high number of all commits there must be, I think the chance of a collision is still very unlikely. 2^160 is a pretty big number.
- gpvos 12y ago
  Too bad he didn't use SHA-256 though. It had been available for three years at that moment.
- MichaelGG 12y ago
  The number of inputs before a likely collision is more on the order of 2^80. Which is still pretty large.
  - meowface 12y ago
    True, the birthday paradox definitely makes it a lot more likely, but as you say the odds should still be too low.
  - thret 12y ago
    This is comparable to the number of atoms in the universe. Pretty large! We will never see an accidental collision.
    - zxcdw 12y ago
      Not quite, atoms in the universe is in the range of 10^80, which is a bit less than 2^266. On the other hand, 2^80 is "only" approx. 1.2 * 10^24. Still, good luck colliding with that without big effort.
- userbinator 12y ago
  There's a table in http://en.wikipedia.org/wiki/Birthday_attack http://en.wikipedia.org/wiki/Birthday_attack which gives some numbers, but it's missing the 160-bit entry. Nevertheless, even the number of 128 bits hashes required for a random collision are extremely high. In hindsight, it's good that git didn't choose MD5, since collisions for MD5 can be generated almost trivially now. However, the decreasing security of SHA-1 could be a concern for the future.
  - keypusher 12y ago
    I don't think commit hash was ever intended to be cryptographically secure. It's just a unique identifier. > Source control management systems such as Git and Mercurial use SHA-1 not for security but for ensuring that the data has not changed due to accidental corruption. Linus Torvalds has said about Git: "If you have disk corruption, if you have DRAM corruption, if you have any kind of problems at all, Git will notice them. It's not a question of if, it's a guarantee. You can have people who try to be malicious. They won't succeed. [...] Nobody has been able to break SHA-1, but the point is the SHA-1, as far as Git is concerned, isn't even a security feature. It's purely a consistency check. The security parts are elsewhere, so a lot of people assume that since Git uses SHA-1 and SHA-1 is used for cryptographically secure stuff, they think that, OK, it's a huge security feature. It has nothing at all to do with security, it's just the best hash you can get. http://en.wikipedia.org/wiki/SHA-1#Data_integrity http://en.wikipedia.org/wiki/SHA-1#Data_integrity
beagle3 12y ago
According to the Wikipedia entry[0], "No actual collisions have yet been produced", github or otherwise. The NSA might have produced them, but publicly non have been found, and it's not for lack of trying. [0] http://en.wikipedia.org/wiki/SHA-1 http://en.wikipedia.org/wiki/SHA-1
- CUViper 12y ago
  I take that statement to imply "on purpose", or as part of an attack. You can't know whether there's a coincidental collision anywhere in github unless you bother to look. But I do understand that it's still extremely improbable.
- hyp0 12y ago
  In a thousand years, a git sha-1 collision is going to cause a lot of trouble.

by CUViper 12y ago

meowface 12y ago

>I wonder if there are any git sha1 collisions out there in aggregate, say across all of github. Despite the incredibly high number of all commits there must be, I think the chance of a collision is still very unlikely. 2^160 is a pretty big number.

gpvos 12y ago
Too bad he didn't use SHA-256 though. It had been available for three years at that moment.
MichaelGG 12y ago
The number of inputs before a likely collision is more on the order of 2^80. Which is still pretty large.
- meowface 12y ago
  True, the birthday paradox definitely makes it a lot more likely, but as you say the odds should still be too low.
- thret 12y ago
  This is comparable to the number of atoms in the universe. Pretty large! We will never see an accidental collision.
  - zxcdw 12y ago
    Not quite, atoms in the universe is in the range of 10^80, which is a bit less than 2^266. On the other hand, 2^80 is "only" approx. 1.2 * 10^24. Still, good luck colliding with that without big effort.
userbinator 12y ago
There's a table in http://en.wikipedia.org/wiki/Birthday_attack http://en.wikipedia.org/wiki/Birthday_attack which gives some numbers, but it's missing the 160-bit entry. Nevertheless, even the number of 128 bits hashes required for a random collision are extremely high. In hindsight, it's good that git didn't choose MD5, since collisions for MD5 can be generated almost trivially now. However, the decreasing security of SHA-1 could be a concern for the future.
- keypusher 12y ago
  I don't think commit hash was ever intended to be cryptographically secure. It's just a unique identifier. > Source control management systems such as Git and Mercurial use SHA-1 not for security but for ensuring that the data has not changed due to accidental corruption. Linus Torvalds has said about Git: "If you have disk corruption, if you have DRAM corruption, if you have any kind of problems at all, Git will notice them. It's not a question of if, it's a guarantee. You can have people who try to be malicious. They won't succeed. [...] Nobody has been able to break SHA-1, but the point is the SHA-1, as far as Git is concerned, isn't even a security feature. It's purely a consistency check. The security parts are elsewhere, so a lot of people assume that since Git uses SHA-1 and SHA-1 is used for cryptographically secure stuff, they think that, OK, it's a huge security feature. It has nothing at all to do with security, it's just the best hash you can get. http://en.wikipedia.org/wiki/SHA-1#Data_integrity http://en.wikipedia.org/wiki/SHA-1#Data_integrity

beagle3 12y ago

According to the Wikipedia entry[0], "No actual collisions have yet been produced", github or otherwise. The NSA might have produced them, but publicly non have been found, and it's not for lack of trying. [0] http://en.wikipedia.org/wiki/SHA-1 http://en.wikipedia.org/wiki/SHA-1

CUViper 12y ago
I take that statement to imply "on purpose", or as part of an attack. You can't know whether there's a coincidental collision anywhere in github unless you bother to look. But I do understand that it's still extremely improbable.
hyp0 12y ago
In a thousand years, a git sha-1 collision is going to cause a lot of trouble.