En las noticias, hay varios artículos ( aquí , aquí , y el punto de vista técnico ) que tienen que ver con una debilidad en un generador de números aleatorios.
La pregunta es algo doble. ¿Qué síntomas muestran los RNG débiles? ¿Esto significa, por ejemplo, que varias semillas diferentes dan el mismo resultado? ¿O me estoy perdiendo lo que quieren decir con "débil"?
Y, ¿Cómo pasa uno de descifrar que hay un RNG débil para descifrar completamente el tráfico cifrado?
Cuando generas una clave privada, lo haces con una fuente de aleatoriedad. Si esa fuente de aleatoriedad puede generar N diferentes flujos de bits, entonces, como máximo, puede obtener N diferente clave privada. Aquí es donde nos gusta hablar de entropía , que es una medida de cuán grande es N . Cuando se dice que la fuente de aleatoriedad ofrece "100 bits de entropía", significa que (aproximadamente) N = 2 100 .
El atacante querrá obtener su clave privada. Si sabe que usa una fuente débil con un N bajo (por ejemplo, solo 40 bits de entropía), entonces puede, en su propia máquina, enumerar todos los resultados posibles de la fuente aleatoria y resolver la clave privada correspondiente.
Por ejemplo, suponga que utilizó un PRNG sembrado con la hora actual, expresado en microsegundos. Este es el momento conocido por su máquina. El atacante asume que su máquina está razonablemente bien configurada con la hora actual, por ejemplo, dentro de 10 segundos. Por lo tanto, desde el punto de vista del atacante, la semilla para su PRNG se conoce dentro de un rango de 10 segundos; ya que el PRNG usa el tiempo en microsegundos, eso lo deja con N = 10000000 posibles semillas. Luego, el atacante se dice a sí mismo: "SI ese tipo usó como valor inicial x , ENTONCES su código produjo un valor de clave privada Kx ; veamos si eso coincide con su clave pública ... no. Por lo tanto, no usó x . Intentemos nuevamente con x + 1 (y así sucesivamente). "
Por lo tanto, un PRNG débil es mortal en tales situaciones.
¿Cómo puedes detectar un PRNG débil? Bueno, la mayoría de las veces, no puedes. Un PRNG muy pobre puede parecer pobre desde el principio; por ejemplo, si genera dos claves privadas y obtiene dos veces lo mismo, entonces es probable que haya algo incorrecto ... pero, como lo muestra el ejemplo del "tiempo como semilla", esto no siempre es fácil de detectar: el tiempo fluye continuamente, por lo que nunca reutilizar una semilla Y sin embargo esto es débil. Debido a que la debilidad proviene de lo difícil que es adivinar el estado interno de la fuente aleatoria, que no es lo mismo que tener un sesgo estadístico.
Un gran sesgo estadístico es detectable y es una debilidad obvia; pero un PRNG puede ser débil sin ser detectable como tal.
Si eres un tipo malo y quieres hacer un PRNG débil indetectable , entonces puedes tomar un buen cifrado de bloque (por ejemplo, AES ), elija un valor clave K y cifre los valores sucesivos de un contador, comenzando en 0. Esto producirá un flujo muy largo de bytes pseudoaleatorios que nadie podrá probar que no sea aleatorio, precisamente porque AES es bueno para cifrar cosas. Pero tú, como el chico malo, sabes K , por lo que puedes predecir fácilmente todo el flujo.
La única forma confiable de detectar un PRNG débil es inspeccionar el método exacto por el cual funciona el PRNG, hasta los detalles más bajos: qué eventos físicos recopila, por qué se pueden considerar estos eventos " aleatorio ", cómo se mezclan con algoritmos criptográficos para producir bytes pseudoaleatorios. No se puede hacer eso con un RNG de hardware opaco, por lo tanto, el recorte actual de rumores.
Los RNG débiles son, por definición, difíciles de detectar (en una secuencia aleatoria, todas las secuencias son igualmente probables, por lo que se necesitaría una corriente infinita para demostrar que no son aleatorias), pero una buena definición es si puede (aparentemente) predecir de manera confiable el siguiente dígito en el flujo aleatorio es mejor que 'chance'. Nuevamente, esto solo es demostrable si tiene un flujo infinito, pero para romper el cifrado, esto no es tan importante como suponer un RNG débil por observación y usar la suposición para romper el cifrado (es decir, usando su suposición de cómo un se genera un (pseudo) patrón aleatorio; esta es una mejor manera de demostrar un RNG débil que esperar a que se genere una corriente infinita y probar su distribución).
Una vez que haya determinado / adivinado cómo predecir el patrón en un flujo aleatorio, si ese flujo se ha usado para generar claves, o una vez, tendrá una forma de usar la distribución predicha como una forma de reducir la búsqueda. espacio para adivinar las claves (secretas) o buscar la distribución en un cifrado de transposición, etc. Para las almohadillas de una vez, es especialmente un problema, ya que tiene una forma de invertir la almohadilla (lo cual es trivial si conoce una cantidad significativa de la clave) .
Todos los algoritmos criptográficos son susceptibles de una aleatoriedad pobre en un grado diferente de curso y, a veces, es suficiente 'pseudo'.
Lea otras preguntas en las etiquetas cryptography encryption random