SHAttered で Git の SHA-1 ハッシュを衝突させられるか試す

https://shattered.it/ のリリースを受けて、Git において、違うファイルをコミットしたにも関わらず、それらのコミットを参照する SHA-1 ハッシュが同じである状態を実現できるかを試しました。

同じ SHA-1 ハッシュを持つ PDF ファイルで可能か

https://shattered.it/ で公開されている、SHA-1 ハッシュが同じ PDF ファイルを、それぞれ空のレポジトリにコミットします。

$ wget https://shattered.it/static/shattered-1.pdf https://shattered.it/static/shattered-2.pdf
$ diff shattered-1.pdf shattered-2.pdf
Binary files shattered-1.pdf and shattered-2.pdf differ
$ shasum shattered-1.pdf shattered-2.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-1.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-2.pdf
$ cp shattered-1.pdf shattered.pdf
$ git --git-dir=.git-1 --work-tree=. init
Initialized empty Git repository in /path/to/.git-1/
$ git --git-dir=.git-1 --work-tree=. add shattered.pdf
$ GIT_AUTHOR_DATE='Fri Feb 24 15:00:00 JST 2017' GIT_COMMITTER_DATE='Fri Feb 24 15:00:00 JST 2017' git --git-dir=.git-1 --work-tree=. commit -m 'test'
[master (root-commit) e95789a] test
 1 file changed, 0 insertions(+), 0 deletions(-)
 create mode 100644 shattered.pdf
$ git --git-dir=.git-1 --work-tree=. log --pretty=fuller
commit e95789af5bf00006938d8ab048ab51c9b68711a6
Author:     asannou <asannou@example.com>
AuthorDate: Fri Feb 24 15:00:00 2017 +0900
Commit:     asannou <asannou@example.com>
CommitDate: Fri Feb 24 15:00:00 2017 +0900

    test

shattered-1.pdf をコミットしたときの SHA-1 ハッシュは e95789af5bf00006938d8ab048ab51c9b68711a6 です。

$ cp shattered-2.pdf shattered.pdf
$ git --git-dir=.git-2 --work-tree=. init
Initialized empty Git repository in /path/to/.git-2/
$ git --git-dir=.git-2 --work-tree=. add shattered.pdf
$ GIT_AUTHOR_DATE='Fri Feb 24 15:00:00 JST 2017' GIT_COMMITTER_DATE='Fri Feb 24 15:00:00 JST 2017' git --git-dir=.git-2 --work-tree=. commit -m 'test'
[master (root-commit) ded44e8] test
 1 file changed, 0 insertions(+), 0 deletions(-)
 create mode 100644 shattered.pdf
$ git --git-dir=.git-2 --work-tree=. log --pretty=fuller
commit ded44e864ff901c3bb6367f13ad6aeb0b6c0cfa0
Author:     asannou <asannou@example.com>
AuthorDate: Fri Feb 24 15:00:00 2017 +0900
Commit:     asannou <asannou@example.com>
CommitDate: Fri Feb 24 15:00:00 2017 +0900

    test

全く同じ日時を指定したのですが shattered-2.pdf をコミットしたときは ded44e864ff901c3bb6367f13ad6aeb0b6c0cfa0 となり、違うハッシュでした。原因を知るために、コミットの SHA-1 ハッシュがどのように計算されるかを調べましょう。

Git のコミットは、コミットオブジェクトというもので管理されています。コミットオブジェクトは、下記のように確認することができます。

$ git --git-dir=.git-1 --work-tree=. cat-file -p e95789af5bf00006938d8ab048ab51c9b68711a6
tree 8004c8a7b6fce1452539556bb4c4c91b92b5c2bc
author asannou <asannou@example.com> 1487916000 +0900
committer asannou <asannou@example.com> 1487916000 +0900

test

コミットの SHA-1 ハッシュというのは、このコミットオブジェクトの内容の先頭に "commit \0" を付加して SHA-1 ハッシュを計算したものです。

$ git --git-dir=.git-1 --work-tree=. cat-file -p e95789af5bf00006938d8ab048ab51c9b68711a6 > commit-1
$ wc -c commit-1
     163 commit-1
$ printf "commit 163\0" > commit-header-1
$ cat commit-header-1 commit-1 | shasum
e95789af5bf00006938d8ab048ab51c9b68711a6  -

実は、これをやってくれるコマンド git hash-object が既にあります。

$ git hash-object -t commit commit-1
e95789af5bf00006938d8ab048ab51c9b68711a6

ここで shattered-2.pdf のコミットオブジェクトを覗くと、tree という値だけが異なっていることがわかります。

$ git --git-dir=.git-2 --work-tree=. cat-file -p ded44e864ff901c3bb6367f13ad6aeb0b6c0cfa0
tree 32a3329d74097e4a877b1180106e65d3b9f76848
author asannou <asannou@example.com> 1487916000 +0900
committer asannou <asannou@example.com> 1487916000 +0900

test

tree もツリーオブジェクトなので、内容を確認します。

$ git --git-dir=.git-1 --work-tree=. cat-file -p 8004c8a7b6fce1452539556bb4c4c91b92b5c2bc
100644 blob ba9aaa145ccd24ef760cf31c74d8f7ca1a2e47b0  shattered.pdf
$ git --git-dir=.git-2 --work-tree=. cat-file -p 32a3329d74097e4a877b1180106e65d3b9f76848
100644 blob b621eeccd5c7edac9b7dcba35a8d5afd075e24f2  shattered.pdf

ツリーオブジェクトも似たような方法で SHA-1 ハッシュが求められます。

$ printf "100644 shattered.pdf\0%s" $(echo ba9aaa145ccd24ef760cf31c74d8f7ca1a2e47b0 | xxd -r -p) | git hash-object -t tree --stdin
8004c8a7b6fce1452539556bb4c4c91b92b5c2bc
$ printf "100644 shattered.pdf\0%s" $(echo b621eeccd5c7edac9b7dcba35a8d5afd075e24f2 | xxd -r -p) | git hash-object -t tree --stdin
32a3329d74097e4a877b1180106e65d3b9f76848

つまり blob という値が一致しないため、ハッシュが異なると言えます。そして同様に blob もブロブオブジェクトです。

$ git --git-dir=.git-1 --work-tree=. cat-file -p ba9aaa145ccd24ef760cf31c74d8f7ca1a2e47b0 > blob-1
$ git --git-dir=.git-2 --work-tree=. cat-file -p b621eeccd5c7edac9b7dcba35a8d5afd075e24f2 > blob-2

ブロブオブジェクトの内容は、コミットしたファイルそのものです。

$ diff blob-1 shattered-1.pdf
$ diff blob-2 shattered-2.pdf
$

ブロブオブジェクトも SHA-1 ハッシュが求められます。

$ git hash-object -t blob blob-1
ba9aaa145ccd24ef760cf31c74d8f7ca1a2e47b0
$ git hash-object -t blob blob-2
b621eeccd5c7edac9b7dcba35a8d5afd075e24f2

ここで git hash-object がどのような処理をするかを思い出すと、ハッシュが異なる理由がわかります。

$ wc -c blob-1
  422435 blob-1
$ printf "blob 422435\0" > blob-header-1
$ cat blob-header-1 blob-1 | shasum
ba9aaa145ccd24ef760cf31c74d8f7ca1a2e47b0  -

要するに、ブロブオブジェクトのハッシュには、コミットされたファイルそのままの SHA-1 ハッシュが使われず、ファイルに "blob \0" ヘッダが付加されたものの SHA-1 ハッシュが使用されるため、それをもとに計算される、ツリーオブジェクト、コミットオブジェクトのハッシュも一致しないという真相でした。


後日リリースされる、同じハッシュの PDF のペアを作成するコードを使えば可能か


90 日後に、ふたつの異なる画像から、同じ SHA-1 ハッシュを持つ PDF のペアを作ることができるコードがリリースされるそうです。

Following Google’s vulnerability disclosure policy, we will wait 90 days before releasing code that allows anyone to create a pair of PDFs that hash to the same SHA-1 sum given two distinct images with some pre-conditions.

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

これを用いて、先頭が "blob \0" となっていて、内容が異なり、同じハッシュのファイルを作れるでしょうか。



https://shattered.it/static/pdf_format.png


おそらく PDF に含まれる JPEG の部分のみを差し替えられるコードと思われますので prefix (pre-determined) となっている PDF Header の前に "blob \0" を挿入するのは無理だろうと予想します。

このコードを予想する記事 を書きました。

prefix をブロブオブジェクトにして同じ手法を用いれば可能か

https://shattered.it/static/shattered.pdf では prefix を PDF にしていますが、Git のブロブオブジェクトのヘッダを prefix として、書かれている通りにすれば、同じハッシュのブロブオブジェクトを作れるでしょうか。

多分可能でしょうが 6,500 年の CPU 時間と 110 年の GPU 時間が必要だそうです。

This attack required over 9,223,372,036,854,775,808 SHA1 computations. This took the equivalent processing power as 6,500 years of single-CPU computations and 110 years of single-GPU computations.

https://shattered.it/

既存のコミットと同じハッシュのコミットを作ることは可能か

SHAttered は、prefix が同じで内容が異なるふたつのファイルを調整して、同じ SHA-1 ハッシュにするというアプローチなので、既にあるコミットと同じハッシュのコミットを作ることには使えません。

ただし、同じハッシュを持つ、正常なコミット A と不正なコミット B を作り、まず A を信頼させてから B にすり替えるというシナリオはありえます。

コミットに GPG による署名があれば信頼してもよいか

Git には、コミットに GPG で署名する機能があるので、そのコミットオブジェクトを確認します。

$ git --git-dir=.git-3 --work-tree=. add shattered.pdf
$ git --git-dir=.git-3 --work-tree=. commit -S -m 'test'

You need a passphrase to unlock the secret key for
user: "asannou (Git signing key) <asannou@example.com>"
2048-bit RSA key, ID 05CFBEA7, created 2017-02-26

[master (root-commit) e82463b] test
 1 file changed, 0 insertions(+), 0 deletions(-)
 create mode 100644 shattered.pdf
$ git --git-dir=.git-3 --work-tree=. cat-file -p e82463b
tree 8004c8a7b6fce1452539556bb4c4c91b92b5c2bc
author asannou <asannou@example.com> 1487916000 +0900
committer asannou <asannou@example.com> 1487916000 +0900
gpgsig -----BEGIN PGP SIGNATURE-----
 Comment: GPGTools - https://gpgtools.org

 iQEcBAABCgAGBQJYsq5mAAoJEMxRxTEFz76nLr8IALmPtkI9ZgvHMtKqQOcLl51l
 YOFoMu4k2fQ65DJyJFaj/HXhcdbw21rUkf1OAsxcpewFWZV2udfJUWt3LItNKbXf
 YWM/Z074VPBIdJlme7jMfdq96Q4fJwX7Lf5ypRgzOYswIj2Yd+2viuKZjwx5yujt
 pC/H4Gc08hmOhKpVNXlmDNd6IO8McBOLAGD3NvA8xsXFlSoLquVwcaq3vWTwKpT1
 DMKG18aDYr7LRjXS3417r3zn2a2rQaZl7F6gBKy9+qH+e9gfZa/wNrzRxYxZ+lJw
 tNOA/rLflylROK+k6TtISTJXRAhIUCafbD8WMLaD9KAxxR6gKO2huGFH0yxFq9I=
 =tbnx
 -----END PGP SIGNATURE-----

test

前述までのコミットオブジェクトに gpgsig という署名が付加された形です。この署名の対象はなにかというと、コミットオブジェクトの内容のみのようです。

$ git --git-dir=.git-3 --work-tree=. cat-file -p e82463b > commit-3
$ gpg --detach-sign commit-3

You need a passphrase to unlock the secret key for
user: "asannou (Git signing key) <asannou@example.com>"
2048-bit RSA key, ID 05CFBEA7, created 2017-02-26

$ gpg --verify commit-3.sig commit-3
gpg: Signature made 日  2/26 19:33:48 2017 JST using RSA key ID 05CFBEA7
gpg: Good signature from "asannou (Git signing key) <asannou@example.com>" [ultimate]

つまり、署名によって tree, author, committer とコミットメッセージの正しさしか保証されないということです。tree には SHA-1 ハッシュしか書かれていないので、同一のハッシュを持つツリーオブジェクトがあれば、それにすり替えることが可能と考えます。



したがって、署名されていたとしても、すり替えが可能な状態にあるレポジトリのファイルを信頼するのはやめましょう。