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

Question

Tengo algunas preguntas que me han estado preocupando por un tiempo.

La prueba de entropía se utiliza a menudo para identificar datos encriptados. La entropía alcanza su máximo cuando los bytes de los datos analizados están distribuidos uniformemente. La prueba de entropía identifica datos encriptados, porque estos datos tienen una distribución uniforme, al igual que los datos comprimidos, que se clasifican como encriptados al usar la prueba de entropía.

Ejemplo: La entropía de un archivo JPG es de 7,9961532 bits/byte, la entropía de un contenedor TrueCrypt es de 7,9998857. Esto significa que con la prueba de entropía no puedo detectar una diferencia entre datos encriptados y comprimidos. PERO: como puedes ver en la primera imagen, obviamente los bytes del archivo JPG no están distribuidos uniformemente (al menos no tan uniformemente como los bytes del contenedor TrueCrypt).

Otra prueba puede ser el análisis de frecuencia. Se mide la distribución de cada byte y se realiza, por ejemplo, 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 datos JPG y TrueCrypt, el resultado es diferente.

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

Ahora mi pregunta: ¿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 a todos por cualquier respuesta/idea!

Imagen JPG Contenedor TrueCrypt

Answer 1

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

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

  $$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 cercanas tanto entre sí como al límite teórico de $H_0 = 8$.

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

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

  Utilizando esta fórmula podemos deducir que una entropía de $7.9961532$, que es una discrepancia de $0.0038468$, es producida 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 el $0.5$%. Un cálculo similar para una entropía de $7.9998857$ corresponde a una desviación cuadrática media en $p_i$ de solo el 0.09%.

  (En una figura como la última en la pregunta, cuya altura abarca alrededor de $1000$ píxeles, si asumimos que las alturas de las barras representan los $p_i$, entonces una variación del $0.09$% 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. Así es como se ve. Un RMS del $0.5$%, por otro lado, estaría asociado con variaciones de alrededor de $6$ píxeles en promedio, pero rara vez superando los $15$ píxeles aproximadamente. Esto no es lo que parece la figura superior, con sus obvias variaciones de $100$ o más píxeles. Por lo tanto, estoy suponiendo que estas figuras 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 suposiciones, porque la pregunta no nos dice cómo se utilizaron 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, necesita tener en cuenta la variación aleatoria. En este caso, las frecuencias observadas (a partir de las cuales se han calculado las entropías) tenderán a variar de las verdaderas frecuencias subyacentes debido al azar. Estas variaciones se traducen, a través de las fórmulas dadas anteriormente, en variaciones de la entropía observada respecto a la entropía verdaderamente subyacente. Dados datos suficientes, podemos detectar si la verdadera entropía difiere del valor de $8$ asociado con una distribución uniforme. Manteniendo todo lo demás igual, la cantidad de datos necesaria para detectar una discrepancia media de solo el $0.09$% en comparación con una discrepancia media del 0.5% será aproximadamente $(0.5/0.09)^2$ veces mayor: en este caso, eso resulta ser más de $33$ veces más datos.

En consecuencia, es muy 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 sería incapaz de distinguir $7.99988\ldots$ de $8$. (Esta situación, por cierto, se llama un falso negativo, no un "falso positivo", porque ha fallado en identificar la falta de uniformidad, que se considera un resultado "negativo".) Por lo tanto, propongo que (a) las entropías se han calculado correctamente y (b) la cantidad de datos explica adecuadamente lo sucedido.

---

Por cierto, las figuras parecen ser inútiles o engañosas, porque carecen de etiquetas adecuadas. Aunque la inferior parece representar una distribución casi uniforme (asumiendo que el eje x es discreto y corresponde a los $256$ valores de bytes posibles y el eje y es proporcional a la frecuencia observada), la superior no puede corresponder a una entropía en absoluto cercana a $8$. Sospecho que el cero del eje y en la figura superior no se ha mostrado, por lo que las discrepancias entre las frecuencias se han exagerado. (Tufte diría que esta figura tiene un gran Factor de Mentira.)