2009-09-09 12 views
9

Entiendo que el tiempo (0) se usa comúnmente para sembrar generadores de números aleatorios y que solo se convierte en un problema cuando el programa se ejecuta más de una vez por segundo. Me pregunto cuáles son algunas semillas mejores para considerar al generar números aleatorios. Leí acerca de GetTickCount, timeGetTime y QueryPerformanceCounter en Windows. ¿Serán suficientes para casi todas las operaciones o hay incluso mejores opciones de siembra?¿Mejores semillas que el tiempo (0)?

Aquí es un ejemplo de código rápida utilizando la biblioteca de impulso:

#include <iostream> 
#include <boost/random.hpp> 
using namespace std; 
using namespace boost; 

int main() 
{ 
    mt19937 randGen(42); 
    uniform_int<> range(0,100); 
    variate_generator<mt19937&, uniform_int<> > GetRand(randGen, range); 

    for (int i = 0; i < 30; ++i) 
     cout << GetRand() << endl; 
} 
+0

Realmente depende de lo que los números aleatorios son para. Usted dice que el tiempo (0) "solo se convierte en un problema cuando el programa se ejecuta más de una vez por segundo", lo que sugiere que los requisitos en sus números aleatorios son muy bajos. Todos respondieron asumiendo los requisitos de seguridad. Si todo lo que necesita es una semilla única para cada ejecución de su programa, concatene la hora y el PID. –

+0

Sí, obviamente los grandes programas, especialmente los juegos en línea que están haciendo la generación aleatoria de números para potencialmente decenas de miles de jugadores por segundo, necesitarían algo mucho más sólido. Sin embargo, para mis simples propósitos en este punto más lento que una vez por segundo está bien. Solo tenía curiosidad. – trikker

Respuesta

12

Algunos cortes tempranos de la seguridad de Netscape en torno saber cuándo se envió un paquete cifrado y la reducción a la posible gama de semillas con ese conocimiento. Por lo tanto, obtener una cuenta de garrapatas u otra cosa remotamente determinista no es su mejor opción.

Incluso usando una semilla, la secuencia de números "aleatorios" es determinista basada en esa semilla. Un investigador de la Comisión de Juego de Nevada se dio cuenta de esto sobre ciertas máquinas tragamonedas que se suponía que debía inspeccionar y utilizó ese conocimiento para ganar bastante dinero antes de ser atrapado.

Si necesita aleatoriedad de clase mundial, puede agregar hardware a su sistema que proporcione un número altamente aleatorio. Así es como lo hacen los sitios de póquer conocidos (al menos, eso es lo que dicen).

Además de eso, combina una serie de factores de tu sistema que cambian de forma independiente y rápida, con la menor previsibilidad posible, para crear una semilla muy decente. Una respuesta a una publicación relacionada en SO sugirió usar Guid.NewGuid(). GetHashCode(). Desde un Guid se basa en una serie de factores deterministas incluyendo el tiempo, que no forma una buena base para una semilla:

Criptoanálisis de la generador WinAPI GUID muestra que, puesto que la secuencia de V4 GUID es pseudoaleatorio, dado el estado inicial que se puede predecir hasta los próximos 250 000 GUID devueltos por la función UuidCreate [2]. Esta es la razón por la que los GUID no se deben usar en la criptografía, , por ejemplo, como claves aleatorias.

Fuente: Wikipedia Globally Unique Identifier

5

en sistemas UNIX, puede tomar unos pocos bytes de/dev/random como una semilla para su generador de números aleatorios./dev/random se supone que es muy bueno al azar, usando las diferentes fuentes de entropía disponibles en una PC. Por supuesto, esto depende completamente de la implementación.

Un caso en el que podría ser útil es para aplicaciones criptográficas, ya que el tiempo (0) es relativamente fácil de adivinar.

4

Necesitará una fuente alternativa/secundaria de entropía.Dependiendo de la cantidad de entropía que desea utilizar, se puede calcular un hash de cualquiera de las siguientes entradas y utilizarlo como una semilla para su último generador:

  • declarar una matriz de caracteres al azar tamaño unintialized en la pila
  • asignar un número indeterminado de bytes de memoria
  • pedir al usuario que mueva el ratón
  • pedir al usuario que ponga CD aleatorio en la unidad de CD y leer bytes aleatorios en lugar aleatorio desde la primera pista
  • abrir el micrófono del usuario o cámara, recolecte un número aleatorio de segundos de entrada, calcule ah ceniza y la semilla
  • de Windows: utilizar CryptGenRandom para obtener un búfer de bytes criptográficamente aleatoria
  • Unix: como han mencionado otros, leer de /dev/random
+0

los segundos dos probablemente serían más problemas de lo que valen: D –

+0

Depende de qué tan importante es la aleatoriedad de la semilla para @trikker :-) –

4

en UNIX intente leer desde/dev/random. Leer desde este dispositivo es lento, así que no lo haga con demasiada frecuencia, por ejemplo, solo para establecer la inicialización. El dispositivo aleatorio obtiene datos de la entropía generada por el hardware (ruido ambiental de los dispositivos) y no hay cantidad infinita de ellos disponibles para un período de tiempo determinado. Si se queda sin entropía, las bibliotecas SSL pueden fallar. La entropía se vuelve a llenar después de un tiempo (en realidad es un grupo de entropía). También hay urandom afaik que es más económico pero menos aleatorio y no se bloquea en condiciones de baja entropía.

1

Usar tickCout() o cualquier cosa con una alta frecuencia es una mala idea. Esto es porque el couter vuelve a cero muy rápidamente, por lo que ofrece la posibilidad de tener la misma semilla.

time(NULL): Repeats every 64 years. 
tickCouter() Repeats every X days. 

Puede intentar obtener un valor aleatorio de la naturaleza.
La luz golpea en todo el mundo en el último segundo (aparentemente está en línea)? (Puede que necesite investigar para ver si eso es variable).

+2

Los relámpagos en el último segundo son como hipercifrados sin el hiper.Si el atacante conoce tu fuente de aleatoriedad y la hora aproximada en que generó tu semilla, entonces como él tiene acceso a los mismos datos que tú, estás de regreso donde estabas usando 'tiempo (0)'. Si el atacante no conoce tu fuente de aleatoriedad, es una mejora, pero ¿es ese el tipo de detalle de implementación que confías que puedes mantener en secreto? ¿Qué pasa si alguien descubre a qué sitio web te estás conectando? –

+1

Dado que el contador de tic-tac ciclos muy rápido, y el problema con el tiempo (0) es que ciclos demasiado lento, la solución obvia es sembrar con ambos. Si su semilla RNG está limitada a 16 o 32 bits, tiene problemas. En ese caso, inicialice su RNG con el contador de ticks y guarde algunos bits de eso. Reseed with time (0) y descarta una cantidad de valores iniciales, o XOR todos los resultados subsecuentes usando los bits inicialmente guardados. – MSalters

+0

Votando esto solo porque la respuesta estaba fuera de la caja. – trikker

6

demasiado largo para un comentario, pero interesante historia sobre las semillas de 32 bits en los primeros días de póquer en línea

El algoritmo de barajar utilizado en el software ASF siempre comienza con una cubierta ordenada de tarjetas, y luego genera una secuencia de números aleatorios utilizada para reordenar la plataforma. En una baraja de cartas real , ¡hay 52! (~ 2^226) posibles combinaciones únicas. Recuerde que la semilla para un generador de número aleatorio de 32 bits debe ser un número de 32 bits, , lo que significa que hay un poco más de 4 millones de semillas posibles. Como la plataforma se reinicializa y el generador se resembró antes de cada mezcla, solo 4 mil millones de combinaciones posibles pueden dar como resultado de este algoritmo. 4B posible barajar es alarmantemente menos de 52 !.

La herramienta desarrollada RST para explotar esta vulnerabilidad requiere cinco tarjetas del que debe conocerse. Basado en las cinco tarjetas conocidas, el programa busca a través de los pocos cientos de miles de posibles combinaciones y deduce que una combinación de es perfecta.En el caso de Texas Hold'em Poker, esto significa que el programa toma como entrada las dos cartas que se reparte al jugador infiel, más las primeras tres cartas comunitarias que se reparten boca arriba (el flop). Estas cinco cartas son conocidas después de la primera de cuatro rondas de apuestas , y son suficientes para determinar (en tiempo real, durante el juego) la combinación exacta.

http://www.ibm.com/developerworks/library/s-playing/

1

Puede almacenar semilla aleatoria en la salida del programa y cargarla al inicio, por lo que deberá inicializar su RNG con tiempo (0) solo el primer inicio del programa.

+0

¿Quiere decir almacenar el valor actual del rng en la salida y usarlo como semilla en la próxima ejecución? – Patrick

0

El método con generadores de números aleatorios es solo sembrarlo una vez para que su ejemplo de un juego en línea no sea un problema ya que, potencialmente, se usará el mismo rng para cada valor que se hubiera sembrado cuando el programa fue primero comenzó (tal vez hace varios años).

De forma similar, en su propio código intente sembrar el rng una vez y luego utilice la misma instancia donde se requiera en lugar de crear un nuevo rng con una nueva semilla en todo el lugar.

+0

Patrick, usar un PRNG para sembrar otros PRNG tiene consecuencias bastante graves y debe evitarse (a menos que sepa absolutamente lo que está haciendo; hay maneras de hacer que esto funcione, nada de eso es ingenuo o fácil). – Joey

+0

¿Qué consecuencias? No estamos hablando de rngs criptográficamente seguros aquí ... – Patrick

+1

También los arruina para simulaciones y otras tareas que no sean de cifrado. Esta es una de las razones por las que el uso de PRNGs en paralelo y simulaciones distribuidas es un gran problema. – Joey

0

utilizando (únicamente) el tiempo como semilla PRNG tiene básicamente dos problemas:

  1. Es predecible (que lo hace inadecuado para cripto)
  2. semillas consecutivos tienen más o menos dependencia lineal

Para el primer problema, generalmente es imprescindible que tome tantas fuentes de entropía que pueda tener en sus manos.

En cuanto al segundo problema, el documento Common defects in initialization of pseudorandom number generators de Makoto Matsumoto podría dar alguna idea.

1

Dado que ya está utilizando boost, es probable que desee boost::random_device.

(Por lo menos en Linux. No recuerdo si la aplicación CryptGenRandom evidente de que está todavía disponible en Windows.)

Cuestiones relacionadas