在git的哈希冲突在git的哈希冲突(Hash collision in git)

如果我不得不同时使用Git哈希碰撞居然会发生什么？

例如，我设法犯了同样的SHA1校验两个文件，将发现的git它或将文件的腐败吗？

难道混帐提高到住在一起，否则我将不得不改变到一个新的哈希算法？

（请不要讨论如何不太可能是偏离了这个问题 - 谢谢）

Answer 1:

10个月亮采摘原子

的SHA-1散列是一个40进制字符串...这是每个字符40倍... 160个比特4个比特。 现在我们知道10位的大约1000（1024是精确的）这意味着有1 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000不同的SHA-1散列... 10 ^48。

这是什么等同呢？ 那么月球是由约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已经存在，你犯了一个commit对象相同的哈希，它会在更新“裁判”时失败。
5. 如果一个blob已存在，则使具有相同散列树形对象。 创建提交时，会失败。
6. 如果树对象已存在，则做出承诺的对象相同的哈希，它会在更新“裁判”时失败。
7. 如果树对象已存在，则使用相同的哈希树对象，一切看上去都那么好。 但是，当你提交，所有的仓库都将引用错误的树。
8. 如果提交对象已存在，则使用相同的哈希提交对象，一切看上去都那么好。 但是，当你提交，提交将永远不能被创造，和头指针将被移动到老犯。
9. 如果提交对象已存在，则使用相同的哈希树对象，它会创建提交时失败。

正如你似乎有些情况并不好。 尤其是案例＃2，＃3弄乱了你的资料库。 但是，它似乎是故障停留在该仓库内，并攻击/离奇的不可能性不会传播到其他reposistories。

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

Answer 2:

如果两个文件在混帐相同的散列总和，那就把这些文件作为相同。 在这种情况绝对不可能的情况下，你总是可以回去一次提交，并改变一些文件中，这样他们就不会再发生冲突......

见Linus Torvalds的线程后在git的邮件列表‘开始考虑SHA-256？’ 。

Answer 3:

这是不是真的有可能来回答与正确的“但”这个问题也没有解释为什么它不是一个问题。 这是不可能做到这一点，而不真的有什么哈希确实是一个良好的抓地力。 这比你可能已经在CS程序被暴露在简单的情况更加复杂。

有信息理论的一个基本的误解在这里。 如果您减少了大量的信息到一个较小的量通过丢弃一些量（即哈希）会有碰撞的机会，直接关系到数据的长度。 该数据越短，就越有可能会。 现在，绝大多数的碰撞将是乱码，使他们更可能实际发生（你永远不会在胡言乱语检查......即使二进制图像有些结构化）。 最后，机会是远程的。 要回答你的问题，是的，git会对待他们一样，改变了哈希算法不会帮助，它会采取某种形式的“第二支票”，但最终，你需要尽可能多的“额外检查”数据作为数据的长度为100％肯定...记住你会99.99999 ....到一个很长的位数....肯定有一个简单的检查像你描述。 SHA-x分别强加密散列，这意味着通常岂不等于难以有意创建都非常相似，彼此，并且具有相同的哈希两个源的数据集。 在数据变化应该创建一个以上（最好是尽可能多的）中的散列输出，这也意味着它是非常困难的（但不是完全不可能）从哈希工作回到了一整套的变化位的一个位碰撞，从而从该组碰撞拉出原始消息 - 除了少数会胡言乱语，那是那些不是仍然有数量庞大的筛选，如果消息长度为任何显著的长度。 一个加密散列的缺点是，它们是缓慢的计算...一般。

那么，什么是所有这一切意味着然后Git的？ 不多。 哈希得到所以很少（相对于其他一切），他们的计算代价是低的整体运营来完成。 打一对碰撞的几率是如此之低，它不会发生，而不是一个现实的机会可以立即检测（即你的代码很可能会突然停止建设），允许用户解决问题（备份版本，并再次做出改变，你几乎肯定会得到，因为时间的变化，这也混帐饲料哈希不同的哈希）。 还有更容易为它，如果你存储任意的二进制文件在Git中，这是不是真的就是它的主要用途模型是对你的一个现实问题。 如果你想这样做......你可能最好使用传统的数据库。

这不是错误地认为这一点 - 这是一个很好的问题，很多人只是冒充“所以不太可能是不值得考虑” - 但它确实比这更复杂一点。 如果它确实发生，这应该是很容易检测的，也不会是在一个正常的工作流程无声的腐败。

Answer 4:

难道混帐提高到住在一起，否则我将不得不改变到一个新的哈希算法？

碰撞是可能的任何哈希算法，所以改变了哈希函数并不排除这个问题，它只是使得它不太可能发生。 所以，你应该选择再一个很好的散列函数（SHA-1已经是的，但你不愿告诉:)

Answer 5:

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

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

IMO，因为故意冲撞现在是可能的混帐绝对应该使用更好的散列算法。

Answer 6:

你可以看到在“好好学习的Git将如何处理在一个blob一个SHA-1碰撞？ ”。

由于SHA1碰撞现在可以（我在引用这个答案与shattered.io ），知道了Git 2.13（Q2 2017）将提高/使用的“检测企图制造冲突”变种缓解目前的状况SHA1实现由马克·史蒂文斯（CWI）和达恩·舒莫（微软） 。

见提交f5f5e7f ， 提交8325e43 ， 提交c0c2006 ， 提交45a574e ， 提交28dc98e通过（2017年3月16日）， 杰夫·金（ peff ） 。
^{（通过合并JUNIOÇ滨野- gitster -在提交48b3693 3月24日2017）}

Makefile ：让DC_SHA1默认

我们使用默认使用SHA1实现从OpenSSL库。
当我们正努力成为对近期的“粉碎”公布后碰撞攻击小心，切换默认为鼓励人们使用DC_SHA1实现代替。
谁想要使用来自OpenSSL的实现可以明确要求它OPENSSL_SHA1=YesPlease运行“时make ”。

我们实际上并没有一个Git对象碰撞，所以我们能做的最好的就是通过测试-SHA1运行破碎的PDF文件之一。 这应该引起碰撞检查和死亡。

---

Git的能改善生活就这样，否则我将不得不改变到一个新的哈希算法？

更新2017年12月使用Git 2.16（Q1 2018）：这方面的努力，以支持替代SHA正在进行：详见“ 为什么不混帐使用更现代化的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的手段。
文本的以前版本中没有提到任何的混帐已经给这个特定的攻击缓解，这破碎的研究人员声称将检测密码破译冲突攻击。

我可能已经找到了一些细微差别错的，但据我所知，这个新的文本准确地总结了SHA-1目前的局势饭桶。 即Git并不真正使用SHA-1了，它采用硬齿面-SHA-1（他们只是这么碰巧产生相同的输出99.99999999999 ...％的时间）。

因此，在前文中断言是不正确的：

[...]结果[压碎了]，SHA-1不能被加密认为是安全的任何更多的[...]

这是不是这样的。 我们有对破碎的缓解， 但是我们认为稳健的移动迈向工作NewHash应该在任何SHA-1未来的脆弱或硬化-SHA-1出现。

因此， 新的文件 ，原先为：

Git的v2.13.0后来随后移动到默认硬化SHA-1的情况，这是不容易破碎的攻击。

这样的Git实际上已经已经迁移到一个新的哈希不是SHA-1，并没有分享它的弱点，它的新散列函数正好产生相同的输出所有已知的投入，除了被震碎出版了两个PDF文件研究人员和新的实现（这些研究人员写的）声称发现未来的密码破译冲突攻击。

无论如何，它被认为是审慎的做法是过去的SHA-1的任何变体移动到一个新的哈希值。 有没有保证，今后关于SHA-1的攻击将不会在未来的出版，这些攻击可能没有可行的缓解。

如果SHA-1及其变种将被打破真正的，Git的散列函数不能被视为加密安全了。 这将影响到哈希值的通信，因为我们无法相信，一个给定的哈希值表示的内容已知好版本，扬声器之意。

注意：现在同一文档（Q3 2018年，混帐2.19）显式地引用了“新的哈希”作为SHA-256：详见“ 为什么不混帐使用更现代化的SHA？ ”。

Answer 7:

散列碰撞是如此的可能性很小，这是纯粹的令人兴奋的！ 科学家们在世界各地都在努力实现一个，但还没有对其进行管理。 对于某些算法，如MD5他们successed，虽然。

有多大？

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神达 。 与SHA-256发生碰撞的几率就像赢得连续11天的彩票！

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

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

成功的MD5碰撞

即使是MD5的机会是很小的。 虽然，数学家成功地创建一个冲突：

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

有MD5为相同

d131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965ab6ff72a70

这并不意味着MD5现在，它的算法被破解是不太安全。 您可以在目的创建的MD5碰撞，但一个偶然的MD5碰撞的机会仍然是2 ^ 128，这仍然是一个很大。

结论

你不必有关于碰撞一丝烦恼。 散列算法是第二个最安全的方式来检查文件的同一性。 唯一安全的方法是二进制比较。

Answer 8:

嗯，我想我们现在知道会发生什么-你应该预料到你的仓库将成为损坏（ 源 ）。

Answer 9:

我最近在一个BSD讨论小组发现了一个帖子，从2013年4月29日在

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

在海报称：

我遇到了一个哈希冲突一次，使用Git变基。

不幸的是，他没有提供任何证据为他的要求。 但是，也许你想尝试与他联系，问他关于这个所谓的事件。

但在更广泛的层面，由于生日攻击对于SHA-1散列冲突的机会是1 POW（2，80）。

这听起来很多，肯定比目前世界上合并的所有Git仓库单个文件的版本总数方式更多。

然而，这仅适用于这实际上保留在版本历史版本。

如果开发人员依靠非常多的基础重建，每一次重订运行的一个分支，在该分支（或分支的衍合部分）的所有版本的所有提交获得新的哈希值。 每个文件与“混帐过滤分支”修改也是如此。 因此，“重订”和“过滤器分支”可能是随着时间的推移产生的散列的数量大乘数，即使不是所有的人实际上保存：通常情况下，重订（尤其是“清理”的一个分支目的后），原来的分支扔掉。

但是，如果底垫或过滤器分支过程中发生碰撞，它仍然可以产生不利影响。

另一件事是估算的git仓库散列实体的总数，看看他们是从POW（2 80）有多远。

比方说，我们有大约8十亿人，他们都将是运行git，并保持自己的东西，在每人100个git仓库版本。 让我们进一步假设平均仓库有100次的提交和10个文件，其中只有每提交这些文件的变化之一。

对于每一个版本，我们至少有一个哈希树对象，然后提交对象本身。 连同已更改的文件，我们必须每3个修改散列，因此300元库哈希值。

对于100个库8十亿人这给POW（2，47），这是由POW（2 80）仍远。

然而，这并不包括上面提到的所谓倍增效应，因为我不确定如何将其纳入这个估计。 也许这可能增加显着碰撞的机会。 特别是，如果将长提交历史（如Linux内核）非常大的仓库被不少人对于小的变化，但它为所有受影响的提交创建不同的散列重建基础。

文章来源: Hash collision in git