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 000 个不同的 SHA-1 哈希...10⁴⁸.

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

在此基础上，我们可以提出这个问题...

在

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

这与所谓的"生日攻击">

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

维基百科有一个关于生日悖论碰撞概率的表格。没有 40 个字符哈希的条目。但是，对 32 和 48 个字符的条目进行插值，我们进入 5*10²² git 提交的范围内，发生冲突的概率为 0.1%。这是五千万亿次不同的提交，或者五十次Zettacommits，在你发生碰撞的几率达到0.1%之前。

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

这样做的要点是，除非有人故意造成碰撞，否则随机发生碰撞的可能性非常小，你可以忽略这个问题。

"但是当碰撞确实发生时，那么实际会发生什么？">

好吧，假设

不可能的事情确实发生了，或者假设有人设法定制了一个故意的 SHA-1 哈希碰撞。那怎么办呢？

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

考虑这一点并没有错——这是一个很好的问题，很多人

只是冒充"不太可能，不值得考虑"——但它真的比这复杂一些。 如果它确实发生了，它应该很容易检测到，它不会是正常工作流程中的无声损坏。

Answer 4

你可以在

"Git 如何处理 blob 上的 SHA-1 冲突？"中看到一个很好的研究。

由于 SHA1 碰撞现在是可能的(正如我在本回答中引用的 shattered.io(，请知道 Git 2.13(2017 年第 2 季度(将通过 Marc Stevens (CWI( 和 Dan Shumow (Microsoft( 的 SHA-1 实现的"检测尝试创建冲突"变体来改善/缓解当前情况。

请参阅提交 f5f5e7f、提交 8325e43、提交 c0c2006、提交 45a574e、提交 28dc98e (2017 年 3 月 16 日(，作者：Jeff King ( peff (。
^{(由Junio C Hamano -- gitster -- 在提交 48b3693 中合并，2017 年 3 月 24 日(}

Makefile：将DC_SHA1设为默认值

我们曾经使用 OpenSSL 库中的 SHA1 实现 违约。
由于我们试图在最近的"破碎"公告之后小心冲突攻击，因此请切换默认值以鼓励人们使用DC_SHA1实现。
那些想要使用OpenSSL实现的人可以明确要求 它通过OPENSSL_SHA1=YesPlease运行时运行" make "。

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

---

Git 可以改进以接受它，还是我必须更改为新的哈希算法？

2017 年 12 月使用 Git 2.16 更新(2018 年第 1 季度(：支持替代 SHA 的工作正在进行中：请参阅"为什么 Git 不使用更现代的 SHA？

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

---

Git 2.18(2018 年第 2 季度(记录了该过程。

参见 提交 5988eb6， 提交 45fa195 (26 Mar 2018( 由 Ævar Arnfjörð Bjarmason ( avar (。
^{(由Junio C Hamano -- gitster -- 合并于 提交 d877975,2018 年 4 月 11 日(}

文档hash-function-transition：澄清SHAttered的含义

尝试澄清 SHAttered 攻击在实践中意味着什么 吉特。
该文本的先前版本没有提到Git已经对这种特定攻击进行了缓解，SHAttered研究人员声称这将检测密码分析冲突攻击。

我

可能弄错了一些细微差别，但据我所知 新文本准确地总结了 SHA-1 的现状 吉特。即 git 不再真正使用 SHA-1，它使用 硬化-SHA-1(它们恰好产生相同的输出

99.99999999999...%的时间(。

因此，先前的案文断言

：

[...]由于[SHAttered]，不能考虑SHA-1 加密安全再[...]

事实并非如此。但是，我们有针对SHAttered的缓解措施 我们认为，谨慎的做法是努力实现NewHash未来 SHA-1 或强化 SHA-1 中的漏洞都出现了。

因此，新文档现在为：

Git v2.13.0 及更高版本随后移至强化的 SHA-1 默认情况下实现，它不容易受到 SHAttered 攻击。

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

无论如何，超越SHA-1的任何变体被认为是谨慎的。 到新的哈希。不能保证未来对SHA-1的攻击不会 将来发布，这些攻击可能不可行 缓解措施。

如果要真正破坏 SHA-1 及其变体，Git 的哈希函数 不能再被视为加密安全。这将 影响哈希值的通信，因为我们不能信任 给定的哈希值表示已知良好的内容版本 演讲者的意图。

注意：现在同一文档(2018 年第 3 季度，Git 2.19(明确引用">新哈希"为 SHA-256：请参阅"为什么 Git 不使用更现代的 SHA？"。

Answer 5

git 可以改进以接受它，还是我必须更改为新的哈希算法？

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

Answer 6

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

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

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

Answer 7

好吧，

我想我们现在知道会发生什么 - 您应该期望您的存储库会损坏(来源(。

Answer 8

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

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

海报声称：

我遇到过一次哈希冲突，使用 git 变基。

不幸的是，他没有为他的说法提供任何证据。但也许你想尝试联系他并询问他这个所谓的事件。

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

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

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

如果开发人员非常依赖变基，则每次为分支运行变基时，该分支的所有版本(或分支的变基部分(中的所有提交都会获得新的哈希。对于使用"git 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 内核(被许多人重新定位以进行小更改，但这仍然为所有受影响的提交创建不同的哈希。

Answer 9

哈希

碰撞的可能性很小，这简直令人震惊！全世界的科学家都在努力实现一个目标，但还没有做到。不过，对于某些算法，如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 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 2fcab58712467eab 4004583eb8fb7f8955AD340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5bD8823E3156348F5B AE6DACD436C919C6 DD53E2B487DA03FD 02396306D248CDA0e99f33420f577ee8 ce54b67080a80d1e c69821bcb6a88393 96f9652b6ff72a70

具有相同的 MD5

d131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab 4004583eb8fb7f8955AD340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5bD8823E3156348F5B AE6DACD436C919C6 DD53E23487DA03FD 02396306D248CDA0e99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965ab6ff72a70

这并不意味着MD5现在其算法被破解后安全性降低。你可以故意制造 MD5 碰撞，但意外发生 MD5 碰撞的几率仍然是 2^128，这仍然很多。

结论

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