Comparaison de l'entropie et de la distribution des octets dans les données compressées / cryptées

J'ai une question qui m'occupe depuis un moment.

Le test d'entropie est souvent utilisé pour identifier les données chiffrées. L'entropie atteint son maximum lorsque les octets des données analysées sont distribués uniformément. Le test d'entropie identifie les données chiffrées, car ces données ont une distribution uniforme, comme les données compressées, qui sont classées comme chiffrées lors de l'utilisation du test d'entropie.

Exemple: l'entropie de certains fichiers JPG est de 7,9961532 bits / octet, l'entropie de certains conteneurs TrueCrypt est de 7,9998857. Cela signifie qu'avec le test d'entropie, je ne peux pas détecter de différence entre les données chiffrées et compressées. MAIS: comme vous pouvez le voir sur la première image, les octets du fichier JPG ne sont évidemment pas distribués uniformément (du moins pas aussi uniformes que les octets du conteneur truecrypt).

Un autre test peut être l'analyse de fréquence. La distribution de chaque octet est mesurée et, par exemple, un test du chi carré est effectué pour comparer la distribution avec une distribution hypothétique. en conséquence, j'obtiens une valeur p. lorsque j'effectue ce test sur JPG et TrueCrypt-data, le résultat est différent.

La valeur de p du fichier JPG est 0, ce qui signifie que la distribution à partir d'une vue statistique n'est pas uniforme. La valeur de p du fichier TrueCrypt est de 0,95, ce qui signifie que la distribution est presque parfaitement uniforme.

Ma question maintenant: quelqu'un peut-il me dire pourquoi le test d'entropie produit des faux positifs comme celui-ci? Est-ce l'échelle de l'unité dans laquelle le contenu de l'information est exprimé (bits par octet)? Par exemple, la valeur de p est-elle une bien meilleure "unité", en raison d'une échelle plus fine?

Merci beaucoup pour toute réponse / idée!

Conteneur TrueCrypt JPG-Image

Cette question manque encore d'informations essentielles, mais je pense que je peux faire quelques suppositions intelligentes:

• L' entropie d'une distribution discrète$\mathbb{p} = (p_0, p_1, \ldots, p_{255})$ est défini comme

  $$H(\mathbb{p}) = -\sum_{i=0}^{255} p_i \log_2{p_i}.$$

• Parce que $-\log$ est une fonction concave, l'entropie est maximisée lorsque tous $p_i$sont égaux. Puisqu'ils déterminent une distribution de probabilité (ils résument à l'unité), cela se produit lorsque$p_i = 2^{-8}$ pour chaque $i$, d'où l'entropie maximale est

  $$H_0 = -\sum_{i=0}^{255} 2^{-8} \log_2{(2^{-8})} = \sum_{i=0}^{255} 2^{-8}\times 8 = 8.$$

• Les entropies de $7.9961532$bits / octet ( c'est -à- dire en utilisant des logarithmes binaires) et$7.9998857$ sont extrêmement proches les uns des autres et de la limite théorique de $H_0 = 8$.

  A quelle distance? Expansion$H(\mathbb{p})$ dans une série de Taylor autour du maximum montre que l'écart entre $H_0$ et toute entropie $H(\mathbb{p})$ équivaut à

  $$H_0 - H(\mathbb{p}) = \sum_i \frac{(p_i - 2^{-8})^2}{2 \cdot 2^{-8} \log(2)} + O(p_i - 2^{-8})^3.$$

  En utilisant cette formule, nous pouvons déduire qu'une entropie de $7.9961532$, qui est une différence de $0.0038468$, est produite par une déviation quadratique moyenne de seulement $0.00002099$ entre le $p_i$ et la distribution parfaitement uniforme de $2^{-8}$. Cela représente un écart relatif moyen de seulement$0.5$%. Un calcul similaire pour une entropie de$7.9998857$ correspond à un écart RMS $p_i$ de seulement 0,09%.

  (Dans une figure comme celle du bas de la question, dont la hauteur s'étend sur environ $1000$ pixels, si nous supposons que les hauteurs des barres représentent la $p_i$, puis un $0.09$La variation% RMS correspond à des changements d'un seul pixel au-dessus ou au-dessous de la hauteur moyenne, et presque toujours moins de trois pixels. Voilà à quoi ça ressemble. UNE$0.5$En revanche, le% RMS serait associé à des variations d'environ $6$ pixels en moyenne, mais dépassant rarement $15$pixels ou plus. Ce n'est pas à cela que ressemble la figure du haut, avec ses variations évidentes de$100$ou plusieurs pixels. Je suppose donc que ces chiffres ne sont pas directement comparables entre eux.)

Dans les deux cas, ce sont de petits écarts, mais l'un est plus de cinq fois plus petit que l'autre. Maintenant, nous devons faire quelques suppositions, car la question ne nous dit pas comment les entropies ont été utilisées pour déterminer l'uniformité, ni nous dire combien de données il y a. Si un véritable "test d'entropie" a été appliqué, alors comme tout autre test statistique, il doit tenir compte de la variation du hasard. Dans ce cas, les fréquences observées (à partir desquelles les entropies ont été calculées) auront tendance à différer des véritables fréquences sous-jacentes en raison du hasard. Ces variations se traduisent, via les formules données ci-dessus, en variations de l' entropie observée à partir de la véritable entropie sous-jacente. Compte tenu des données suffisantes, nous pouvons détecter si la véritable entropie diffère de la valeur de $8$associée à une distribution uniforme. Toutes choses étant égales par ailleurs, la quantité de données nécessaires pour détecter un écart moyen de$0.09$% par rapport à un écart moyen de $0.5$% sera approximativement $(0.5/0.09)^2$ fois: dans ce cas, cela équivaut à plus que $33$ fois autant.

Par conséquent, il est tout à fait possible qu'il y ait suffisamment de données pour déterminer qu'une entropie observée de $7.996\ldots$diffère considérablement de$8$ alors qu'une quantité équivalente de données serait incapable de distinguer $7.99988\ldots$ de $8$. (Soit dit en passant, cette situation est qualifiée de faux négatif et non de «faux positif», car elle n'a pas permis d'identifier un manque d'uniformité (ce qui est considéré comme un résultat «négatif»).) Par conséquent, je propose que (un ) les entropies ont en effet été correctement calculées et (b) la quantité de données explique correctement ce qui s'est passé.

Soit dit en passant, les chiffres semblent être inutiles ou trompeurs, car ils manquent d'étiquettes appropriées. Bien que celui du bas semble représenter une distribution presque uniforme (en supposant que l'axe des x est discret et correspond à la$256$ valeurs d'octets possibles et l'axe y est proportionnel à la fréquence observée), celui du haut ne peut pas correspondre à une entropie n'importe où près $8$. Je soupçonne que le zéro de l'axe des y dans la figure du haut n'a pas été montré, de sorte que les écarts entre les fréquences sont exagérés. (Tufte dirait que ce chiffre a un grand facteur de Lie.)