(seguro) Cadena aleatoria?

Question

En Lua, normalmente se generarían valores aleatorios y/o cadenas utilizando math.random & math.randomseed, donde os.time se usa para math.randomseed.

Sin embargo, este método tiene una gran debilidad; El número devuelto siempre es tan aleatorio como la hora actual, Y el intervalo para cada número aleatorio es un segundo, que es demasiado largo si se necesitan muchos valores aleatorios en muy poco tiempo.

Este problema lo señalan incluso los usuarios de Lua wiki: http://lua-users.org/wiki/MathLibraryTutorial, y la correspondiente receta de RandomStringS: http://lua-users.org/wiki/RandomStrings.

Así que he senté a escribir un algoritmo diferente (si es que se puede llamar así), que genera números aleatorios por el (mal) uso de las direcciones de memoria de tablas:

math.randomseed(os.time()) 
function realrandom(maxlen) 
    local tbl = {} 
    local num = tonumber(string.sub(tostring(tbl), 8)) 
    if maxlen ~= nil then 
     num = num % maxlen 
    end 
    return num 
end 

function string.random(length,pattern) 
    local length = length or 11 
    local pattern = pattern or '%a%d' 
    local rand = "" 
    local allchars = "" 
    for loop=0, 255 do 
     allchars = allchars .. string.char(loop) 
    end 
    local str=string.gsub(allchars, '[^'..pattern..']','') 
    while string.len(rand) ~= length do 
     local randidx = realrandom(string.len(str)) 
     local randbyte = string.byte(str, randidx) 
     rand = rand .. string.char(randbyte) 
    end 

    return rand 
end 

Al principio , todo parece perfectamente aleatorio, y estoy seguro de que son ... al menos para el programa actual.

Así que mi pregunta es, ¿qué tan aleatorios son estos números devueltos por realrandom realmente?

O hay una mejor manera de generar números aleatorios en un intervalo de menos de un segundo (lo que implica que tipo de os.time no debe utilizarse, como explaind arriba), sin depender de bibliotecas externas, Y, si es posible, de una manera completamente cruzada?

EDIT:
Parece haber un gran malentendido con respecto a la forma en que se sembró el RNG; En el código de producción, la llamada al math.randomseed() ocurre una sola vez, este fue solo un ejemplo mal elegido aquí.

Lo que quiero decir con el valor aleatorio es única al azar una vez por segundo, es fácilmente demostrable con esta pasta: http://codepad.org/4cDsTpcD

---

Como se conseguirá downvoted esta pregunta sin tener en cuenta mis ediciones, también cancelaron mi respuesta previamente aceptada - En la esperanza de una mejor, incluso si solo mejores opiniones. Entiendo que los problemas relacionados con los valores/números aleatorios se han discutido muchas veces antes, pero no he encontrado una pregunta que pueda ser relevante para Lua. ¡Por favor, téngalo en cuenta!

Answer 1

Reflexiones sobre la primera parte de su pregunta:

Así que mi pregunta es, ¿cómo aleatorios son estos números devueltos por realrandom realmente?

Su función intenta descubrir la dirección de una tabla utilizando una peculiaridad de su implementación predeterminada de tostring(). No creo que la cadena devuelta por tostring{} tenga un formato específico o que el valor incluido en esa cadena tenga algún significado documentado. En la práctica, se deriva de la dirección de algo relacionada con la tabla específica, por lo que las tablas distintas se convierten en cadenas distintas. Sin embargo, la próxima versión de Lua es libre de cambiar eso a cualquier cosa que sea conveniente. Peor aún, el formato que toma dependerá en gran medida de la plataforma, ya que parece utilizar el especificador de formato %p en sprintf(), que solo se especifica como una representación razonable de un puntero.

También hay un problema mucho más grande. Si bien la dirección de la enésima tabla creada en un proceso puede parecer aleatoria en su plataforma, puede que no sea aleatoria. O podría variar en solo unos pocos bits. Por ejemplo, en mi caja win7 sólo unos pocos bits varían, y no muy al azar:

 
C:...>for /L %i in (1,1,20) do @ lua -e "print{}" 
table: 0042E5D8 
table: 0061E5D8 
table: 0024E5D8 
table: 0049E5D8 
table: 0042E5D8 
table: 0042E5D8 
table: 0042E5D8 
table: 0064E5D8 
table: 0042E5D8 
table: 002FE5D8 
table: 0042E5D8 
table: 0049E5D8 
table: 0042E5D8 
table: 0042E5D8 
table: 0042E5D8 
table: 0024E5D8 
table: 0042E5D8 
table: 0042E5D8 
table: 0061E5D8 
table: 0042E5D8 

Otras plataformas variarán, por supuesto. Incluso esperaría que hubiera plataformas donde la dirección de la primera tabla asignada sea completamente determinista, y por lo tanto idéntica en cada ejecución del programa.

En resumen, la dirección de un objeto arbitrario en la imagen de proceso no es una muy buena fuente de aleatoriedad.

Edit: Para completar, me gustaría agregar un par de otros pensamientos que me vinieron a la mente durante la noche.

La función tostring() es suministrada por la biblioteca base y se implementa con la función luaB_tostring(). El bit relevante es este fragmento:

switch (lua_type(L, 1)) { 
    ... 
    default: 
    lua_pushfstring(L, "%s: %p", luaL_typename(L, 1), lua_topointer(L, 1)); 
    break; 

Si realmente se llama a esta función, entonces el final de la cadena será una dirección, representada por el formato estándar de C sprintf()%p, fuertemente relacionada con la tabla específica. Una observación es que he visto varias implementaciones distintas para %p. Windows MSVCR80.DLL (la versión de la biblioteca C utilizada por la versión actual de Lua para Windows) lo hace equivalente a %08X. Mi cuadro Ubuntu Kohmic Koala parece hacer que sea equivalente a %#x, que notablemente deja caer ceros a la izquierda. Si va a analizar esa parte de la cadena, debe hacerlo de una manera más flexible ante la variación del significado de %p.

Tenga en cuenta, también, que hacer algo como esto en el código de la biblioteca puede exponerlo a un par de sorpresas.

En primer lugar, si la tabla pasada a tostring() tiene un metatabla que proporciona la función __tostring(), se llamará a esa función y el fragmento arriba mencionado nunca se ejecutará en absoluto. En su caso, ese problema no puede surgir porque las tablas tienen metatablas individuales y no se aplicó accidentalmente un metatabla a su tabla local.

En segundo lugar, cuando el módulo se carga, algún otro módulo o código proporcionado por el usuario podría haber reemplazado el stock tostring() con otra cosa. Si el reemplazo es benigno (como un contenedor memoization), entonces probablemente no le importe al código tal como está escrito. Sin embargo, esto sería una fuente de ataque y está completamente fuera del control de su módulo. Eso no me parece una buena idea si el objetivo es algún tipo de seguridad mejorada para su material de semilla al azar.

En tercer lugar, es posible que no se cargue en un intérprete Lua de serie, y la aplicación más grande (Lightroom, WoW, Wireshark, ...) puede optar por reemplazar las funciones de la biblioteca base con sus propias implementaciones. Este es un problema mucho menos probable para tostring(), pero tenga en cuenta que print() de la biblioteca base es un objetivo frecuente para reemplazo o eliminación en implementaciones alternativas y hay módulos (Lua Lanes, para uno) que se rompen si print no es la implementación en la biblioteca base .

Answer 2

Algunas cosas importantes vienen a la mente:

• En la mayoría de los otros idiomas que normalmente sólo se llama a la función aleatoria 'semilla' una vez al principio del programa o tal vez en un tiempo limitado, a lo largo de su ejecución. Por lo general, no desea llamarlo cada vez que genera un número/secuencia aleatoria. Si lo llamas una vez cuando se inicia el programa, obtienes la limitación de "una vez por segundo". Al llamarlo cada vez, en realidad puede terminar con menos aleatoriedad en sus resultados.
• Su función real (aleatorio) parece depender de un detalle de implementación privada de Lua. Lo que sucede en la próxima versión principal si cambia este detalle, siempre devuelve el mismo número, o solo números pares, etc. Simplemente porque funciona por ahora no es una garantía lo suficientemente fuerte, especialmente en el caso de querer un RNG seguro. .
• Cuando dices "todo parece perfectamente aleatorio", ¿cómo estás midiendo este rendimiento? Los humanos somos terribles para determinar si una secuencia es aleatoria o no, y simplemente mirando una secuencia de números sería prácticamente imposible decir realmente si fueron aleatorios o no. Hay muchas maneras de cuantificar la "aleatoriedad" de una serie que incluye distribución de frecuencia, autocorrelación, compresión y muchas más más allá de mi comprensión.
• Si está escribiendo un verdadero "PRNG seguro" para producción, ¡no escriba el suyo! Investigue y use una biblioteca o algoritmo por expertos que han pasado años/décadas estudiando, diseñando e intentando romperlo. La verdadera generación segura de números aleatorios es difícil.

Si necesita más información, comience por el artículo PRNG en Wikipedia y utilice las referencias/enlaces allí cuando sea necesario.

Answer 3

1. No debe llamar la semilla cada vez que llame al azar, usted debe llamar sólo una vez, en el inicio del programa (a menos que obtenga la semilla de alguna parte, por ejemplo, para replicar algunos anterior "al azar "comportamiento".

2. El generador aleatorio Lua estándar es de mala calidad en el sentido estadístico (ya que es, de hecho, generador aleatorio estándar C), no lo use si lo desea. Utilice, por ejemplo, el módulo lrandom (disponible en LuaRocks).

3. Si necesita más seguridad al azar, lea desde /dev/random en Linux. (Creo que Windows debe tener algo a lo largo de las mismas líneas -. Pero puede que tenga que codificar algo en C para usarlo)

4. Basándose en los valores de indicador de la mesa es una mala idea. Piense en implementaciones de Lua alternativas, en Java, por ejemplo, no se sabe qué devolverían. (Además, los valores del puntero pueden ser predecibles, y pueden ser, en ciertas circunstancias, los mismos cada vez que se invoca el programa).

5. Si desea una precisión más fina para la semilla (y lo querrá solo si 'iniciando el programa más de una vez por segundo), debe usar un temporizador con mejor resolución. Por ejemplo, socket.gettime() de LuaSocket. Multiplíquelo por algún valor, ya que math.randomseed está trabajando solo con la parte entera, y socket.gettime() devuelve el tiempo en (coma flotante) segundos.

   require 'socket' 
   
   math.randomseed(socket.gettime() * 1e6) 
   
   for i = 1, 1e3 do 
       print(math.random()) 
   end 
   

Answer 4

Este método sin embargo tiene una importante debilidad; El número devuelto es siempre tan aleatorio como el tiempo actual , Y el intervalo para cada número aleatorio es de un segundo, que es demasiado de largo si se necesitan muchos valores aleatorios en muy poco tiempo.

Tiene esas debilidades solo si lo implementa incorrectamente.

math.randomseed se supone que se llama con moderación, por lo general solo una vez al principio de su programa, y ​​por lo general las semillas utilizan os.time. Una vez que se establece la semilla, puede usar math.random muchas veces, y arrojará valores aleatorios.

ver lo que sucede en este ejemplo:

> math.randomseed(1) 
> return math.random(), math.random(), math.random() 
0.84018771715471 0.39438292681909 0.78309922375861 
> math.randomseed(2) 
> return math.random(), math.random(), math.random() 
0.70097636929759 0.80967634907443 0.088795455214007 
> math.randomseed(1) 
> return math.random(), math.random(), math.random() 
0.84018771715471 0.39438292681909 0.78309922375861 

Cuando cambio la semilla desde 1 hasta 2, consigo diferentes resultados aleatorios. Pero cuando vuelvo a 1, la "secuencia aleatoria" se restablece. Obtengo los mismos valores que antes.

os.time() devuelve un número cada vez mayor. Usarlo como semilla es apropiado; luego puede invocar math.random para siempre y tener diferentes números aleatorios cada vez que lo invoque.

El único escenario del que debe preocuparse un poco la no aleatoriedad es cuando se supone que su programa debe ejecutarse más de una vez por segundo. En ese caso, como dicen los otros, la solución más simple es usar un reloj con una definición más alta.

En otras palabras:

• invocación math.randomseed con una semilla apropiada (os.time() es aceptable un 99% de los casos) al comienzo de su programa
• math.random invocación cada vez que se necesita un número aleatorio .

¡Recuerdos!