579

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

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

4

6 回答 6

790

我做了一个实验来确切了解 Git 在这种情况下的行为方式。这是版本 2.7.9~rc0+next.20151210（Debian 版本）。我基本上只是通过应用以下差异并重建 git 将哈希大小从 160 位减少到 4 位：

--- git-2.7.0~rc0+next.20151210.orig/block-sha1/sha1.c
+++ git-2.7.0~rc0+next.20151210/block-sha1/sha1.c
@@ -246,6 +246,8 @@ void blk_SHA1_Final(unsigned char hashou
    blk_SHA1_Update(ctx, padlen, 8);

    /* Output hash */
-   for (i = 0; i < 5; i++)
-       put_be32(hashout + i * 4, ctx->H[i]);
+   for (i = 0; i < 1; i++)
+       put_be32(hashout + i * 4, (ctx->H[i] & 0xf000000));
+   for (i = 1; i < 5; i++)
+       put_be32(hashout + i * 4, 0);
 }

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

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

对于#2，当你运行“git push”时，你通常会得到这样的错误：

error: object 0400000000000000000000000000000000000000 is a tree, not a blob
fatal: bad blob object
error: failed to push some refs to origin

或者：

error: unable to read sha1 file of file.txt (0400000000000000000000000000000000000000)

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

对于 #4 和 #6，您通常会收到如下错误：

error: Trying to write non-commit object
f000000000000000000000000000000000000000 to branch refs/heads/master
fatal: cannot update HEAD ref

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

对于 #5 和 #9，您通常会收到如下错误：

fatal: 1000000000000000000000000000000000000000 is not a valid 'tree' object

运行“git commit”时

如果有人试图克隆您损坏的存储库，他们通常会看到如下内容：

git clone (one repo with collided blob,
d000000000000000000000000000000000000000 is commit,
f000000000000000000000000000000000000000 is tree)

Cloning into 'clonedversion'...
done.
error: unable to read sha1 file of s (d000000000000000000000000000000000000000)
error: unable to read sha1 file of tullebukk
(f000000000000000000000000000000000000000)
fatal: unable to checkout working tree
warning: Clone succeeded, but checkout failed.
You can inspect what was checked out with 'git status'
and retry the checkout with 'git checkout -f HEAD'

我“担心”的是，在两种情况下（2,3），存储库在没有任何警告的情况下损坏，在 3 种情况下（1,7,8），一切似乎都正常，但存储库内容与您的预期不同成为。克隆或拉取的人将拥有与您拥有的内容不同的内容。案例 4、5、6 和 9 都可以，因为它会因错误而停止。我想如果至少在所有情况下都失败并出现错误会更好。

于 2016-01-04T20:15:12.333 回答
247

原始答案（2012）（请参阅shattered.io下面的 2017 SHA1 冲突）

来自 Linus 的旧（2006年）答案可能仍然相关：

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

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

但是，从安全的角度来看，“早期将覆盖”非常符合您的要求：请记住，git 模型是您应该主要只信任自己的存储库。
因此，如果您执行“ git pull”，则根据定义，新传入对象的可信度低于您已有的对象，因此允许新对象替换旧对象是错误的。

所以你有两种碰撞情况：

  • 不经意的那种，你不知何故非常不走运，两个文件最终具有相同的 SHA1。
    那时，发生的情况是，当您提交该文件（或执行“ git-update-index”将其移动到索引中，但尚未提交）时，将计算新内容的 SHA1，但由于它匹配旧对象，不会创建新对象，并且 commit-or-index 最终指向旧对象。
    您不会立即注意到（因为索引将与旧对象 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。

注意（幽默）：您可以使用Brad Fitzpatrick ( )的项目gitbrute强制提交到特定的 SHA1前缀。bradfitz

gitbrute 暴力破解一对作者+提交者时间戳，以便生成的 git 提交具有您想要的前缀。

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

Daniel Dinnyes在7.1 Git Tools - Revision Selection的评论中指出，其中包括：

您的编程团队的每个成员都更有可能在同一晚在不相关的事件中被狼袭击和杀死。

甚至最近（2017 年 2 月）也shattered.io证明了伪造 SHA1 冲突的可能性：（在我的单独答案
中查看更多信息，包括 Linus Torvalds 的 Google+ 帖子）

  • a/ 仍然需要超过 9,223,372,036,854,775,808 次 SHA1 计算。这相当于 6,500 年的单 CPU 计算和 110 年的单 GPU 计算的处理能力。
  • b/ 将伪造一个文件（具有相同的 SHA1），但在附加约束的情况下，其内容和大小将产生相同的 SHA1（仅内容冲突是不够的）：请参阅“如何计算 git 哈希？ ”） ：根据内容和大小计算 blob SHA1 。

有关更多信息，请参阅Valerie Anita Aurora的“加密哈希函数的生命周期” 。 在该页面中，她指出：

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

在下面我的单独答案中查看更多信息。

于 2012-02-22T09:53:05.517 回答
42

根据Pro Git：

如果您碰巧提交了一个对象，该对象的哈希值与您的存储库中的前一个对象相同，Git 将在您的 Git 数据库中看到前一个对象并假设它已经被写入。如果您尝试在某个时候再次检查该对象，您将始终获得第一个对象的数据。

所以它不会失败，但它也不会保存你的新对象。
我不知道这在命令行上会是什么样子，但这肯定会令人困惑。

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

这是一个示例，可让您了解发生 SHA-1 冲突需要什么。如果地球上所有 65 亿人都在编程，并且每一秒，每个人都在生成相当于整个 Linux 内核历史（100 万个 Git 对象）的代码并将其推送到一个巨大的 Git 存储库中，那么这将需要 5 年时间直到该存储库包含足够的对象，以使单个 SHA-1 对象冲突的概率为 50%。您的编程团队的每个成员都更有可能在同一晚在不相关的事件中被狼袭击和杀死。

于 2012-02-22T09:52:42.757 回答
29

为了补充我之前 2012 年的回答，现在（2017 年 2 月，五年后）是 SHA-1 与shattered.io实际碰撞的示例，您可以在其中制作两个碰撞的 PDF 文件：即获得一个 SHA-第一个 PDF 文件上的 1 个数字签名，也可以被滥用为第二个 PDF 文件上的有效签名。
另请参阅“多年来在死亡之门，广泛使用的 SHA1 函数现已死亡”，以及此插图。

2 月 26 日更新：Linus在 Google+ 帖子中确认了以下几点：

(1) 首先——天没有塌下来。将加密哈希用于安全签名之类的事情，与使用加密哈希为像 git 这样的内容可寻址系统生成“内容标识符”之间存在很大差异。

(2) 其次，这种特殊 SHA1 攻击的性质意味着它实际上很容易缓解，并且已经发布了两组补丁用于缓解。

(3) 最后，实际上有一个相当直接的过渡到不会破坏世界的其他一些哈希 - 甚至是旧的 git 存储库。

关于该转换，请参阅Q1 2018 Git 2.16添加表示哈希算法的结构。该过渡的实施已经开始。

从 Git 2.19 (Q3 2018) 开始，Git 选择了SHA-256 作为 NewHash，并且正在将其集成到代码中（这意味着 SHA1 仍然是默认值（Q2 2019，Git 2.21），但 SHA2 将是继任者）

原始答案（2 月 25 日）但是：

Joey Hess在Git 存储库中尝试了这些 pdf ，他发现：

这包括两个具有相同 SHA 和大小的文件，由于 git 将标题添加到内容的方式，它们确实会得到不同的 blob。

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 个字符的十六进制字符串（有点像我们已经在很多情况）。
这样，围绕 git 的工具甚至看不到更改，除非传入一些特殊的 " --full-hash" 参数（或 " --abbrev=64" 或其他任何东西——默认为我们缩写为 40）。

尽管如此，转换计划（从 SHA1 到另一个散列函数）仍然很复杂，但需要积极研究。
一个convert-to-object_id活动正在进行中：

3 月 20 日更新：GitHub 详细说明了可能的攻击及其保护：

可以通过各种机制为 SHA-1 名称分配信任。例如，Git 允许您对提交或标签进行加密签名。这样做只会对提交或标记对象本身进行签名，这反过来又通过使用它们的 SHA-1 名称指向包含实际文件数据的其他对象。这些对象中的冲突可能会产生一个看似有效的签名，但它指向的数据与签名者预期的数据不同。在这样的攻击中，签名者只看到一半的碰撞，而受害者看到另一半。

保护：

最近的攻击使用特殊技术来利用 SHA-1 算法中的弱点，从而在更短的时间内发现冲突。这些技术在字节中留下了一种模式，当计算碰撞对的任何一半的 SHA-1 时，可以检测到这种模式。

GitHub.com 现在对其计算的每个 SHA-1 执行此检测，如果有证据表明该对象是碰撞对的一半，则中止操作。这可以防止攻击者使用 GitHub 来说服项目接受他们碰撞中“无辜”的一半，以及阻止他们托管恶意的一半。

参见马克·史蒂文斯sha1collisiondetection的“”

Again, with Q1 2018 Git 2.16 adding a structure representing hash algorithm, the implementation of a transition to a new hash has started.
As mentioned above, the new supported Hash will be SHA-256.

于 2017-02-25T00:05:30.637 回答
6

我认为密码学家会庆祝的。

引用SHA-1 上的 Wikipedia 文章：

2005 年 2 月，王晓云、尹毅群、尹丽莎和于洪波的袭击被宣布。攻击可以在完整版的 SHA-1 中发现冲突，需要少于 2^69 次操作。（蛮力搜索需要 2^80 次操作。）

于 2012-02-22T10:37:34.917 回答
6

像 SHA-1 这样的哈希有几种不同的攻击模型，但通常讨论的一种是碰撞搜索，包括 Marc Stevens 的HashClash工具。

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

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

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

然而，我怀疑该项目的开发人员可能会做的许多事情可能会暴露或意外破坏您价值数百万美元的黑客攻击。git push --no-thin特别是，如果某些您没有破解的开发人员在修改受影响的文件后运行上述程序，有时甚至没有--no-thin依赖，这将是一大笔钱。

于 2014-12-19T11:28:35.710 回答