SHA-1をぶつけた

何の話だ
面白いのか
何が起きたの
- SHA-1がぶつかった
- インパクト重視のアイデア大賞を受賞した
やってみる
やってみた
SHA-1はあぶない

何の話だ

SHA-1ハッシュが同じになるPDFペアを作った。
それぞれのファイルをgitでcommitしてみた。
SHA-1はあぶない。

面白いのか

話が古く、みんなやっているので、あまり面白くない。

何が起きたの

SHA-1がぶつかった

Googleが上手いことSHA-1がぶつかるデータを作ったのが先週の話。

shattered.ioからPaperを適当に読みます。

まとめると、良さげなP(192バイト)を用意して、その後ろに付加するとSHA-1ハッシュが衝突する異なるデータのペア(128バイト)を見つけたということです。まだGoogleの計算資源が頑張らなくちゃいけないレベルではあるが、かなり効率よく発見できた（のかな？）らしい。

SHA-1ハッシュは512ビット(64バイト)ごとに区切られて計算されます(RFC3174)。そのため、先頭320バイト(64×5)のSHA-1ハッシュが衝突すれば、その後ろにどんな共通のSを付加してもSHA-1ハッシュは一致しますね。

強衝突耐性が破られた、ということになります。

詳しい話はこんな感じ。

インパクト重視のアイデア大賞を受賞した

「320バイトの衝突ペアを見つけた」と画像もなく（まぁあったとしてハッシュ関数の概念図くらい）伝えるニュースだったとしたら、ここまで大騒ぎにはならなかったかなと。

手元にやってくる恐怖

今回SHA-1ハッシュぶつかりイベントで面白かった点は、SHA-1ハッシュが一致する、かつ内容に意味のあるファイルのペアが示されたことでしょう。shattered.ioのAttack proofから、色が全く違うのにSHA-1ハッシュは一致しているPDFファイルを実際にダウンロードできます。このファイルは先述の通り、先頭から192〜320バイトまでの128バイトだけが異なるデータで、残りの部分は一緒のものです。

Good docとBad docが並べられ、いかにも世界の終わりを感じさせるInfographicも提供されています。こんなの、もうSHA-1なんて使えない。あぁ、暗号化は、バージョン管理システムは……とみなさん大騒ぎでした。

ただ今回の攻撃にあたっては、Bad docを作りやすいように（SHA-1ハッシュが衝突しやすいように）工夫してGood docを作っているので、どちらかと言えばBad doc (A)とBad doc (B)を作ってる感じですね。まぁ、最初から提供者が悪意を持って文書を差し替えようとしているシナリオを考えるとあぶないが、既存の全てのGood文書が今すぐ影響を受けるわけではなさそうです。

見せるテクニック

今回のSHA-1ハッシュぶつかりPDFで色が変わってる様子ですが、実はSHA-1の衝突自体が直接影響を与えてるわけではないです。関係なくはないんだけど。Good docとBad docが並んでいる絵を見ると、勘違いしがちですよね（斜め読みして勘違いしてました）。

まちがい: お互いに異なっているがSHA-1ハッシュが一致しており、かつ意味のある画像のペアが埋め込まれている。これは恐ろしい。
せいかい: ほぼ共通の画像データが埋め込まれており、前半部分で条件分岐（のようなこと）をして、前の画像を表示するか後ろの画像を表示するか決めている。

こういう感じで、JPEGのコメントの読ませ方を変えることで、同一のJPEGファイルを違う画像に見せています。SHA1のテクニックというか、JPEGのテクニック。先頭320バイトを知っていれば誰でも作れるし、Googleも90日後には「違う画像なのにSHA-1ハッシュぶつかりファイルを誰でも作れるマシーン」を配るらしいです。計算資源が叩き出した320バイトをそのまま使うのでしょう。

2つの矛盾する画像が埋め込まれた契約書PDFファイル、今すぐ。

もう作った人もいます。

じゃあ、やってみよう。

やってみる

大体資料はまとまっているので、本当にやってみるだけですね。

JPEG

JPEGはすごい。画像を圧縮できる。

JPEGファイルはマーカーとフィールド、あと画像データでできている。今回は中身は基本的にどうでもよくて、正しくマーカーを見つけ出してコメントを挿入できればよい。

マーカーはプレフィクスb"\xFF"で始まり、b"\x00"以外が続けばマーカーである。b"\xFF\x00"は画像データ中でb"\xFF"の意味を持つ。マーカー単体、またはマーカー + 長さの記述 + フィールドをセグメントという。

JPEG: Still Image Data Compression Standardを見たりしながらマーカーの情報を集めた。

フィールドがあるマーカー

以下は、固定長もしくは可変長のフィールドが続くマーカーである。フィールド長の固定可変に関わらず、マーカーの後ろに2バイトでフィールド長（フィールド長を宣言する自分自身の2バイトも含む）を宣言し、さらにフィールドを続ける。

[b"\xFF\xC0", b"\xFF\xC1", b"\xFF\xC2", b"\xFF\xC3",
 b"\xFF\xC4", b"\xFF\xC5", b"\xFF\xC6", b"\xFF\xC7",
 b"\xFF\xC9", b"\xFF\xCA", b"\xFF\xCB", b"\xFF\xCC",
 b"\xFF\xCD", b"\xFF\xCE", b"\xFF\xCF",
 b"\xFF\xDA", b"\xFF\xDB", b"\xFF\xDC", b"\xFF\xDD",
 b"\xFF\xDE", b"\xFF\xDF",
 b"\xFF\xE0", b"\xFF\xE1", b"\xFF\xE2", b"\xFF\xE3",
 b"\xFF\xE4", b"\xFF\xE5", b"\xFF\xE6", b"\xFF\xE7",
 b"\xFF\xE8", b"\xFF\xE9", b"\xFF\xEA", b"\xFF\xEB",
 b"\xFF\xEC", b"\xFF\xED", b"\xFF\xEE", b"\xFF\xEF",
 b"\xFF\xFE", ]

スキャン開始(SOS)マーカー(b"\xFF\xDA")は特別なマーカーで、セグメントの後ろから画像データが始まる。画像データはフィールド長に含まれず、フィールドがあるマーカーやイメージ終了(EOI)マーカー(b"\xFF\xD9")にぶつかるまで続く。

フィールドがないマーカー

以下は、それ自身のみで記述が完結するマーカーである。

[b"\xFF\xD0", b"\xFF\xD1", b"\xFF\xD2", b"\xFF\xD3",
 b"\xFF\xD4", b"\xFF\xD5", b"\xFF\xD6", b"\xFF\xD7",
 b"\xFF\xD8", b"\xFF\xD9",
 b"\xFF\x01", b"\xFF\x4F", b"\xFF\x51", b"\xFF\x52",
 b"\xFF\x53", b"\xFF\x55", b"\xFF\x57", b"\xFF\x58",
 b"\xFF\x5C", b"\xFF\x5D", b"\xFF\x5E", b"\xFF\x5F",
 b"\xFF\x60", b"\xFF\x61", b"\xFF\x63", b"\xFF\x64",
 b"\xFF\x90", b"\xFF\x91", b"\xFF\x92", b"\xFF\x93", ]

イメージ開始(SOI)マーカー(b"\xFF\xD8")は特別なマーカーで、一度だけJPEGデータの開始を宣言する。

EOIマーカーも特別なマーカーで、一度だけJPEGデータの終了を宣言する。EOIマーカーがあることと、それがファイル終端であるかどうかは関係ない。画像を2枚埋め込むとして、1枚目の終端に使えそうだ。

フィールドがないマーカーが画像データ中に出てきた場合は、EOIでなければ画像データの一部として読み飛ばしてよい。

PDF

PDFはすごい。なんてったってポータブル。

PDFファイルはヘッダとかオブジェクトの宣言が大体テキストで乗っかっていて、間にバイナリがstreamとして入っている。shattered.ioで提供されているPDFファイルは、自由に変更できる後ろの部分に画像に関するメタデータが載っており、なんとも改造しやすい。

先頭はこんな感じ。

%PDF-1.3
%


1 0 obj
<</Width 2 0 R/Height 3 0 R/Type 4 0 R/Subtype 5 0 R/Filter 6 0 R/ColorSpace 7 0 R/Length 8 0 R/BitsPerComponent 8>>
stream

stream + 改行の後ろからJPEGのバイナリを書いていき、改行 + endstreamで終了する。そこからは先頭から参照されている画像サイズやら何やらのつじつまを合わせていけばよい。

endstream
endobj

2 0 obj
{width}
endobj

3 0 obj
{height}
endobj

4 0 obj
/XObject
endobj

5 0 obj
/Image
endobj

6 0 obj
/DCTDecode
endobj

7 0 obj
/DeviceRGB
endobj

8 0 obj
{length}
endobj

...(*snip*)...

くふうしたPDFをつくる

以下のように2枚のJPEG画像を組み合わせて2つのPDFファイル(A, B)を作る。

先頭320バイトを見る。PDFのヘッダ、JPEGのSOIセグメント、JPEGのコメントが記述されている。そのままAとBに書き込む。
コメントセグメントを挿入しながら1枚目の画像を書き込む。詳細は以下。
2枚目の画像を書き込む。ただし、SOIはもう宣言されているので飛ばす。
画像に関するPDF上のメタデータを書き込む。

くわしく: コメントセグメントを挿入する

コメントをくふうして挿入するために、フィールドがコメントマーカーになっているb"\xFF\xFE\x00\x06\xFF\xFE\x..\x.."という全長8バイトの「くふうコメント」を考える（上のツイートにおけるinterleaveである）。

このセグメントを先頭から読めば、単にフィールド長6バイトのコメントがあるように見える。しかし、これを4バイト飛ばして読んだとすれば、b"\xFF\FE"のコメントマーカーと共にb"\x..\x.."をフィールド長として読んでしまう。b"\x..\x.."にうまく値を設定することで、以降のセグメントをいくつかスキップし、さらに次のくふうコメントに飛ばして同様の動作をさせることができる。

今回は、先頭320バイトに含まれるコメントセグメントのフィールド長の違いから、くふうコメントを発動させる。

242バイトのパディングを挿入する。これは先頭320バイトから続くコメントフィールドの一部。
（Aのコメントセグメントが終了した）b"\xFF\xFE\x00\x0E"と長さ14バイトの新たなコメントセグメントを宣言し、8バイトのパディングを挿入する。残りは4バイトである。
（Bのコメントセグメントが終了した）しかし、AはここからさらにBより4バイト余分に読み飛ばすため、くふうコメントが活きてくる。
1枚目の画像について、2バイトで表現できる範囲までセグメントを読む。ただし、SOIはもう宣言されているので飛ばす。
読んだセグメント群（次のくふうコメントがあればさらに+4バイト）を読み飛ばすフィールド長を宣言したくふうコメントを挿入し、セグメント群をそのまま書き込む。
4と5を1枚目のEOIにぶつかるまで繰り返す。

2の直後に置かれたくふうコメントに引っかかると、1枚目のEOI直後までは全てコメントとして扱われることになる。逆にくふうコメントに引っかからないと、1枚目のEOIにぶつかってJPEGデータが終了する。好都合。

今回使えるJPEGペア

1枚目は、あまり大きくないもの。画像データの各パートが65529バイトを超えてはいけない(2 + 65529 + 4 = 65535)。
解像度が同じもの。これはPDFにメタデータを書くときの都合。
あと、~~ドヤ顔するためにわざわざ~~特殊なJPEGを引っ張ってくると上手く生成できないかも。分からん。

もっとくふう

1枚目の画像はプログレッシブJPEGに変換した。画像データが分割されて使えるJPEGになる。
どんな長さの画像でも画像データをガチャガチャ分割できたりしないのかな。

やってみた

Googleに倣って、青の大仏(good.jpg)と赤の大仏(bad.jpg)を持ってきた。

青の大仏（左）と赤の大仏（右）の比較写真

元の大きさの: good.jpg, bad.jpg

成果物

ここから、a.pdfとb.pdfを作った。

a.pdfはくふうコメントに引っかかり、1枚目のgood.jpgをスキップし、2枚目のbad.jpgだけを読んだ。一方、b.pdfはくふうコメントに引っかからず、1枚目のgood.jpgを読んで終了した。

SHA-1ハッシュ

SHA-1ハッシュはぶつかった。

$ sha1sum a.pdf b.pdf
d2b057375f548eb2c265ab8149223e317fe0349d  a.pdf
d2b057375f548eb2c265ab8149223e317fe0349d  b.pdf

git commit

それぞれを同名のファイルとしcommitした結果はこっち。

a.pdf: sha1_pdf_a(ce729eb...)
b.pdf: sha1_pdf_b(c487df3...)

とりあえずコミットした時刻が違うので、コミットハッシュは同じにならなかった。

まぁ、blobオブジェクトを作る時に余計なモノを付け足す(b"blob 135042\x00"、135042はファイルサイズ)ので、単純に同じSHA-1ハッシュを持つ異なるファイルを同時刻にコミットしても、違うコミットハッシュになる。残念。

残念か？

blob...の部分も含めた衝突が見つかればいいけど、ファイルの長さが含まれているから今回ほど簡単には流用できない。フーム。

こっちはa.pdfの場合

$ git cat-file -p ce729eba52d6304b80f135bf7d87b2c75e388b3a
tree 34c35e681b372dd25157ab713543ca4ba32e9ad9
parent 0febdb7da92feca1b38aa80ea2310b94b61cb450
author Amane Katagiri <amane@ama.ne.jp> 1488604206 +0900
committer Amane Katagiri <amane@ama.ne.jp> 1488604206 +0900

Add pdf file
$ git cat-file -p 34c35e681b372dd25157ab713543ca4ba32e9ad9
100644 blob f80dcac6ddb00d75af74e039e4eaa9bd4ea50b97    README
100644 blob b6feab8e4b00ec11b0b0bf55c51345c6e5690790    collision.pdf
$ cat .git/objects/b6/feab8e4b00ec11b0b0bf55c51345c6e5690790 | python -c 'print(__import__("zlib").decompress(__import__("sys").stdin.buffer.read())[:100])'
b'blob 135042\x00%PDF-1.3\n%\xe2\xe3\xcf\xd3\n\n\n1 0 obj\n<</Width 2 0 R/Height 3 0 R/Type 4 0 R/Subtype 5 0 R/Filter 6 0'

こっちがb.pdfの場合

$ git cat-file -p c487df367e1fd5ccbe55fde68a705841dd60d3cb
tree d9aa567f36547412737b5c89c1c86e57f9fa04eb
parent 0febdb7da92feca1b38aa80ea2310b94b61cb450
author Amane Katagiri <amane@ama.ne.jp> 1488604238 +0900
committer Amane Katagiri <amane@ama.ne.jp> 1488604238 +0900

Add pdf file
$ git cat-file -p d9aa567f36547412737b5c89c1c86e57f9fa04eb
100644 blob f80dcac6ddb00d75af74e039e4eaa9bd4ea50b97    README
100644 blob 9f6e3dcdb8f5f24016fd451e34a59e986fd9e542    collision.pdf
$ cat .git/objects/9f/6e3dcdb8f5f24016fd451e34a59e986fd9e542 | python -c 'print(__import__("zlib").decompress(__import__("sys").stdin.buffer.read())[:100])'
b'blob 135042\x00%PDF-1.3\n%\xe2\xe3\xcf\xd3\n\n\n1 0 obj\n<</Width 2 0 R/Height 3 0 R/Type 4 0 R/Subtype 5 0 R/Filter 6 0'

blobにb"blob 135042\x00"が付いてるのが分かる。

SHA-1はあぶない

みんなは……SHA-1って、知ってるかな？　これから先……SHA-1をつかわないようにしようね。