Intentaré responder una pregunta simplificada: ¿existe un ataque factible en un CSPRNG verdadero (generador de números aleatorios criptográficamente seguro)? Y luego, ¿qué pasa si no es un CSPRNG perfecto?
caso 1)
Para simplificar las cosas, suponga que no se agrega entropía después de la configuración de inicialización de un CSPRNG verdadero determinista. Además, no asuma ninguna fuga de información en la inicialización.
Desde wikipedia, la definición de CSPRNG es la siguiente:
Cada CSPRNG debe satisfacer la siguiente prueba de bits. Es decir, dados los primeros k bits de una secuencia aleatoria, no hay tiempo polinomial
Algoritmo que puede predecir el bit (k + 1) con probabilidad de éxito.
No despreciable mejor que el 50%. Andrew Yao demostró en 1982 que una
generador pasando la prueba de bit siguiente pasará todos los demás
Pruebas estadísticas de aleatoriedad en tiempo polinómico.
Cada CSPRNG debe soportar "extensiones de compromiso de estado". En el caso de que parte o la totalidad de su estado haya sido revelado (o adivinado)
correctamente), debería ser imposible reconstruir el flujo de
Números aleatorios previos a la revelación. Además, si hay un
La entrada de entropía durante la ejecución, no debería ser factible utilizar el conocimiento.
del estado de la entrada para predecir las condiciones futuras del estado CSPRNG.
Eso dice incluso si parte de la secuencia de salida aleatoria se filtra, las partes de la secuencia antes y después de esa parte filtrada no se pueden determinar.
En ese caso, está completamente seguro al utilizar /dev/urandom
, incluso si hay una filtración de los datos de secuencia aleatoria y incluso si no se agregan datos aleatorios externos a la secuencia después de la inicialización.
caso 2)
Supongamos que resulta que el llamado CSPRNG está realmente roto. Solo por la venta del argumento, supongamos que, dada una filtración parcial de la secuencia, tanto las partes pasadas como futuras de la secuencia "lo suficientemente cerca" de la filtración están gravemente comprometidas.
En tal caso de CSPRNG roto, la entropía agregada agregará seguridad al sistema. Si 256 bits verdaderos de entropía separan la fuga y un número aleatorio X utilizado para un propósito crítico, entonces el espacio de búsqueda para un ataque en X se amplía en 2 ^ 256, y por lo tanto es totalmente seguro.
Entonces, el caso 2 es un riesgo bajo las siguientes 2 condiciones:
- Hay una fuga del estado de secuencia aleatoria.
- El PRNG no es un CSPRNG perfecto.
Pero asegurar una entropía suficiente puede mitigar perfectamente el riesgo.
Sobre la condición (1): la posibilidad de una fuga de datos. Algunas implementaciones de Java proporcionan acceso a los datos / dev / random subyacentes. Lo dice en la documentación de Java.
Eso es genial para elegir números aleatorios en Java, pero podría ser usado por malware basado en Java para filtrar información en su secuencia aleatoria. Además de Java, cada vez que cree una contraseña aleatoria con su software y la distribuya a un sitio web externo, es probable que se filtre información sobre su estado de secuencia aleatoria.
Sobre la condición (2): si bien es posible demostrar que un PRNG en particular no es un CSPRNG, no es posible probar que un PRNG en particular es un CSPRNG. Solo debes esperar que el CSPRNG no haya sido refutado sin que lo sepas. También hay sombras de gris: un ataque particular solo abre una ventana estrecha de vulnerabilidad antes y después de una fuga, y requeriría enormes recursos para explotarla. Evaluar el riesgo de un ataque desconocido (para usted) con un número concreto es difícil o imposible, pero tratar el riesgo como una variable desconocida y examinar el costo de la mitigación frente a las consecuencias, ya que el riesgo varía, es un ejercicio significativo.
Nota: hay una pregunta de un laico: si el PRNG es determinista, ¿cómo puede el siguiente bit no ser predecible si ocurre una fuga? La respuesta es que aunque el algoritmo de secuencia aleatoria general en sí mismo se conoce públicamente, la función utilizada para la transición de un par (valor, estado) al siguiente par (valor, estado) se elige inicialmente de una gran familia de funciones, por ejemplo, una de 2 ^ 256 tales funciones. Luego se pueden usar otros 256 bits para inicializar la función elegida. (En realidad, solo se requieren 128 bits para inicializar la secuencia /dev/random
).