Identifizieren der DEFLATE-Algorithmusvariante, die im proprietären Dateiformat verwendet wird

Question

Haftungsausschluss: Dieses Problem erfordert sehr gute Kenntnisse des DEFLATE-Algorithmus.

Ich hoffe, ich könnte einige Ideen für die Identifizierung des Komprimierungsalgorithmus in einem bestimmten Dateiformat. Dies ist ein Legacy-proprietäres Format, das meine Anwendung unterstützen muss. Daher versuchen wir, es rückzuentwickeln. (Zum ursprünglichen Schöpfer zu gehen ist keine Option, aus Gründen, auf die ich nicht eingehen werde).

Ich bin extrem nahe, es zu Rissbildung, aber ich fühle mich wie ich bin Xeno Paradox leben, weil ich jeden Tag scheinen auf halber Strecke näher an der Ziellinie zu bekommen, aber nie da!

Hier ist, was ich weiß, bisher:

Es ist auf jeden Fall etwas sehr ähnlich den DEFLATE Algorithmus. Similarities -

• Die komprimierten Daten durch kanonischen Huffman-Codes dargestellt werden (in der Regel mit 000 beginnen, aber ich bin nicht sicher, dass es immer der Fall).
• Den Daten ist (ich glaube sofort) eine Header-Tabelle vorangestellt, die die Bitlängen jedes der tatsächlichen Codes identifiziert. Wie DEFLATE enthält diese Tabelle ALSO die kanonischen Huffman-Codes (beginnend entweder bei 0 oder 00). Diese Codes liefern die Bitlängen von jedes Zeichen in der 0-255 + Alphabet plus welche Abstand Codes verwendet werden könnten.
• schließlich wieder wie DEFLATE, der Header-Tabelle mit den Bit lenghts für die wichtigsten Codes auch (glaube ich sofort) durch eine Reihe von 3-Bit-Codes verwendet, vorangestellt ist die Header-Tabelle Codes (Ich werde herzuleiten nennen Sie das den "Pre-Header").

An diesem Punkt scheinen die Ähnlichkeiten jedoch zu enden.

Die 3-Bit-Codes im Pre-Header erscheinen nicht in der 16, 17, 18, 0, 8 ... optimalen Reihenfolge wie von DEFLATE angegeben, sondern scheinen sequenziell zu gehen, wie 6 7 8 9 ....

Ein weiterer Unterschied ist, dass jeder 3-Bit-Code nicht unbedingt eine wörtliche Bitlänge ist. Zum Beispiel, hier ist ein Header, die ich meistens entziffert habe (ich bin 99,99% sicher, dass es richtig ist):

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 

die nicht markierten Bits Ignorieren, führt dies in der folgenden Code-Tabelle:

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 

Das eklatanteste Problem ist, dass in der Header-Tabelle zusätzliche Bitlängen vorhanden sind, die nicht verwendet werden. Und tatsächlich wären sie überhaupt nicht verwendbar, da es beispielsweise keine zusätzlichen 2-Bit- oder 3-Bit-Codes geben kann, damit die Codes kanonisch sind (richtig?).

Der Autor verwendet auch Nicht-Standard-Codes für 16+. Sie scheinen den Kopiercode (16 in DEFLATE) überhaupt nicht zu verwenden; Die Hauptheader haben alle riesige Strings mit identischen Längencodes (schrecklich ineffizient ...), und die Skip-Codes verwenden die nächsten 4 und 9 Bits, um die Anzahl der Übersprungen zu bestimmen, anstatt 3 und 7 wie in DEFLATE.

Ein weiterer wichtiger Unterschied ist in den allerersten Bits des Headers. In DEFLATE sind die ersten Bits HLIT (5), HDIST (5) und HCLEN (4).Wenn ich den obigen Header mit LSB-Packing interpretiere, würde ich HLIT = 257 (korrekt), HDIST = 21 (unsicher, wenn korrekt) und HCLEN = 7 (definitiv nicht korrekt) bekommen. Wenn ich stattdessen MSB-Packungen verwende, würde ich HLIT = 257, HDIST = 6 (wahrscheinlicher korrekt) und HCLEN = 16 (erscheint korrekt) bekommen. ABER, ich glaube nicht, dass es tatsächlich beabsichtigt ist, 14 Bits in dem Präfix zu sein, weil ich anscheinend die "100" (siehe oben) für die Bitzahl des 0-Bit- (Sprung-) Codes benötige. Und in anderen Beispielen scheinen die Bits 10-13 überhaupt nicht mit der Länge des Vor-Headers zu korrelieren.

Apropos andere Beispiele, scheint nicht jede Datei das gleiche Header-Format zu folgen. Hier ist ein weiterer Header:

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

In diesem zweiten Beispiel, ich noch einmal passieren zu wissen, dass die Code-Tabelle für den Header ist:

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 

Doch wie Sie sehen können, viele der erforderlichen Code lenghts sind überhaupt nicht in der Kopfzeile. Zum Beispiel gibt es keine "001", um den 8-Bit-Code darzustellen, und sie sind nicht einmal nahe an der Reihenfolge (weder aufeinanderfolgend noch durch die optimalen 16, 17, 18 ...).

Und doch, wenn wir die Bits nach links verschieben von 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 

Das ist viel besser, aber wir können immer noch nicht korrekt den Code für SKB (110) ableiten, oder 3 oder 4 (111). Das Verschieben um ein weiteres Bit verbessert die Situation nicht. Wenn Sie sich fragen, wie ich sicher bin, dass ich die Codetabellen in diesen beiden Beispielen kenne, ist die Antwort viel mühsames Reverse Engineering, dh, die Bits in Dateien zu betrachten, die sich geringfügig unterscheiden oder erkennbar sind Muster und Ableiten der verwendeten kanonischen Codetabelle. Diese Codetabellen sind 99 +% sicher korrekt.

Zusammenfassend, dann scheinen wir eine extrem enge Variante von DEFLATE zu haben, aber aus unerklärlichen Gründen eine, die eine Art von Nicht-Standard-Pre-Header verwendet. Wo ich gestolpert bin, wird natürlich identifiziert, welche Vor-Header-Bits den Code-Bitlängen für den Haupt-Header entsprechen. Wenn ich das hätte, würde alles zusammenpassen.

Ich habe ein paar andere Beispiele, die ich schreiben könnte, aber anstatt die Leute zu bitten, Muster für mich zu tun, bete ich wirklich dafür, dass jemand den Algorithmus erkennt, der benutzt wird und mich darauf hinweisen kann es. Ich finde es unwahrscheinlich, dass der Autor, anstatt einen bestehenden Standard zu verwenden, sich die Mühe gemacht hätte, seinen eigenen Algorithmus von Grund auf neu zu programmieren, der zu 99% wie DEFLATE war, aber dann die Pre-Header-Struktur nur geringfügig änderte. Das macht keinen Sinn; Wenn sie nur die Daten verschleiern wollten, um zu verhindern, was ich versuche zu tun, gibt es viel einfachere und effektivere Wege.

Die Software stammt übrigens aus den späten 90er Jahren, Anfang der 2000er Jahre, also überlegen Sie, was damals gemacht wurde. Das ist nicht "mittelfristig" oder etwas Neues und Verrücktes. Es ist etwas Altes und wahrscheinlich unklar. Ich vermute eine Variante von DEFLATE, die um diese Zeit in einer halb-populären Bibliothek benutzt wurde, aber ich hatte nicht viel Glück bei der Suche nach Informationen über alles, was nicht wirklich DEFLATE ist.

Vielen, vielen Dank für jede Eingabe.

Peter

PS - Wie gewünscht, hier ist der komplette Datenblock aus dem ersten Beispiel in der Post. Ich weiß nicht, ob es viel nützt, aber hier geht es. Übrigens sind die ersten vier Bytes die unkomprimierte Ausgabegröße. Das fünfte Byte beginnt den Pre-Header.

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 

bearbeiten 7/11/2015

ich es geschafft habe ziemlich viel zusätzliche Informationen zu entschlüsseln. Der Algorithmus verwendet definitiv LZ77 und Huffman-Codierung. Die Längencodes und zusätzlichen Bits scheinen alle denen von Deflate zu entsprechen.

Ich konnte viel mehr Details über die Pre-Header auch lernen. Es hat folgenden Aufbau:

     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 

Die nicht markierten Bits kann ich noch nicht entschlüsseln. Was ich jetzt sehe, ist, dass die Pre-Header-Codes selbst einige zusätzliche Bits enthalten (beachte das ?? zwischen SkL und 3, oben). Sie sind nicht alle geraden 3-Bit-Codes.

Also, die einzigen wesentlichen Informationen, die jetzt fehlen, sind:

• Wie die Pre-Header für zusätzliche Bits und so weiter zu analysieren; und
• Wie viele Abstandscodes folgen die wörtliche Codes

Wenn ich diese Informationen hatte, konnte ich tatsächlich die restlichen Daten füttern durch manuell zlib die Codelänge Wörterbuch liefert zusammen mit der richtigen Anzahl von wörtlichen vs. Abstand Codes. Alles nach diesem Header folgt DEFLATE dem Buchstaben nach.

Hier sind einige weitere Beispielheader mit den Bitlängencodes, die zusammen mit der Anzahl der Literal- und Längencodes angezeigt werden. In jedem Fall konnte ich die Antworten zurückentwickeln, aber ich kann die entschlüsselten Bits nicht mit diesen Statistiken vergleichen.

Sample 1 
(273 literals, 35 length, 308 total) 
????? ???????? ??? ? HLEN 0 SkS SkL ?? 3 ? 4 ? 5 6 7 8 9  HLIT 
00000 00100010 010 0 1100 110 101 110 10 111 0 111 0 101 011 010 001 110  100010001 

Sample 2 
(325 literal, 23 length, 348 total) 
????? ???????? ??? ? HLEN 0 SkS SkL ?? 3 4 5 6 7 8 9   HLIT 
00000 00110110 001 0 1100 101 101 110 10 110 000 101 000 011 010 001   101000101 

Sample 3 
(317 literal, 23 length, 340 total) 
????? ???????? ??? ? HLEN 0 SkS SkL ??? 4 5 ? 6 7 8 9   HLIT 
00000 01000100 111 0 1100 000 101 111 011 110 111 0 100 011 010 001   100111101 

Sample 4 
(279 literals, 18 length, 297 total) 
????? ???????? ??? ? 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 

Sample 5 
(258 literals, 12 length, 270 total) 
????? ???????? ??? ? HLEN 0 SkS SkL ?? 2 3 4       HLIT 
00000 00000010 000 0 0111 011 000 011 01 010 000 001       100000010 

Ich hoffe immer noch, dass jemand einen nicht standardmäßigen DEFLATE-style-Header wie diesen zuvor gesehen hat. Oder vielleicht sehen Sie ein Muster, das ich nicht sehen kann ... Vielen Dank für weitere Informationen.

Answer 1

Nun, endlich habe ich es geschafft, es vollständig zu knacken. Es verwendete tatsächlich eine Implementierung von LZ77 und Huffman-Kodierung, aber sehr viel eine Nicht-Standard-DEFLATE-ähnliche Methode zum Speichern und Ableiten der Codes.

Wie sich herausstellt, waren die Pre-Header-Codes selbst fixierte Wörterbuch-Huffman-Codes und keine wörtlichen Bitlängen. Das Herausfinden der Entfernungscodes war ähnlich schwierig, da sie im Gegensatz zu DEFLATE nicht die gleichen Bitlängencodes wie die Literale verwendeten, sondern stattdessen ein anderes festes Huffman-Wörterbuch verwendeten.

Der Take Away für alle Interessierten ist, dass es anscheinend alte Dateiformate gibt, die DEFLATE-Derivate verwenden. Sie können mit Entschlossenheit rückentwickelt werden. In diesem Fall habe ich wahrscheinlich insgesamt etwa 100 Stunden verbracht, wobei die meisten manuell komprimierte Daten von den bekannten dekomprimierten Samples rekonstruierten, um die Codemuster zu finden. Sobald ich genug darüber wusste, was sie tun sollten, um diesen Prozess zu automatisieren, konnte ich ein paar Dutzend Beispiel-Header erstellen und dadurch die Muster finden.

Ich verstehe immer noch nicht, warum sie dies taten, anstatt ein Standardformat zu verwenden. Es muss eine Menge Arbeit geleistet haben, um ein neues Komprimierungsformat abzuleiten, anstatt nur ZLib zu verwenden. Wenn sie versuchen würden, die Daten zu verschleiern, hätten sie das viel effektiver tun können, indem sie es verschlüsseln, mit anderen Werten xorieren, usw. Nein, nichts davon.Sie haben einfach beschlossen, ihren Chefs ihr Genie zu zeigen, denke ich, indem sie etwas "Neues" vorbrachten, auch wenn die Unterschiede zum Standard trivial waren und keinen weiteren Wert hatten, als MIR das Leben schwer zu machen. :)

Danke an diejenigen, die ihre Eingabe angeboten haben.