Comparación de entropía y distribución de bytes en datos comprimidos / cifrados

Tengo una pregunta que me ocupa por un tiempo.

La prueba de entropía se usa a menudo para identificar datos cifrados. La entropía alcanza su máximo cuando los bytes de los datos analizados se distribuyen uniformemente. La prueba de entropía identifica datos cifrados, porque estos datos tienen una distribución uniforme, como los datos comprimidos, que se clasifican como cifrados cuando se usa la prueba de entropía.

Ejemplo: la entropía de algún archivo JPG es 7,9961532 Bits / Byte, la entropía de algún contenedor TrueCrypt es 7,9998857. Esto significa que con la prueba de entropía no puedo detectar una diferencia entre datos cifrados y comprimidos. PERO: como puede ver en la primera imagen, obviamente los bytes del archivo JPG no están distribuidos uniformemente (al menos no tan uniformes como los bytes del contenedor de cripta verdadera).

Otra prueba puede ser el análisis de frecuencia. Se mide la distribución de cada byte y, por ejemplo, se realiza una prueba de chi-cuadrado para comparar la distribución con una distribución hipotética. Como resultado, obtengo un valor p. Cuando realizo esta prueba en JPG y TrueCrypt-data, el resultado es diferente.

El valor p del archivo JPG es 0, lo que significa que la distribución desde una vista estadística no es uniforme. El valor p del archivo TrueCrypt es 0,95, lo que significa que la distribución es casi perfectamente uniforme.

Mi pregunta ahora: ¿Alguien puede decirme por qué la prueba de entropía produce falsos positivos como este? ¿Es la escala de la unidad, en la que se expresa el contenido de la información (bits por byte)? ¿Es, por ejemplo, el valor p una "unidad" mucho mejor, debido a una escala más fina?

Muchas gracias muchachos por cualquier respuesta / ideas!

JPG-Image TrueCrypt-Container

Esta pregunta aún carece de información esencial, pero creo que puedo hacer algunas suposiciones inteligentes:

• La entropía de una distribución discreta.$\mathbb{p} = (p_0, p_1, \ldots, p_{255})$ Se define como

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

• Porque $-\log$ es una función cóncava, la entropía se maximiza cuando todo $p_i$son iguales. Como determinan una distribución de probabilidad (suman la unidad), esto ocurre cuando$p_i = 2^{-8}$ para cada $i$, de donde es la entropía máxima

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

• Las entropías de $7.9961532$bits / byte ( es decir , utilizando logaritmos binarios) y$7.9998857$ son extremadamente cercanos entre sí y al límite teórico de $H_0 = 8$.

  ¿Qué cerca? En expansión$H(\mathbb{p})$ en una serie de Taylor alrededor del máximo muestra que la desviación entre $H_0$ y cualquier entropía $H(\mathbb{p})$ es igual

  $$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.$$

  Usando esta fórmula podemos deducir que una entropía de $7.9961532$, que es una discrepancia de $0.0038468$, se produce por una desviación cuadrática media de solo $0.00002099$ Entre los $p_i$ y la distribución perfectamente uniforme de $2^{-8}$. Esto representa una desviación relativa promedio de solo$0.5$% Un cálculo similar para una entropía de$7.9998857$ corresponde a una desviación RMS en $p_i$ de solo 0.09%.

  (En una figura como la inferior en la pregunta, cuya altura abarca aproximadamente $1000$ píxeles, si suponemos que las alturas de las barras representan el $p_i$, Entonces un $0.09$La variación del% RMS corresponde a cambios de solo un píxel por encima o por debajo de la altura media, y casi siempre menos de tres píxeles. Eso es exactamente lo que parece. UNA$0.5$El% RMS, por otro lado, estaría asociado con variaciones de aproximadamente $6$ píxeles en promedio, pero rara vez exceden $15$píxeles más o menos. Eso no es como se ve la figura superior, con sus variaciones obvias de$100$o más píxeles Por lo tanto, supongo que estas cifras no son directamente comparables entre sí).

En ambos casos, estas son pequeñas desviaciones, pero una es más de cinco veces más pequeña que la otra. Ahora tenemos que hacer algunas conjeturas, porque la pregunta no nos dice cómo se usaron las entropías para determinar la uniformidad, ni nos dice cuántos datos hay. Si se ha aplicado una verdadera "prueba de entropía", entonces, como cualquier otra prueba estadística, debe tener en cuenta la variación de probabilidad. En este caso, las frecuencias observadas (a partir de las cuales se han calculado las entropías) tenderán a variar de las frecuencias subyacentes verdaderas debido al azar. Estas variaciones se traducen, a través de las fórmulas dadas anteriormente, en variaciones de la entropía observada desde la entropía subyacente verdadera. Dados datos suficientes, podemos detectar si la verdadera entropía difiere del valor de $8$asociado con una distribución uniforme. En igualdad de condiciones, la cantidad de datos necesarios para detectar una discrepancia media de solo$0.09$% en comparación con una discrepancia media de $0.5$% será aproximadamente $(0.5/0.09)^2$ veces más: en este caso, eso resulta ser más que $33$ veces tanto.

En consecuencia, es bastante posible que haya suficientes datos para determinar que una entropía observada de $7.996\ldots$difiere significativamente de$8$ mientras que una cantidad equivalente de datos no podría distinguir $7.99988\ldots$ desde $8$. (Esta situación, por cierto, se llama falso negativo , no "falso positivo", porque no ha podido identificar una falta de uniformidad (lo que se considera un resultado "negativo")). En consecuencia, propongo que (un ) las entropías se han calculado correctamente y (b) la cantidad de datos explica adecuadamente lo que ha sucedido.

Por cierto, las cifras parecen ser inútiles o engañosas, porque carecen de etiquetas apropiadas. Aunque el de abajo parece representar una distribución casi uniforme (suponiendo que el eje x es discreto y corresponde al$256$ posibles valores de bytes y el eje y es proporcional a la frecuencia observada), el superior no puede corresponder a una entropía cerca $8$. Sospecho que no se ha mostrado el cero del eje y en la figura superior, por lo que las discrepancias entre las frecuencias son exageradas. (Tufte diría que esta cifra tiene un gran factor de mentira).