nccgroup/zipdefragPresented at Recon Montreal 2018
あるいは、愚か者と反逆者のための高度なショットガンパーシング
むかしむかし、親愛なる読者よ、暗く嵐の夜のこと、あなたの忠実な著者は、実に当惑させられる神秘的な状況に出くわした――チップオフメモリ解析とリバースエンジニアリングを阻む唯一のものが、未知の断片化されたプロプライエタリファイルシステムと、組み込みJavaの使用による圧縮の組み合わせであり、それが既存のファイルカービングツールの効果を低下させていたのである。
当時は、手動でくっつきそうなチャンクをつなぎ合わせ、少しばかりの厄介なPythonコンソール作業と醜いアドホックなbashスクリプトで、その場しのぎの解決策が間に合わせで作られたかもしれない。それは「十分に良い」ものだったが、時間がかかった。
チップオフ解析において、平文の非圧縮データを抽出することは、ハードウェアハッカーにとっては日常茶飯事の仕事だが、圧縮データの断片が非合理的で不愉快な方法であちこちに散らばっている場合、抽出に対する他の実際の保護が何もなくても、圧縮は重大な問題を引き起こす。
特にZipファイルにはいくつか興味深い点がある（JARファイルに使われる基本フォーマットである）。長い間International Journal of PoC||GTFOの真面目な読者であり、特にAnge Albertiniによるファイルフォーマットの変形技法の研究を追ってきた者として、zipファイルの中にはzipファイル自身についての十分なデータが含まれており、それをすべて再びつなぎ合わせるのにかなり良い仕事ができるのではないかと思った。
さて、前置きはこのくらいにして、技術的な詳細に入ろう。
まず最初に、ファイルシステムの詳細については私たちは知らないかもしれない（そして私の研究の観点から、問題に遭遇したシステムから独立して、私は単に気にしない方が良いと判断した）。しかし、ほとんどのファイルシステムが実装される方法について、私たちはいくつか知っている。特に、それらはチャンク単位で書き込まれる傾向があることを知っている。チャンクにはページと呼ばれる何らかの最小サイズがあり、ダンプを閲覧して書き込まれる最小ブロックサイズを特定することで、そのページサイズを識別できる。
これらの一部は連続しているかもしれないが、一部はそうではなく、ブロックが連続するタイミングに明確なパターンはない。
つまり、私たちが抱える問題は、抽出したいファイルの有効な（あるいは十分に近い）イメージが得られるように、データページをどのように並べ替えるかということだ。
Zipファイルは一種の逆階層を実装するように書かれている。最初に圧縮されたファイルデータ（それを説明するローカルファイルヘッダーで包まれている）。次にセントラルディレクトリ（ローカルファイルヘッダーのオフセットをリストする）、そしてエンドオブセントラルディレクトリレコード（とりわけzipに格納されているファイル数、セントラルディレクトリが始まるオフセット、セントラルディレクトリのサイズを記述する）が続く。
それを逆から見て、もう少し詳しく掘り下げよう：
エンドオブセントラルディレクトリは以下を教えてくれる：
各セントラルディレクトリレコードは以下を教えてくれる：
各ローカルファイルレコードは以下を教えてくれる：
以上のすべてにより、ファイルの大部分について再構築が達成される。
まず第一に、異なるファームウェアからのデータを区別するためのステップが必要だ。その理由は、すべてのオフセットがそれぞれのzipファイル内でのみ有効だからである――競合が発生するとzipストリームの不一致と破損を招き、私たちは破損していないデータをできるだけ多く取り出したいのである。また、例えば対象ファームウェアで診断した脆弱性が、普段動作しているのを見るファームウェアに影響し、単に置き去りにされた他のファイルには影響しないという確かな保証も欲しい。
ここで必要な解決策はkmeansアルゴリズム（別名「ロイドのアルゴリズム」）だ。仕組みを説明する素晴らしいビデオはこちら。SciPyには使える優れたバージョンが既にあったが、Rust実装でこれを動作させるには、このアルゴリズムを実装している唯一のクラスタリング/解析クレートを特定/パッチする必要があった。幸運なことに、ゼロから書く必要はなかった。
その後はもうお手の物だ。
これを行うにはいくつかの特徴量を使用できる。Flags、Method、Versionの各フィールドは、ファイルの圧縮に使用されたZipスタックによって異なる。さらに、ヘッダーにはタイムスタンプがあり、すべてのファームウェアがまったく同じ時刻にコンパイルおよび圧縮されたとは通常考えにくい。
ちなみに、ZipファイルはMS-DOS形式のタイムスタンプを使用していることに言及しておく価値がある。 これは年-月-日と時-分-2秒を表すビット詰めのショート整数である。 これを分類データとして使用する前に絶対スカラー値に変換しなければ、 1年の差と1秒の差に同じ重みを与えてしまうことになりかねず、それはまったく良くない！
これらをユークリッドベクトル（ℝ上の値のn次元配列、つまり浮動小数点座標を指す格好いい言葉だが、上でリンクしたビデオがおそらく最もわかりやすい説明だろう）に変換すると、クラスタリングアルゴリズムが残りのほとんどすべてをやってくれ、解析されたすべてのヘッダーを期待する数のバケットに集めてくれる。
この手法のプロトタイピングとしてこれをかなり粗雑なPythonスクリプトで書いたが、PoCでおおよそ70〜80%のJARコンテンツ復元率に達したため、そこで止めてRustで高速版を実装することに決めた。
Rustにはnomというクレートがあり、パーサー検証器を書くのに絶対的に素晴らしい。これがRustで書き直す主な魅力の一つだった（参考までに）。明確で非常に厳格なパーサーを書ける能力は、これをすべてPythonで処理しようとするよりも、ある意味ではるかに簡単にする（Pythonははるかに寛容な傾向があり、その寛容さゆえに、エッジケースを捕まえる際に誤った失敗を見逃してしまっていないと確信するのが、時には少し難しいほどである）。
素晴らしく高速で読みやすいパーサーに興味があれば、こちらをチェックしてほしい。
何はともあれ、この種の解析をPythonで実行することは本質的に遅い部類であり、そもそもこの手法の実現可能性を探るためのPoCへの道筋以上のものとして意図されたことはなかった。
とにかく、その話はこれくらいにして...
残りのチャンクを再構築するアプローチには、まず残りのページを高エントロピー候補でフィルタリングすること、まず小さなギャップを埋めること（検索リストからできるだけ多くのページを排除する。これらへの順列テストは最悪の場合指数時間のタスクであるため、簡単なケースを素早く解くことが優先であり、進めるにつれて私たちの問題を指数関数的に単純化する！）が含まれる。
また、ページ境界のためにローカルファイルヘッダーがパースできないインスタンスを見つけることで、迅速な成果を得ることもできる（同様のアラインメントが一意であり、他の破損アーティファクトと衝突しないケースでは、同じアラインメントの対応物とマッチさせることができるはずだ）。
欠落ページの候補をどのようにチェックするのか？ 私たちのセントラルディレクトリにはファイルのCRC32チェックサムがすぐそこにあるではないか！ ファイル全体に対してCRC32を計算するよりも、おそらくこの問題に取り組む最善の方法は、既知のチャンクに対してCRC32を計算することだ（ギャップが始まる前のページの末尾にあるデータから前方へ、そしてデータ（またはdeflateストリームの後のDataDescriptorチャンク）から後方へ）そしてこれらから、欠落ページの各ブロックについて期待すべき中間CRC32を割り出す。
基本的に、私たちが最も単純/最速の問題を選んで解くたびに、無駄を排除することで、より困難な問題を大幅に単純化する。これがシャノンエントロピーを使用して空のページやほぼ空のページを完全に捨て去る理由だ――高エントロピーのzipページだけが存在するとは限らないが、外れ値があったとしても、最初にその複雑さに対処するのを避けることは大幅な高速化になる。
これで遊んでみたいなら、rustをインストールしよう（素晴らしいrustup nightlyを使用することを推奨する）。そして：
$ git clone [repo]
...
$ cd zipdefrag
...
$ cargo build --release
デバッグを有効にするにはreleaseフラグを付けずにビルドできる。
ビルド成果物は/target/{debug,release}に置かれる。
cargo docでドキュメントをビルドできる（このクレートは非常に充実したドキュメントが付いている。私は書くことが好きなのだ）。
現在、Rust版にはデフォルトのターミナル出力がない。cliハーネスを実行したい場合は、環境変数RUST_LOG=zipdefragを設定する必要がある。これにより、これまでの解析を示す詳細なターミナルログが有効になる。
未知のファイルシステムからのパズル解きzipダンプ用の、高速でポータブルなネイティブ実行可能ファイル（pythonフック付き）。
デモ用のダンプ
現在、Rust実装のパフォーマンスは、対応するLFHチャンクの検索まわりの無駄な挙動のために壊れている。これを修正し、教訓とするつもりだ。
この手法は、JAR内の多くのファイルがページサイズよりも大幅に大きい場合にはうまく機能しない。zipファイルに本来備わっている構造に大きく依存しているため、データ量の多いファイルはあまりうまくいかない。
幸いなことに、J2MEミドレットのクラスファイルは一般にかなり小さい傾向があるが、内部にパッケージされた大きなバイナリはおそらく復元不可能だろう。
また、python PoCには多くの算術バグが含まれている。