Entendiendo a los PRGs: ¿Cómo podemos expandir la aleatoriedad?

Un PRNG criptográficamente seguro comienza con un estado inicial (a menudo llamado "semilla") Lo cual es desconocido para el atacante. Podemos considerar que el estado es una secuencia de bits n . Desde ese estado, el PRNG funciona de manera determinista y genera muchos bits, y el estado interno se actualiza continuamente.

Hay un ataque genérico que se puede aplicar teóricamente a todos los PRNG, lo que se denomina "búsqueda exhaustiva" o "fuerza bruta": es decir, pruebe todos los valores posibles para la semilla, hasta que coincida. Se encuentra con la salida observada. El costo de este ataque es, en promedio, 2^n-1 "intentos" (en promedio, tienes que probar la mitad de los valores de semilla posibles antes de golpear el correcto) ). Este ataque genérico se frustra al hacer que n sea lo suficientemente grande como para que 2^n-1 sea un valor ridículamente grande. Los buenos algoritmos tradicionalmente usan n = 128 o más, que es lo suficientemente grande .

Por supuesto, con un estado inicial de 2 bits, la búsqueda exhaustiva es muy rápida: ¡solo son posibles 4 valores semilla!

Necesitamos un estado inicial grande. La parte difícil es entonces diseñar un PRNG de modo que el ataque genérico sea también el mejor ataque; es decir, que no hay un "atajo" que use la estructura de PRNG que permita la poda eficiente de una gran proporción de semillas candidatas sin probarlas todas. Esto es difícil y no está bien fundamentado por la teoría matemática: matemáticamente, no hay ninguna prueba de que un PRNG seguro pueda existir en absoluto; así que organizamos muchas "operaciones de aleatorización" que mezclan datos y esperamos lo mejor. Aún más difícil es diseñar una mezcla de este tipo para que el resultado no solo sea seguro, sino también rápido. Actualmente, lo mejor que podemos hacer es hacer que algunos criptógrafos piensen mucho en un diseño y luego lo envíen a muchos otros criptógrafos que intenten romperlo durante algunos años. Los diseños supervivientes se consideran "probablemente seguros". Consulte la cartera de eSTREAM para obtener información sobre este esfuerzo.

  

Ahora argumentaría que no logramos ninguna expansión de aleatoriedad, siempre que tengamos memoria para almacenar estas asignaciones.

Usted tiene razón si solo está esperando una salida de 4 bits de su PRG.

Recuerde la definición de un PRG seguro: dado dos entradas, una que es verdaderamente aleatoria y otra que se genera utilizando un PRG, no existe ningún adversario que pueda distinguir eficientemente entre las dos.

Dada una PRG que puede producir una salida de una longitud de n bits arbitraria, como es común con los cifrados de flujo, creo que está subestimando gravemente la cantidad de almacenamiento necesaria para mapear completamente todas las salidas posibles de una PRG.