Vergleich der Entropie und Verteilung von Bytes in komprimierten / verschlüsselten Daten

8

Ich habe eine Frage, die mich eine Weile beschäftigt.

Der Entropietest wird häufig verwendet, um verschlüsselte Daten zu identifizieren. Die Entropie erreicht ihr Maximum, wenn die Bytes der analysierten Daten gleichmäßig verteilt sind. Der Entropietest identifiziert verschlüsselte Daten, da diese Daten eine gleichmäßige Verteilung aufweisen - wie komprimierte Daten, die bei Verwendung des Entropietests als verschlüsselt klassifiziert werden.

Beispiel: Die Entropie einer JPG-Datei beträgt 7.9961532 Bit / Byte, die Entropie eines TrueCrypt-Containers beträgt 7.9998857. Dies bedeutet, dass ich mit dem Entropietest keinen Unterschied zwischen verschlüsselten und komprimierten Daten feststellen kann. ABER: Wie Sie auf dem ersten Bild sehen können, sind die Bytes der JPG-Datei offensichtlich nicht gleichmäßig verteilt (zumindest nicht so einheitlich wie die Bytes aus dem TrueCrypt-Container).

Ein weiterer Test kann die Frequenzanalyse sein. Die Verteilung jedes Bytes wird gemessen und z. B. wird ein Chi-Quadrat-Test durchgeführt, um die Verteilung mit einer hypothetischen Verteilung zu vergleichen. Als Ergebnis erhalte ich einen p-Wert. Wenn ich diesen Test mit JPG- und TrueCrypt-Daten durchführe, ist das Ergebnis anders.

Der p-Wert der JPG-Datei ist 0, was bedeutet, dass die Verteilung aus statistischer Sicht nicht einheitlich ist. Der p-Wert der TrueCrypt-Datei beträgt 0,95, was bedeutet, dass die Verteilung nahezu gleichmäßig ist.

Meine Frage jetzt: Kann mir jemand sagen, warum der Entropietest solche falsch positiven Ergebnisse liefert? Ist es die Skala der Einheit, in der der Informationsgehalt ausgedrückt wird (Bits pro Byte)? Ist zB der p-Wert aufgrund einer feineren Skala eine viel bessere "Einheit"?

Vielen Dank für jede Antwort / Idee!

JPG-Image Geben Sie hier die Bildbeschreibung ein TrueCrypt-Container Geben Sie hier die Bildbeschreibung ein

tommynogger
quelle
2
Obwohl Sie zwei Beispiele für Entropien angeben, wenden Sie nichts an, was als "Entropietest" bezeichnet wird. Können Sie uns explizit sagen, was dieser Test ist und wie er mit Ihren beiden Dateien funktioniert?
whuber
Sie sollten jetzt in der Lage sein, die Bilder zu posten. Bitte geben Sie weitere Details gemäß dem Kommentar von @ whuber an.
Kardinal
Für die Entropie berechne ich die Wahrscheinlichkeit, mit der jede Zahl (0-255) erscheint. dann fasse ich alle log (Wahrscheinlichkeit) zusammen und habe die Entropie. Software wie encase, die für forensische Untersuchungen verwendet wird, verwendet die Entropie zum Erkennen verschlüsselter Daten. Aber wie Sie sehen können, führt die Entropie zu vielen Fehlalarmen. Andere Ansätze wie das Chi-Quadrat haben viel bessere Ergebnisse. Die beiden Tests werden jedoch für dasselbe verwendet, um die Vereinheitlichung von Bytes festzustellen. Wie kann das Ergebnis so unterschiedlich sein?
Tommynogger
Entschuldigung, meine Beschreibung war falsch ... Ich berechne die Entropiesumme (p log p), wobei p die Wahrscheinlichkeit für jede Zahl ist.
Tommynogger
Ich denke, es ist sehr wahrscheinlich, dass Sie die Entropie falsch berechnen. Es könnte sich lohnen, weitere Details und einen Beispielcode anzugeben. Haben Sie die Wahrscheinlichkeitsverteilung korrekt normalisiert (so summiert sie sich zu eins)? Wie machst du das genauer? Sind die beiden Abbildungen auf derselben y-Skala? Wenn dies der Fall ist, sollte die JPEG-Entropie meiner Meinung nach niedriger sein, aber liegen sie im gleichen Maßstab?
Throp

Antworten:

6

Diese Frage enthält noch keine wesentlichen Informationen, aber ich denke, ich kann einige intelligente Vermutungen anstellen:

  • Die Entropie einer diskreten Verteilung ist definiert alsp=(p0,p1,,p255)

    H(p)=i=0255pilog2pi.
  • Da eine konkave Funktion ist, wird die Entropie maximiert, wenn alle gleich sind. Da sie eine Wahrscheinlichkeitsverteilung bestimmen (sie summieren sich zu Eins), tritt dies auf, wenn für jedes , woraus die maximale Entropie istlogpipi=28i

    H0=i=025528log2(28)=i=025528×8=8.
  • Die Entropien von Bit / Byte ( dh unter Verwendung von binären Logarithmen) und liegen sowohl nahe als auch nahe an der theoretischen Grenze von .7.99615327.9998857H0=8

    Wie knapp? Das Erweitern von in einer Taylor-Reihe um das Maximum zeigt, dass die Abweichung zwischen und einer Entropie gleich istH(p)H0H(p)

    H0H(p)=i(pi28)2228log(2)+O(pi28)3.

    Mit dieser Formel können wir schließen, dass eine Entropie von , was einer Diskrepanz von , durch eine Abweichung des quadratischen Mittelwerts von nur zwischen und der perfekt gleichmäßigen Verteilung von . Dies entspricht einer durchschnittlichen relativen Abweichung von nur %. Eine ähnliche Berechnung für eine Entropie von entspricht einer RMS-Abweichung in von nur 0,09%.0,0038468 0,00002099 p i 2 - 8 0,5 7,9998857 p i7.99615320.00384680.00002099pi280.57.9998857pi

    (In einer Abbildung wie der untersten in der Frage, deren Höhe etwa Pixel umfasst, entspricht eine Variation von % RMS Änderungen von nur einem Pixel über oder unter der mittleren Höhe , wenn wir annehmen, dass die Höhe der Balken und fast immer weniger als drei Pixel. So sieht es aus. Ein Effektivwert von % würde dagegen mit Abweichungen von durchschnittlich etwa Pixeln verbunden sein, aber selten mehr als Pixel oder so. Das ist nicht das, was Die obere Figur sieht mit ihren offensichtlichen Variationen von oder mehr Pixeln so aus. Ich vermute daher, dass dies bei diesen Figuren nicht der Fall istp i 0,09 0,5 6 15 1001000pi0.090.5615100 direkt miteinander vergleichbar.)

In beiden Fällen handelt es sich um kleine Abweichungen, aber eine ist mehr als fünfmal kleiner als die andere. Jetzt müssen wir einige Vermutungen anstellen, da die Frage weder Aufschluss darüber gibt, wie die Entropien zur Bestimmung der Einheitlichkeit verwendet wurden, noch darüber, wie viele Daten vorhanden sind. Wenn ein echter "Entropietest" angewendet wurde, muss er wie jeder andere statistische Test die zufällige Variation berücksichtigen. In diesem Fall variieren die beobachteten Frequenzen (aus denen die Entropien berechnet wurden) aufgrund des Zufalls tendenziell von den tatsächlich zugrunde liegenden Frequenzen . Diese Variationen führen über die oben angegebenen Formeln zu Variationen der beobachteten Entropie von der tatsächlich zugrunde liegenden Entropie. Bei ausreichenden DatenWir können feststellen, ob die wahre Entropie von dem Wert abweicht, der mit einer gleichmäßigen Verteilung verbunden ist. Wenn alle anderen Dinge gleich sind, wird die Datenmenge, die benötigt wird, um eine mittlere Diskrepanz von nur % im Vergleich zu einer mittleren Diskrepanz von % festzustellen , ungefähr mal so groß sein: In diesem Fall funktioniert das bis mehr als mal so viel sein.0,09 0,5 ( 0,5 / 0,09 ) 2 3380.090.5(0.5/0.09)233

Folglich ist es durchaus möglich , dass es genügend Daten , um zu bestimmen , dass eine beobachtete Entropie von unterscheidet sich deutlich von , während eine äquivalente Menge an Daten nicht in der Lage wäre , zu unterscheiden von . (Diese Situation, nebenbei bemerkt , ist ein sogenannter falsch negativ , kein „falsch positiv“ , weil es versäumt einen Mangel an Einheitlichkeit zu identifizieren (die eine „negative“ Ergebnis betrachtet wird).) Daher schlage ich vor , dass (a ) Die Entropien wurden tatsächlich korrekt berechnet und (b) die Datenmenge erklärt angemessen, was passiert ist.8 7.99988 87.99687.999888


Im Übrigen scheinen die Zahlen entweder nutzlos oder irreführend zu sein, da ihnen entsprechende Etiketten fehlen. Obwohl die untere eine nahezu gleichmäßige Verteilung darzustellen scheint (vorausgesetzt, die x-Achse ist diskret und entspricht den möglichen Bytewerten und die y-Achse ist proportional zur beobachteten Frequenz), kann die obere möglicherweise nirgendwo einer Entropie entsprechen in der Nähe von . Ich vermute, dass die Null der y-Achse in der oberen Abbildung nicht angezeigt wurde, so dass die Abweichungen zwischen den Frequenzen übertrieben sind. (Tufte würde sagen, diese Figur hat einen großen Lügenfaktor.)82568

whuber
quelle
Die berechnete Entropie bezieht sich auf die obigen Bilder. Die JPG-Datei hat eine Größe von ca. 5MB, der TrueCrypt-Container ca. 100MB. Selbst wenn ich ein 5-MB-Stück des TrueCrypt-Containers nehme, ist es gleichmäßig verteilt - viel gleichwertiger als die JPG-Datei. Ihre Antwort gibt viele Details über die Entropie, die ich nicht gehört habe, danke dafür! Vielleicht einige Details zu viel, ich mag Statistiken nicht zu sehr ... Ich habe gerade versucht, Statistiken für eine Weile zu "verwenden". Eine Frage bleibt noch offen: Was ist der Grund, warum bei der Frequenzanalyse (zB Chi-Quadrat) unterschieden werden kann, nicht aber bei der Entropie?
Tommynogger
Der Chi-Quadrat-Test berücksichtigt die wahrscheinliche Menge an Zufallsschwankungen. Soweit ich das beurteilen kann, funktioniert Ihr Vergleich der Entropien nicht. Das scheint die Ursache des Unterschieds zu sein. Sie müssen auch vorsichtig sein, wie Sie die Ergebnisse interpretieren: Die Dinge können zu gleichmäßig verteilt sein ; das kann auch als Beweis gegen zufälliges Verhalten genommen werden.
whuber