Git 原理漫步及 SHA-1 碰撞

Contents

1. 1. 基本原理
2. 2. 数据压缩
3. 3. SHA-1 碰撞

基本原理

接触 Git 以来有三四个年头，第一次往 GitHub 提的 repo 还在这儿 learn 。关于 Git 的原理这块儿，除了大二那次阿里实习面试被问了下还就一点交集没了。

最近突然想起来，网上搜索下来看看 Git 内部原理，具体讲得比较简练但还是能了解个大概。

Git 是一套内容寻址文件系统。

这是 Git 官方的定义。

1.文件存储为快照

2..git/objects 文件夹下存放三种对象：tree/blob/commit

tree 可以指向 blob 也可以指向另一个 tree 指针，tree 就是文件路径结构

blob 就是文件本身

commit 就是使用 Git 时候接触的那个 commit

3.这三种对象使用 SHA-1 来摘要信息得出一个 40 位的十六进制字符串，取前两位 00 到 ff 255 个作为 .git/objects 的子目录，剩下的作为文件名。

随后找个网友的博客看看，翻了 Git源码学习（一） 我理解的基本对。这位网友学习源码的方式是找到 Git 最早最简单的那个版本 commit 历史回溯到第一次提交，然后挨个 commit 的来看。这样可以顺着开发者的思路来看，而且不会被一开始庞大的项目体系压垮。我曾经用这样的方式看了下 SDWebImage 的源码，很可惜没看两天就弃坑了，找机会再捡起来接着看。

数据压缩

前面看原理说道：存储快照。这意味着每个文件每个 commit 都要存储一个文件。比方说：

commit 1 : test.txt 其内容为 version 1

commit 2 : test.txt 其内容为 version 1, version 2

这两个 test.txt 都会被 hash 一下，然后分散的存储到 .git/objects目录下。我在想这要是非常多 commit，非常多文件这样存储快照岂不是要 GG ？最后 .git 目录的大小比 repo 本身还要大？或者考虑 test.txt 有 10G 大，commit 2 只加了一行字，那我 .git 只要变成 20G ？

带着这样的疑问查询网络，原来 Git 有个叫 Packfiles 的概念。之前的那种保存文件方式 Git 称之为松散对象（loose object），Git 会把这些对象打包成一种叫 packfile 的二进制文件来节省空间。这个动作对应的命令是 git gc ，对应的终端输出是

$ git gc
Counting objects: 17, done.
Delta compression using 2 threads.
Compressing objects: 100% (13/13), done.
Writing objects: 100% (17/17), done.
Total 17 (delta 1), reused 10 (delta 0)

这实在是熟悉不过了，看来在 push 的时候调用了 gc 命令。数据压缩主要是通过使用差异编码的方式，就是 commit 2 存放的那个 test.txt 只存一个指向 commit 1 的对应 test.txt 的指针，同时记录这两者的差异。最大的部分通过指针来共享，差异部分另外编码。这个命令叫 gc 也是有意思，不知道是不是 garbage collection 的意思。

SHA-1 碰撞

看了几篇介绍原理的文章，寻思着不如看看源码。

找到了 GitHub 上一个叫 git 的 repo git，真是有意思。赫然看到一个 submodule sha1collisiondetection @ 19d97bf，看名字是叫 SHA-1 碰撞检测。这玩意儿是拿来检测 SHA-1 hash 算法冲突的？

搜索了下 git sha1 collision probability 第一个是 SO 上的问答

Hash collision in git

有人说，如果能搞到两个文件具有相同的 hash sum，那就说这两个文件是一样的 identical。

还有个人具体描述了下，SHA-1 hash 有 40 位的十六进制长度，可以表示 10^48 种状态，而组成月球的原子总数才 10^47。Git hash 冲突的概率类似于从十个月球中挑一个月球，再从里面取一个原子小球是蓝色，再从这十个月球中再挑一个月球取一个原子小球也是蓝色的概率（第一次取的原子小球应该是不放回去了，放回去了不会对结果产生显著影响）。

Git 官方对此也有一个类比解释

许多人可能会担心一个问题：在随机的偶然情况下，在他们的仓库里会出现两个具有相同 SHA-1 值的对象。那会怎么样呢？

如果你真的向仓库里提交了一个跟之前的某个对象具有相同 SHA-1 值的对象，Git 将会发现之前的那个对象已经存在在 Git 数据库中，并认为它已经被写入了。如果什么时候你想再次检出那个对象时，你会总是得到先前的那个对象的数据。

不过，你应该了解到，这种情况发生的概率是多么微小。SHA-1 摘要长度是 20 字节，也就是 160 位。为了保证有 50% 的概率出现一次冲突，需要 2^80 个随机哈希的对象（计算冲突机率的公式是 p = (n(n-1)/2) * (1/2^160))。2^80 是 1.2 x 10^24，也就是一亿亿亿，那是地球上沙粒总数的 1200 倍。

现在举例说一下怎样才能产生一次 SHA-1 冲突。如果地球上 65 亿的人类都在编程，每人每秒都在产生等价于整个 Linux 内核历史（一百万个 Git 对象）的代码，并将之提交到一个巨大的 Git 仓库里面，那将花费 5 年的时间才会产生足够的对象，使其拥有 50% 的概率产生一次 SHA-1 对象冲突。这要比你编程团队的成员同一个晚上在互不相干的意外中被狼袭击并杀死的机率还要小。

冲突的概率比某天晚上你的同事被狼袭击并杀死的概率还小。

但是，事情并没有那么简单。还是前面那个 SO 帖子，看到一个赞数很少的人说

Google now claims that SHA-1 collision is possible under certain preconditions:

https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

想起来去年初的时候好像是有这么一回大事，当时看 TK 教主微博看到的。

https://shattered.io/ Google 在这个网站解释了他们的工作，并且给了两个 pdf 的例子。hash 值一样，但是内容不一样。

https://bugs.webkit.org/show_bug.cgi?id=168774#c23 WebKit 的 svn 仓库有人提交了这两个 pdf 做测试，证明 svn 是会受到攻击的。

到这里总算明白为啥 Git 源码引用了一个 submodule 来检测是否存在潜在的 SHA-1 碰撞风险了，那个 submodule 就是实现稳定碰撞的科学家写的工具。这几个科学家还写了篇关于碰撞的论文 The first collision for full SHA-1 。

It is based on the concept of counter-cryptanalysis and it is able to detect known and unknown SHA-1 cryptanalytic collision attacks given just a single file from a colliding file pair.

反正它就是能根据某些特征就能识别出已知的和未知的存在碰撞攻击文件，具体不懂。

到最后建议使用 SHA-256，我在想这又能安全到啥时候？

漫游到此为止~