Detectar el uso de PRNG de la salida

5

Pregunta: ¿Hay alguna forma de detectar el uso de un PRNG estrictamente observando el resultado provisto por una aplicación?

Antecedentes: durante una auditoría de un algoritmo de generación de claves que sabía que se basaba en la LCG noté que el secuenciador de Burp calificaba la entropía de las claves como fuerte, lo cual es falso, ya que son predecibles. Luego realicé la misma prueba con enteros brutos generados por el módulo aleatorio basado en Mersenne Twister de Python para ver la entropía con la calificación alta otra vez.

La falla de esta herramienta me hizo preguntarme si hay herramientas / enfoques disponibles para detectar realmente el uso de PRNG desde la salida.

    
pregunta 0x90 09.01.2013 - 03:15
fuente

1 respuesta

8

Si el PRNG es criptográficamente fuerte , entonces, por definición, su salida no se puede distinguir de los bytes aleatorios. Ese es el experimento mental mediante el cual se supone que se prueba un PRNG: se le dan dos cajas negras al atacante, una que implementa el PRNG, la otra que produce bytes realmente aleatorios (la que contiene un gnomo que lanza los dados muy rápido ). El objetivo del atacante es encontrar qué caja contiene el PRNG, con una mejor tasa de éxito que la suerte pura (es decir, 50%).

Los PRNG que son NO criptográficamente fuertes, como Mersenne Twister, pueden ser reconocidos como tales por un atacante que los ataque específicamente . Pero no necesariamente por una herramienta genérica de análisis estadístico.

Para tomar una analogía, existen PRNG que son fuertes contra los ejércitos de criptógrafos que conocen el código fuente completo de PRNG y tienen acceso a mil computadoras grandes. También hay PRNG que puede ser declarado no aleatorio por una marmota empuñando un ábaco. Y hay PRNG que están en el medio: las herramientas genéricas simples no los atraparán, pero no significa que no puedan ser atrapadas, solo que requiere un poco más de esfuerzo.

(Matemáticamente, no se sabe si el PRNG criptográficamente fuerte realmente puede existir; esta es toda la diferencia entre un algoritmo que no se puede romper y un algoritmo que no sabemos cómo romper. Un corolario es que lo hacemos No sabemos si puede existir una herramienta de análisis implementable que reconociera de manera confiable a todos los PRNG no fuertes. Ahora mismo , tenemos PRNG que son criptográficamente débiles, pero estadísticamente muy buenos, por lo que herramientas de análisis como Burp's el secuenciador no encontrará nada no aleatorio en ellos.)

    
respondido por el Thomas Pornin 09.01.2013 - 04:17
fuente

Lea otras preguntas en las etiquetas