Git中的哈希碰撞问题

Question

Git中的哈希碰撞问题

githashsha1hash-collision

233

如果我在使用Git时发生哈希碰撞会发生什么？

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

Git能否改进以处理这种情况，还是我必须更换新的哈希算法？

（请不要通过讨论这种情况有多么不可能来回避这个问题-谢谢）

- Sec

34

我收到了Git之神的通知，说SHA1冲突的概率就像地球被CERN加速器制造的黑洞吸进去一样小。如果这是真的，那么就没有必要再进行额外的memcmp操作了。 - KurzedMetal

20

绝对不是这样。引用丹·伯恩斯坦（Dan Bernstein）的话：“学者们尚未进行SHA-1碰撞攻击的事实是一个小小的历史意外” - 现在，SHA-3竞赛已经结束，相关人员很有可能会将注意力转向使用已知的攻击来生产碰撞。马克·史蒂文斯（Marc Stevens）估计难度仅为2^61次操作。很可能很快就会展示出SHA-1碰撞；奇怪的是它还没有发生过。 - Paul Crowley

34

@KurzedMetal说：在CERN有可能会创造黑洞（两个质子会精准地碰撞（10^-15米）），但这个黑洞不会将地球吸进去，它会因为霍金辐射而迅速蒸发...所以SHA1碰撞的概率比被吸进黑洞的概率要大得多...只是说一下... - Jaa-c

11

可能是How would git handle a SHA-1 collision on a blob?的重复问题。 - user229044

36

令人惊讶的是，你明确要求人们不要讨论git碰撞的不可行性，几乎每个人都谈论了git碰撞的不可行性。这些人应该被终身禁止在stackoverflow上发言！ - Max

显示剩余10条评论

9个回答

71

如果在 Git 中两个文件具有相同的哈希值，它会将这些文件视为相同。如果出现这种几乎不可能的情况，您可以回到上一个提交，更改文件中的某些内容，以便它们不再发生冲突。

请参见 Git 邮件列表中 Linus Torvalds 在“开始考虑 sha-256？”主题中发布的帖子：http://web.archive.org/web/20120701221418/http://kerneltrap.org/mailarchive/git/2006/8/28/211065。

- klaustopher

4

如果在git中两个文件具有相同的哈希值，则将这些文件视为相同。这实际上是一个正确的答案。但是，klaustopher，你有关于这个语句的来源吗？你的链接对我来说无法使用。 - Bitcoin Cash - ADA enthusiast

5

但是，如果您在一个哈希碰撞样本集的项目上工作，这并不是完全不可能的。 - Doomjunky

7

@JBishop 没有发生哈希碰撞。如果你能证明哈希碰撞的存在，你将会一炮走红。别忘了发布它！如果你能在一周内向我展示一个在 Git 中生成的完整大小的 SHA-1 哈希碰撞，我会送一箱真正好喝的 Haarlem 啤酒给你。请注意，它必须是一个单独的哈希碰撞，而不是已经在其他地方引用过的（尽管到目前为止还没有人发布过）。 - Maarten Bodewes

10

到目前为止，唯一一个真正回答了这个问题。其它的只是在说可能会发生的“小几率”，而每个开发者都已经知道了。 - Max

2

非常小心Linus讨论IT安全 - 他以前就错过了，这次也错了。如果有人可以随意创建SHA-1碰撞，那么可以将其用于各种混乱，例如创建导致Git服务器和客户端崩溃的循环历史记录。 - DomQ

显示剩余4条评论

24

这个问题的答案不能仅简单地用"但是"回答，必须解释为何这不是问题。而这也需要对哈希的真实含义有很好的掌握，它比你在计算机科学课程中接触到的简单情况要复杂得多。

在这里存在一个基本的信息论误解。如果将大量信息缩小成较小的一部分（即哈希），那么可能发生碰撞的几率与数据长度直接相关。数据越短，出现碰撞的可能性就越小。现在，绝大多数冲突将是无意义的，这使它们更有可能真正发生（你永远不会检查无意义的东西......即使是二进制图像也有些结构）。最终，机会是渺茫的。回答您的问题，是的，Git将将它们视为相同的，更改哈希算法没有帮助，它将需要某种“第二次检查”，但最终，您需要与数据长度一样多的“附加检查”数据才能百分之百地确定......请记住，使用您描述的简单检查，您可以99.99999.. .等很多数字...确信。SHA-x是加密强度很强的哈希，这意味着通常很难故意创建两个非常相似的源数据集，并且具有相同的哈希。数据发生一位变化应该导致哈希输出发生多于一位（最好尽可能多）的更改，这也意味着很难（但不是完全不可能）从哈希中回溯出完整的碰撞集合，并从其中提取原始消息——除了少数几个以外，其余的都将是无意义的，而对于不是无意义的那些，则仍有大量数字需要筛选，如果消息长度任何显著长度，则会增加这一点。加密哈希的缺点是计算速度较慢。那么，这对Git来说意味着什么？其实并不重要。相对于其他操作，哈希计算的频率很低，它们的计算代价总体上很低。发生一对碰撞的概率非常之低，几乎不可能发生而不被立即检测到（例如，您的代码很可能突然停止构建），使用户可以修复问题（备份一个版本，再次进行更改，由于时间变化也会影响git中的哈希，因此您几乎肯定会获得不同的哈希）。但如果您在git中存储任意二进制文件，则更有可能出现实际问题，这并不是它的主要使用模型。如果您想这样做...您最好使用传统数据库。

考虑这个问题并没有错 - 很多人认为“这么不可能，根本不值得考虑” - 但实际上情况比较复杂。如果确实发生了碰撞，应该很容易检测到，而不会在正常工作流程中默默发生损坏。

- Steve

6

由于时间更改，Git中哈希值也会受到影响，因此您几乎肯定会得到不同的哈希值。哈希值仅基于文件内容吗？ - fredoverflow

5

一个数据块的哈希基于文件内容（包括一点元数据），而一个提交的哈希（理论上也可能冲突）则包括当前时间、树的哈希值、作者信息、父提交的哈希值等。但正如 @Steve 指出的那样，小的东西发生碰撞的可能性较小，而提交是一个小的东西。 - cdyson37

3

不认同“数据越短，碰撞发生的可能性就越小”这个观点。如果你是指缩短哈希长度，则会减少可能哈希值的数量，导致更多输入映射到每个哈希值上，从而增加了碰撞的概率。如果你是指缩短消息的长度，则只有在使用字符数限制可能输入的数量时才成立，这一点似乎非常明显，我感觉自己可能没有理解你的重点。 - Basic

我从未考虑过“非常相似”的点，这是一个非常好的点。它基本上意味着为了具有相同散列值的两个提交，您需要更改每个文件中大部分字符的数量（更不用说文件名、路径和文件数）。 - PieterNuyts

2

@PieterNuyts 不，为了从任意初始文件中获取特定的哈希值，您通常需要更改文件中的信息，使其与哈希值中的信息位数相似，即对于SHA-1约为160位。但是，在此处也计算哪些位要更改的信息，因此文件越长，如果选择正确的文件，则需要更改的位数就越少。假设给定一个长度远远超过2^160字节的文件，通过更改单个位可以获得几乎任何哈希值，因为该位的位置携带的信息超过160位！ - M Kloster

16

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

由于SHA1冲突现在已经成为可能（就像我在这个答案中引用的shattered.io一样），请知道Git 2.13（2017年第二季度）将通过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实现。
由于最近的“shattered”公告后，我们正在小心应对碰撞攻击，因此将默认选项更改为鼓励人们使用DC_SHA1实现。
那些想要使用OpenSSL实现的人可以在运行“make”时通过OPENSSL_SHA1=YesPlease明确请求。

我们实际上并没有Git对象碰撞，所以我们能做的最好的事情就是通过test-sha1运行shattered PDFs之一。这应该触发碰撞检查并导致程序崩溃。

Git能否改进以适应此情况，还是我必须更换新的哈希算法？

2017年12月更新：随着Git 2.16（2018年第一季度）的推出，支持使用另一种哈希算法的工作正在进行中：请参见“为什么Git不使用更现代的SHA算法？”。

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

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

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

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


尝试澄清SHAttered攻击在Git中的实际含义。

  之前的版本中完全没有提到Git已经针对这种特定攻击采取了缓解措施，而SHAttered研究人员声称，这种措施将检测到密码分析碰撞攻击。
我可能有些细微之处理解不正确，但据我所知，这个新文本准确地总结了SHA-1在Git中的当前情况。也就是说，git现在不再使用SHA-1，而是使用Hardened-SHA-1（它们恰好99.99999999999...%的时间产生相同的输出）。
因此，之前的文本在断言以下内容时是不正确的：

[...]结果[SHAttered]，SHA-1不能再被认为是具有密码学安全性的[...]

事实并非如此。我们已经针对SHAttered采取了缓解措施，但是如果未来SHA-1或Hardened-SHA-1出现漏洞，我们认为采取向NewHash迁移的工作是明智的。

因此，新文档 现在的内容如下：

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？”。

- VonC

4

这是这里唯一靠谱的回答或评论。总结一下就是——虽然可能性极小，但还是有可能发生。此外，它们也可以立即被修复并通过调整文件（附带评论）避免冲突，从而无法识别。故意的利用行为被认为不相关，因为有人可以轻易地提交“坏代码”，而且有签名和有意向的拉取请求等机制可以防止随机的人提交随机的东西。 - Brad

1

感谢您提供的精彩概述。 - Vankog

6

Git能否改进以解决这个问题，还是我需要更换一个新的哈希算法？

任何哈希算法都有可能发生冲突，因此更改哈希函数并不能完全避免问题，只能降低发生的概率。所以你应该选择一个真正优秀的哈希函数（SHA-1已经是一个好的选择了，但你不想听这个 :)）。

- Roberto Bonvallet

我想你的意思是“更不可能”或“更少可能”，对吗？当然，你可以改用一个输出字节数较少的哈希算法，但这不是你想要的，对吧？ :) - MichaelK

2

SHA-1已经被攻破，这意味着可以创建故意的哈希碰撞。我认为在2012年它已经被攻破了。因此，更换为另一种更安全、状态和输出更大的哈希肯定会有所不同。 - Maarten Bodewes

6

谷歌现在声称，在某些先决条件下，SHA-1碰撞是可能的: https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html 由于git使用SHA-1来检查文件完整性，这意味着git中的文件完整性已经受到损害。

在我看来，git应该一定要使用更好的哈希算法，因为现在可以故意制造碰撞。

- Petercommand Hsu

4

此外，不应轻信Linus在计算机安全方面的话。他以前就犯过错误，这次也错了。（例如，SHA-1碰撞预示着可以创建循环提交历史记录来崩溃服务器和客户端）。 - DomQ

1

最近我在一个BSD讨论组中发现了一篇2013-04-29的帖子，网址为

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

在这篇文章中，作者声称：

我曾经在使用git rebase时遇到了哈希碰撞。

不幸的是，他没有提供任何证明。但也许你想尝试联系他并询问他是否真的遇到了这个问题。

但更普遍地说，由于生日攻击，SHA-1哈希碰撞的机会是pow(2,80)中的1。

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

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

如果开发人员非常依赖于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内核）由许多人为小更改进行变基，尽管所有受影响的提交都会创建不同的哈希，但仍然会产生不同的哈希。

- Guenther Brunthaler

有趣。+1。正如我之前提到的，这个问题最终会消失：https://dev59.com/hF4c5IYBdhLWcg3wOoK6#47838703 - VonC

1

我想现在我们知道会发生什么了 - 你应该期望你的代码库会变得损坏 (source)。

- Conor Bradley

0

哈希碰撞是如此不太可能发生的事情，它令人难以置信！全世界的科学家都在努力实现它，但至今未能成功。然而对于某些算法，比如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

中奖的概率大约是1 : 14百万。SHA-256发生碰撞的概率就像连续11天中彩票一样难中！

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

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

MD5碰撞成功

即使对于MD5，机会也是微乎其微的。尽管如此，数学家们还是成功地创建了一次碰撞：

d131dd02c5e6eec4 693d9a0698aff95c 2fcab58712467eab 4004583eb8fb7f89
55ad340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2b487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080a80d1e c69821bcb6a88393 96f9652b6ff72a70

与以下文本具有相同的MD5：

d131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89 55ad340609f4b302 83e4888325f1415a085125e8f7cdc99f d91dbd7280373c5b d8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd02396306d248cda0 e99f33420f577ee8 ce54b67080280d1ec69821bcb6a88393 96f965ab6ff72a70

这并不意味着MD5现在的算法被破解后就不安全了。你可以故意创建MD5碰撞，但是意外发生MD5碰撞的几率仍然是2^128，这仍然是非常大的。

结论

你不必担心碰撞问题。哈希算法是检查文件相同性的第二安全的方法。唯一更安全的方法是进行二进制比较。

- bytecode77

5

这个答案主要讨论了SHA-256，这与问题有关的SHA-1无关。显示SHA-256碰撞不太可能发生的数学计算比SHA-1更乐观。尽管仍然很不可能，但关于SHA-1的回答将更为相关。 - Andrew Arnott

@AndrewArnott SHA-256和SHA-1之间没有实质性的区别。SHA-1弱2^128倍，但这也不重要。它仍然是无法破解的，所以我的答案并不是那么不合适。 - bytecode77

6

“SHA-1确实已经被破解了”，因此说“它仍然无法破解”也是不正确的。鉴于SHA-1实际上已经被破解，有人可能会故意攻击git的sha-1算法，以替换内容而不被检测到。SHA-256尚未被破解，因此更加安全。因此，回答关于潜在的git冲突问题最好使用SHA-1。请注意，这里只是翻译，没有任何解释或其他内容。 - Andrew Arnott

1

这并不意味着 MD5 现在算法被破解后就不再安全了。重申一遍，您需要我解释这句话的含义吗？ - Maarten Bodewes

答案原因：因为有很多不熟悉计算机的人从网络搜索中来到这里，他们之间存在很多混淆。在我看来，“加密与计算能力”方面的误解比你想象的要普遍得多，因此我提供了额外的信息来解决这个问题。 - bytecode77

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MichaelK · Accepted Answer

在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哈希碰撞。那么接下来会发生什么？

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

如果使用相同的哈希值已存在 blob，则您将不会收到任何警告。一切似乎都很正常，但是当您推送、克隆或还原时，您将丢失最新版本（与上面所述的相符）。

如果已经存在树对象并且您使用相同的哈希值创建 blob：一切都似乎正常，直到您尝试推送或有人克隆您的存储库。然后您将看到存储库已损坏。

如果已经存在提交对象并且您使用相同的哈希值创建 blob：与＃2相同-损坏

如果已经存在 blob 并且您使用相同的哈希值创建提交对象，则在更新“ref”时将失败。

如果已经存在 blob 并且您使用相同的哈希值创建树对象，则在创建提交时将失败。

如果已经存在树对象并且您使用相同的哈希值创建提交对象，则在更新“ref”时将失败。

如果已经存在树对象并且您使用相同的哈希值创建树对象，则一切似乎都很正常。但是，当您提交时，整个存储库将引用错误的树。

如果已经存在提交对象并且您使用相同的哈希值创建提交对象，则一切似乎都很正常。但是，当您提交时，提交将永远不会被创建，并且 HEAD 指针将移动到旧提交。

如果已经存在提交对象并且您使用相同的哈希值创建树对象，则在创建提交时将失败。

正如你所看到的，有些情况并不好。特别是#2和#3这两种情况会破坏你的代码库。然而，似乎问题仅限于该代码库内部，攻击或奇怪的不可能性并不会传播到其他代码库。

此外，人为碰撞的问题被认为是一个真正的威胁，因此例如GitHub正在采取措施防止这种情况发生。

Git中的哈希碰撞问题

在10个卫星上选择原子

“但是，当发生碰撞时，会发生什么？”

Makefile：使DC_SHA1成为默认选项

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

几率是多少？

MD5碰撞成功

`Makefile`：使`DC_SHA1`成为默认选项

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