git中的哈希冲突

Question

如果我在使用git时遇到哈希冲突会发生什么？

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

可以改进git以适应它,或者我是否必须更改为新的哈希算法？

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

Answer 1

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

这相当于什么？月球由大约10 ^47个原子组成.所以,如果我们有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中具有相同的哈希值,则会将这些文件视为相同.在极不可能发生这种情况的情况下,您可以随时返回一个提交,并更改文件中的某些内容,以便它们不会再发生冲突......

请参阅git邮件列表中的线索"开始思考sha-256？"中的Linus Torvalds的帖子.

Answer 3

用正确的"但是"回答这个问题是不可能的,但也没有解释为什么它不是问题.如果没有真正掌握哈希的真正含义,就不可能做到这一点.它比你在CS程序中可能遇到的简单案例更复杂.

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

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

考虑这个问题并没有错 - 这是一个很好的问题,很多人只是因为"不太可能不值得思考"而被忽略了 - 但它确实比那复杂得多.如果它发生了,它应该是非常容易检测的,它不会是正常工作流程中的沉默腐败.

Answer 4

可以改进git以适应它,或者我是否必须更改为新的哈希算法？

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

Answer 5

您可以在“ Git如何处理Blob上的SHA-1碰撞？ ”中看到很好的研究。

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

请参阅Jeff King（）提交的commit f5f5e7f，commit 8325e43，commit c0c2006，commit 45a574e和commit 28dc98e（2017年3月16日）。^{（通过合并JUNIOÇ滨野- -在提交48b3693 3月24日2017）}peff
gitster

Makefile：设为DC_SHA1默认

我们以前默认使用OpenSSL库中的SHA1实现。
由于我们在最近的“崩溃”声明后要努力防止碰撞攻击，因此请切换默认值以鼓励人们使用DC_SHA1实现。
那些希望使用OpenSSL实施的人可以OPENSSL_SHA1=YesPlease在运行“ make” 时明确要求它。

我们实际上没有发生Git对象碰撞，因此，我们能做的最好的事情就是通过test-sha1运行破碎的PDF之一。这将触发碰撞检查并死亡。

可以改进Git来使其兼容吗，还是我必须更改为新的哈希算法？

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

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

Git 2.18（Q2 2018）记录了该过程。

见提交5988eb6，提交45fa195通过（2018年3月26日）ÆvarArnfjörðBjarmason（ ）avar。
^{（通过合并JUNIOÇ滨野- gitster-在提交d877975 4月11日2018）}

doc hash-function-transition：阐明“破碎”的含义

尝试弄清楚“破碎”攻击在实践中对Git意味着什么。
文本的先前版本没有提及Git已经对此特定攻击有所缓解的任何方法，粉碎的研究人员声称，它将检测到密码分析冲突攻击。

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

因此，先前的文本在断言以下方面是错误的：

[...]由于[不正确]的结果，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的哈希函数视为加密安全了。这将影响散列值的通信，因为我们无法相信给定的散列值代表说话者想要的内容的已知良好版本。

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

Answer 6

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

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

IMO，git绝对应该使用更好的哈希算法，因为现在有可能发生故意冲突。