月別: 2017年2月

SHA-1衝突とsubversionもう少し

昨日の記事については特に誰も教えてくれなかったが、subversionのメールスレッドは自力で発見した。

http://mail-archives.apache.org/mod_mbox/subversion-dev/201702.mbox/%3C20170223200227.ynjumirjnmlesy5m%40sunbase.org%3E

これによると、Subversionのバックエンドでrep-sharingという機能がオンかオフかで判断されていて、デフォルトはオン、オフだと大丈夫、ということっぽい?

ただ、試してみると、shattered-1.pdfとshattered-2.pdfの内容は完全に一致してしまうため、変なバグは残っているような気がする。なんでこうなってるんだろうな。内容はshattered-1.pdfになっている。が、エラーにはならない、という意味ではマシ。


さて、rep-sharingがどういう機能なのかというと、 http://svnbook.red-bean.com/en/1.6/svn.reposadmin.maint.html によれば、

Repositories created with Subversion 1.6 or later further enjoy the disk space savings afforded by representation sharing, a feature which allows multiple files or file revisions with identical file content to refer to a single shared instance of that data rather than each having their own distinct copy thereof.

ということなので、コンテントのハッシュを計算し、ハッシュ値が一致した場合は片方だけを保存しておくということなのだろう。一方、コミット時のMD5およびSHA1の値は、メタデータとして別個に保存しておき、svn co時に使われる、ということなのだろうか?

ところで、昨日の記事には間違いがあった(訂正済み)。エラーメッセージを再掲すると、

$ svn co file:///tmp/svntest/repo2
A repo2/shattered-1.pdf
svn: E200014: Checksum mismatch for '/tmp/svntest/c2/repo2/shattered-2.pdf':
 expected: 5bd9d8cabc46041579a311230539b8d1
 actual: ee4aa52b139d925f8d8884402b0a750c

となっているのだけど、expectedはshattered-2.pdfの正しいMD5値、actualはshattered-1.pdfのMD5値になっている。つまり、チェックアウト時にコンテントのMD5値も検証していて、この不一致がエラーになっている。

コードはちゃんと読めていないけれど、ここから推測するに

  • svn coの際、コンテントのハッシュを検証する。SHA1とMD5の両方で検証されるか、MD5のみ検証するかどっちか
  • rep-sharingが有効な場合、レポジトリ内にはshattered-1.pdfの内容だけが保存されている。svn coではこの内容が取り出される
  • 一方、rep-sharingが有効な場合、メタデータのMD5とSHA1はキャッシュされているので、この内容を使って検証される
  • MD5値は一致しないのでエラー

といった流れになると思われる。

rep-sharingが有効でない場合でも、チェックアウトするとなぜか両方ともshattered-1.pdfの内容になってしまうのだけど、これはプロトコルが何らかの最適化により、同じSHA1値のものを取得するのを避けているからだろうか? よくわからないな……。

なおsvnadmin dumpの内容をよく見ると、

  • rep-sharingが有効な場合、dump内容ではshattered-1.pdfとshattered-2.pdfの内容は一致している(が、メタデータのMD5が異なる)
  • rep-sharingが無効な場合、dump時にはファイルの中身は異なる

となっていて、rep-sharingの機能が窺い知れる。

なおダンプ内容にも元々のMD5とSHA1の値が記録されるけれど、rep-sharingによってコンテントのハッシュは一致しないので、このダンプ結果をsvnadmin loadすると同じ検証エラーにより失敗することになる。

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

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

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

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

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

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

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

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