Fallo en el cifrado a través del flujo de números pseudoaleatorios (de la documentación de PGP)

Un PRNG es "bueno" (tener fuertes garantías de aleatoriedad estadística, por ejemplo, además de tener un período largo) no dice nada sobre su seguridad. Ver por ejemplo discusión en este hilo .

El hilo discute la diferencia entre:

• Almohadillas de una vez (en principio irrompibles, siempre y cuando no se filtren ni se vuelvan a utilizar, pero por lo general no son prácticas)
• cifrados de flujo (que pueden hacerse tan seguros como sea necesario y pueden ser bastante prácticos)
• Los PRNG (que no fueron diseñados para ser criptográficamente seguros) se utilizan como cifrados de flujo (generalmente se rompen fácilmente)

Lo que Phil debería haber usado fue un cifrado de flujo no solo cualquier PRNG antiguo. MT (y los PRNG anteriores) no son adecuados para su uso como cifrado de flujo. Salsa20 / ChaCha (por Dan Bernstein) y ISAAC son dos cifrados de flujo específicos. ISAAC es utilizado por shred . Salsa20 forma parte del programa eSTREAM / ECRYPT de la UE. Por supuesto, se puede perdonar a Phil por no usar un cifrado de flujo: RC4 (que se considera roto, su debilidad es parte de lo que hace que WEP sea inseguro, pero que es la base de ISAAC) solo se inventó en 1987.

Las debilidades criptográficas de los PRNG normales (incluidos MT y Wichmann-Hill) han dado lugar a vulnerabilidades en, por ejemplo, Número de secuencia TCP de ataques. Esas vulnerabilidades a veces se resuelven utilizando un tipo diferente de CSPRNG, que reúne la entropía "como se hace" (por ejemplo, desde el mouse / jitter de sincronización). Para ser adecuado para su uso como cifrado de flujo, un CSPRNG debe tener toda la entropía de entrada disponible al comienzo, en lugar de recopilarla a medida que avanza. Consulte las páginas de wikipedia en CSPRNGs y en / dev / [u] random .

No tengo ni idea de lo que utilizó originalmente el método que usó Phil Zimmerman para su cifrado, así que realmente no puedo decir nada al respecto.

Sin embargo, Mersenne-Twister se puede convertir en un cifrado de flujo "seguro", por ejemplo CryptMT . Sin embargo, CryptMT se rompió posteriormente: Ataque Distintivo en CryptMT . La lectura de ese artículo probablemente da una idea bastante buena sobre cómo atacar a Mersenne-Twister y su tipo.

En realidad, hice un poco más de investigación. En primer lugar, el artículo que cité ha sido redactado posteriormente por los autores, consulte la discusión aquí , y fue contra CryptMTv1, no CryptMTv3 que es la versión actual. No hay ataques conocidos contra CryptMTv3. El más cercano a un ataque que he encontrado es Sobre la seguridad de Stream Cipher CryptMT v3 , que explícitamente dice:

  

Sin embargo, no hemos encontrado ninguna no aleatoriedad acerca de la   salida del flujo de clave.

También, el informe final de eSTREAM para CryptMT dice:

  

CryptMT v3. El cifrado CryptMT tiene un diseño muy inusual que entrega   rendimiento muy razonable. Si bien no ha habido criptoanalítica negativa   resultados contra el cifrado en la última fase de eSTREAM, estamos algo   preocupado por el hecho de que la seguridad del cifrado, en particular el componente de filtro no lineal, aún no se entienda tan bien como algunos de los otros finalistas. Nosotros   anticipamos que los elementos de CryptMT continuarán siendo de interés para la comunidad criptográfica, y esperamos que todas las ventajas del enfoque   incorporado en CryptMT v3 puede ser evaluado. Sin embargo, actualmente no tenemos suficiente confianza en el diseño y la seguridad de este algoritmo para que podamos incluirlo en la cartera final.

¡Apenas un mérito negativo!

También, mirando el "rendimiento muy razonable" mencionado anteriormente en eBASH , parece que CryptMTv3 ofrece un rendimiento increíble para mensajes largos (por ejemplo, 1,82 ciclos por byte para mensajes largos), a menudo solo superado por Salsa20 / 8, donde como Salsa20 / 8 ya se ha roto (apenas, y Salsa20 / 12 todavía es muy seguro).

¡Así que diría que CryptMT es definitivamente un competidor en cifrados de flujo, incluso si aún no se ha analizado lo suficiente!

Cualquier cifrado XOR / PRNG simple donde se usa la clave para inicializar el PRNG es vulnerable a un ataque de texto plano conocido con complejidad 1:

1. Cifre un texto simple al menos mientras el texto cifrado desconocido.
2. XOR el texto plano conocido con su texto cifrado. Esto le proporciona la cadena clave .
3. XOR la secuencia de teclas con el texto cifrado desconocido: esto le da el texto sin formato original.

Si puede cifrar un texto sin formato que consta de todos los "0", puede omitir el paso 2: la salida del proceso de cifrado es el flujo de clave.

No importa qué PRNG esté utilizando: todo, desde RANDU hasta Fortuna es vulnerable a este tipo de ataque de recuperación de cadena clave.

Tenga en cuenta que hay cifras que usan "XOR el texto plano con la secuencia de teclas" como el núcleo de su operación. Sin embargo, toman precauciones para evitar este ataque: almohadillas de un solo uso nunca reutilizan la contraseña, stream ciphers requieren claves de un solo uso o valores de un solo uso llamados nonces , y retroalimentación de salida y modos de operación de contrarrestar bloques cifrados use la clave y un segundo valor de uso único denominado vector de inicialización para asegurarse de que el RNG nunca se siembra igual dos veces.

Creo que la mejor manera de abordar esta cuestión como un laico criptográfico es alejarse de la criptografía moderna y considerar, en su lugar, los cifrados clásicos de papel y lápiz. En este caso, probablemente el mejor ejemplo a considerar es el cifrado de clave en ejecución :

  

En la criptografía clásica, el cifrado de clave en ejecución es un tipo de cifrado de sustitución polialfabética en el que se utiliza un texto, típicamente de un libro, para proporcionar un flujo de claves muy largo.

Básicamente, tal cifrado toma un texto en claro y un texto en lenguaje natural igualmente largo (por ejemplo, un pasaje de una novela), y encripta cada letra del texto en claro al cambiarlo en una cantidad que depende de su correspondiente letra de cadena clave.

Tales cifrados son fácilmente rompibles:

  

[I] f (como es habitual) la clave en ejecución es un bloque de texto en un lenguaje natural, la seguridad en realidad se vuelve bastante pobre, ya que ese texto tendrá características no aleatorias que pueden usarse para ayudar al criptoanálisis. Como resultado, la entropía por carácter tanto del texto plano como de la clave de ejecución es baja, y la operación de combinación se invierte fácilmente.

     

Para atacar el cifrado, un criptoanalista ejecuta supuestos plaintexts a lo largo del texto cifrado, restándolos de cada posición posible. Cuando el resultado es una parte de algo inteligible, existe una alta probabilidad de que el texto simple adivinado sea correcto para esa posición (ya sea como texto simple real o como parte de la clave de ejecución). La "parte de algo inteligible" puede extenderse a menudo en cualquiera de los dos extremos, proporcionando así un texto plano más probable, que a su vez puede extenderse, y así sucesivamente. Eventualmente, es probable que se identifique la fuente de la clave en ejecución y que la plantilla esté arriba.

La razón por la que funcionan estos ataques es porque:

1. El atacante normalmente tiene alguna información parcial sobre el texto plano. En la criptografía clásica, estos serían los lenguajes y temas de texto simple (que implican frecuencias de letras y palabras y dependencias entre letras y palabras consecutivas). En la criptografía moderna, esto sería cosas como el protocolo de comunicaciones que se está cifrando (por ejemplo, HTTP sobre SSL), los puntos finales de la conexión (por ejemplo, Google), etc.
2. Una secuencia clave del lenguaje natural tiene patrones tales que, dadas algunas letras de la secuencia clave, debes adivinar las siguientes letras con una probabilidad muy alta. Ahora, la clave a tener en cuenta es que los PRNG no criptográficos también tienen esta propiedad y, por lo tanto, admiten ataques similares.

Esta serie de blogs describe cómo romper los RNG congruentes lineales simples y el Mersenne Twister. Para el java.util.Random RNG, si tiene dos salidas consecutivas de int s del PRNG, eso es suficiente para reconstruir su estado y predecir el resto de la secuencia pseudoaleatoria (tanto hacia delante como hacia atrás). Por lo tanto, si usó ese PRNG para generar su flujo de claves, un atacante que sepa o adivine ocho bytes consecutivos del texto cifrado puede aplicar una variante del ataque de cifrado en ejecución y las técnicas de craqueo PRNG de la serie de blogs para descifrar el resto del mensaje.

Parte 3 de la serie de blogs describe cómo puede predecir de manera similar la salida de un Mersenne Twister Si puedes obtener 624 palabras de salida consecutivas. Así que es más difícil que el generador lineal congruente, pero todavía vulnerable.