¿Es posible descifrar g ++ rand ()?

5

Por lo tanto, tengo esto:

Sé que se usó algo de código para generar una secuencia aleatoria, y se parecía aproximadamente a esto:

#include <iostream>
#include <string>

int main() {
    const std::string alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    std::string temp = "1234567890";
    srand(MAGICNUMBER);
    for (int i = 0;; ++i) {
        for (int j = 0; j < 10; ++j) {
            temp[j] = alphabet[rand() % alphabet.size()];
        }
        std::cout << temp << std::endl;
    }
}

Se usó para generar una secuencia de 124660967 cadenas, la última de las cuales fue "2lwd9JjVnE", y luego se detuvo. El compilador utilizado fue g ++ 4.8 de 64 bits para Linux. Lo que quiero es encontrar la cadena 124660968, es decir, la que se imprimirá a continuación. La advertencia, por supuesto, es que no conozco el MAGICNUMBER . Estoy bastante seguro de que es posible forzar todas las posibilidades, pero parece que llevaría milenios. He intentado husmear en el código fuente de rand() , pero realmente no lo entiendo, y mucho menos explotarlo. ¿Es posible encontrar esa cadena en un tiempo más o menos razonable?

UPD ¿Es incluso posible generar lo que se supone que va después de mi cadena sin descubrir la semilla?

    
pregunta Akiiino 30.03.2016 - 16:03
fuente

2 respuestas

6

El compilador en sí es irrelevante; La función rand() es implementado en libc .

La implementación de glibc utiliza un generador lineal congruente (LCG) o un registro de desplazamiento de realimentación lineal (LFSR) para su rand() . Estos pueden ser fácilmente resquebrajados dados algunos de los resultados (que parece que tienes). Los detalles se pueden encontrar en la respuesta a otra pregunta ya formulada aquí , pero el problema es que las LCG y las LFSR no son seguras y que algunos cálculos y probabilidades simples pueden obtener la respuesta correcta con bastante rapidez.

Necesitarás averiguar qué versión de glibc se usó, pero la versión del compilador debería darte una idea aproximada del estado del parche del sistema, para que puedas deducirlo.

Puede encontrar más recursos en Google, pero aquí hay un conjunto rápido de enlaces para ayudar:

respondido por el Polynomial 30.03.2016 - 16:26
fuente
1

Google dice:

  

Para generar números aleatorios, srand generalmente se inicializa a algún valor distintivo de tiempo de ejecución, como el valor devuelto por la función time (declarado en el encabezado <ctime\> ). Esto es lo suficientemente distintivo para la mayoría de las necesidades aleatorias triviales.

Si se usa esta técnica y conoce una estimación más o menos cercana del tiempo (como, si puede reducirlo a un día), probablemente sea factible un ataque de fuerza bruta en el espacio de entrada izquierdo.

Aparte de eso, si sigues google un poco más, encontrarás una serie de entradas de blog Eso podría llevarte por el camino correcto.

    
respondido por el Tobi Nary 30.03.2016 - 16:20
fuente

Lea otras preguntas en las etiquetas