宣伝
コミックマーケットC93でZIPの本を頒布します。
コミックマーケット #C93 1日目（金）東キ29bで、圧縮フォーマットZIPの仕様と暗号に対する攻撃法を解説した「ZIP、完全に理解した」を頒布します。本の素数ページをサンプルとして公開しています。 #understandziphttps://t.co/fIzXKK8o8h pic.twitter.com/VReHvvsW3x
— superflip@1日目（金）東キ29b (@sprflp) 2017年12月18日
ZIPの暗号
ZIPの仕様書に記載されている「Traditional PKWARE Encryption」（以下、ZIPの暗号）が良く使われる。
仕様書にも書かれているように、この暗号は脆弱。
This form of encryption is considered weak by today's standards and its use is recommended only for situations with low security needs or for compatibility with older .ZIP applications.
ZIPにもAESなどのより強力な暗号化があるし、PGPもopensslもあるのだから、ZIPの暗号を使わずに済むのならば使わない方が良い。しかし、ZIPの暗号は復号方法を説明しなくてもWindowsのエクスプローラーでそのまま復号できるという大きなメリットがある。ZIPのより強力な暗号はPKWARE社が特許を持っていて、エクスプローラーには復号処理が実装されていない。いきなり相手に暗号化したファイルを送って、「このスクリプトを実行してくれ」とか「このプログラムをインストールしてくれ」とか「自己解凍形式だからそのまま実行してくれ」というのはなかなか難しい。
ということで、ZIPの暗号をできるだけ攻撃に耐性を持つように実装した。
ZIPの暗号に対する攻撃
BIHAM, Eli; KOCHER, Paul C. A known plaintext attack on the PKZIP stream cipher. In: International Workshop on Fast Software Encryption. Springer, Berlin, Heidelberg, 1994. p. 144-153.
に攻撃法が書かれている。圧縮後の暗号文と平文の組が12バイトあれば、パスワード（を処理して得られる内部状態）が逆算できて、このファイルの残りの部分や、同じパスワードで暗号化された他のファイルが復号できるというもの。
既知平文攻撃対策
ZIPの暗号化は圧縮の後に行われる。元のファイルが既知であっても、圧縮後の内容が分からなければ、既知平文攻撃は受けない。他の多くの圧縮法と同様に、ZIPで使われるDeflate圧縮も、圧縮をする側には自由度がある。復号すると同じファイルになる、異なる圧縮データが作れる。そこでデータサイズを小さくすることは捨て置いて、なるべくランダムな要素を入れながら圧縮することにした。
Deflate圧縮では、まずは元データを「xという文字」もしくは「ここからy文字はz文字前と同じ」という符号の列に変換する。データサイズを小さくするため、xとyはひとまとめにして扱われる。256未満ならばx、257以上ならばy。その後、この符号の出現頻度を調べて、ハフマン符号で圧縮する。最初の処理によって同じパターンが繰り返し出現するデータが圧縮され、後の処理で文字の出現頻度に偏りがあるデータが圧縮される。
文字とハフマン符号の対応表であるハフマン符号表をそのまま圧縮データに含めるとサイズが大きくなってしまうので、各文字のビット長の列（をさらに圧縮したもの）が送られる。圧縮する側と解凍する側が仕様書に定められた方法でビット長からハフマン符号表を構築することで、同じハフマン符号表を共有できる。
例えば、文字とビット長の対応が
| 文字 | ビット長 |
|---|---|
0 |
2 |
1 |
3 |
2 |
4 |
3 |
2 |
4 |
4 |
5 |
3 |
6 |
3 |
となっているとき、仕様にしたがって得られるハフマン符号表は次のようになる。
| 文字 | ハフマン符号 |
|---|---|
0 |
00 |
1 |
100 |
2 |
1110 |
3 |
01 |
4 |
1111 |
5 |
101 |
6 |
110 |
圧縮を目的にするならば、出現頻度の高い文字には短いビット長を、低い文字には長いビット長を割り当てる。ここで、出現頻度を無視してビット長をランダムに割り振るようにした。例えば、ビット長を次のように割り当てると、ハフマン符号表が変化して、元のハフマン符号表とは対応する符号がある程度異なるようになる。
| 文字 | ビット長 |
|---|---|
0 |
4 |
1 |
2 |
2 |
4 |
3 |
3 |
4 |
3 |
5 |
3 |
6 |
2 |
| 文字 | ハフマン符号 |
|---|---|
0 |
1110 |
1 |
00 |
2 |
1111 |
3 |
100 |
4 |
101 |
5 |
110 |
6 |
01 |
ビット長を送信する部分もランダムになるし、ハフマン符号表で符号化したデータ本体もランダムになる。
Deflate圧縮のヘッダ部分は次のようになっている。
| 項目 | ビット長 | 内容 |
|---|---|---|
| BFINAL | 1 | 1ならば最後のブロック |
| BTYPE | 2 | 10ならばカスタムハフマン符号表 |
| HLIT | 5 | リテラル符号の個数（上述のxとy） |
| HDIST | 5 | 距離符号の個数（上述のz） |
| HCLEN | 4 | ↑の符号の圧縮に使われる符号の個数 |
この後に、符号の圧縮に使われる符号のビット長と、リテラル符号や距離符号のビット長、データ本体が続く。この部分も推測できないようにするために、各符号の個数をある程度ランダムにした。BFINALとBTYPEは諦めて固定している。
また、「xという文字」や「ここからy文字はz文字前と同じ」に変換する部分では、普通は可能ならばxよりはyを、さらにyがなるべく大きくなるように選択するけれど、ここで何を選ぶかもランダムにした。これによって、aaaaaa…のような元データに対して、aにあたるハフマン符号を総当たりするという攻撃が防げる。
1個弱点があって、abaabba…のように文字の種類数が少なく、同じパターンが現れないデータだと、aとbにあたるハフマン符号を総当たりするということが可能になってしまう。
これによって、同じファイルを圧縮しても圧縮するたびにランダムなデータ得られる。
00000000 50 4b 03 04 14 00 00 08 08 00 00 00 00 00 84 21 |PK.............!|
00000010 35 af 1e 43 0b 00 df 51 09 00 0a 00 00 00 73 61 |5..C...Q......sa|
00000020 6d 70 6c 65 2e 70 64 66 9d b3 5d 76 6c bb 6e 2c |mple.pdf..]vl.n,|
00000030 ed b5 eb 58 f7 6a 95 af ed 3d ef 2d df 3b 6b ae |...X.j...=.-.;k.|
00000040 b3 e7 b6 7c ee da 47 7b ce 2b 1d ed 3a b6 b4 34 |...|..G{.+..:..4|
00000050 ab ee f5 a9 eb 3d f7 f1 5a f7 d8 55 25 5d df 5a |.....=..Z..U%].Z|
00000060 e7 1e 95 67 a9 ee 9a 3a 5b ab 4e cd 5a 67 d5 3e |...g...:[.N.Zg.>|
00000070 7b af eb ad 5d fb 94 e7 92 e7 9d c7 7b df 7b 8f |{...].......{.{.|
00000080 5d 7b ba ae cf 9d 73 9d 63 f9 ec 3b 97 f6 bd 67 |]{....s.c..;...g|
00000090 ce ba ba 73 1d 59 b5 ae 8f cf ba f3 ae 5d 5e cb |...s.Y.......]^.|
000000a0 f2 dc eb 9e 79 bc 55 f3 ce 69 79 7a 6b d7 be 67 |....y.U..iyzk..g|
000000b0 dd bd cb 6b 6a 6a d7 ba 77 d9 73 d7 da 5a c7 6b |...kjj..w.s..Z.k|
000000c0 96 97 ce 5d d7 3a 13 c4 64 ce c9 cc 9c 98 e0 9c |...].:..d.......|
000000d0 7f 3f f1 33 f8 3f 18 1b f9 a9 bf f5 f7 ed 3f fd |.?.3.?........?.|
000000e0 c3 ff f1 b7 0e fe d4 d8 4f 3e fc 91 87 a9 d9 f9 |........O>......|
000000f0 bf 15 8d 8e e2 4f e6 4b 27 3e 3b 8a e7 b3 a5 13 |.....O.K'>;.....|
00000000 50 4b 03 04 14 00 00 08 08 00 00 00 00 00 84 21 |PK.............!|
00000010 35 af bc 37 0b 00 df 51 09 00 0a 00 00 00 73 61 |5..7...Q......sa|
00000020 6d 70 6c 65 2e 70 64 66 85 da e9 ae ee 4c b7 5c |mple.pdf.....L.\|
00000030 39 9f b5 cf d1 7e 97 e5 f3 ac f5 9d 67 2f eb 95 |9....~......g/..|
00000040 fc e9 79 df f5 9d 67 bd 4b d2 7e 5e 2f af ef fb |..y...g.K.~^/...|
00000050 f6 f6 de df fb bc 5b 8f de bd 7c f4 ac 73 be 4f |......[...|..s.O|
00000060 3a 47 af b7 b5 9f f7 39 d6 d1 f7 6d 1f af 67 f9 |:G.....9...m..g.|
00000070 7d 1f ef f3 bc f6 f9 ce 39 ef fa 9e b5 fc 7d 8f |}.......9.....}.|
00000080 d6 f7 3c e7 59 eb ec a5 b3 f7 7a 97 f6 b7 d7 7a |..<.Y.....z....z|
00000090 1e 9f e7 59 e7 d9 ef 79 3e 9f ad 7d de ef db c7 |...Y...y>..}....|
000000a0 e7 bc df e7 7d ce 67 9d a5 e7 fd 8e df ef 7d 6c |....}.g.......}l|
000000b0 9d 57 cf f1 7a ce fb 6a 7f e7 93 fc 7a 69 9f 7d |.W..z..j....zi.}|
000000c0 ce f9 d6 f3 7e 67 eb 3d df fe ce f3 bd f6 ab b3 |....~g.=........|
000000d0 bc cf f2 7e df fd 3c a1 9c 6b 3e 6b ad 48 45 e4 |...~..<..k>k.HE.|
000000e0 93 6b 3e 7a a6 9e 35 f6 93 53 3f f6 e8 e4 3f 3e |.k>z..5..S?...?>|
000000f0 fa c3 63 b6 f3 df 5f fb e1 bf 7f 74 f2 c8 c3 ff |..c..._....t....|
懸賞問題
このツールを使って、31,337円分のAmazonギフト券を暗号化した。攻撃法を思いついたら、破ってAmazonギフト券を手に入れてほしい。2018年12月31日まで破られなかったら、もったいないので私が自分で使う。
sample.pdfが既知平文攻撃用のファイルで元のファイルはここにある。コミケで頒布する本のサンプル。amazon.txtがAmazonギフト券。CRCからの推測を防ぐためにランダムな英数字を加えている。パスワードは英数字32文字なので、パスワードの総当たりは無理だと思う。Windows 10上のGoogle Chromeで実行した。乱数の生成にはwindow.crypto.getRandomValuesを使用している。暗号用の乱数なので乱数の推測も無理なはず。
破ることができたら教えてください。
2019年1月9日追記
Amazonギフト券を回収した。@aki33524さんが頑張ってくれていた（ありがとうございます！）けど、破られることは無かった。このツールで保護されているものが3万円くらいまでなら安全そう。ちなみに、パスワードは 6nI6OMtXIyLub7rwdnyEoGPf6rV2xVbo でした。