logo标签列表

Git在blob发生SHA-1碰撞时会如何处理？

githash-collision
592

这种情况可能在现实世界中从未发生过，并且可能永远不会发生，但让我们考虑一下：假设您有一个git存储库，在其中进行了一次提交，然后非常不幸地发现其中一个blob的SHA-1与已经存在于您的存储库中的另一个blob相同。问题是，Git会如何处理这种情况？会简单地失败吗？会找到一种方式将两个blob关联起来并根据上下文检查哪一个是需要的吗？

这更像是一个脑筋急转弯而不是一个真正的问题，但我认为这个问题很有趣。

88
曾经是一道脑筋急转弯，现在可能成为一个实际的问题。 - user1038550
12
这个问题涉及到“预像攻击”，而Google所展示的是“碰撞攻击”——相似但略有不同。你可以在这里阅读更多关于两者之间差异的内容：http://cstheory.stackexchange.com/questions/585/what-is-the-difference-between-a-second-preimage-attack-and-a-collision-attack。 - Saïd
3
@Toby 最初的谜题并不涉及攻击（无论是预映像还是碰撞），而是关于偶然碰撞的问题，这种情况发生的概率极小，几乎可以忽略不计。我认为Saheed正确地指出了这仍然不是一个实际问题。但是你说得对，Google的碰撞攻击可能会根据Git的使用方式造成安全问题。 - Andrew W. Phillips
2
这是第二个仅有320字节的碰撞 https://privacylog.blogspot.com/2019/12/the-second-sha-collision.html - William Entriken
2
随着对SHA-1的选择前缀攻击的发展，这已经成为可能的领域。https://arstechnica.com/information-technology/2020/01/pgp-keys-software-security-and-much-more-threatened-by-new-sha1-exploit/ - Dan Is Fiddling By Firelight
显示剩余2条评论
6个回答
810

我进行了一项实验，以确定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：一切似乎都正常，直到您尝试推送或有人克隆您的存储库。然后您会看到仓库已损坏。
  3. 如果已经存在一个具有相同哈希值的提交对象，并且您创建了一个具有相同哈希值的blob：与＃2相同 - 损坏
  4. 如果已经存在一个blob，并且您使用相同的哈希值创建commit对象，则更新“ref”将失败。
  5. 如果已经存在一个blob，并且您使用相同的哈希值创建tree对象，则创建commit时将失败。
  6. 如果已经存在一个具有相同哈希值的树对象，并且您创建了一个具有相同哈希值的提交对象，则更新“ref”将失败。
  7. 如果已经存在一个具有相同哈希值的树对象，并且您创建了一个具有相同哈希值的树对象，则一切似乎都正常。但是，当您提交时，整个存储库将引用错误的树。
  8. 如果已经存在一个具有相同哈希值的提交对象，并且您创建了一个具有相同哈希值的提交对象，则一切似乎都正常。但是，当您提交时，该提交将永远不会被创建，并且HEAD指针将移动到旧提交。
  9. 如果已经存在一个具有相同哈希值的提交对象，并且您创建了一个具有相同哈希值的树对象，则创建commit时将失败。

对于＃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）中，存储库会在没有任何警告的情况下变得损坏。而在另外三种情况（1、7、8），看起来一切正常，但存储库内容与预期不同。克隆或拉取的人将得到与您不同的内容。第4、5、6和9种情况是可以的，因为它们将停止并显示一个错误。我认为如果在所有情况下至少出现错误会更好。

188
很棒的答案 - 减小哈希大小以观察其实际行为是一个好主意。 - Gnurou
5
还有，如果要更换哈希算法，是否有任何计划？ - Pete
9
必读 - Linus Torvalds 的解释：https://plus.google.com/+LinusTorvalds/posts/7tp2gYWQugL - phil_lgr
10
当G+被关闭时，Linus的言论是否得到了任何支持？ - Dan Is Fiddling By Firelight
1
可以使用Wayback机器找到更新的Google Plus链接工作版本此处。 - Julie Nielsen
显示剩余5条评论
253

原始答案（2012）（请参见下面的shattered.io 2017 SHA1碰撞）：

Linus于2006年的旧答案可能仍然相关：

如果两个对象有相同的SHA1值，那么当我们从另一端接收到这个对象时，就不会覆盖已经存在的对象。因此，如果我们发现碰撞，每个特定存储库中的“早期”对象将始终被覆盖。但请注意，“更早期”的定义显然是针对每个存储库的，因为git对象网络生成的DAG没有完全排序，因此虽然不同的仓库在直系祖先情况下会达成共识，但如果这个对象通过不相关分支进行，则两个不同的仓库可能会以不同的顺序获取两个对象。
然而，“早期优先”非常符合安全角度的要求：记住，git模型要求您主要只信任自己的仓库。因此，如果您执行“git pull”，新传入的对象明显比您已经拥有的对象不可信，因此允许新对象替换旧对象是错误的。
所以你会遇到两种碰撞情况：
- “无意类型”碰撞，其中你非常非常不幸，两个文件最终具有相同的SHA1。此时，当您提交该文件（或使用“git-update-index”将其移动到索引中但未提交）时，将计算新内容的SHA1，但由于它与旧对象匹配，因此不会创建新对象，提交或索引最终指向旧对象。您不会立即注意到（因为索引将与旧对象的SHA1匹配，这意味着类似于“git diff”之类的东西将使用已检出的副本），但是如果您进行树级别的diff（或者您进行克隆或拉取，或者强制执行checkout），则会突然注意到该文件已经变成了与预期完全不同的内容。因此，您通常会比较快地注意到这种碰撞。 - 攻击者类型的碰撞，因为某人损坏（或暴力破解）了SHA1。这一点显然比无意类型更可能发生，但根据定义，它始终是“远程”存储库。如果攻击者可以访问本地仓库，则他有更容易搞乱您的方法。因此，在这种情况下，碰撞完全不是问题：您将获得一个与攻击者意图不同的“恶意”仓库，但由于您永远不会实际使用他的相撞对象，因此它与攻击者根本没有找到相撞的区别，但只是使用了您已经拥有的对象（即它与生成相同SHA1的相同文件的“平凡”碰撞是100%等效的）。

使用SHA-256的问题经常被提及，但目前尚未实施（2012年）。
注意：从2018年和Git 2.19开始, 代码正在重构以使用SHA-256。

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

gitbrute会暴力破解作者和提交者时间戳的组合，以便生成具有所需前缀的git提交。

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

Daniel Dinnyes在评论中指出7.1 Git 工具 - 版本选择，其中包括:

你的编程团队中每个成员在同一天晚上都有可能遭受不相关事件中袭击和死亡。

即使是最近（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进行安全关键应用。
同样也因为它很酷

请查看我下面的单独的答案以了解更多信息。
31
twist：在添加“/此行添加以避免冲突/”后仍然具有相同的哈希值:D你可以两次赢得彩票:P - Janus Troelsen
4
当然可以，但这仍然是一场彩票，不是吗？（正如这篇关于SHA1的简短说明中所述）。 - VonC
6
@VonC 关于这个引用：全球狼人流行病的爆发，将摧毁所有人类，并导致我所有开发人员在同一晚上惨遭杀害，尽管他们地理位置分散，这是否被认为是无关事件？？当然，假设这发生在满月之夜，显然情况会有所不同。现在，这样的情况会改变一切。甚至思考这个问题都是疯狂的！这是一个完全不同概率范围内的事情！这意味着我们必须... 立即停止使用GIT！现在就逃跑！！！！ - Daniel Dinnyes
2
@JanusTroelsen 然后你可以添加：/* 此行用于避免避撞行与其他代码的冲突 */ - smg
2
今天Linus和其他开发人员进行了进一步的讨论。他仍然认为这不是什么大问题，但是“我并不是在争论人们不应该扩展git到一个新的（更大的）哈希值。我认为这是显而易见的，我们确实希望最终能够向SHA3-256或其他哈希算法迁移。” - Jeremy
显示剩余7条评论
44
根据Pro Git：
如果您提交的对象与存储库中先前对象的SHA-1值相同，Git将看到已经在Git数据库中存在先前的对象并假定它已经被写入。如果您尝试在某个时候再次检出该对象，则始终会获得第一个对象的数据。
因此，它不会失败，但也不会保存您的新对象。我不知道在命令行上会是什么样子，但肯定会让人困惑。
在稍后的部分，同一参考试图说明这种碰撞的可能性：
这是一个例子，让您了解获得SHA-1冲突所需的工作量。如果地球上65亿人都在编程，并且每秒钟每个人都可以生成相当于整个Linux内核历史记录（100万Git对象）的代码并将其推送到一个巨大的Git存储库中，那么需要5年时间才能使该存储库包含足够数量的对象，以具有50％的单个SHA-1对象冲突概率。更高的可能性是您的编程团队的每个成员会在同一晚因不相关事件而被狼攻击并死亡。
45
我想看一下最后一句话数字的来源；-) - Joachim Sauer
18
@Jasper：那个链接是很好的文档，但它并不包含有关一个团队中每个成员在同一晚上分别遭受狼袭击和死亡的概率统计数据。 - Joachim Sauer
5
@Jasper：根据我的理解，这段文字字面上的意思是声称65亿团队成员在同一天晚上被狼杀死的概率超过50%。但我对他的陈述主要反对点是这种事件必须是全球性的现象；由于不相关的事件，这种事情发生是不可想象的。;) - Keith Robertson
5
我很确定这篇帖子是在谈论你的实际团队成员全部被吃掉的概率与如果全世界所有人都生产大量代码时哈希冲突的概率相比，以及在这些情况下达到50%冲突概率所需的时间（即狼事件并没有涉及整个世界，而且50%与狼事件是无关的）。不过你已经理解了重点，如果这样的事件是不可想象的，那么Git哈希冲突也应该如此。（当然，一个（几乎）纯粹基于机会，而另一个则不是，但仍然如此。） - Jasper
13
今晚当心狼。 - user1038550
显示剩余4条评论
30

在我2012年的答案（链接）之后，现在已经有一个实际的SHA-1碰撞例子了（2017年2月，五年后），可以在shattered.io上制作两个相撞的PDF文件：也就是说，在第一个PDF文件上获得SHA-1数字签名，同时该签名也可以被滥用为第二个PDF文件的有效签名。
另请参阅“多年来濒于崩溃的广泛使用的SHA1功能现已死亡”和此插图。

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

(1) 首先，天空并没有塌下来。在安全签名等方面使用加密哈希和在像Git这样的内容可寻址系统中生成“内容标识符”之间有很大的区别。
(2) 其次，这种特定的SHA1攻击方式实际上非常容易被缓解，而且已经发布了两组补丁以进行缓解。
(3) 最后，实际上有一种相当简单的转换方式可以使用其他哈希算法，而不会破坏整个世界，甚至是旧的Git存储库。
关于这种转换，请参见Q1 2018 Git 2.16添加表示哈希算法的结构。该转换的实现已经开始。 从Git 2.19开始（2018年第三季度），Git选择了SHA-256作为NewHash，并正在将其集成到代码中（这意味着SHA1仍然是默认值（2019年第二季度，Git 2.21），但SHA2将是其继任者）。

原始答案（2月25日）

  • 这允许伪造一个blob，但是由于伪造的blob的大小可能与原始的blob不同，因此树的SHA-1仍然会改变：请参见 "How is the git hash calculated?"；blob SHA1基于内容和大小计算。
    然而，这对于git-svn来说确实存在一些问题。或者更确切地说，是svn本身存在问题，如此处所示。
  • 正如我在我的原始回答中提到的，目前这种尝试的成本仍然是禁止性的（需要6500个CPU年和100个GPU年）。另请参见Valerie Anita Aurora在“Lifetimes of cryptographic hash functions”中的论述。
  • 如前所述，这不涉及安全或信任，而是数据完整性（去重和错误检测），可以通过git fsck轻松检测出来，如今天Linus Torvalds所说的那样。git fsck会警告有一个带有NUL之后隐藏的不透明数据的提交消息（尽管欺诈文件中并不总是存在NUL）。
    并非每个人都开启transfer.fsck，但GitHub会：如果出现格式不正确的对象或损坏的链接，任何推送都将被中止。尽管...这并不是默认激活的原因。
  • PDF文件可以有任意二进制数据，您可以更改以生成碰撞的SHA-1，而不是伪造的源代码。
    实际问题在于创建具有相同头提交哈希但内容不同的两个Git存储库。即使如此，攻击仍然很复杂。
  • Linus补充道：

    SCM的整个目的就是它不是关于一次性事件，而是关于持续的历史。这也从根本上意味着，成功的攻击需要随时间而变化，并且不能被检测到。
    如果您可以欺骗SCM一次，插入您的代码，然后在下周被检测到，那么您实际上没有做任何有用的事情。您只是自己烧掉了。

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 comments：

哈希表的大小和哈希算法的选择是独立的问题。
你可能会切换到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说服项目接受他们碰撞的“无辜”一半，同时也阻止他们托管恶意的一半。 请参见Marc Stevens的 "sha1collisiondetection"。
再次，随着 Q1 2018 Git 2.16 添加了一个表示哈希算法的结构，实现向新哈希的过渡已经开始。
如上所述，新支持的哈希将是 SHA-256。
碰撞事件：1.尝试创建碰撞，而非偶然发生的碰撞。2.从PDF报告中了解到：总计计算所花费的时间相当于2^63.1次SHA-1压缩，并且大约需要6,500个CPU年和100个GPU年。 3.虽然我们应该放弃MD5和SHA-1，但它们通常用于文件唯一性使用是可以的。 - zaph
值得注意的是，WebKit为测试提交了发生冲突的PDF文件。这打破了他们的git-svn镜像基础设施：https://bugs.webkit.org/show_bug.cgi?id=168774#c24 - dahlbyk
1
@dahlbyk 值得注意的是...因为我在答案中指出了它（“git-svn”存在一些问题的链接间接地提到了它）。 - VonC
1
@Mr_and_Mrs_D 不，它目前还没有出现错误。正在进行一个大的补丁程序，将有助于促进碰撞检测：https://marc.info/?l=git&m=148987267504882&w=2 - VonC
1
@Mr_and_Mrs_D 请查看 http://stackoverflow.com/posts/42450327/revisions 中的第4个编辑：现在它确实失败了，至少在上传到GitHub时是这样的。 - VonC
显示剩余2条评论
6

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

“截至2012年，最有效的攻击SHA-1的方法被认为是由Marc Stevens提出的一种方法，估计需要花费$2.77M租用云服务器的CPU算力才能破解一个哈希值。”

正如大家指出的，您可以通过git强制发生哈希碰撞，但这样做并不会覆盖另一个存储库中的现有对象。我想即使使用git push -f --no-thin也无法覆盖现有的对象，但并不确定。

话虽如此，如果您成功入侵了远程存储库，那么您可以在那里将您的伪造对象变成较旧的版本，并可能将黑客代码嵌入到GitHub或类似网站上的开源项目中。如果您小心谨慎，也许可以引入一个被黑客攻击过的版本供新用户下载。

然而，我怀疑项目开发人员可能会做很多事情，这些事情可能会暴露或意外摧毁您的数百万美元的黑客攻击。特别是如果某个未被您攻击的开发人员修改了受影响的文件后运行上述git push --no-thin甚至没有使用--no-thin，那么你投入的大量资金可能就打了水漂。

6
我认为密码学家会庆祝。
引自SHA-1维基百科文章的一句话：

在2005年2月，王小云、尹丽萨和余红波宣布了一次攻击。该攻击可以在SHA-1的完整版本中找到碰撞，需要少于2^69个操作。（暴力搜索需要2^80个操作。）

8
重点是SHA1算法存在缺陷，并且这正好是Git被引入的时间。此外，概率是非线性的。仅仅因为你买了五十年彩票并不意味着你赢得的机会更高。每次购买彩票的机会都是相同的。第一次玩的人仍然有可能赢得奖金。 - 0xC0000022L
这是唯一能找到碰撞的攻击，这意味着你可以找到一个 y 使得 h(x) == h(y)，这对于任意数据（如 SSL 证书）是严重威胁，但这不会影响 Git，因为它容易受到第二前像攻击的攻击，这意味着如果有消息 x，你可以将其修改为消息 x'，使得 h(x) == h(x')。因此，这种攻击并不会削弱 Git 的安全性。此外，Git 并没有选择 SHA-1 作为安全原因。 - Hauleth
现在已经发现了一次碰撞 - 只是目前还没有直接影响git的碰撞。 - Willem Hengeveld
1
2的69次方约为600艾克萨操作。八年后，配备了Nvidia A100的SaturnV超级计算机可以实现4.6艾克萨OPS，因此它可能在略超过2分钟内解决这个问题，或在几天内进行暴力攻击。 - qdin
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接