Intel ME 11.xでのハフマンテーブルリカバリ

本日、ロンドンで開催されたBlack HatカンファレンスのPositive Technologiesの専門家であるDmitry Sklyarovは、 Intel CSME / MEバージョン11.xの一部とこのシステムのファイルが配置されているファイルシステムの配置について説明します 。 Intel ME 11.xでのハフマンテーブルの復元に関する彼の記事に注目してください。







ご存知のように 、多くのIntel ME 11.xモジュールはフラッシュメモリにパック形式で保存されており、圧縮には2つのアルゴリズムLZMAとHuffman Encodingが使用されています。 アンパックに使用できるLZMAのパブリック実装がありますが、ハフマンの場合、すべてがより複雑です。 MEのハフマンエンコーディングアンパッカーはハードウェアレベルで実装され、同等のプログラムコードの構築は複雑で非標準のタスクです。

MEの以前のバージョン

unhuffmeプロジェクトの一部であるソースコードを確認した後、MEの以前のバージョンには2セットのHuffmanテーブルがあり、各セットには2つのテーブルが含まれていることが簡単にわかります。 2つのテーブル（1つはコード用、もう1つはデータ用）の存在は、おそらくコードとデータの統計的性質が非常に異なるためです。



次のプロパティも注目に値します。

• テーブルのセットが異なると、コードワードの長さの範囲が異なります（7〜19および7〜15ビットを含む）。
• 各コードシーケンスは、整数のバイト数（1〜15を含む）をエンコードします。
• どちらのセットもCanonical Huffman Codingを使用します（これにより、アンパック時に次のコードワードの長さをすばやく決定できます）。
• 1つのセット内では、コードワードのエンコード値の長さはすべてのテーブル（コードとデータ）で同じです。

問題の声明

ME 11.xのハフマンテーブルでは、最後の3つのプロパティも観察されると想定できます。 次に、テーブルを完全に復元するには、次を見つける必要があります。

• コードワード長の範囲;
• 同じ長さのコードワードの値の境界（形状）;
• 各コードワードのエンコードされたシーケンスの長さ。
• 両方のテーブルの各コードワードのエンコードされた値。

圧縮データを個別のページに分離します

個々のモジュールに関する情報を取得するには、ファームウェアの内部構造に関する既存の知識を使用できます 。



コードパーティションディレクトリの一部であるルックアップテーブルを調べたところ、ハフマンコーディングが適用されるモジュール、パックされたデータの開始場所、およびアンパック後のモジュールのサイズを簡単に判断できます。



特定のモジュールのモジュール属性拡張機能を調べた後、圧縮および解凍されたデータのサイズと、解凍されたデータからSHA256を簡単に見つけることができます。



ME 11.xのいくつかのファームウェアを簡単に分析した後、ハフマンによる解凍後のデータサイズは常にページサイズの倍数であることがわかります（4096 == 0x1000バイト）。 パックされたデータの先頭には、4バイト整数値の配列があります。 配列要素の数は、展開されたデータのページ数に対応します。

たとえば、サイズ81920 == 0x14000バイトのモジュールの場合、配列は80 == 0x50バイトを占有し、20 == 0x14要素で構成されます。







各リトルエンディアン値の上位2ビットには、テーブル番号（コードの場合は0b01、データの場合は0b11）が格納されます。 残りの30ビットには、オフセット配列の末尾に対する圧縮ページの先頭のオフセットが格納されます。 上記のスニペットは20ページを説明しています。







各ページのパックデータのオフセットは昇順でソートされ、明示的な形式の各ページのパックデータのサイズはどこにも表示されないことに注意してください。 上記の例では、特定の各ページのパックデータは64 = 0x40バイトの境界倍数から始まり、未使用領域はゼロで埋められます。 しかし、他のモジュールについては、調整が不要であることが確認できます。 これは、アンパックされたページのデータサイズが4096バイトに達したときにアンパッカーが停止することを示しています。



（Module Attributes Extensionから）パックされたモジュールの合計サイズがわかっているため、パックされたデータを個別のページに分割し、各ページを個別に操作できます。 パックされたページの先頭はオフセットの配列から決定され、サイズは次のページの先頭のオフセットまたはモジュールの合計サイズによって決定されます。 この場合、パックされたデータの後に、任意の数の重要でないビットが続く可能性があります（これらのビットは任意の値を持つことができますが、実際には通常ゼロです）。







スクリーンショットは、最後の圧縮ページ（オフセット0xFA40で始まる）がバイト0xB2 == 0b10110010で構成され、その後に値0xEC == 0b11101100の273バイトが続き、その後にゼロのみが続くことを示しています。 ビットシーケンス11101100（または01110110）は273回繰り返されるため、4096/273 == 15の同一バイト（ほとんどの場合値0x00または0xFF）をエンコードすると想定できます。 次に、ビットシーケンス10110010（または1011001）は4096-273 * 15 == 1バイトをエンコードします。



これは、各コードシーケンスが整数バイト（1〜15を含む）をエンコードするという仮定とよく一致しています。 ただし、この方法でハフマンテーブルを完全に復元することはできません。

「圧縮テキスト-平文」のペアを見つける

前に示したように 、ME 11の異なるファームウェアバージョンでは、同じ名前のモジュールを異なるアルゴリズムでパックできます。 LZMAとHuffmanの両方でパックされた同じ名前のモジュールのモジュール属性拡張を解析し、各モジュールのSHA256値を抽出した場合、異なるアルゴリズムでパックされた同じハッシュ値を持つモジュールのペアは見つかりません。



しかし、LZMAでパックされたモジュールの場合、SHA256は通常圧縮データから計算され、LZMAをアンパックした後にモジュールのSHA256をカウントすることを思い出すと、非常に多くの適切なペアが見つかります。 そして、そのような「ペア」モジュールごとに、ハフマンのパックおよびアンパック形式で、すぐにいくつかのページのペアを受け取ります。

形状、長さ、値

圧縮された開いた形式（コードとデータとは別に）のページの大きなセットが存在するため、これらのページで使用されているすべてのコードシーケンスを復元できます。 この問題の解決策は、線形代数と検索エンジン最適化の接点にあります。 おそらく、すべての制限を考慮に入れた厳密な数学モデルを構築できますが、タスクは1回限りのタスクであるため、作業の一部を手動で、一部を自動化する方が高速であることが判明しました。



最も重要なことは、Shape（コードシーケンスの長さの変化点）を少なくとも大まかに決定することです。 たとえば、その7ビットシーケンスの値は1111111から1110111まで、8ビットシーケンスの11101101から10100011までなどです。CanonicalHuffmanコーディングが使用されるため、Shapeを知ることで次のコードシーケンスの長さを決定できます（最短シーケンスは単位のみで構成されます、最長はゼロのみで、値が小さいほどシーケンスが長くなります）。



圧縮されたデータの正確なサイズがわからないため、ゼロビットのみで構成されるすべてのシーケンスを「テール」から消去することができます（最長であり、最後の位置に最もまれなコードシーケンスが出現する可能性は低いため）。



各圧縮ページが一連のコードシーケンスとして表現できる場合、それらによってエンコードされた値の長さを判断し始めることができます。 各ページのエンコードされた値の長さの合計は、4096バイトである必要があります。 これにより、エンコードされた値の長さが不明で、係数が圧縮ページ内の対応するコードシーケンスの出現回数であり、4096が常にフリーメンバーの代わりにある線形方程式のシステムを作成できます。同一のコードシーケンスの場合、エンコードされた長さ値は一致する必要があります。



十分な数のページ（および方程式）が与えられた場合、システムの唯一の解はガウス法によって簡単に見つかります。 また、各値の長さとそれらのシーケンスの順序を知っているプレーンテキストを使用すると、コードシーケンスとそれらによってエンコードされた値の対応を簡単に取得できます。

不明なシーケンス

利用可能なすべての「ペア」ページを処理した後、コードテーブルのシーケンスの約70％とデータテーブルのシーケンスの68％の値を見つけることができます。 配列の約92％の長さがわかります。 また、Shapeには不確実性があります：いくつかの場所では、短い長さの1つの値または長い長さの2つの値のいずれかを使用でき、パックデータで値の1つが見つかるまで境界を決定することはできません。



これで、平文が存在しないモジュールでのみ見つかったコードシーケンスの値の復元を開始できます。



未知の長さのシーケンスに遭遇した場合、方程式システムに別の行が追加され、これにより長さをすばやく決定できます。 しかし、明確なテキストを持たずに意味を判断する方法は？

検証者とブルートフォース

幸いなことに、アンパックされたモジュールのSHA256はメタデータに保存されます。 また、モジュールを構成するすべてのページのすべての不明なコードシーケンスの値を正しく推測した場合、計算されたSHA256値はモジュール属性拡張のSHA256値と一致する必要があります。



不明なシーケンスの合計長が1または2バイトの場合、不明なバイトは正面列挙によって基本的に検出されます。 また、3または4個の不明なバイト（特にモジュールの終わり近くにある場合）を処理できますが、1つのコアで検索するのに数時間から数日かかることがあります（複数のコアまたはマシンに簡単に並列化できます）。 5バイト以上を列挙する試みは行われませんでした。



したがって、さらにいくつかのコードシーケンス（およびいくつかのモジュール）を回復することができます。 ただし、不明なバイトの合計量がブルートフォース選択の機能を超えるモジュールのみがあります。

ヒューリスティック

ただし、互いにわずかに異なる多数のモジュールが存在するため、さまざまなヒューリスティックを使用でき、それらの助けを借りて未知のコードシーケンスの値を見つけることができます。

2番目のハフマンテーブルの使用

アンパッカーには2つのハフマンテーブルがあるため、コンプレッサーは各テーブルのデータを圧縮しようとし、占有するバージョンが少ないスペースを残します。 結果として、「コード」と「データ」への分割は条件付きです。 また、ページの一部を変更すると、別のテーブルがより効果的になる場合があります。 つまり、同じモジュールの他のバージョンを見ると、別のテーブルでパックされた同一のフラグメントを見つけて、未知のバイトを復元できます。

再利用可能

1つの（または異なる）モジュール（コードやデータなど）で1つのコードシーケンスが何度も発生する場合、未知の値にどのような制限が課されているかを簡単に判断できます。

オフセット付きの定数とテーブル

これらのモジュールの分野では、定数とオフセットは非常に一般的です（たとえば、テキスト文字列または関数）。 定数はさまざまなモジュールで共通であることがあり（たとえば、ハッシュ関数や暗号化アルゴリズム）、オフセットはモジュールの各バージョンで一意ですが、同じ（または非常に類似した）データまたはコードを参照する必要があります。 また、その値は非常に簡単に回復できます。

オープンライブラリの文字列定数

MEコードの一部のフラグメントは、オープンソースプロジェクト（wpa_supplicantなど）から明らかに借用されており、テキスト文字列のフラグメントは、コンテキストおよびソースのピアリングによって簡単に推測されます。

オープンライブラリのコード

ソースを見て関数のテキストを見つけたら、いくつかのバイトが不明なコンパイル済みコードについて、コンパイラーとして働いて、この場所で適切な値を推測できます。

別のバージョンのモジュールの同様の機能

1つのモジュールの異なる（しかし近い）バージョンでは大きな違いはないはずなので、別のバージョンのモジュールで同等の関数を見つけて、コードで未知のバイトに何があるべきかを理解するだけで十分な場合があります。

MEの以前のバージョンの同様の機能

コードがパブリックソースから取得されていない場合、一部のフラグメントはモジュールの利用可能なすべてのバージョンで不明であり、他のモジュールでは見つかりません（つまり、amtモジュールで見つかりました）、同じ場所を見つけることができます（たとえば、ME 10で）、ロジックを見つける機能し、ME 11.xの未知の場所に投影します。

プロセス収束

未知のシーケンスが少ないモジュールから始め、さまざまなヒューリスティックを組み合わせることで、ハフマンテーブルの既知の部分を段階的に増やすことができました（毎回SHA256を計算して仮定の正確性をチェックしました）。 カバレッジが増加すると、未知のシーケンスの数が最初に数十で測定されていたモジュールはそれほど威圧的ではなくなりました。 プロセスは収束しているように見えましたが、すべてがamtになりました。



このモジュールは最大サイズ（約2メガバイト、合計の約30％）であり、他のモジュールには見られないが、amtのすべてのバージョンに見られる多くのコードシーケンスが含まれています。 いくつかのシーケンスを高い確率で推測することは可能ですが、仮定を検証する唯一の方法は、それらすべてを推測することです（したがって、SHA256が一致します）。 Maxim Goryachyの非常に貴重な助けのおかげで、この障壁を克服することができました。その結果、ファームウェアに含まれ、ハフマンアルゴリズムでパックされたモジュールをアンパックできました。



時間が経つにつれて、新しいファームウェアが登場し、以前は満たされていないコードワードに遭遇しました。 しかし、ヒューリスティックの1つが機能するたびに、モジュールは正常にアンパックされ、テーブルのカバレッジが増加しました。

最後のタッチ

2017年6月中旬までに、コードテーブルのシーケンスの約89.4％とデータテーブルのシーケンスの86.4％を回復できました。 しかし、新しいモジュールの分析を通じて、妥当な時間内にテーブルの100％カバレッジを構築する可能性は非常に弱いです。



6月19日に、コードテーブルのシーケンスの80.8％とデータテーブルのシーケンスの78.1％をカバーするハフマンテーブルのフラグメントが 、IllegalArgumentというニックネームを持つユーザーによってGitHubに公開されました。 おそらく、著者（または複数の著者）は、既存のファームウェアの分析に基づいて同様のアプローチを使用しました。 また、公開された表には新しいものは何もありませんでした。



そして7月17日、Mark ErmolovとMaxim Goryachyは、圧縮データのアンパック値を見つける機会を得ました。 4つの圧縮ページ（コード用に2つ、データ用に2つ）を準備し、両方のテーブルの1519シーケンスをすべて復元しました。



同時に、理解できない場所が1つ発見されました。 データのハフマンテーブルでは、値00410E088502420D05は、シーケンス10100111（8ビット長）とシーケンス000100101001（12ビット長）の両方に対応しています。 これは明らかな冗長性ですが、ほとんどの場合、ランダムエラーが原因です。



結果のShapeは次のとおりです。







Posted by Dmitry Sklyarov、ポジティブテクノロジーズ