如果我在使用git时发生了哈希冲突,会发生什么?

例如,我设法提交了两个具有相同sha1校验和的文件, git会注意到它还是会破坏其中一个文件?

git是否可以改进以适应这种情况,或者我必须更改为一个新的哈希算法?

(请不要通过讨论这有多不可能来转移这个问题-谢谢)


当前回答

用正确的“但是”来回答这个问题,而不解释为什么这不是一个问题是不可能的。如果没有很好地理解哈希是什么,是不可能做到这一点的。它比你在计算机科学课程中接触到的简单情况要复杂得多。

There is a basic misunderstanding of information theory here. If you reduce a large amount of information into a smaller amount by discarding some amount (ie. a hash) there will be a chance of collision directly related to the length of the data. The shorter the data, the LESS likely it will be. Now, the vast majority of the collisions will be gibberish, making them that much more likely to actually happen (you would never check in gibberish...even a binary image is somewhat structured). In the end, the chances are remote. To answer your question, yes, git will treat them as the same, changing the hash algorithm won't help, it'll take a "second check" of some sort, but ultimately, you would need as much "additional check" data as the length of the data to be 100% sure...keep in mind you would be 99.99999....to a really long number of digits.... sure with a simple check like you describe. SHA-x are cryptographically strong hashes, which means is't generally hard to intentionally create two source data sets that are both VERY SIMILAR to each other, and have the same hash. One bit of change in the data should create more than one (preferably as many as possible) bits of change in the hash output, which also means it's very difficult (but not quite impossible) to work back from the hash to the complete set of collisions, and thereby pull out the original message from that set of collisions - all but a few will be gibberish, and of the ones that aren't there's still a huge number to sift through if the message length is any significant length. The downside of a crypto hash is that they are slow to compute...in general.

So, what's it all mean then for Git? Not much. The hashes get done so rarely (relative to everything else) that their computational penalty is low overall to operations. The chances of hitting a pair of collisions is so low, it's not a realistic chance to occur and not be detected immediately (ie. your code would most likely suddenly stop building), allowing the user to fix the problem (back up a revision, and make the change again, and you'll almost certainly get a different hash because of the time change, which also feeds the hash in git). There is more likely for it to be a real problem for you if you're storing arbitrary binaries in git, which isn't really what it's primary use model is. If you want to do that...you're probably better off using a traditional database.

思考这个问题并没有错——这是一个很好的问题,很多人只是把它当作“太不可能了,不值得思考”——但实际上比这要复杂一些。如果它确实发生了,它应该很容易被检测到,它不会是正常工作流程中的无声损坏。

其他回答

好吧,我想我们现在知道会发生什么了——你应该预料到你的存储库会被损坏(源代码)。

git是否可以改进以适应这种情况,或者我必须更改为一个新的哈希算法?

任何哈希算法都有可能发生冲突,所以改变哈希函数并不能排除问题,它只是让它不太可能发生。所以你应该选择一个非常好的哈希函数(SHA-1已经是,但你要求不要被告知:)

如果两个文件在git中具有相同的哈希和,它会将这两个文件视为相同的。在绝对不可能发生这种情况的情况下,你可以总是返回一次提交,并更改文件中的某些内容,这样它们就不会再碰撞了……

请参阅Linus Torvalds的帖子“开始考虑sha-256?”的邮件列表。

用正确的“但是”来回答这个问题,而不解释为什么这不是一个问题是不可能的。如果没有很好地理解哈希是什么,是不可能做到这一点的。它比你在计算机科学课程中接触到的简单情况要复杂得多。

There is a basic misunderstanding of information theory here. If you reduce a large amount of information into a smaller amount by discarding some amount (ie. a hash) there will be a chance of collision directly related to the length of the data. The shorter the data, the LESS likely it will be. Now, the vast majority of the collisions will be gibberish, making them that much more likely to actually happen (you would never check in gibberish...even a binary image is somewhat structured). In the end, the chances are remote. To answer your question, yes, git will treat them as the same, changing the hash algorithm won't help, it'll take a "second check" of some sort, but ultimately, you would need as much "additional check" data as the length of the data to be 100% sure...keep in mind you would be 99.99999....to a really long number of digits.... sure with a simple check like you describe. SHA-x are cryptographically strong hashes, which means is't generally hard to intentionally create two source data sets that are both VERY SIMILAR to each other, and have the same hash. One bit of change in the data should create more than one (preferably as many as possible) bits of change in the hash output, which also means it's very difficult (but not quite impossible) to work back from the hash to the complete set of collisions, and thereby pull out the original message from that set of collisions - all but a few will be gibberish, and of the ones that aren't there's still a huge number to sift through if the message length is any significant length. The downside of a crypto hash is that they are slow to compute...in general.

So, what's it all mean then for Git? Not much. The hashes get done so rarely (relative to everything else) that their computational penalty is low overall to operations. The chances of hitting a pair of collisions is so low, it's not a realistic chance to occur and not be detected immediately (ie. your code would most likely suddenly stop building), allowing the user to fix the problem (back up a revision, and make the change again, and you'll almost certainly get a different hash because of the time change, which also feeds the hash in git). There is more likely for it to be a real problem for you if you're storing arbitrary binaries in git, which isn't really what it's primary use model is. If you want to do that...you're probably better off using a traditional database.

思考这个问题并没有错——这是一个很好的问题,很多人只是把它当作“太不可能了,不值得思考”——但实际上比这要复杂一些。如果它确实发生了,它应该很容易被检测到,它不会是正常工作流程中的无声损坏。

谷歌现在声称在某些前提条件下SHA-1碰撞是可能的: https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

由于git使用SHA-1来检查文件完整性,这意味着git中的文件完整性受到了损害。

在我看来,git应该使用更好的哈希算法,因为故意碰撞现在是可能的。