SHA1衝突とバージョン管理システム

SHA1については https://www.slideshare.net/herumi/googlesha1 を読んでフムフムーと勉強していた。わかりやすい。

ところでwebkitがテスト用に入れてみたところ（ブラウザキャッシュをハッシュで管理しているから衝突時のテストをしたかったようだ）、subversion自体が発狂するという珍事件が発生したらしい: https://bugs.webkit.org/show_bug.cgi?id=168774&comment=c27#c27

これはひどいｗって思うわけだけど、実際なんでこんなことが起こるんですかね？　誰か詳しい人に教えて欲しい。実際、

$ cd /tmp
$ mkdir svntest
$ cd svntest
$ mkdir repo
$ cd repo
$ svnadmin create .
$ cd ..
$ mkdir co1
$ cd co1
$ svn co file:///tmp/svntest/repo
Checked out revision 0.
$ cd repo
$ cp ~/shattered-* .
$ svn add shattered-*
A (bin) shattered-1.pdf
A (bin) shattered-2.pdf
$ svn commit -m 'test'
Adding (bin) shattered-1.pdf
Adding (bin) shattered-2.pdf
Transmitting file data ..done
Committing transaction...
Committed revision 1.
$ cd ../..
$ mkdir co2
$ cd co2
$ svn co file:///tmp/svntest/repo
A repo/shattered-1.pdf
svn: E200014: Checksum mismatch for '/tmp/svntest/co2/repo/shattered-2.pdf':
 expected: 5bd9d8cabc46041579a311230539b8d1
 actual: ee4aa52b139d925f8d8884402b0a750c
$ svn --version
svn, version 1.9.3 (r1718519)
 compiled Mar 14 2016, 07:39:01 on x86_64-pc-linux-gnu

などとなる。ここで”actual”は正しいSHA1ハッシュを計算できているので、なぜかサーバが提供するexpectedなハッシュが狂っているということになる。でもsvnadmin dumpすると正しいハッシュ値なんだよな。謎だ。（訂正：expectedは正しいMD5値、actualはshattered-1.pdfのMD5値だった）

git

gitにおいてファイルコミットはgitオブジェクトを作ることに相当し、gitオブジェクトはざっくりいうとSHA1ハッシュ値で識別される。ので、同じような理由により衝突の懸念がある。

ただ実際には https://git-scm.com/book/en/v2/Git-Internals-Git-Objects で詳しく解説されているようにヘッダ情報（ファイル長などの情報）とファイルの中身で構成されている。のでファイルの中身のSHA1ハッシュが一緒でもヘッダが先頭についているため、オブジェクトのハッシュ値は異なったものになるはず。

もっとも↑の解説スライドを読む限り、同じ手法により同じ長さの2つの相異なるPDFファイルをコミットすることにより、同じハッシュ値を持つgitオブジェクトが生成することは可能という気がする。その場合、その2つのファイル自体の中身は今回と全然異なるものになる。ファイルの中身自体のSHA1ハッシュも同じでかつgitのハッシュ値も同じになるというのは、今回の話とは関係なく、遥かに難しい問題であるように思う。

そもそもgitではハッシュは識別にしか使っていないだろうから、その場合でもcloneしたら2つのファイルの中身が同じになってしまうという意味では異常だけども、エラーを引き起こすようなことはない気がするけれど。

Mercurial

Mercurialではハッシュ値はグローバルな名前空間ではない。ファイルごとにそれぞれ履歴データを持っていて履歴をハッシュで管理するスタイルになっている。したがってそもそも違うファイルで同じハッシュ値となっても根本的に問題ないはず。

じゃあ同じファイル内の変更履歴でハッシュ値が衝突するとどうなるかというと、これは確かに問題になるかもしれない。ただし、ハッシュ値の計算には親のハッシュ値等を含むヘッダ情報が使われるため、このアプローチが正しいとすると通用しない（ヘッダ部分が共通でないため）。ただこれがどのような問題を引き起こすのかはわからない。ともあれこんなに簡単に壊れるような構造にはなっていないように思われる。

他のバージョン管理システム

知らんし調べてないけど問題ないんじゃないかなあ。