独自のファイル形式で使用されているDEFLATEアルゴリズムバリアントの特定

Question

免責事項：この問題には、DEFLATEアルゴリズムに関する非常に優れた知識が必要です。

私は、特定のファイル形式で使用されている圧縮アルゴリズムを特定するアイデアを募集したいと考えています。これは私のアプリケーションがサポートしなければならない旧式の独自フォーマットです。そのため、リバースエンジニアリングを試みています。 （元のクリエイターに行くのは、私が入ってこない理由のために、オプションではありません）。

私は非常にクラックすることに近いですが、毎日私はフィニッシュラインに途中まで近づいているようですが、決してそこにはいないので、私はゼノのパラドックスを生きているように感じます！

は、ここで私はこれまで知っているものです：

それは間違いなく、deflateアルゴリズムに非常に類似したものを使用しています。類似点 -

• 圧縮されたデータは、標準的なハフマン符号 で表される（通常は000から始まるが、私はそれは常に ケースではよく分かりません）。
• データは実際のコードのビット数を識別するヘッダテーブル によって先行されます（私はすぐに信じます）。 DEFLATEと同様に、このテーブルは、（0または00のいずれかで開始する）カノニカルハフマンコード も含みます。これらのコードは、 のビット数と、0-255 +アルファベットの各文字と、いずれの距離コード でも使用できます。ヘッダテーブルコード （I'LLを導出するために使用される3ビットの符号一連の最後に、再びDEFLATEように、メインコードの ビットlenghtsとヘッダテーブルも先行する
• （Iはすぐに思い） これを「プレヘッダー」と呼ぶ）。

この時点で類似点は終了しているようです。

プリヘッダーの3ビットコードは、DEFLATEで指定されているように16,17,18,0,8 ...最適な順序で表示されず、むしろ6 7 8 9 ....

もう1つの違いは、各3ビットコードが必ずしもリテラルビット長であるとは限りません。例えば、ここでIはほとんど解読きたヘッダが（私はそれが正しい99.99％確信して）は次のとおり

00000001011 100 010 110 010 010 011 010 110 101 100 011 010 010 011 100 010 111 
      *0*  skA     *3* *4* *5* *6* *7* *8* *9* skB 

はマークされていないビットを無視すると、これは次のコード表の結果：

00  7-bits 
01  8-bits 
100  6-bits 
101  9-bits 
1100  0-bits (skip code) 
1101  skA = skip 3 + value of next 4 bits 
1110  5-bits 
11110 4-bits 
111110 skB = skip 11? + value of next 9 bits 
111111 3-bits 

最も目立つ問題は、ヘッダーテーブルに未使用の追加のビット長があることです。そして、実際には、2ビットまたは3ビットのコードを追加することはできません。例えば、コードが正規（正義）であるためです。

著者はまた、16+の非標準コードを使用しています。彼らはコピーコード（DEFLATEでは16）をまったく使用していないようです。メインヘッダーはすべて同じ長さのコード（ひどく非効率な...）の巨大な文字列を持ち、スキップコードは、DEFLATEのように、次の4ビットと9ビットを使用してスキップ数を3と7ではなくそれぞれ決定します。

さらに別の重要な違いは、ヘッダーの最初のビットです。 DEFLATEでは、最初のビットはHLIT（5）、HDIST（5）、およびHCLEN（4）です。上記のヘッダーをLSBパッキングを使用して解釈すると、HLIT = 257（正しい）、HDIST = 21（正しい場合は不明）、HCLEN = 7（間違いなく正しい）が得られます。代わりにMSBパッキングを使用すると、HLIT = 257、HDIST = 6（正しい可能性が高い）、HCLEN = 16（正しいと思われる）が得られます。しかし、0ビット（スキップ）コードのビット数には "100"（上記参照）が必要なように見えるため、実際には接頭辞に14ビットがあるとは思われません。また、他の例では、ビット10〜13は、プリヘッダの長さに全く相関していないように見える。

他の例で言えば、すべてのファイルが同じヘッダー形式に従っているとは限りません。ここでは、別のヘッダーがあります：

00000001000 100 100 110 011 010 111 010 111 011 101 010 110 100 011 101 000 100 011 

この第2の例では、私は再びヘッダのコード表があることを知ることが起こる：しかし

0   8-bits 
10  7-bits 
110  6-bits 
11100  skA 
11101  5-bits 
111100 0-bits (skip) 
111101 skB 
111110 9-bits 
1111110 3-bits 
1111111 4-bits 

、あなたが見ることができるよう、必要なコードlenghtsの多くヘッダーにはまったくありません。たとえば、8ビットコードを表現するための "001"はありませんし、連続していなくても（連続的でも最適な16,17,18 ...でもない）

それでも、我々は1だけ左にビットシフトする場合：

      skA     *0* *5* *6* *7* *8* *9* 
0000000100 010 010 011 001 101 011 101 011 101 110 101 011 010 001 110 100 010 001 1 

これははるかに優れているが、我々はまだ正しくSKBため（110）、コードを導き出すことができない、あるいは3または4を（111 ）。別のビットでシフトしても状況は改善されません。

ちなみに、これらの2つの例でコード表を知っていると私は確信していますが、答えは苦労しているリバースエンジニアリングです。つまり、ファイルが少し違っていたり、パターンを生成し、使用されている正規のコードテーブルを導出する。これらのコード表は99 +％が間違いなく正しいです。

要約すると、DEFLATEに非常に近い変形があるように見えますが、不可解な理由から、ある種の非標準プリヘッダーを使用するものがあります。もちろん、私が立ち上がっているところでは、どのプレヘッダービットがメインヘッダーのコードビット長に対応しているかを識別しています。もし私がそれを持っていれば、すべてがうまくいくでしょう。

私はいくつかの例を挙げることができますが、人々に私のパターンマッチングを依頼するのではなく、私が本当に祈っているのは、誰かが使用されているアルゴリズムを認識し、それ。私は、既存の標準を使用するのではなく、DEFLATEのような99％の独自のアルゴリズムをコーディングするのではなく、プリヘッダー構造をわずかに変更するという難しさを感じることはほとんどありませんでした。意味がない;彼らが単に私がやろうとしていることを防ぐためにデータを難読化したいのであれば、はるかに簡単で効果的な方法があります。

ソフトウェアは90年代後半から2000年代初頭にかけて作られています。これは「ミドルアウト」や何か新しいものではありません。それは古いもので、おそらくあいまいです。私はその時間の間にいくつかの人気のあるライブラリで使用されていたDEFLATEの変種を推測していますが、実際にはDEFLATEではないものについては情報を見つけることができませんでした。

多くの方々には、多くのご協力ありがとうございます。

ピーター

PSは - 要求されたとして、ここではポストの最初の例から完全なデータブロックです。私はそれが多くの使用のだろうか分からないが、ここに行く。最初の4バイトは圧縮されていない出力サイズです。 5番目のバイトはプレヘッダーを開始します。

B0 01 00 00 01 71 64 9A D6 34 9C 5F C0 A8 B6 D4 D0 76 6E 7A 57 92 80 00 54 51 16 A1 68 AA AA EC B9 8E 22 B6 42 48 48 10 9C 11 FE 10 84 A1 7E 36 74 73 7E D4 90 06 94 73 CA 61 7C C8 E6 4D D8 D9 DA 9D B7 B8 65 35 50 3E 85 B0 46 46 B7 DB 7D 1C 14 3E F4 69 53 A9 56 B5 7B 1F 8E 1B 3C 5C 76 B9 2D F2 F3 7E 79 EE 5D FD 7E CB 64 B7 8A F7 47 4F 57 5F 67 6F 77 7F 87 8F 97 9D FF 4F 5F 62 DA 51 AF E2 EC 60 65 A6 F0 B8 EE 2C 6F 64 7D 39 73 41 EE 21 CF 16 88 F4 C9 FD D5 AF FC 53 89 62 0E 34 79 A1 77 06 3A A6 C4 06 98 9F 36 D3 A0 F1 43 93 2B 4C 9A 73 B5 01 6D 97 07 C0 57 97 D3 19 C9 23 29 C3 A8 E8 1C 4D 3E 0C 24 E5 93 7C D8 5C 39 58 B7 14 9F 02 53 93 9C D8 84 1E B7 5B 3B 47 72 E9 D1 B6 75 0E CD 23 5D F6 4D 65 8B E4 5F 59 53 DF 38 D3 09 C4 EB CF 57 52 61 C4 BA 93 DE 48 F7 34 B7 2D 0B 20 B8 60 60 0C 86 83 63 08 70 3A 31 0C 61 E1 90 3E 12 32 AA 8F A8 26 61 00 57 D4 19 C4 43 40 8C 69 1C 22 C8 E2 1C 62 D0 E4 16 CB 76 50 8B 04 0D F1 44 52 14 C5 41 54 56 15 C5 81 CA 39 91 EC 8B C8 F5 29 EA 70 45 84 48 8D 48 A2 85 8A 5C 9A AE CC FF E8 

編集2015年7月11日

私はかなりの追加情報を解読することに成功しました。アルゴリズムはLZ77とハフマン符号化を使用しています。長さコードと余分なビットは、Deflateで使用されているものとすべて一致しているようです。

私はプリヘッダーについてもっと詳しく学ぶことができました。それは次の構造を持っています：

     HLEN 0 SkS SkL ?? 3 4 5 6 7 8 9 HLIT 
00000 00101110 001 0 1100 100 100 110 10 110 101 100 011 010 010 011 100010111 

HLEN = the last bit-length in the pre-header - 3 (e.g. 1100 (12) means 9 is the last bit-length code) 
HLIT = the number of literal codes in the main dictionary 
SkS = "skip short" - skips a # of codes determined by the next 4-bits 
SkL = "skip long" - skips a # of codes determined by the next 9-bits 
0 - 9 = the number of bits in the dictionary codes for the respective bit lengths 

マークされていないビットはまだ解読できません。また、私が今見ているのは、プレヘッダーコード自体に余分なビットが入っているように見えることです（上記のSkLと3の間に注意してください）。それらはすべてストレート3ビットコードではありません。

だから、今欠けている唯一の重要な情報は以下のとおりです。

• 余分なビットとその他もろもろのための事前のヘッダを解析する方法。私はその情報を持っていた場合と
• は多くの距離コードリテラルコード

に従う方法は、私は実際に手動で距離対リテラルの正しい数とともに符号長辞書を供給することにより、ZLIBに残りのデータを送ることができコード。このヘッダーの後のすべてが、DEFLATEの後ろの文字に続きます。

ここに、ビット長コードとリテラルおよび長さコードの数を示したヘッダーの例をいくつか示します。それぞれの回答をリバースエンジニアリングすることができたことに注意してください。しかし、私は解読されていないビットをそれらの統計値に一致させることができません。

私はまだ誰かがこのような非標準のDEFLATEスタイルのヘッダーを見ていることを期待しています。または、私が見逃しているパターンが表示されるかもしれません。

Answer 1

私は最終的に完全にそれをクラックすることができました。実際にはLZ77とハフマンコーディングの実装を使用していましたが、コードを格納して派生させるための非標準のDEFLATEのようなメソッドでした。

プレヘッダーコード自体は固定小数点ハフマンコードであり、リテラルビット長ではありませんでした。 DEFLATEとは異なり、リテラルと同じビット長コードを使用せず、むしろ別の固定ハフマン辞書を使用していたため、遠隔コードの把握も同様に難解でした。

興味のある方は、DEFLATE派生語を使用している古いファイル形式があるようです。それらは決定でリバースエンジニアリングすることができます。この場合、コードパターンを見つけるために、圧縮されたデータを既知の解凍されたサンプルから手動で再構築していたものがほとんどです。そのプロセスを自動化するために何をしているのか分かったら、数十種類のサンプルヘッダーを作成してパターンを見つけることができました。

標準フォーマットを使用するのではなく、なぜこれを行ったのか分かりません。 ZLibを使用するのとは対照的に、新しい圧縮フォーマットを導き出すことはかなりの労力を要していたに違いありません。彼らがデータを難読化しようとしていたら、それを暗号化したり、他の値でxor'ingしたりすることで、はるかに効果的に行うことができました。彼らは、スタンダードとの違いが些細なものであっても、私の人生を困難にする以外に価値がないとしても、彼らの天才を上司に誇示することを決めたのです。 :)

入力した方に感謝します。