¿Qué estadísticas se pueden usar para identificar datos pseudoaleatorios?

Question

¿Qué estadísticas se pueden usar para identificar datos pseudoaleatorios?

#1 de Thomas Pornin (10 votos)
#2 de mr.spuratic (0 votos)

19

Estoy trabajando en un código que intenta identificar archivos cuyo contenido parece ser "aleatorio". Como tal, estoy buscando medidas estadísticas que puedan usarse para identificar dicha aleatoriedad.

He implementado lo siguiente hasta ahora:

entropía de Shannon de la muestra (es decir, -∑ p (x _i) log ₂ p (x _i) sobre la muestra X )
Varianza de la muestra de bytes (0.0 es una puntuación perfecta)
media bitwise (0.5 es una puntuación perfecta)
media bitwise distribuida entre los bits 0 a 7 de cada byte (en busca de cualquier variación significativa)
Porcentaje de bytes dentro del rango 0x20 & leq; b & leq; 0x7E (37.11% es una puntuación perfecta)
Recuentos de pares de bits (es decir, comprobación de recuentos iguales de 00, 01, 10, 11)
Distancias de bytes repetidas (es decir, buscando xx , x*x , x**x , x***x , ... patrones)

Estos parecen dar una medida razonable de "aleatoriedad" uniforme, ya que 128 bytes generados por la concatenación de dos hashes SHA512 se pueden distinguir fácilmente de un texto ASCII o un archivo ejecutable simplemente mirando las estadísticas.

Sin embargo, me gustaría saber si hay algún otro indicador sólido que deba examinar que pueda indicar que los datos de muestra fueron generados por un PRNG criptográfico.

Actualización: Para ser absolutamente claro, no estoy tratando de probar la calidad de un PRNG como fuente de aleatoriedad criptográfica. Estoy intentando distinguir entre archivos no aleatorios (por ejemplo, archivos ejecutables, JPEG, archivos, etc.) y archivos aleatorios (por ejemplo, archivos de claves TrueCrypt). Hasta ahora, mis pruebas se usan para identificar datos obviamente no aleatorios (por ejemplo, texto ASCII) y datos que no están distribuidos de manera uniforme de alguna manera. Estoy buscando otras formas de probar esto.

statistics random entropy

pregunta Polynomial 11.03.2013 - 05:20

fuente

2 respuestas

0

enlace usa lo siguiente

prueba de Chi cuadrado
media aritmética
Estimación de Monte Carlo Pi
Coeficiente de correlación serial

Es posible que también desee agregar "incompresibilidad" (esto también significa que es posible que necesite identificar los archivos comprimidos para eliminarlos). La sugerencia de Diehard ( y Dieharder ) de Dan D parece una solución muy completa. ( Editar: Dieharder está estrictamente orientado a probar PRNG, no a instantáneas de su salida, y definitivamente no es adecuado para muestras de datos pequeños).

Su tarea comparte algunos de los problemas relacionados con la estadística File Carving y la búsqueda forense de datos cifrados: cuanto más pequeños sean los datos establece cuanto más difícil es ser definitivo sobre si es "aleatorio".

respondido por el mr.spuratic 11.03.2013 - 11:25

fuente

Lea otras preguntas en las etiquetas statistics random entropy

¿Cómo demostrar el descifrado de Skype usando las herramientas de FOSS? ¿Alguien podría explicar partes del Firefox de 0 días del FBI?

score 10 · Accepted Answer

Durante la competición AES , el organismo organizador (el NIST) se tomó la molestia de realizar extensas pruebas estadísticas en el salida de los 15 cifrados en bloque presentados, con lo que se creía que era el estándar de oro de tales pruebas, las Pruebas duras . No encontraron nada, por supuesto. Los comentarios de los criptógrafos en ese momento indicaron que estas pruebas eran un poco ridículas en el contexto de los algoritmos criptográficos (comentarios no oficiales, por supuesto: sería descortés avergonzar al anfitrión del evento); Fue bueno para las Relaciones Públicas que alguien las administre, pero no se esperaba nada de ello.

Esto ilustra la diferencia entre aleatoriedad estadística , como se necesita, por ejemplo, para impulsar grandes simulaciones de sistemas físicos, y imprevisibilidad , que se requiere para la seguridad. Considere, por ejemplo, lo siguiente PRNG :

Establece un contador para una semilla de 128 bits.
Para producir los siguientes 128 bits del PRNG, incremente el contador en 1, luego encripte ese valor con AES y una clave de todo cero, obteniendo los 128 bits.

Este PRNG pasará con éxito todas las pruebas de la suite Diehard; es estadísticamente "perfecto" en lo que concierne a las pruebas (la desviación de pure alea puede ser detectable después de generar aproximadamente 2 bits ⁷¹, es decir, más de 200 millones de terabytes). Sin embargo, para seguridad , es terrible, ya que es trivial predecir la salida futura una vez que se hayan observado 128 bits de salida (descifre estos 128 bits con AES y una clave de todo cero: esto le dará el valor del contador actual).

Resumen: un PRNG criptográficamente seguro produce una salida que no se puede distinguir del azar; no solo con pruebas estadísticas, sino también por alguien que conoce exactamente el algoritmo PRNG específico que se utilizó potencialmente. Si tiene una herramienta estadística que puede mostrar que una secuencia dada de bytes proviene de un PRNG, entonces no solo ha demostrado que el PRNG no es criptográficamente seguro, sino que también es muy malo. Incluso hash de Dave es "aleatorio" desde el punto de vista de las pruebas de Diehard.

En palabras más cortas, su herramienta no detectará la aleatoriedad que se generó con algo de experiencia, pero tampoco detectará la mayoría de no aleatoriedad de los aficionados completos. Con estas herramientas, no está apuntando a "no criptógrafos que deberían saber más que a usar esquemas caseros", sino a "chimpancés a los que no se les debe permitir tocar un teclado".

Nota: las buenas esteganografía cifran los datos antes de introducirlos en el medio de transporte, precisamente Para evitar la detección de la herramienta estadística. El cifrado también debería producir bits indistinguibles de la aleatoriedad.