反転したのはどのbit? - SECCON CTF福岡大会 問題レポート

2012年2月18日, 19日に開催されたSECCON CTF福岡大会のレポートを、実行委員の園田さんが@ITで執筆されていました。僕は残念ながら参加する事が出来なかったのですが、大会で出題された問題の内の一題がレポート中で引用されていたので、解いてみました。
以下、そのレポート(とオマケ)です。ネタバレを含むので、これから解こうと思っている人は注意してください。


問題は

「以下のファイルダンプは宇宙からの中性子線で1bitのデータが反転したものである。(略)1bitだけ異なる正常なデータファイルを復元し、秘密の鍵を答えよ。」

というもの。実行委員長の竹迫さん作成の問題です。

まずは、ダンプのテキストを素のバイナリに戻します。テキストを corrupted.txt との名で保存し、毎行頭のアドレスを削除した上で、

cat corrupted.txt | xxd -r -p > corrupted.bin

とすると、素のバイナリがcorrupted.binとして保存されます。
次に、corrupted.binがどういうファイルなのか調べます。fileコマンドに入力したところ、出力は以下の通りでした。

corrupted.bin: gzip compressed data, was "z.txt", from Unix, last modified: Tue Feb 14 00:28:39 2012, max compression

これにより、このファイルはどうやらgzipで圧縮されたものらしいという事が分かったので、拡張子をgzに変えてgzip -dで解凍を試みたところ、

 incomplete distance tree

gzip: corrupted.gz: invalid compressed data--format violated

となりました。確かにこのファイルは破損しているようです。
corrupted.gzの大きさは357bytes = 2856bitsで、反転したビットは1ビットのみである事が分かっているので、総当りで1bitずつ反転させて解凍を試みる方法が現実的に実行可能であると推測できます。後は、corrupted.gzを読み込んで全ビットを1つずつ反転させながら保存していくプログラムを書き、保存された2856個のgzファイル全てに対しシェルスクリプトでgzip -dを試みて、そのうちの1つ、ファイル先頭から383bit目を反転させたファイルの解凍に成功しました。その中身がまさに「秘密の鍵」だったのですが、それは敢えてここには書きません。是非自分でやってみましょう。

オマケ

とりあえず上の方法で解くことは出来たものの、この流れではおそらく定石であろう総当たりだけをして終わるのは、もったいない。
というわけで、エラーメッセージを手がかりにした総当りによらない反転箇所の絞り込みを試みました。以下詳細。

出力されたエラーメッセージを眺めてみると

incomplete distance tree

という文がいかにも反転箇所の手がかりになりそうです。"distance tree"が何処にあるのか突き止めるため、まずはgzipのファイルフォーマットについて調べます。"gzip ヘッダ"等でぐぐって、以下のページを発見しました。
[Studying HTTP] gzip
gzip format
上のページの内容とcorrupted.gzのバイナリを突き合わせた所、corrupted.gzの中身は以下のようになっている事が分かりました。

+-----------+-------------+---------+---------+
|header(16B)|payload(333B)|CRC32(4B)|ISIZE(4B)|
+-----------+-------------+---------+---------+

括弧内の数字はその部分のバイト数を表しています。ヘッダにも末尾のデータにも"distance tree"らしき物が無いので、どうやらペイロードが怪しいです。ヘッダによれば、このペイロードにはDeflateで圧縮されたデータが格納されているとの事なので、今度はDeflateについて調べます。ぐぐって出てきた以下のページを参考に考えてみることにします。
デフレート圧縮(LZ77圧縮)処理の概要 - ウェブで用いられる画像形式。
RFC 1951 DEFLATE Compressed Data Format Specification version 1.3 日本語訳 - futomi's CGI Cafe
Notes on Deflate in PNG files
上のページ曰く、Deflateのバイナリの構造はこんな感じ。

+----------+--------+---------+---------+
|header(3b)|HLIT(5b)|HDIST(5b)|HCLEN(4b)| ->
+----------+--------+---------+---------+
   +-----------------------------+-------------------+--------------------+
-> |len for len((HCLEN + 4) * 3b)|len for literal(?b)|len for distance(?b)| ->
   +-----------------------------+-------------------+--------------------+
   +---------------+---+
-> |compressed data|EOD|
   +---------------+---+

今度は、括弧内の数字はビット数を表しています。各部分の名称は適当に略してありますが、ここで言う"len for distance"がエラーメッセージの"distance tree"を指しているようです。
反転していると思しき部分はこれで判明しましたが、問題はその範囲です。上のページや図を見るとわかるように、Deflateのバイナリは符号化されたビット単位の可変長データが複数組み合わさって構成されており、"len for distance"の範囲を求めるのは容易ではありません。もしかするとこの世の何処かにはDeflateのバイナリをそのまま読んで解読できるイカれたよく訓練されたバイナリアンが居るのかもしれませんが、僕には無理です。
そこで、gzipコマンドのソースコードを弄って、解凍中に当該部分の範囲を出力させてみる事にしました。gzipソースコード(gzip-1.4.tar.gz)を落としてきて、まずは元々のエラーメッセージでgrepします。inflate.cのinflate_dynamic関数中でエラーとなっているようです。エラー箇所の前後や定義されているマクロを調べると、inflate_dynamic関数中で、DUMPBITSというマクロを用いて、"HLIT"から"len for distance"までを読み込んでいる事が分かりました。そこで、

<       DUMPBITS(j)
---
>       DUMPBITS(j);printf("%d,",j);

という風にinflate_dynamic関数中のDUMPBITSマクロを置換し、読み込みが発生する度にそのビット長を出力させる事にしました。また、"len for literal"と"len for distance"が同一while文中(/* read in literal and distance code lengths */)でまとめて読み込まれているようなので、while文先頭に

if (i == nl) printf("D,");

というコードを挟み、"len for distance"部分に入ったら"D"という文字が出力されるようにしました。以上の改造を施したgzipでcorrupted.gzの解凍を試みると

5,5,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,3,3,3,3,3,4,7,4,4,3,2,4,7,4,7,2,4,3,3,3,3,3,2,2,2,2,4,2,6,4,4,2,4,2,2,2,2,2,3,3,6,D,2,4,3,3,3,2,3,2,6,2,4,2,6,2,2,3,2,3,2,2,2,

という文字列が出力されました。後は、この文字列を表計算ソフトに読み込ませて、ヘッダのサイズに留意しつつ"len for distance"の範囲を求めると、"len for distance"はgz全体で342 - 401bitの範囲にある事が分かりました。実際に反転していた箇所は383bit目なので、求まった範囲とも合致します。これにより、総当りによらず、反転していると推測される箇所の範囲を60/2856まで絞り込むことが出来ました。

まとめ

この問題については、範囲絞り込みの手間より総当りの手間のほうが明らかに少ないので、総当たりを選ぶべきです。しかし、問題によっては、何かしらの方法で範囲を絞り込む事が必要になることもあるでしょう。
誤りがあれば指摘お願いします。