5 月末に公開される SHAttered のコードを予想して新しい PDF を作る

前回に引き続き 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 日後です。

現在公開されている情報から、このコードがどのようなものか予想し、実証しようと思います。

縦に長くなったので、最初に成果物へリンクしておきます。

さて、SHA-1 ハッシュが同じで違う画像が表示される GooglePDF 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 1PDF 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        X

COM というマーカーが頻出しますが、これはコメントを表します。コメントマーカーが現れると、そのペイロードの長さ分だけ、データが無視されるため、矢印でその範囲がスキップされることを表現しています。また、EOI の後ろにあるデータも、同様に無視されるので X とします。見ての通り、PDF 1 の COM に PDF 2 のデータが、PDF 2 の COM に PDF 1 のデータが入っているという、カドゥケウスの杖のような形をしていることが判明しました。

https://commons.wikimedia.org/wiki/File:Caduceus.svg

PDF 1PDF 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.pdfhttps://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.pdfhttps://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

最後に Gmailhttps://asannou.github.io/shatterized-1.pdfhttps://asannou.github.io/shatterized-2.pdf が検出されるかを確認しました。

本手法で作られたファイルも、Gmail に添付して送ろうとするとエラーになりました。

Google がコードを公開したら、答え合わせをします。