Rompe el cifrado roto

12

He diseñado un generador aleatorio simple que cicla dos números de manera caótica utilizando un método de multiplicación y módulo. Funciona muy bien para eso.

Sin embargo, si lo usara como generador de cifrado, sería vulnerable a un ataque de texto sin formato conocido, dado que un atacante puede realizar ingeniería inversa de la semilla de una serie de números aleatorios de una manera computacionalmente eficiente.

Para probar que el cifrado no funciona, encuentre un par legal de valores de inicialización que generen 7 ceros seguidos en el rango [0; 255], utilizando la menor potencia, tiempo de CPU, etc. posible.

Aquí está el generador aleatorio escrito en JavaScript:

function seed(state1,state2){
    //Constants
    var mod1=4294967087
    var mul1=65539
    var mod2=4294965887
    var mul2=65537
    function random(limit){
        //Cycle each state variable 1 step
        state1=(state1*mul1)%mod1
        state2=(state2*mul2)%mod2
        //Return a random variable
        return (state1+state2)%limit
    }
    //Return the random function
    return random
}

//Initiate the random generator using 2 integer values,
//they must be in the ranges [1;4294967086] and [1;4294965886]
random=seed(31337,42)
//Write 7 random values in the range [0;255] to screen
for(a=0;a<7;a++){
    document.write(random(256)+"<br>")
}

He creado una herramienta para probar pares de números candidatos, se puede encontrar aquí .

Durante los próximos 3 días, no se permiten spoilers , una respuesta debe contener solo un conjunto de números y, por supuesto, debe ser un conjunto diferente de los publicados por solucionadores anteriores. A partir de entonces, se le recomienda publicar código y explicar su enfoque.

Editar, la cuarentena ha terminado: las
respuestas deben contener un conjunto único de números y una explicación y un código para documentar el método de resolución.

La solución más elegante gana.

Para el registro:
escribir un programa que pueda encontrar una solución rápidamente es elegante.
Hacer un programa que utilice las características de una GPU de manera eficiente para hacerlo aún más rápido es elegante.
Hacer el trabajo en una pieza de "museo" es elegante.
Encontrar un método de solución que pueda utilizarse con solo lápiz y papel es muy elegante.
Explicar su solución de manera instructiva y fácil de entender es elegante.

Usar computadoras múltiples o muy caras es poco elegante.

aaaaaaaaaaaa
fuente
¿Estás seguro de que existe una respuesta para esto?
Wile E. Coyote
Sí, hay ~ 256 de ellos. Y también estoy seguro de que es posible encontrar una respuesta en unos minutos, dada una PC moderna y la programación correcta.
aaaaaaaaaaaa
Solo me pregunto, ¿por qué las GPU son elegantes pero no múltiples CPU?
JB
Porque son más difíciles de programar de manera eficiente que las CPU. Debes asegurarte de que realmente estás utilizando la GPU, no hay puntos para que la mayoría de los sombreadores estén inactivos porque algún otro subsistema tiene un cuello de botella. Y, por supuesto, aún debe implementar un algoritmo eficiente para anotar los grandes puntos.
aaaaaaaaaaaa
Si envío mi código de trabajo, es casi como si hubiera enviado un gran grupo de pares de semillas. ¿Fin del juego ya?
JB

Respuestas:

6

C ++, 44014022/164607120

Está en C ++, usa 1 GB de memoria y tardó unos 45 segundos en encontrar este primer par. Actualizaré la hora una vez que los encuentre a todos.

Código a continuación. Primero encuentra todos los pares que generan 4 ceros, luego los reduce mediante una prueba simple (vea el checkmétodo). Encuentra pares que generan 4 ceros al generar dos matrices grandes, una que contiene los primeros 4 bytes de bajo orden del generador de estado1 y la segunda que contiene el negativo de los primeros 4 bytes de bajo orden del generador de estado2. Estas matrices se ordenan y se busca una coincidencia, que corresponde al generador general que genera 4 ceros para comenzar.

Las matrices son demasiado grandes para almacenarlas en la memoria, por lo que hace el trabajo en lotes dimensionados para caber en la memoria.

Parece que la ejecución completa tomará ~ 12 horas.

Editar : se mejoró el código, por lo que solo lleva ~ 1 hora obtener todas las semillas posibles. Ahora genera las tablas en 256 archivos diferentes, uno para cada primer byte de salida. Entonces podemos procesar cada archivo de forma independiente para no tener que regenerar datos.

Editar : resulta que puede generar las 256 subtablas individualmente en lugar de todas a la vez, por lo que no se necesita disco. Tiempo de ejecución hasta ~ 15 minutos con 256 MB.

#include <stdio.h>
#include <stdint.h>
#include <algorithm>
using namespace std;

#define M1 65539
#define N1 4294967087
#define M2 65537
#define N2 4294965887
#define MATCHES 7

// M^-1 mod N                                                                                                                                                        
#define M1_INV 3027952124
#define M2_INV 1949206866

int npairs = 0;

void check(uint32_t seed1, uint32_t seed2) {
  uint32_t s1 = seed1;
  uint32_t s2 = seed2;
  for (int i = 0; i < MATCHES; i++) {
    s1 = (uint64_t)s1 * M1 % N1;
    s2 = (uint64_t)s2 * M2 % N2;
    if (((s1 + s2) & 0xff) != 0) return;
  }
  printf("%d %u %u\n", npairs++, seed1, seed2);
}

struct Record {
  uint32_t signature; // 2nd through 5th generated bytes                                                                                                             
  uint32_t seed;      // seed that generated them                                                                                                                    
};
// for sorting Records                                                                                                                                               
bool operator<(const Record &a, const Record &b) {
  return a.signature < b.signature;
}

int main(int argc, char *argv[]) {
  Record *table1 = (Record*)malloc((N1/256+1)*sizeof(*table1));
  Record *table2 = (Record*)malloc((N2/256+1)*sizeof(*table2));

  for (int i = 0; i < 256; i++) {  // iterate over first byte                                                                                                        
    printf("first byte %x\n", i);

    // generate signatures (bytes 2 through 5) for all states of generator 1                                                                                         
    // that generate i as the first byte.                                                                                                                            
    Record *r = table1;
    for (uint64_t k = i; k < N1; k += 256) {
      uint32_t sig = 0;
      uint32_t v = k;
      for (int j = 0; j < 4; j++) {
        v = (uint64_t)v * M1 % N1;
        sig = (sig << 8) + (v & 0xff);
      }
      r->signature = sig;
      r->seed = k;
      r++;
    }
    Record *endtable1 = r;

    // generate signatures (bytes 2 through 5) for all states of generator 2                                                                                         
    // that generate -i as the first byte.                                                                                                                           
    r = table2;
    for (uint64_t k = (-i & 0xff); k < N2; k += 256) {
      uint32_t sig = 0;
      uint32_t v = k;
      for (int j = 0; j < 4; j++) {
        v = (uint64_t)v * M2 % N2;
        sig = (sig << 8) + (-v & 0xff);
      }
      r->signature = sig;
      r->seed = k;
      r++;
    }
    Record *endtable2 = r;

    sort(table1, endtable1);
    sort(table2, endtable2);

    // iterate through looking for matches                                                                                                                           
    const Record *p1 = table1;
    const Record *p2 = table2;
    while (p1 < endtable1  && p2 < endtable2) {
      if (p1->signature < p2->signature) p1++;
      else if (p1->signature > p2->signature) p2++;
      else {
        check((uint64_t)p1->seed * M1_INV % N1, (uint64_t)p2->seed * M2_INV % N2);
        // NOTE: may skip some potential matches, if p1->signature==(p1+1)->signature or p2->signature==(p2+1)->signature                                            
        p1++;
      }
    }
  }
}
Keith Randall
fuente
No pensé que un disco duro sería lo suficientemente rápido como para ser eficiente para la tarea. Interesante.
aaaaaaaaaaaa