¿Por qué utilizar la clase C # System.Random en lugar de System.Security.Cryptography.RandomNumberGenerator?

¿Por qué alguien usaría el generador de números aleatorios "estándar" de System.Random en lugar de usar siempre el generador de números aleatorios criptográficamente seguro de System.Security.Cryptography.RandomNumberGenerator (o sus subclases porque RandomNumberGenerator es abstracto)?

Nate Lawson nos dice en su presentación de Google Tech Talk " Crypto Strikes Back " en el minuto 13:11 que no usemos los generadores de números aleatorios "estándar" de Python, Java y C # y que en su lugar usemos la versión criptográficamente segura.

Conozco la diferencia entre las dos versiones de generadores de números aleatorios (consulte la pregunta 101337 ).

Pero, ¿qué razón hay para no utilizar siempre el generador seguro de números aleatorios? ¿Por qué utilizar System.Random en absoluto? ¿Desempeño quizás?

Velocidad e intención. Si está generando un número aleatorio y no necesita seguridad, ¿por qué usar una función de criptografía lenta? No necesita seguridad, entonces, ¿por qué hacer que alguien más piense que el número puede usarse para algo seguro cuando no lo será?

Además de la velocidad y la interfaz más útil ( NextDouble()etc.), también es posible hacer una secuencia aleatoria repetible utilizando un valor de semilla fijo. Eso es bastante útil, entre otros, durante las pruebas.

Random gen1 = new Random();     // auto seeded by the clock
Random gen2 = new Random(0);    // Next(10) always yields 7,8,7,5,2,....

En primer lugar, la presentación que vinculó solo habla de números aleatorios por motivos de seguridad. Por lo tanto, no afirma que Randomsea ​​malo para fines que no sean de seguridad.

Pero afirmo que lo es. La implementación de .net 4 de Randomtiene varias fallas. Recomiendo usarlo solo si no le importa la calidad de sus números aleatorios. Recomiendo utilizar mejores implementaciones de terceros.

Defecto 1: La siembra

El constructor predeterminado se inicia con la hora actual. Por lo tanto, todas las instancias de Randomcreadas con el constructor predeterminado dentro de un período de tiempo corto (aproximadamente 10 ms) devuelven la misma secuencia. Esto está documentado y "por diseño". Esto es particularmente molesto si desea realizar múltiples subprocesos en su código, ya que no puede simplemente crear una instancia de Randomal comienzo de la ejecución de cada subproceso.

La solución es tener mucho cuidado al usar el constructor predeterminado y sembrar manualmente cuando sea necesario.

Otro problema aquí es que el espacio semilla es bastante pequeño (31 bits). Entonces, si genera 50k instancias de Randomcon semillas perfectamente aleatorias, probablemente obtendrá una secuencia de números aleatorios dos veces (debido a la paradoja del cumpleaños ). Por lo tanto, la siembra manual tampoco es fácil de realizar.

Defecto 2: la distribución de números aleatorios devueltos por Next(int maxValue)está sesgada

Hay parámetros para los que Next(int maxValue)claramente no es uniforme. Por ejemplo, si calcula r.Next(1431655765) % 2, obtendrá 0aproximadamente 2/3 de las muestras. (Código de muestra al final de la respuesta).

Defecto 3: el NextBytes()método es ineficaz.

El costo por byte de NextBytes()es casi tan grande como el costo de generar una muestra entera completa Next(). De esto sospecho que de hecho crean una muestra por byte.

Una mejor implementación con 3 bytes de cada muestra se aceleraría NextBytes()en casi un factor 3.

Gracias a esta falla Random.NextBytes()es solo un 25% más rápido que System.Security.Cryptography.RNGCryptoServiceProvider.GetBytesen mi máquina (Win7, Core i3 2600MHz).

Estoy seguro de que si alguien inspeccionara el código de bytes fuente / descompilado, encontraría aún más fallas de las que encontré con mi análisis de caja negra.

Muestras de código

r.Next(0x55555555) % 2 está fuertemente sesgado:

Random r = new Random();
const int mod = 2;
int[] hist = new int[mod];
for(int i = 0; i < 10000000; i++)
{
    int num = r.Next(0x55555555);
    int num2 = num % 2;
    hist[num2]++;
}
for(int i=0;i<mod;i++)
    Console.WriteLine(hist[i]);

Actuación:

byte[] bytes=new byte[8*1024];
var cr=new System.Security.Cryptography.RNGCryptoServiceProvider();
Random r=new Random();

// Random.NextBytes
for(int i=0;i<100000;i++)
{
    r.NextBytes(bytes);
}

//One sample per byte
for(int i=0;i<100000;i++)
{   
    for(int j=0;j<bytes.Length;j++)
      bytes[j]=(byte)r.Next();
}

//One sample per 3 bytes
for(int i=0;i<100000;i++)
{
    for(int j=0;j+2<bytes.Length;j+=3)
    {
        int num=r.Next();
        bytes[j+2]=(byte)(num>>16);   
        bytes[j+1]=(byte)(num>>8);
        bytes[j]=(byte)num;
    }
    //Yes I know I'm not handling the last few bytes, but that won't have a noticeable impact on performance
}

//Crypto
for(int i=0;i<100000;i++)
{
    cr.GetBytes(bytes);
}

System.Random es mucho más eficaz ya que no genera números aleatorios criptográficamente seguros.

Una prueba simple en mi máquina para llenar un búfer de 4 bytes con datos aleatorios 1,000,000 de veces toma 49 ms para Random, pero 2845 ms para RNGCryptoServiceProvider. Tenga en cuenta que si aumenta el tamaño del búfer que está llenando, la diferencia se reduce a medida que la sobrecarga para RNGCryptoServiceProvider es menos relevante.

Las razones más obvias ya se han mencionado, por lo que aquí hay una más oscura: los PRNG criptográficos normalmente necesitan ser resembrados continuamente con entropía "real". Por lo tanto, si usa un CPRNG con demasiada frecuencia, podría agotar el grupo de entropía del sistema, que (dependiendo de la implementación del CPRNG) lo debilitará (lo que permitirá que un atacante lo prediga) o se bloqueará mientras intenta llenarlo. su reserva de entropía (convirtiéndose así en un vector de ataque para un ataque DoS).

De cualquier manera, su aplicación ahora se ha convertido en un vector de ataque para otras aplicaciones totalmente ajenas que, a diferencia de la suya, dependen de manera vital de las propiedades criptográficas del CPRNG.

Este es un problema real del mundo real, por cierto, que se ha observado en servidores sin cabeza (que naturalmente tienen grupos de entropía bastante pequeños porque carecen de fuentes de entropía como la entrada del mouse y el teclado) que ejecutan Linux, donde las aplicaciones usan incorrectamente el /dev/randomkernel CPRNG para todo tipo. de números aleatorios, mientras que el comportamiento correcto sería leer un valor de semilla pequeño /dev/urandomy usarlo para generar su propio PRNG.

Si está programando un juego de cartas o lotería en línea, entonces querrá asegurarse de que la secuencia sea casi imposible de adivinar. Sin embargo, si muestra a los usuarios, digamos, una cita del día, el rendimiento es más importante que la seguridad.

Esto se ha discutido con cierto detalle, pero en última instancia, la cuestión del rendimiento es una consideración secundaria al seleccionar un RNG. Existe una amplia gama de RNG, y el Lehmer LCG enlatado que contiene la mayoría de los sistemas de RNG no es el mejor ni necesariamente el más rápido. En sistemas antiguos y lentos, era un compromiso excelente. Ese compromiso rara vez es realmente relevante en estos días. La cosa persiste en los sistemas actuales principalmente porque A) la cosa ya está construida y no hay una razón real para 'reinventar la rueda' en este caso, y B) para qué la usará la gran mayoría de personas, es 'suficientemente bueno'.

En última instancia, la selección de un RNG se reduce a la relación Riesgo / Recompensa. En algunas aplicaciones, por ejemplo un videojuego, no existe ningún riesgo. Un Lehmer RNG es más que adecuado, y es pequeño, conciso, rápido, bien entendido y "en la caja".

Si la aplicación es, por ejemplo, un juego de póquer en línea o de lotería en el que hay premios reales involucrados y el dinero real entra en juego en algún punto de la ecuación, el Lehmer "en la caja" ya no es adecuado. En una versión de 32 bits, solo tiene 2 ^ 32 posibles estados válidos antes de que comience a circular en el mejor de los casos . En estos días, esa es una puerta abierta a un ataque de fuerza bruta. En un caso como este, el desarrollador querrá ir a algo así como un RNG de período muy largo de algunas especies, y probablemente sembrarlo de un proveedor criptográficamente fuerte. Esto proporciona un buen compromiso entre velocidad y seguridad. En tal caso, la persona estará buscando algo como el Mersenne Twister o un generador recursivo múltiple de algún tipo.

Si la aplicación es algo así como comunicar grandes cantidades de información financiera a través de una red, ahora existe un gran riesgo y supera con creces cualquier posible recompensa. Todavía hay carros blindados porque a veces hombres fuertemente armados es la única seguridad que es adecuada, y créanme, si una brigada de personas de operaciones especiales con tanques, cazas y helicópteros fuera financieramente viable, sería el método de elección. En un caso como este, tiene sentido usar un RNG criptográficamente fuerte, porque sea cual sea el nivel de seguridad que pueda obtener, no es tanto como desea. Por lo tanto, tomará todo lo que pueda encontrar y el costo es un problema de segundo lugar muy, muy remoto, ya sea en tiempo o en dinero. Y si eso significa que cada secuencia aleatoria tarda 3 segundos en generarse en una computadora muy potente, esperará los 3 segundos,

Tenga en cuenta que la clase System.Random en C # está codificada incorrectamente, por lo que debe evitarse.

https://connect.microsoft.com/VisualStudio/feedback/details/634761/system-random-serious-bug#tabs

No todo el mundo necesita números aleatorios criptográficamente seguros, y podrían beneficiarse más de un prng sencillo más rápido. Quizás lo más importante es que puede controlar la secuencia de los números System.Random.

En una simulación que utiliza números aleatorios que quizás desee volver a crear, vuelva a ejecutar la simulación con la misma semilla. Puede ser útil para rastrear errores cuando también desea regenerar un escenario defectuoso dado, ejecutando su programa con exactamente la misma secuencia de números aleatorios que bloqueó el programa.

Si no necesito la seguridad, es decir, solo quiero un valor relativamente indeterminado, no uno que sea criptográficamente fuerte, Random tiene una interfaz mucho más fácil de usar.

Diferentes necesidades requieren diferentes RNG. Para las criptomonedas, desea que sus números aleatorios sean lo más aleatorios posible. Para las simulaciones de Monte Carlo, desea que llenen el espacio de manera uniforme y puedan iniciar el RNG desde un estado conocido.

Random no es un generador de números aleatorios, es un generador de secuencias pseudoaleatorias determinista, que toma su nombre por razones históricas.

La razón para usarlo System.Randomes si desea estas propiedades, es decir, una secuencia determinista, que está garantizada para producir la misma secuencia de resultados cuando se inicializa con la misma semilla.

Si desea mejorar la "aleatoriedad" sin sacrificar la interfaz, puede heredar de System.Randominvalidar varios métodos.

• https://msdn.microsoft.com/en-us/library/system.random.sample(v=vs.110).aspx

¿Por qué querrías una secuencia determinista?

Una razón para tener una secuencia determinista en lugar de una verdadera aleatoriedad es porque es repetible.

Por ejemplo, si está ejecutando una simulación numérica, puede inicializar la secuencia con un número aleatorio (verdadero) y registrar qué número se utilizó .

Luego, si desea repetir exactamente la misma simulación, por ejemplo, con fines de depuración, puede hacerlo inicializando la secuencia con el valor registrado .

¿Por qué querrías esta secuencia en particular, no muy buena

La única razón que se me ocurre es la compatibilidad con versiones anteriores del código existente que usa esta clase.

En resumen, si desea mejorar la secuencia sin cambiar el resto de su código, adelante.

Escribí un juego (Crystal Sliders en el iPhone: aquí ) que pondría una serie "aleatoria" de gemas (imágenes) en el mapa y tú rotarías el mapa como querías y las seleccionarías y desaparecieron. - Similar a Bejeweled. Estaba usando Random (), y fue sembrado con el número de ticks de 100ns desde que se inició el teléfono, una semilla bastante aleatoria.

Me pareció sorprendente que generara juegos que eran casi idénticos entre sí; de las 90 gemas o más, de 2 colores, obtendría dos EXACTAMENTE iguales, ¡excepto por 1 a 3 gemas! Si lanza 90 monedas y obtiene el mismo patrón, excepto 1-3, ¡es MUY improbable! Tengo varias capturas de pantalla que muestran lo mismo. ¡Me sorprendió lo malo que era System.Random ()! Supuse que DEBO haber escrito algo horriblemente mal en mi código y lo estaba usando mal. Aunque estaba equivocado, era el generador.

Como experimento, y como solución final, volví al generador de números aleatorios que he estado usando desde 1985 aproximadamente, que es MUY mejor. Es más rápido, tiene un período de 1.3 * 10 ^ 154 (2 ^ 521) antes de que se repita. El algoritmo original fue sembrado con un número de 16 bits, pero lo cambié a un número de 32 bits y mejoré el sembrado inicial.

El original está aquí:

ftp://ftp.grnet.gr/pub/lang/algorithms/c/jpl-c/random.c

A lo largo de los años, he lanzado todas las pruebas de números aleatorios que pude pensar en esto, y las superó a todas. No espero que tenga ningún valor como criptográfico, pero devuelve un número tan rápido como "return * p ++;" hasta que se agoten los 521 bits, y luego ejecuta un proceso rápido sobre los bits para crear nuevos aleatorios.

Creé un contenedor de C #, lo llamé JPLRandom () implementé la misma interfaz que Random () y cambié todos los lugares donde lo llamé en el código.

La diferencia fue MUY mejor - Dios mío, estaba asombrado - no debería haber forma de que pudiera decirlo con solo mirar las pantallas de aproximadamente 90 gemas en un patrón, pero hice un lanzamiento de emergencia de mi juego después de esto.

Y nunca volvería a usar System.Random () para nada. ¡Me sorprende que su versión esté impresionado por algo que ahora tiene 30 años!

-Juegos de Traderhut

Dado que System.Random es criticado aquí por su "incorrección" y sesgo, me revisé.

distribución

Este código f # demuestra que se comporta realmente bien, en mi máquina promedio:

let r = System.Random()
Seq.init 1000000 (fun _ -> r.Next(0,10))
|> Seq.toList
|> Seq.groupBy id
|> Seq.map (fun (v,ls) -> v, ls |> Seq.length)
|> Seq.sortBy fst
|> Seq.iter (printfn "%A")

(0, 100208)
(1, 99744)
(2, 99929)
(3, 99827)
(4, 100273)
(5, 100280)
(6, 100041)
(7, 100001)
(8, 100175)
(9, 99522)    

Las versiones del marco, la máquina y el sistema operativo pueden marcar la diferencia. Ingrese el código en F # interactivo en su máquina y pruébelo usted mismo. Para la cirptografía leí

let arr = [| 0uy |]
let rr = System. Security.Cryptography.RandomNumberGenerator.Create()
Seq.init 1000000 (fun _ -> rr.GetBytes(arr); arr.[0])
|> Seq.toList
|> Seq.groupBy id
|> Seq.map (fun (v,ls) -> v, ls |> Seq.length)
|> Seq.sortBy fst
|> Seq.take 10 // show first 10 bytes
|> Seq.iter (printfn "%A")

// distribution of first 10 bytes
(0uy, 3862)
(1uy, 3888)
(2uy, 3921)
(3uy, 3926)
(4uy, 3948)
(5uy, 3889)
(6uy, 3922)
(7uy, 3797)
(8uy, 3861)
(9uy, 3874)

actuación

#time

let arr = [| 0uy |]

let r = System.Random()
Seq.init 1000000 (fun _ -> r.NextBytes(arr); arr.[0] |> int64) |> Seq.sum

Real: 00:00:00.204, CPU: 00:00:00.203, GC gen0: 45, gen1: 1, gen2: 1
val it : int64 = 127503467L

let rr = System. Security.Cryptography.RandomNumberGenerator.Create()
Seq.init 1000000 (fun _ -> rr.GetBytes(arr); arr.[0] |> int64) |> Seq.sum

Real: 00:00:00.365, CPU: 00:00:00.359, GC gen0: 44, gen1: 0, gen2: 0
val it : int64 = 127460809L

lo que sugiere una relación 1: 2 y un comportamiento de memoria algo más agradable de la versión criptográfica.

conclusión

Principalmente por su API mucho más agradable, algo por su rendimiento y bastante buena distribución, se prefiere System.Random. System.Random también podría reducir las dependencias de la biblioteca y, si se porta un marco, es probable que System.Random esté disponible antes que la variante Crypto.