4 ms·

Git's use of SHA1 is explicitly not intended to provide any security (per Linus), so this argument really doesn't make sense. On github, right now, I can commit

by ryan-c 11y ago

Git's use of SHA1 is explicitly not intended to provide any security (per Linus), so this argument really doesn't make sense. On github, right now, I can commit as you all I want, no exploits required, and that seems like a much more pressing reason to sign commits. The other thing is that the SHA1 weaknesses are collisions. It's not likely to be possible in the foreseeable future to create a commit that matches an arbitrary hash - to generate colliding commits, the committer would need to generate the good and evil commit at the same time.

joeyh 11y ago
The existence of things that claim to have been committed as me, with no proof and not in the history of my master branch or a released tag, is irrelevant. My users use my release tags, and my master branch, they don't use random commits you make "as me" elsewhere. Before SHA1 is broken, you can't change things that I have committed, unless you have access to my account. If a SHA1 preimage attack becomes available, you can. If a SHA1 bithday attack becomes available (for the low low price of $75k, croudfund one today!), you can, by sending me some particularly evil forms of merge requests.
- espadrine 11y ago
  > If a SHA1 preimage attack becomes available, you can. Actually, no. You need a SHA-1 second-preimage attack, which is vastly more difficult. However, even if there was one, it would cause git pull to fail, as downloading the objects would likely require terabytes of garbage data.
  - _asummers 11y ago
    What evidence do you have for the terabytes claim? Not saying you're incorrect, but I'm unfamiliar with any literature that suggests that.
    - cjbprime 11y ago
      If there is another input that SHAs to the same commit hash, it's not going to be as small, and it's not going to look like a standard patch. I'm not sure "terabytes" is justified either, but the point's a good one.
    - espadrine 11y ago
      Like I said, finding a SHA-1 second-preimage attack is vastly more difficult than finding a SHA-1 preimage attack. You can claim to have found one as soon as you have any means that is not brute-force which produces a colliding preimage, no matter how practical it is (ie, it could require the use of humanity's entire energy spending for a thousand years, and more disk space than can be built with the Earth's atoms). In theory, nothing I know forbids the possibility of finding an algorithm which yields a 160-bit solution within a few years. In practice, such an algorithm is tremendously more difficult (and potentially impossible) to find than simply finding a SHA-1 second-preimage attack, which is already vastly more difficult to find than a preimage attack, which is also vastly more difficult than getting a non-bruteforce collision. It would certainly be a phenomenal achievement, however. We still don't have a practical preimage attack on MD5, 10 years after the first actual collision found… Regardless, we're only now beating the first challenge after 20 years. It is likely to take more to go from there to a second-preimage attack, and more still to have it be a 160-bit solution within a practical amount of time. git will double its lifetime multiple times before then. Something shinier will have replaced it.
  - jepler 11y ago
    nah, "terabytes of garbage data" is unlikely to be required. Consider the case of taking the SHA1 of a message only 1024 bits (128) characters long (shorter than a tweet, let alone this reply). There are 2^1024 such messages, but only 2^160 hashes. So on average, there are 2^(1024-160) = 2^864 ~= 1.2x10^260 messages of length 1024 that must share each SHA1 hash. It would be a very interesting result if you could prove that you had some 1024-bit message that didn't share a SHA1 hash with any other message of length less than 1TB ~= 8x10^12 bits, and this property couldn't be true of very many 1024-bit messages, because this means you "take away" from the hash space of messages of length 1032 to length 8x10^12. If you took away just 2^140 out of the 2^160 hashes, for instance, we'd readily see hash collisions in those in-between sizes, because there would just be 2^20 hashes left. But even then, this special property you imagine would only apply to 1 in 2^884 ~= 1 in 1.2x10^254 of all 1024-bit messages so you'd have trouble finding one of them in the first place, and more to the point it's almost impossible that your victim would have selected one of these hashes that would require your hypothetical terabyte file to collide the SHA1 hash.

by ryan-c 11y ago

joeyh 11y ago

The existence of things that claim to have been committed as me, with no proof and not in the history of my master branch or a released tag, is irrelevant. My users use my release tags, and my master branch, they don't use random commits you make "as me" elsewhere. Before SHA1 is broken, you can't change things that I have committed, unless you have access to my account. If a SHA1 preimage attack becomes available, you can. If a SHA1 bithday attack becomes available (for the low low price of $75k, croudfund one today!), you can, by sending me some particularly evil forms of merge requests.

espadrine 11y ago
> If a SHA1 preimage attack becomes available, you can. Actually, no. You need a SHA-1 second-preimage attack, which is vastly more difficult. However, even if there was one, it would cause git pull to fail, as downloading the objects would likely require terabytes of garbage data.
- _asummers 11y ago
  What evidence do you have for the terabytes claim? Not saying you're incorrect, but I'm unfamiliar with any literature that suggests that.
  - cjbprime 11y ago
    If there is another input that SHAs to the same commit hash, it's not going to be as small, and it's not going to look like a standard patch. I'm not sure "terabytes" is justified either, but the point's a good one.
  - espadrine 11y ago
    Like I said, finding a SHA-1 second-preimage attack is vastly more difficult than finding a SHA-1 preimage attack. You can claim to have found one as soon as you have any means that is not brute-force which produces a colliding preimage, no matter how practical it is (ie, it could require the use of humanity's entire energy spending for a thousand years, and more disk space than can be built with the Earth's atoms). In theory, nothing I know forbids the possibility of finding an algorithm which yields a 160-bit solution within a few years. In practice, such an algorithm is tremendously more difficult (and potentially impossible) to find than simply finding a SHA-1 second-preimage attack, which is already vastly more difficult to find than a preimage attack, which is also vastly more difficult than getting a non-bruteforce collision. It would certainly be a phenomenal achievement, however. We still don't have a practical preimage attack on MD5, 10 years after the first actual collision found… Regardless, we're only now beating the first challenge after 20 years. It is likely to take more to go from there to a second-preimage attack, and more still to have it be a 160-bit solution within a practical amount of time. git will double its lifetime multiple times before then. Something shinier will have replaced it.
- jepler 11y ago
  nah, "terabytes of garbage data" is unlikely to be required. Consider the case of taking the SHA1 of a message only 1024 bits (128) characters long (shorter than a tweet, let alone this reply). There are 2^1024 such messages, but only 2^160 hashes. So on average, there are 2^(1024-160) = 2^864 ~= 1.2x10^260 messages of length 1024 that must share each SHA1 hash. It would be a very interesting result if you could prove that you had some 1024-bit message that didn't share a SHA1 hash with any other message of length less than 1TB ~= 8x10^12 bits, and this property couldn't be true of very many 1024-bit messages, because this means you "take away" from the hash space of messages of length 1032 to length 8x10^12. If you took away just 2^140 out of the 2^160 hashes, for instance, we'd readily see hash collisions in those in-between sizes, because there would just be 2^20 hashes left. But even then, this special property you imagine would only apply to 1 in 2^884 ~= 1 in 1.2x10^254 of all 1024-bit messages so you'd have trouble finding one of them in the first place, and more to the point it's almost impossible that your victim would have selected one of these hashes that would require your hypothetical terabyte file to collide the SHA1 hash.