Git 将如何处理 blob 上的 SHA-1 冲突？

StackOverflow https://stackoverflow.com/questions/9392365

  •  29-10-2019
  •  | 
  •  

题

这在现实世界中可能从未发生过，也可能永远不会发生，但让我们考虑一下：假设你有一个 git 存储库，进行提交，然后变得非常非常不幸：其中一个 Blob 最终具有与存储库中已有的另一个 Blob 相同的 SHA-1。问题是，Git 将如何处理这个问题？简单地失败？找到一种方法来链接两个 blob 并根据上下文检查需要哪一个？

与其说是一个实际问题，不如说是一个脑筋急转弯，但我发现这个问题很有趣。

有帮助吗？

解决方案

我做了一个实验，以找出Git在这种情况下的确切表现。这是版本2.7.9〜rc0 + next.20151210（Debian版本）。我基本上只是通过应用以下diff并重建git来将哈希大小从160位减小为4位： 通用标签

然后我做了一些提交，并注意到了以下内容。

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

    对于＃2，当您运行“ git push”时，通常会收到如下错误： 通用标签

    或： 通用标签

    如果删除文件，然后运行“ git checkout file.txt”。

    对于＃4和＃6，通常会出现如下错误： 通用标签

    运行“ git commit”时。在这种情况下，您通常可以再次键入“ git commit”，因为这将创建一个新的哈希（由于更改的时间戳）

    对于＃5和＃9，通常会出现如下错误： 通用标签

    运行“ git commit”时

    如果有人尝试克隆您损坏的存储库，通常会看到类似以下内容的： 通用标签

    让我“担心”的是，在两种情况下（2,3），该存储库在没有任何警告的情况下已损坏，而在3种情况下（1,7,8），一切似乎都正常，但是该存储库的内容不同于您希望是这样。克隆或拉人的内容将与您拥有的内容不同。情况4,5,6和9可以，因为它会因错误而停止。我想如果至少在所有情况下都因错误而失败，那就更好了。

其他提示

原始答案（2012）（参见 shattered.io 2017 SHA1 碰撞如下）

那 Linus 的旧（2006）答案 可能仍然相关：

没有。如果它具有相同的 SHA1，则意味着当我们从另一端接收到该对象时，我们将 不是 覆盖我们已有的对象。

因此，如果我们看到冲突，任何特定存储库中的“较早”对象总是会被覆盖。但请注意，“较早”显然是针对每个存储库的，从某种意义上说，git 对象网络生成一个未完全排序的 DAG，因此，虽然不同的存储库在直接祖先的情况下会就什么是“较早”达成一致，但如果对象来自单独且不直接相关的分支，两个不同的存储库显然可能以不同的顺序获取两个对象。

然而，从安全角度来看，“较早的将覆盖”正是您想要的：请记住，git 模型是您应该主要只信任您的 自己的 存储库。
所以如果你做一个“git pull“从定义上讲，新传入的对象比您已经拥有的对象不值得信任，因此允许新对象替换旧对象是错误的。

所以你有两种碰撞情况：

  • 这 不经意的那种, ，不知何故，你非常非常不幸，两个文件最终具有相同的 SHA1。
    那时，发生的情况是，当您提交该文件（或执行“git-update-index" 将其移动到索引中，但尚未提交），将计算新内容的 SHA1，但是 因为它与旧对象匹配，所以不会创建新对象，并且提交或索引最终指向 老的 目的.
    您不会立即注意到（因为索引将与旧对象 SHA1 匹配，这意味着类似“git diff”将使用签出的副本），但是如果您曾经进行过树级比较（或者您进行克隆或拉取，或强制签出），您会突然注意到该文件已更改为某些内容 完全地 与你的预期不同。
    所以你通常会很快注意到这种碰撞。
    相关新闻中，问题是如何处理不经意的碰撞。
    首先，我要提醒大家，这种不经意的碰撞确实是非常严重的。 真的 太不可能了，所以我们很可能在宇宙的整个历史中永远不会看到它。
    但 如果 它发生了，这不是世界末日： 您最有可能要做的就是更改稍微冲突的文件，然后强制使用更改的内容进行新的提交 （添加评论说“/* This line added to avoid collision */") 然后教 git 有关已被证明是危险的神奇 SHA1 的知识。
    因此，在几百万年的时间里，也许我们将不得不向 git 添加一两个“中毒”的 SHA1 值。这不太可能是维护问题；）

  • 这 攻击者类型的碰撞 因为有人破坏了（或暴力破解）SHA1。
    这显然是一个 很多 比无意的类型更有可能，但根据定义，它始终是一个“远程”存储库。如果攻击者能够访问本地存储库，他就会有更简单的方法来搞砸你。
    所以在这种情况下， 碰撞完全不是问题: ：你会得到一个与攻击者想要的不同的“坏”存储库，但是 因为你永远不会真正使用他的碰撞对象，所以它是 字面上地 与攻击者没有什么不同，只是根本没有发现碰撞, ，但只是使用您已经拥有的对象（即，它 100% 相当于生成相同 SHA1 的相同文件的“微不足道”碰撞）。

这 使用 SHA-256 的问题 经常被提及，但目前尚未采取行动（2012 年）。
笔记： 从 2018 年开始和 Git 2.19, ，代码正在重构以使用 SHA-256。

注意（幽默）：您可以强制提交特定的 SHA1 字首, ，与项目 吉特布鲁特 从 布拉德·菲茨帕特里克（bradfitz).

gitbrute 强制使用一对作者+提交者时间戳，以便生成的 git 提交具有您想要的前缀。

例子： https://github.com/bradfitz/deadbeef

丹尼尔·丁尼斯 指出 在评论中 到 7.1 Git 工具 - 修订版本选择, ， 包括：

更有可能的是，你的编程团队的每个成员都会在同一个晚上在不相关的事件中被狼袭击并杀死。

甚至最近（2017 年 2 月） shattered.io 证明了伪造 SHA1 冲突的可能性：
（更多内容请参见我的 单独回答, ，包括 Linus Torvalds 的 Google+ 帖子）

  • a/ 仍需要超过 9,223,372,036,854,775,808 次 SHA1 计算。这相当于单 CPU 计算 6,500 年和单 GPU 计算 110 年的处理能力。
  • b/ 会锻造 一 文件（具有相同的 SHA1），但具有附加约束其内容 和 size 将产生相同的 SHA1（仅内容上的冲突是不够的）：看 ”git 哈希值是如何计算的？”）：A blob SHA1 是根据内容计算的 和 尺寸.

看 ”加密哈希函数的生命周期“ 从 瓦莱丽·安妮塔·奥罗拉 了解更多。
在那一页中，她指出：

Google 花了 6500 个 CPU 年和 110 个 GPU 年来说服所有人，我们需要停止在安全关键应用程序中使用 SHA-1。
也因为很酷

更多内容请见我的 下面单独回答.

根据 Pro Git ：

如果您确实提交了一个哈希值与存储库中先前对象相同的SHA-1值的对象，则Git将在您的Git数据库中看到该先前对象，并假定该对象已被写入。如果您尝试在某个时候再次检出该对象，则将始终获得第一个对象的数据。

因此它不会失败，但也不会保存新对象。
我不知道在命令行上会怎样，但这肯定会造成混淆。

再往下一点，相同的参考文献试图说明这种碰撞的可能性：

以下是一个示例，可让您大致了解发生SHA-1碰撞的过程。如果地球上所有的65亿人都在编程，并且每一秒钟产生的代码都相当于整个Linux内核历史记录（100万个Git对象）并将其推入一个巨大的Git存储库，则需要5年的时间该存储库包含足够多的对象，因此一次SHA-1对象冲突的可能性为50％。在同一晚发生不相关事件时，您的编程团队中的每个成员都有被狼袭击并杀死的可能性更高。

增加来 我以前的答案来自2012年, 有现在(Feb.2017年，五年之后)，一个实例的实际SHA-1碰撞 打碎了。io, ，你可以手工艺两个碰撞的PDF文件：这是获得SHA-1上的数字签名的第一PDF文件，也可以被滥用作为有效签名第二的PDF文件。
也见"在死亡的大门多年来，广泛使用的SHA1功能是现在死"，并且 这个插图.

更新26日:莱纳斯确认以下几点 在一个谷歌后:

(1)第一个关闭的，天空是不是下降。有一个很大的区别之间的使用加密散列对安全的签名，并使用一个用于产生一个"内容标识"的内容寻址系统中喜欢的饭桶。

(2)其次，这个特别的SHA1攻击的装置，它实际上是很容易减少，并且有的已经两套补贴，减轻。

(3)最后，有实际上是一个相当简单过渡到一些其他的散列，不会破坏世界或甚至老储存库。

关于这一过渡，请参阅 Q1 2018年Git2.16 增加一个结构表示的散列算法。执行，过渡已经开始。

开始Git2.19(Q3 2018年),混帐具有挑选 沙-256为NewHash, ，并在该过程将其集成到代码(意SHA1仍是默认的(Q2 2019年，Git2.21)，但SHA2将是继任者)

原来的答复(第25日) 但是：

乔伊赫斯 试图那些pdf 一个混帐回购协议 和 他发现:

这包括两个文件具有相同的沙和尺寸，它做得到 不同blob感谢的方式git前面添加的标题 内容。

joey@darkstar:~/tmp/supercollider>sha1sum  bad.pdf good.pdf 
d00bbe65d80f6d53d5c15da7c6b4f0a655c5a86a  bad.pdf
d00bbe65d80f6d53d5c15da7c6b4f0a655c5a86a  good.pdf
joey@darkstar:~/tmp/supercollider>git ls-tree HEAD
100644 blob ca44e9913faf08d625346205e228e2265dd12b65    bad.pdf
100644 blob 5f90b67523865ad5b1391cb4a1c010d541c816c1    good.pdf

虽然追加相同的数据，这些碰撞的文件不会产生 其他冲突，加上数据没有。

所以 主矢量的攻击(锻一次提交)将:

  • 产生一个定期提交对象；
  • 使用的整个提交的对象+NUL为所选择的前缀
  • 使用的是相同的-前缀的碰撞击产生碰撞的好坏对象。
  • ...这是无用的，因为良好的和坏的提交对象仍然指向同一棵树!

另外，你已经可以和检测，密码分析冲突攻击的对SHA-1本在每个文件 cr-marcstevens/sha1collisiondetection

增加一个类似的检查在Git本身 会有一些计算成本.

在改变散， Linux的意见:

尺寸的散列和选择的散列算法是独立的问题。
什么你可能做的就是换256位的散列，用， 在内部，并在当地git数据库，然后通过默认只有 显示 散列作为一个40-character hex string(类似我们如何 已经缩写的东西在许多情况)。
这样的工具，围绕git甚至看不到改变，除非通过在 一些特殊的"--full-hash"论据(或者"--abbrev=64"或什么的- 默认的是，我们缩短到40).

仍然， 过渡计划(从SHA1到另一散列函数)将仍然是复杂的, 但积极的研究。
一个 convert-to-object_id 活动 是 在进行:

更新第20日: 审查详细说明可能的攻击和对其保护:

沙-1的名称可以是分配信任通过各种机制。例如，Git可以让你加密签名提交或标签。这样做的迹象，只有提交或标签的对象本身，这反过来点的其他对象包含实际文件的数据，通过使用他们的沙-1的名称。一次碰撞中的那些对象可能产生的签名，这似乎有效，但其分为不同的数据比签署者的本意。在这种攻击的签署人只能看到一半的碰撞，以及受害者看到的另一半。

保护：

最近的袭击使用特殊技术利用的弱点在沙-1的算法，找到一个碰撞中很少的时间。这些技术留下一个模式在字节，它可以检测到的时计算SHA-1的任何一半的碰撞对。

GitHub.com 现在执行这种检测的每个SHA-1计算，并中止操作，如果有证据表明，对象是一半的碰撞对。这可以防止攻击者使用的但说服一个项目，接受了"无辜的"一半的碰撞，以及防止他们主持的恶意的一半。

见"sha1collisiondetection"通过 马克*史蒂文斯

再次， Q1 2018年Git2.16 增加一个结构表示的散列算法，实施一个过渡到一个新的散列已经开始。
如上所述，新的支持散会 沙-256.

我认为密码学家会庆祝。

关于SHA-1的维基百科文章的引用：

2005年2月，宣布了王晓云，尹逸群和俞洪波的袭击。 攻击可以在完整版本的SHA-1中发现冲突，所需操作少于2 ^ 69。（强行搜索将需要2 ^ 80次操作。）

对于像 SHA-1 这样的哈希值，有几种不同的攻击模型，但通常讨论的是冲突搜索，包括 Marc Stevens 的 哈希冲突 工具。

“截至2012年，对SHA-1的最有效攻击被认为是Marc Stevens [34]的攻击，估计成本为277万美元，通过从云服务器中租用CPU电源来打破单个哈希价值。”

正如人们所指出的，您可以强制与 git 发生哈希冲突，但这样做不会覆盖另一个存储库中的现有对象。我什至可以想象 git push -f --no-thin 不会覆盖现有对象，但不能 100% 确定。

也就是说，如果您侵入远程存储库，那么您可以使您的错误对象成为旧对象 那里, ，可能会将被黑的代码嵌入到 github 或类似的开源项目中。如果你小心的话，也许你可以引入新用户下载的黑客版本。

然而，我怀疑项目开发人员可能做的许多事情可能会暴露或意外破坏您价值数百万美元的黑客行为。特别是，如果某些开发人员（您没有破解过）运行了上述内容，那么这将是一大笔钱的流失 git push --no-thin 修改受影响的文件后，有时甚至没有 --no-thin 取决于。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top