210

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

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

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

（请不要通过讨论不太可能来转移这个问题 - 谢谢）

4

9 回答 9

133

在 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 47个原子组成的。因此，如果我们有 10 个卫星……你在其中一个卫星上随机选择一个原子……然后继续在它们上再次选择一个随机原子……那么你会选择同一个原子两次的可能性, 是两个给定的 git 提交具有相同 SHA-1 哈希的可能性。

扩展这个我们可以问这个问题......

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

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

维基百科有一张关于生日悖论碰撞概率的表格。没有 40 个字符的哈希条目。但是 32 和 48 个字符的条目的插值使我们处于 5*10 22次git 提交的范围内，碰撞概率为 0.1%。那是 50,000 亿次不同的提交，或 50个 Zettacommits，在你达到甚至 0.1% 的机会发生碰撞之前。

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

关键是除非有人故意造成碰撞，否则随机发生碰撞的概率非常小，你可以忽略这个问题

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

好吧，假设不可能的事情确实发生了，或者假设有人设法定制了一个故意的 SHA-1 哈希冲突。那会发生什么？

在这种情况下，有一个很好的答案，有人对其进行了实验。我将引用该答案：

  1. 如果已存在具有相同哈希的 blob，则根本不会收到任何警告。一切似乎都很好，但是当你推送时，有人克隆，或者你恢复，你将丢失最新版本（与上面解释的一致）。
  2. 如果树对象已经存在并且您使用相同的哈希创建了一个 blob：一切看起来都很正常，直到您尝试推送或有人克隆您的存储库。然后你会看到 repo 已经损坏了。
  3. 如果提交对象已经存在并且您使用相同的哈希创建了一个 blob：与 #2 相同 - 已损坏
  4. 如果一个 blob 已经存在并且您使用相同的哈希创建了一个提交对象，那么在更新“ref”时它将失败。
  5. 如果 blob 已经存在，并且您使用相同的哈希创建树对象。创建提交时它将失败。
  6. 如果树对象已经存在并且您使用相同的哈希创建提交对象，则更新“ref”时它将失败。
  7. 如果一个树对象已经存在并且你创建了一个具有相同哈希的树对象，那么一切看起来都很好。但是当你提交时，所有的存储库都会引用错误的树。
  8. 如果提交对象已经存在，并且您使用相同的哈希创建提交对象，那么一切看起来都很好。但是当您提交时，将永远不会创建提交，并且 HEAD 指针将移动到旧提交。
  9. 如果提交对象已经存在并且您使用相同的哈希创建树对象，则在创建提交时它将失败。

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

此外，故意碰撞问题似乎被认为是一个真正的威胁，因此例如GitHub 正在采取措施防止它。

于 2014-04-23T19:09:30.457 回答
67

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

请参阅Linus Torvalds 在主题“开始考虑 sha-256？”中的帖子。在 git 邮件列表中。

于 2012-05-03T15:31:15.427 回答
25

如果不解释为什么这不是问题，就不可能用正确的“但是”来回答这个问题。如果没有真正掌握哈希的真正含义，就不可能做到这一点。它比您在 CS 程序中可能遇到的简单案例要复杂得多。

这里对信息论有一个基本的误解。如果您通过丢弃一些数量（即哈希）将大量信息减少为更少量的信息，则可能会发生与数据长度直接相关的冲突。数据越短，它就越不可能。现在，绝大多数碰撞都是乱码，使它们更有可能实际发生（你永远不会检查乱码......即使是二进制图像也有点结构化）。最后，机会很渺茫。要回答您的问题，是的，git 会将它们视为相同，更改哈希算法无济于事，需要进行某种“第二次检查”，但最终，您将需要尽可能多的“附加检查”数据因为数据的长度是 100% 确定的......请记住，您将是 99.99999.... 到一个非常长的数字......肯定像你描述的那样简单检查。SHA-x 是加密强哈希，这意味着通常不难故意创建两个彼此非常相似且具有相同哈希的源数据集。数据中的一点变化应该在散列输出中产生不止一个（最好尽可能多）位的变化，这也意味着从散列返回到完整的一组非常困难（但并非完全不可能）冲突，从而从那组冲突中提取出原始消息——除了少数之外，所有的都是乱码，如果消息长度足够长，那么在那些没有的消息中仍然有大量需要筛选。加密哈希的缺点是它们的计算速度很慢……一般来说。

那么，这对 Git 意味着什么呢？不多。哈希很少（相对于其他所有内容）完成，以至于它们的计算代价总体上对操作来说很低。发生一对碰撞的机会是如此之低，这不是一个现实的机会发生并且不会立即被检测到（即您的代码很可能会突然停止构建），允许用户解决问题（备份修订，并再次进行更改，由于时间更改，您几乎肯定会得到不同的哈希值，这也提供了 git 中的哈希值）。如果您在 git 中存储任意二进制文件，这对您来说更有可能是一个真正的问题，这并不是它的主要使用模型。如果你想这样做......你可能最好使用传统数据库。

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

于 2013-06-30T00:03:42.863 回答
14

您可以在“ Git 如何处理 blob 上的 SHA-1 冲突？ ”中看到一个很好的研究。

由于现在可能发生 SHA1 冲突（正如我在shattered.io的答案中引用的那样），知道 Git 2.13（2017 年第二季度）将通过SHA-1 实现的“检测尝试创建冲突”变体改善/缓解当前情况作者：Marc Stevens (CWI) 和 Dan Shumow (Microsoft)。

请参阅Jeff King ( )的提交 f5f5e7f、提交 8325e43、提交 c0c2006、提交 45a574e、提交 28dc98e（2017 年 3 月 16 日） 。（由Junio C Hamano 合并 -- --在提交 48b3693中，2017 年 3 月 24 日）peff
gitster

Makefile: 设为DC_SHA1默认

我们过去默认使用 OpenSSL 库中的 SHA1 实现。
由于我们在最近的“破碎”公告之后试图小心防止碰撞攻击，因此切换默认值以鼓励人们改用 DC_SHA1 实现。
那些想要使用 OpenSSL 实现的人可以OPENSSL_SHA1=YesPlease在运行“ make”时明确要求它。

我们实际上没有 Git 对象冲突，所以我们能做的最好的事情就是通过 test-sha1 运行其中一个破碎的 PDF。这应该触发碰撞检查并死亡。

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

使用 Git 2.16（2018 年第一季度）更新 2017 年 12 月：支持替代 SHA 的努力正在进行中：请参阅“为什么 Git 不使用更现代的 SHA？ ”。

您将能够使用另一种哈希算法：SHA1 不再是 Git 的唯一算法。

Git 2.18（2018 年第二季度）记录了该过程。

请参阅Ævar Arnfjörð Bjarmason ( ) 的提交 5988eb6和提交 45fa195（2018 年 3 月 26 日）。（由Junio C Hamano 合并 -- --在d877975 提交中，2018 年 4 月 11 日）avar
gitster

doc hash-function-transition: 阐明 SHAttered 的含义

尝试澄清 SHAttered 攻击在实践中对 Git 意味着什么。
之前版本的文本没有提到 Git 已经针对这种特定攻击提供了缓解措施，SHAttered 研究人员声称这将检测到密码分析碰撞攻击。

我可能弄错了一些细微差别，但据我所知，这篇新文本准确地总结了 git 中 SHA-1 的当前情况。即git 不再真正使用 SHA-1，它使用 Hardened-SHA-1（它们恰好在 99.99999999999...% 的时间内产生相同的输出）。

因此，先前的文本断言以下内容是不正确的：

[...]由于 [SHAttered]，SHA-1 不再被认为是加密安全的 [...]

事实并非如此。我们有针对 SHAttered 的缓解措施，但 我们认为，NewHash如果未来出现 SHA-1 或 Hardened-SHA-1 中的漏洞，我们应该谨慎行事。

因此，新文档现在显示为：

Git v2.13.0 和后来的默认情况下转移到强化的 SHA-1 实现，这不容易受到 SHAttered 攻击。

因此，Git 实际上已经迁移到一个不是 SHA-1 并且不共享其漏洞的新哈希，它的新哈希函数恰好为所有已知输入产生完全相同的输出，除了 SHAttered 发布的两个 PDF研究人员和新的实现（由这些研究人员编写）声称可以检测未来的密码分析碰撞攻击。

无论如何，将 SHA-1 的任何变体转移到新的哈希值都被认为是谨慎的。无法保证将来不会发布对 SHA-1 的攻击，并且这些攻击可能没有可行的缓解措施。

如果要真正破解 SHA-1 及其变体，Git 的哈希函数就不能再被认为是加密安全的了。这将影响散列值的通信，因为我们不能相信给定的散列值代表说话者想要的已知良好版本的内容。

注意：同一份文档现在（2018 年第三季度，Git 2.19）明确将“新哈希”引用为 SHA-256：请参阅“为什么 Git 不使用更现代的 SHA？ ”。

于 2017-04-11T20:46:38.617 回答
9

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

任何散列算法都可能发生冲突，因此更改散列函数并不能排除问题，它只会降低发生的可能性。所以你应该选择一个非常好的哈希函数（SHA-1 已经是，但你要求不要被告知:)

于 2012-05-03T15:26:45.637 回答
7

Google 现在声称在某些先决条件下可能发生 SHA-1 冲突： https ://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

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

IMO，git 绝对应该使用更好的散列算法，因为现在可以进行故意碰撞。

于 2017-02-24T03:22:58.773 回答
2

我最近在 BSD 讨论组中发现了 2013-04-29 的帖子

http://openbsd-archive.7691.n7.nabble.com/Why-does-OpenBSD-use-CVS-td226952.html

海报声称：

我曾经遇到过一次哈希冲突，使用 git rebase。

不幸的是，他没有为他的主张提供任何证据。但也许您想尝试联系他并询问他有关此假定事件的情况。

但在更一般的层面上，由于生日攻击，SHA-1 哈希冲突的机会是 1 in pow(2, 80)。

这听起来很多，而且肯定比世界上所有 Git 存储库中存在的单个文件版本的总数加起来还要多。

但是，这仅适用于实际保留在版本历史记录中的版本。

如果开发人员非常依赖 rebase，则每次为分支运行 rebase 时，该分支的所有版本（或分支的 rebase 部分）中的所有提交都会获得新的哈希值。每个使用“git filter-branch”修改的文件也是如此。因此，“rebase”和“filter-branch”可能是随时间生成的散列数量的大乘数，即使它们实际上并非全部保留：经常，在变基之后（特别是为了“清理”一个分支)，原来的分支被扔掉了。

但是如果在 rebase 或 filter-branch 期间发生冲突，它仍然会产生不利影响。

另一件事是估计 git 存储库中散列实体的总数，并查看它们与 pow(2, 80) 的距离。

假设我们有大约 80 亿人，他们所有人都将运行 git，并将他们的东西保存在每人 100 个 git 存储库中。让我们进一步假设平均存储库有 100 个提交和 10 个文件，每次提交只有一个文件更改。

对于每个修订，我们至少有一个树对象和提交对象本身的哈希。连同更改的文件，我们每个修订版有 3 个哈希值，因此每个存储库有 300 个哈希值。

对于 80 亿人的 100 个存储库，这给出的 pow(2, 47) 距离 pow(2, 80) 还很远。

但是，这不包括上面提到的假设乘法效应，因为我不确定如何将它包括在这个估计中。也许它可以大大增加发生碰撞的机会。特别是如果许多人对具有很长提交历史的非常大的存储库（如 Linux 内核）进行了微小的更改，从而为所有受影响的提交创建了不同的哈希值。

于 2018-01-26T07:34:37.003 回答
1

哈希冲突的可能性极小，简直令人震惊！全世界的科学家都在努力实现这一目标，但还没有成功。不过，对于某些算法，例如 MD5，它们是成功的。

几率是多少？

SHA-256有 2^256 个可能的哈希值。那是大约10^78。或者更形象地说，碰撞的可能性大约是

1 : 100 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000

中彩票的几率约为1：14 Mio。与 SHA-256 发生碰撞的几率就像连续 11 天中了彩票一样！

数学解释：14 000 000 ^ 11 ~ 2^256

此外，宇宙有大约 10^80 个原子。这只是 SHA-256 组合的 100 倍。

MD5碰撞成功

即使对于MD5，机会也很小。不过，数学家设法创造了一个碰撞：

d131dd02c5e6eec4 693d9a0698aff95c 2fcab5 8 712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325 7 1415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2 b 487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080 a 80d1e c69821bcb6a88393 96f965 2 b6ff72a70

具有相同的 MD5

d131dd02c5e6eec4 693d9a0698aff95c 2fcab5 0 712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325 f 1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2 3 487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080 2 80d1e c69821bcb6a88393 96f965 a b6ff72a70

这并不意味着 MD5 的算法被破解后安全性降低。可以故意创建MD5碰撞，但是意外MD5碰撞的几率还是2^128，还是很多的。

结论

您不必担心碰撞。散列算法是检查文件相同性的第二种最安全的方法。唯一更安全的方法是二进制比较。

于 2015-03-19T13:50:20.620 回答
0

好吧，我想我们现在知道会发生什么——您应该期望您的存储库会损坏（源）。

于 2017-02-25T10:38:27.287 回答