前回に引き続き https://shattered.it/ の件です。
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
Google 曰く「誰にでも、いくつかの前提条件を満たすふたつの異なる画像から、同じ SHA-1 ハッシュの PDF のペアが作成できるコードをリリースする」とのことです。ただし、脆弱性公開ポリシーに従い、リリースは発表から 90 日後です。
現在公開されている情報から、このコードがどのようなものか予想し、実証しようと思います。
縦に長くなったので、最初に成果物へリンクしておきます。
- https://asannou.github.io/d.hatena.ne.jp-asannou-20170226-1.pdf
- https://asannou.github.io/d.hatena.ne.jp-asannou-20170226-2.pdf
さて、SHA-1 ハッシュが同じで違う画像が表示される Google の PDF 1, PDF 2 にはどのような技巧が用いられているでしょうか。
%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 [...] endstream endobj 2 0 obj 1024 endobj 3 0 obj 740 endobj 4 0 obj /XObject endobj 5 0 obj /Image endobj 6 0 obj /DCTDecode endobj 7 0 obj /DeviceRGB endobj 8 0 obj 421385 endobj [...] %%EOF
PDF ファイルなので、一般的な PDF の構造があります。ここに特殊な箇所は見つかりません。この構造部分は PDF 1 と PDF 2 で完全に一致しています。
"1 0 obj" における stream [...] endstream 間のデータが、幅 1024 高さ 740 の Image として DCTDecode されて（つまり JPEG 画像）表示されます。強いて不自然な点をあげると、"/Width 1024/Height 740" と書かず "/Width 2 0 R/Height 3 0 R" のように "2 0 obj" と "3 0 obj" への参照となっていることです。これは後述する理由により、endstream より後方にあるデータは任意に書き換えが可能なため、画像のサイズを変更できるようにする工夫と窺えます。
stream 内の JPEG データを詳しく見る前に、通常の JPEG の構造を簡単に理解しておきましょう。
JPEG は、複数のセグメントで構成されています。セグメントは、マーカーとペイロードからできていて、マーカーがセグメントがどのような種類の情報かを表します。重要なマーカーは以下のものくらいです。
- SOI（イメージ開始）
- SOF（フレーム開始）
- DHT（ハフマンテーブル定義）
- DQT（量子化テーブル定義）
- SOS（画像データ開始）
- EOI（イメージ終了）
例えば https://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Lichtenstein.jpg/256px-Lichtenstein.jpg の構造は下記のとおりです。
SOI 0000 APP0 0010 DQT 0043 DQT 0043 SOF0 0011 DHT 001c DHT 0040 DHT 001b DHT 0030 SOS 000c SCAN 4983 EOI 0000
マーカーの後ろにある数字は、ペイロードのバイト長です。SCAN はマーカーではなく画像データです。詳細は JPEG - Wikipedia を参照してください。
それでは、件の PDF に含まれる JPEG の構造を分析していきます。
PDF 1 PDF 2
SOI 0000 SOI 0000
COM 0024 COM 0024
V V
COM 0173 COM 017f <--- (A)
[ | ] [ | ] <--- (B) collision blocks
V |
COM 00fc | <--- (C)
| V
| APP0 0010 <--- (D)
| DQT 0043
| DQT 0043
| SOF2 0011
| DHT 001e
| DHT 001d
V COM 0006
COM 27f4 V
| SOS 000c
| SCAN 27a6
| DHT 0038
V COM 0006
COM 218d V
| SOS 0008
| SCAN 210b
| DHT 0070
V COM 0006
COM 9f9a V
| SOS 0008
| SCAN 9f1e
| DHT 006a
V COM 0006
COM 659a V
| SOS 0008
| SCAN 6519
| DHT 006f
V COM 0006
COM ae2e V
| SOS 0008
| SCAN adee
| DHT 002e
V COM 0006
COM 36d2 V
| SOS 0008
| SCAN 36c2
V COM 0006
COM 11b5 V
| SOS 000c
| SCAN 1172
| DHT 002d
V COM 0006
COM 2c5b V
| SOS 0008
| SCAN 2c1b
| DHT 002e
V COM 0006
COM 2dce V
| SOS 0008
| SCAN 2d8e
| DHT 002e
V COM 0006
COM 37d2 V
| SOS 0008
| SCAN 37c0
| EOI 0000
V X
APP0 0010 X
APP1 0040 X
APP13 0038 X
SOF0 0011 X
DHT 001f X
DHT 00b5 X
DHT 001f X
DHT 00b5 X
DQT 0043 X
DQT 0043 X
DRI 0004 X
SOS 000c X
SCAN 39104 X
EOI 0000 XCOM というマーカーが頻出しますが、これはコメントを表します。コメントマーカーが現れると、そのペイロードの長さ分だけ、データが無視されるため、矢印でその範囲がスキップされることを表現しています。また、EOI の後ろにあるデータも、同様に無視されるので X とします。見ての通り、PDF 1 の COM に PDF 2 のデータが、PDF 2 の COM に PDF 1 のデータが入っているという、カドゥケウスの杖のような形をしていることが判明しました。
PDF 1 と PDF 2 で異なる部分は (A) と (B) のみで、残りは完全に一致しています。(A) において、コメントとみなす長さを 0x0173 か 0x017f かに変えることで、続きが (C) か (D) かに分かれ、異なる画像が表示されるという原理です。
(A) でコメント長を示す数値が異なるので、当然 SHA-1 ハッシュも違う値が計算されます。ですが、その直後の SHAttered による (B) collision blocks でそれが解消され、再びハッシュが等しくなります。そして (B) 以降は、どのようなデータを追加しても、ふたつのファイルの SHA-1 ハッシュは同一のままです。"1 0 obj" の stream が、後方の obj を参照していたのは、こういった理由からでした。
結論として、本稿の目的であるコードとは、(C) 以降にあるようなデータと同様の構造を持つ JPEG を生成するコードと言えるでしょう。
ということで、そのようなコードを（Perl で）実装し、それを使って作成した PDF のペアが https://asannou.github.io/shatterized-1.pdf と https://asannou.github.io/shatterized-2.pdf です。
無論、ハッシュが一致しています。
$ shasum shatterized-1.pdf shatterized-2.pdf 5135c8373be5ceb5763406b307cd17d179fafbe2 shatterized-1.pdf 5135c8373be5ceb5763406b307cd17d179fafbe2 shatterized-2.pdf
また、画像のみの PDF だけでなく https://asannou.github.io/d.hatena.ne.jp-asannou-20170226-1.pdf と https://asannou.github.io/d.hatena.ne.jp-asannou-20170226-2.pdf のように、一部の画像（ブックマーク数）が改ざんされているものも作ることができます。
$ shasum d.hatena.ne.jp-asannou-20170226-1.pdf d.hatena.ne.jp-asannou-20170226-2.pdf 6a2cd0570bc6d05cd4777a17925a2095e928582d d.hatena.ne.jp-asannou-20170226-1.pdf 6a2cd0570bc6d05cd4777a17925a2095e928582d d.hatena.ne.jp-asannou-20170226-2.pdf
残念ながら、この手法には欠点があります。それは COM のペイロードの長さの最大が 0xffff であるため、それより長いデータが存在すると、収まりきらないことです。例として https://upload.wikimedia.org/wikipedia/commons/e/e8/Lichtenstein.jpg の構造を示します。
SOI 0000 APP0 0010 DQT 0043 DQT 0043 SOF0 0011 DHT 001c DHT 004a DHT 001a DHT 0032 SOS 000c SCAN 79009 EOI 0000
SOS マーカーの後の画像データの長さが 0x79009 もあって、コメントに収まりません。おそらく、冒頭の「いくつかの前提条件を満たすふたつの異なる画像」というのは、このことを示唆しているのではないかと推測します。
しかしまだ、画像データを分割して、段階的に表示するプログレッシブ JPEG に変換する方法が残っています。やってみましょう。
$ jpegtran -progressive Lichtenstein.jpg > Lichtenstein_p.jpg
SOI 0000 APP0 0010 DQT 0043 DQT 0043 SOF2 0011 DHT 001b DHT 0019 SOS 000c SCAN c486 DHT 0034 SOS 0008 SCAN f1f2 DHT 002c SOS 0008 SCAN 1203 DHT 002d SOS 0008 SCAN 2110 DHT 0037 SOS 0008 SCAN 7195 DHT 002c SOS 0008 SCAN 1729d SOS 000c SCAN 3718 DHT 0027 SOS 0008 SCAN 358d DHT 0029 SOS 0008 SCAN 4499 DHT 002a SOS 0008 SCAN 2c3fb EOI 0000
確かに 10 分割されましたが、まだ 0xffff 以上の画像データが残っています。スキャンの方法をテキストファイルで詳細に指定し、分割数を増やすことができるので、それを試します。テキストファイルの仕様は https://github.com/mozilla/mozjpeg/blob/master/wizard.txt を参照してください。
$ cat <<EOD > scans.txt 0: 0-0, 0, 0; 1: 0-0, 0, 0; 2: 0-0, 0, 0; 0: 1-1, 0, 0; 0: 2-2, 0, 0; 0: 3-3, 0, 0; 0: 4-5, 0, 0; 1: 1-63, 0, 0; 2: 1-63, 0, 0; 0: 6-7, 0, 0; 0: 8-9, 0, 0; 0: 10-12, 0, 0; 0: 13-17, 0, 0; 0: 18-63, 0, 0; EOD $ jpegtran -scans scans.txt Lichtenstein.jpg > Lichtenstein_pp.jpg
SOI 0000 APP0 0010 DQT 0043 DQT 0043 SOF2 0011 DHT 001c SOS 0008 SCAN b243 DHT 001a SOS 0008 SCAN 1ffa DHT 0019 SOS 0008 SCAN 1b35 DHT 0021 SOS 0008 SCAN 87b7 DHT 0020 SOS 0008 SCAN 8b6f DHT 0021 SOS 0008 SCAN 5ac4 DHT 0029 SOS 0008 SCAN cf74 DHT 0038 SOS 0008 SCAN 6474 DHT 0032 SOS 0008 SCAN 4647 DHT 0027 SOS 0008 SCAN 9426 DHT 0026 SOS 0008 SCAN 9464 DHT 002a SOS 0008 SCAN a9a7 DHT 002e SOS 0008 SCAN bf73 DHT 003b SOS 0008 SCAN dcd2 EOI 0000
無事成功しました。それでも画像データが巨大な場合は、最大個数に分割しても収まらないことがあると思います。その時は、画像の品質を下げる等を検討する必要があります。
In order to prevent this attack from active use, we’ve added protections for Gmail and GSuite users that detects our PDF collision technique.
https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html
最後に Gmail で https://asannou.github.io/shatterized-1.pdf と https://asannou.github.io/shatterized-2.pdf が検出されるかを確認しました。
本手法で作られたファイルも、Gmail に添付して送ろうとするとエラーになりました。
Google がコードを公開したら、答え合わせをします。
