¿El hash de un PRNG lo hace criptográficamente seguro?

Hashing la salida de un RNG es típicamente un componente de hacer un RNG criptográficamente seguro, pero no es magia. No puede hacer que un RNG de mierda sea repentinamente seguro.

Un componente clave en un RNG criptográficamente seguro es la imprevisibilidad absoluta. Si puedes predecir la salida, entonces puedes usar esa predicción como parte de tu ataque. La ejecución de la salida a través de un hash no cambia la previsibilidad.

Digamos, por ejemplo, que mi generador de números aleatorios súper asombrosos alterna entre devolver el número 4 y el 7. Puedes argumentar que mi RNG es horrible, y estarías en lo correcto. Pero digamos que ahora ejecuta la salida a través de SHA1. Así que alterna entre devolver SHA1 (4) y SHA1 (7). Aún no es aleatorio. Entonces la respuesta es NO.

Pero los hashes son útiles para los RNG criptográficos

Por otra parte, digamos que tiene una verdadera fuente de entropía (por ejemplo, un contador geiger apuntado a un bloque de plutonio ) que genera resultados probables aleatorios pero en nuestro caso sesgados. Debido a nuestro aparato de muestreo, el flujo de salida es 57% 1's y 43% 0's. Es aleatorio porque absolutamente no puedes predecir los resultados, pero si adivinas "1", acertarás más a menudo.

Podemos neutralizar este sesgo ejecutando la salida a través de un hash criptográfico. Una de las propiedades de un hash criptográfico es que la salida NO es inherentemente sesgada, sin importar cuál sea la entrada. Obviamente, tenemos que recopilar bloques de muestra de entrada el tiempo suficiente para evitar el hashing del mismo valor dos veces. Pero la salida final tendrá un número aproximadamente igual de 1 y 0, lo que hace que nuestro cifrado sea más seguro.

Hashing no tiene ningún efecto en absoluto para aumentar la seguridad de un PRNG como rand() . De hecho, si la salida del PRNG es mayor que la salida de la función de hashing, disminuirá su seguridad.

sha(rand()) es, básicamente, seguridad por oscuridad. Está asumiendo que al hacer que el resultado de PRNG aparezca más aleatorio, lo hará más seguro, lo cual es incorrecto. No abordaré el tema de criptográficamente seguros generadores de números pseudoaleatorios (CSPRNGs) , ya que no estoy bien versado en el tema. Solo necesita saber que si un rand() arbitrario es inseguro, entonces no importa cómo mute su salida, seguirá siendo inseguro e incluso podría hacerlo menos seguro.

Ahora, si estás hablando de PHP / C's rand() , es importante sabe que está lejos de ser un PRNG criptográficamente seguro.

Como CodesInChaos dijo , el El mayor problema con rand() son las fuentes de sus semillas. Viendo php-src/ext/standard/php_rand.h , puede ver claramente cómo es la semilla generado

GENERATE_SEED() (((long) (time(0) * getpid())) ^ ((long) (1000000.0 * php_combined_lcg(TSRMLS_C))))

php_combined_lcg() se reduce a un generador congruente lineal (LLG) , y esos, LLGs, no se recomiendan para ser utilizado para fines de criptografía.

El ataque

El valor devuelto por php_combined_lcg() es idéntico al valor devuelto por uniqid() que se podría filtrar a través de nombres de archivos generados, contraseñas generadas, tokens mal implementados, etc. Una vez que el atacante adquiere ese valor, el resto es simple. Los valores de time() y getpid() son razonablemente fuertes.

Parte 1

No, esto no es seguro, no sería semánticamente seguro (porque Random () no es seguro)

Yo diría que no sería seguro porque una función de hash reduce la entropía de su entrada. En otras palabras, una función hash generalmente tiene menos de 1: 1 de asignación de resultados a entrada, y tiene una mayor probabilidad de colisionar con entradas anteriores que la entrada en bruto en sí misma.

En este caso, la entrada no aleatoria simplemente será "más larga" con más bits, pero no la hará más aleatoria, que es la base de la mayoría de las necesidades criptográficas. (Think One Time Pad)

Una mejor solución:

Alimente la entrada no aleatoria en un "HKDF". Un HKDF le permite derivar muchas claves de una clave, suponiendo que la clave de origen / PRF no es necesariamente aleatoria. El HKDF usa el paradigma "Extraer y luego expandir" que agrega aleatoriedad usando una "sal" no secreta que es aleatoria. Muestra HMAC(salt, yourKey)

Otro enfoque consiste en incluir esa entrada no aleatoria en un cifrado de flujo como AES o 3DES y usarlo como una almohadilla de una vez (o para lo que sea que quieras usar)

¿Cómo lo atacarías?

Necesito saber cómo se está utilizando esto. El ataque es el mismo que el ataque en random () con el retardo de hashing agregado posterior. La versión simplificada de este ataque es saber que el área que necesitas para la fuerza bruta es mucho más pequeña que 2 ^ 51 y es probable que no sea despreciable.

En un ejemplo de cifrado de flujo, significa que SHA1 causará una colisión en menos de 281.5 terabytes está encriptado y la función rand () lo reduce aún más. (Si alguien sabe cómo calcular esto, apreciaría esa información)

Parte 2

Solo te concentras en el aspecto "hashing" que no tiene la relación con un PRNG como sospechabas:

Las colisiones son malas porque le permiten al atacante hacer muchas cosas, como implementar un ataque de mensaje elegido, falsificación existencial o una variedad de otros ataques, según el lugar donde se use el resultado de hash resultante.

En términos de hash, es más probable que ocurra una colisión en 2 ^ n / 2 operaciones (aproximadamente la raíz cuadrada del tamaño del espacio de salida).

Name       Size    Attack Operations
SHA-1       160    2^80               (Insecure, don't use)
SHA-256     256    2^128 
SHA-512     512    2^256
Whirlpool   512    2^256              (AES based and slowest)

Lo que se enumera anteriormente es la mejor resistencia de colisión posible (en teoría) basada únicamente en el número de bits en la salida.

Tenga en cuenta que la seguridad realista de un hash probablemente será menos segura que el máximo teórico. Tome SHA-1, por ejemplo, el buscador de colisiones más conocido solo requiere 2 ^ 51 evaluaciones hash y el mejor caso teórico es 2 ^ 80)

Eso depende completamente de los requisitos de seguridad de su aplicación, su generador de números aleatorios y su función hash. El hecho es que podría ser seguro, pero responder a esa pregunta requeriría una investigación cuidadosa. "Seguro" no siempre significa lo mismo en todos los contextos. ¿Cómo trataría un atacante de capitalizar su generador de números aleatorios comprometidos? Cuando los investigadores de seguridad desarrollan herramientas como CSPRNG, intentan que cumpla ciertos requisitos que pueden convertirla en una herramienta segura para una amplia variedad de aplicaciones.

Dicho esto, generalmente es una mala idea crear sus propias soluciones de seguridad, especialmente cuando están basadas en buenas ideas, porque el diablo está en los detalles, y un error sutil es mucho más peligroso que uno obvio.

Le sugiero que dedique algo de tiempo a leer cómo funciona HMAC. A primera vista, el hash (mensaje | clave secreta) parece ser una forma efectiva de crear un código de autenticación de mensaje. Sin embargo, debido a ciertas debilidades inevitables de las funciones hash, entre otras razones, los expertos en seguridad han decidido que el hashing de la entrada y / o la clave varias veces y la introducción de pads intermedios puede crear un código de autenticación más seguro.

Si se toma un tiempo para leer por qué los HMAC se hacen de la manera en que lo hacen, eso puede ayudarlo a comprender por qué los CSPRNG recomendados probablemente sean mejores que lo que usted mismo puede hacer.

Dicho esto, parece que lo que quieres hacer es cortar algunas esquinas. En lugar de preguntar, ¿cómo puedo hacer un CSPRNG a medias? Es posible que desee preguntar si su generador de números aleatorios realmente necesita ser criptográficamente seguro.

Si realmente necesita ese nivel de seguridad, debe hacerlo correctamente. Si no lo necesita, la mitad solo sirve para darle una falsa sensación de seguridad y dificulta el análisis y la predicción de sus debilidades de seguridad.

Si soy un pirata informático, un error o debilidad bien oculto (algo así como un corazón) será infinitamente más valioso que algo obvio, que se reconocerá y solucionará tan pronto como sea lo suficientemente importante como para merecer atención.

Yo diría que esa es una de las razones más importantes para no inventar la tuya cuando se trata de seguridad.

Si está interesado en investigar más a fondo el potencial de seguridad de su esquema propuesto, este podría ser un lugar para comenzar. Es una pregunta relacionada en el intercambio de pila de criptografía:

enlace