git - git中的哈希冲突

Question

如果我在使用 git 时发生哈希冲突，实际上会发生什么？

例如我设法提交了两个具有相同 sha1 校验和的文件， git 会注意到它或损坏其中一个文件吗？

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

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

Answer 1

在 10 个卫星上挑选原子

SHA-1 散列是一个 40 十六进制字符串...每个字符 4 位乘以 40...160 位。现在我们知道 10 位大约是 1000(准确地说是 1024)，这意味着有 1 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 个不同的 SHA-1 哈希...10^48.

这相当于什么？好吧，月球由大约 10⁴⁷ 原子组成。因此，如果我们有 10 个卫星......并且你在其中一个卫星上随机选择一个原子......然后继续在它们上再次选择一个随机原子......那么你可能会选择同一个原子两次, 是两个给定的 git 提交具有相同 SHA-1 哈希值的可能性。

在此基础上展开，我们可以问这个问题......

在开始担心冲突之前，您需要在存储库中进行多少次提交？

这与所谓的“生日攻击”有关，它又指的是“生日悖论”或“生日问题”，它指出当您从给定的集合中随机挑选时，您需要的选择少得惊人，然后您会得到更多很可能没有选择两次。但“少得惊人”在这里是一个非常相对的术语。

维基百科有 a table on the probability of Birthday Paradox collisions .没有 40 个字符散列的条目。但是对 32 和 48 个字符的条目进行插值使我们在 5*10²² git 提交的范围内发生冲突的概率为 0.1%。这是五万亿次不同的提交，或者五十次 Zettacommits，在你发生碰撞的几率甚至达到 0.1% 之前。

仅这些提交的哈希字节总和就比地球上一年生成的所有数据还要多，也就是说，您需要比 YouTube 流式传输视频更快地制作代码。祝你好运。 :D

重点是，除非有人故意造成碰撞，否则随机发生碰撞的可能性小得惊人，您可以忽略这个问题

“但是当碰撞确实发生时，实际发生了什么？”

好吧，假设确实发生了不可能的事情，或者假设有人设法定制了 a deliberate SHA-1 hash collision .那么会发生什么？

在这种情况下有 an excellent answer where someone experimented on it .我将引用该答案:

1. If a blob already exists with the same hash, you will not get any warnings at all. Everything seems to be ok, but when you push, someone clones, or you revert, you will lose the latest version (in line with what is explained above).
2. If a tree object already exists and you make a blob with the same hash: Everything will seem normal, until you either try to push or someone clones your repository. Then you will see that the repo is corrupt.
3. If a commit object already exists and you make a blob with the same hash: same as #2 - corrupt
4. If a blob already exists and you make a commit object with the same hash, it will fail when updating the "ref".
5. If a blob already exists and you make a tree object with the same hash. It will fail when creating the commit.
6. If a tree object already exists and you make a commit object with the same hash, it will fail when updating the "ref".
7. If a tree object already exists and you make a tree object with the same hash, everything will seem ok. But when you commit, all of the repository will reference the wrong tree.
8. If a commit object already exists and you make a commit object with the same hash, everything will seem ok. But when you commit, the commit will never be created, and the HEAD pointer will be moved to an old commit.
9. If a commit object already exists and you make a tree object with the same hash, it will fail when creating the commit.

如您所见，有些情况并不理想。特别是案例 #2 和 #3 会弄乱你的存储库。但是，故障似乎确实存在于该存储库中，并且攻击或奇怪的不可能性不会传播到其他存储库。

此外，蓄意碰撞问题似乎被视为真正的威胁，例如 GitHub is taking measures to prevent it .