Siempre escucho que C rand() no es seguro, pero ¿cuántas llamadas necesitarías saber para predecir el siguiente valor (o al menos reducir las posibilidades)? ¿Tendrían que ser secuenciales? Si no hay buena información sobre rand (), estoy interesado en cualquier otro generador de números aleatorios de uso frecuente.
Generalmente depende de la implementación. Para la mayoría de las partes, verás Generadores de congruencia lineal , o Linear Feedback Shift Registers .
Un problema común con estos tipos de generadores es que su período generalmente es bastante corto, y que su forma matemática implica una generación determinista. Como tal, puede (generalmente) dividirlos en unos pocos cientos de llamadas o menos. Los resultados secuenciales hacen que romper el algoritmo sea más fácil, ya que puedes hacer correlaciones más fuertes de esa manera, pero no son necesarias.
El defecto más grande con los generadores "nuevos" es que la semilla no es lo suficientemente grande. Por ejemplo, si tiene un generador con una semilla de 32 bits y conoce los primeros 20 valores del generador, es trivial a la fuerza bruta. Solo genera una secuencia para cada semilla de 0 a 2 ^ 32, y compárala. Puede emplear la optimización temprana para reducir masivamente el costo computacional de esto.
Pseudo código:
// the known values from the generator
byte[] knownValues = { 9, 55, 201, 50, 41, 111, 67, 44, 122, 66 };
for(seed = 0 to 2^32)
{
srand(seed);
bool found = true;
for(n = 0 to len(knownValues))
{
if(rand() != knownValues[n])
{
found = false;
break;
}
}
if(found == true)
{
print "Found potential seed: " + seed + "\n";
}
}
Con un RNG razonablemente rápido y un hardware decente, esto definitivamente se convierte en un ataque plausible.
Te recomiendo que leas lo siguiente para una explicación detallada:
Las implementaciones de rand() varían de un sistema a otro. He mirado a varios de ellos, y la seguridad varía de espantosa a absolutamente espantosa. Definitivamente no desea utilizar rand() para nada criptográfico.
En algunos sistemas, una salida de rand() es suficiente para recuperar la semilla y predecir todas las salidas futuras. En otros, necesitas 2 salidas de rand() . En algunos sistemas, si observa la secuencia de salidas de rand()&1 , encontrará que siempre obtiene la secuencia 0,1,0,1,0,1, ... - en otras palabras, los bits menos significativos de salidas consecutivas de rand() alternan entre 0 y 1 (es decir, las salidas de rand() alternan entre impar y par).
¿Qué tan inseguro es? Tan inseguro como puedas imaginar.
No sé la implementación exacta utilizada para rand (), por lo que responderé un caso general.
Un generador aleatorio no criptográfico popular es el Generador de congruencia lineal . Esto se puede predecir con menos de 10 llamadas secuenciales *.
*: el límite superior es probablemente mucho más bajo, pero esto se dio como una asignación de la primera semana en un curso introductorio sobre criptografía que dice algo sobre lo fácil que es romperlo.
Los CSPRNG son un subconjunto de PRNG. Un PRNG solo necesita ser estadísticamente aleatorio. Un CSPRNG debe ser estadísticamente aleatorio y compararlo con el criptoanálisis para determinar los valores pasados o futuros, incluso cuando se conoce una buena cantidad de información sobre los valores iniciales y / o pasados.
Todos los PRNG son lo suficientemente seguros cuando simplemente necesitas un valor estadísticamente aleatorio (como sales de contraseña o identificadores de usuarios aleatorios); sin embargo, un CSPRNG es necesario cuando el sistema que utiliza valores estadísticamente aleatorios debe soportar el criptoanálisis (uso en criptografía).
Lea otras preguntas en las etiquetas random