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

Question

这可能永远不会发生在现实世界中,并且可能永远不会发生,但让我们考虑一下:假设您有一个git存储库,进行提交,并且变得非常不幸:其中一个blob最终拥有相同的SHA-1另一个已存在于您的存储库中.问题是,Git将如何处理这个？简直失败了？找到一种方法来链接两个blob并根据上下文检查哪一个需要？

更多的是脑筋急转弯而非实际问题,但我发现这个问题很有趣.

Answer 1

我做了一个实验,以确切了解Git在这种情况下的表现.这是版本2.7.9~rc0 + next.20151210(Debian版本).我基本上只是通过应用以下diff和重建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已经存在并且您使用相同的哈希创建提交对象,则在更新"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都可以,因为它会因错误而停止.我想如果它失败并且至少在所有情况下都出现错误会更好.

Answer 2

原始答案(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的问题,但暂时不采取行动.

注(幽默):你可以强制提交到一个特定的SHA1 前缀,项目gitbrute从布拉德·菲茨帕特里克(bradfitz).

gitbrute强制执行一对作者+提交者时间戳,以便生成的git commit具有您想要的前缀.

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

丹尼尔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的 " 加密哈希函数的生命周期 " . 在那页中,她指出:

谷歌花了6500个CPU年和110个GPU年来说服每个人我们需要停止使用SHA-1来处理安全关键应用程序.
还因为它很酷

查看更多在我下面的单独的答案.

Answer 3

据Pro Git说:

如果你碰巧提交的哈希值与存储库中的前一个对象具有相同的SHA-1值,Git将会在Git数据库中看到前一个对象,并假设它已经被写入.如果您尝试在某个时刻再次检出该对象,您将始终获得第一个对象的数据.

所以它不会失败,但它也不会保存你的新对象.
我不知道命令行会怎么样,但这肯定会令人困惑.

再往下一点,同样的参考试图说明这种碰撞的可能性:

下面是一个示例,让您了解获取SHA-1冲突所需的内容.如果地球上所有65亿人都在进行编程,而每一秒,每一个人都生成的代码相当于整个Linux内核历史(100万Git对​​象)并将其推入一个巨大的Git存储库,则需要5年时间该存储库包含足够的对象,以使单个SHA-1对象发生碰撞的概率为50%.更高的可能性是你的编程团队的每个成员都会在同一天晚上被无关紧要的事件中的狼袭击和杀死.

Answer 4

要添加到我之前的2012年答案,现在(2017年2月,五年后),与shattered.io n 实际SHA-1碰撞的示例,您可以在其中制作两个碰撞的PDF文件:即获得SHA-第一个PDF文件上的1个数字签名,也可以作为第二个PDF文件上的有效签名被滥用.
另见" 在死亡之门多年,广泛使用的SHA1功能现已死亡 ",并举例说明.

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

(1)首先 - 天空没有下降.使用加密哈希来进行安全签名,并使用一个为内容可寻址系统(如git)生成"内容标识符"之间存在很大差异.

(2)其次,这种特殊SHA1攻击的性质意味着它实际上很容易被缓解,并且已经发布了两组针对该缓解的补丁.

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

关于该转换,请参阅Q1 2018 Git 2.16,添加表示散列算法的结构.该过渡的实施已经开始.

原始答案(2月25日)但是:

• 这允许伪造一个blob,但是树的SHA-1仍然会改变,因为伪造的blob的大小可能与原始blob的大小不同:请参阅" 如何计算git哈希？ "; 一个斑点SHA1是基于所述内容和大小来计算.
  它确实有一些问题的git-svn,虽然.或者更确切地说是svn本身,如此处所示.
• 正如我在原始答案中所提到的,此类尝试的成本目前仍然令人望而却步(6,500 CPU年和100 GPU年)另请参阅Valerie Anita Aurora的" 加密散列函数的生命周期 ".
• 如前所述,这不是关于安全性或信任,而是数据完整性(重复数据删除和错误检测)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评论:

散列的大小和散列算法的选择是独立的问题.
您可能要做的是切换到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添加表示散列算法的结构,已经开始实现向新散列的转换.

Answer 5

我认为密码学家会庆祝.

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

2005年2月,王晓云,益群丽莎和洪洪宇的一次袭击被宣布.攻击可以在完整版SHA-1中发现冲突,只需要少于2 ^ 69次操作.(蛮力搜索需要2 ^ 80次操作.)

Answer 6

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

"截至2012年,针对SHA-1的最有效的攻击被认为是一个由Marc史蒂文斯[34]为$ 2.77M的估计成本通过从云服务器租用CPU功率打破单个散列值".

正如大家所指出的,你可以强制与git进行哈希冲突,但这样做不会覆盖另一个存储库中的现有对象.我想甚至git push -f --no-thin不会覆盖现有的对象,但不是100%肯定.

也就是说,如果你攻入一个远程仓库,那么你可以让你的假对象上了年纪一个有可能嵌入黑客代码到GitHub上或类似的一个开源项目.如果你小心,那么也许你可以介绍新用户下载的黑客版本.

但我怀疑项目开发人员可能做的很多事情可能会暴露或意外地破坏你的数百万美元的黑客攻击.特别是,如果一些你没有破解的开发人员git push --no-thin在修改受影响的文件之后运行上述内容,有时即使没有--no-thin依赖项,也会耗费大量资金.