XOR de muchos ciclos de tamaño primo: ¿seguro?

@Mark está en el camino correcto, pero no del todo bien. Puede considerar los elementos de la matriz y la salida RNG como un sistema de ecuaciones lineales, pero no son linealmente independientes. De hecho, nunca puede recuperar completamente los elementos de la matriz, ya que si se almacena el mismo valor en todos los valores en dos de las matrices se obtendrá la misma salida de RNG, el valor se incluye dos veces en cada elemento de la salida de RNG, por lo que se cancela. En sí.

En realidad, esto facilita el trabajo del atacante, ya que no tienen que inferir la matriz completa para predecir toda la producción futura, por lo que no necesitan tantas ecuaciones (/ salidas). Es posible predecir todas las salidas solo (suma de números primos) - (número de números primos) + 1 salidas consecutivas.

Este es un ejemplo, utilizando matrices de longitudes 2, 3 y 5. Llame a las matrices A (longitud 2), B (longitud 3) y C (longitud 5), y la salida R. Luego tenemos:

R0 = A0 ⊕ B0 ⊕ C0
R1 = A1 ⊕ B1 ⊕ C1
R2 = A0 ⊕ B2 ⊕ C2
R3 = A1 ⊕ B0 ⊕ C3
R4 = A0 ⊕ B1 ⊕ C4
R5 = A1 ⊕ B2 ⊕ C0
R6 = A0 ⊕ B0 ⊕ C1
R7 = A1 ⊕ B1 ⊕ C2
R8 = A0 ⊕ B2 ⊕ C3
R9 = A1 ⊕ B0 ⊕ C4

Considera:

R0 ⊕ R3 ⊕ R5 = (A0 ⊕ B0 ⊕ C0) ⊕ (A1 ⊕ B0 ⊕ C3) ⊕ (A1 ⊕ B2 ⊕ C0)
 = A0 ⊕ B2 ⊕ C3
 = R8

Entonces, al guardar las salidas cero, tercera y quinta se predice la octava. Y al guardar el primero, cuarto y sexto se otorgaría el noveno, etc.

Resultado neto: esto es completamente inútil como un RNG criptográfico.

Puedo poner un límite superior a la fuerza: un atacante que puede observar un número de salidas consecutivas igual a la suma de las longitudes de las matrices individuales puede deducir los valores de las matrices y todas las salidas subsiguientes.

Considere el caso simple de tres matrices, con longitudes 2, 3 y 5: los primeros diez valores (las variables a ) y los valores ocultos que las generan (las variables x ), se muestran a continuación . Cada columna son los tres valores ocultos que están xored para producir el resultado visible.

x1 x2 x1 x2 x1 x2 x1 x2 x1 x2
x3 x4 x5 x3 x4 x5 x3 x4 x5 x3
x6 x7 x8 x9 x0 x6 x7 x8 x9 x0
-----------------------------
a0 a1 a2 a3 a4 a5 a6 a7 a8 a9

Si lo giras hacia un lado, esto se parece mucho a un sistema de diez ecuaciones en diez incógnitas: el tipo de cosas que las personas aprenden a resolver en el álgebra introductoria. Aunque la duración del ciclo es 30, solo se necesitan 10 valores consecutivos para caracterizar completamente el generador y predecir el siguiente valor.

A medida que crece el número de matrices, también lo hace la disparidad entre la duración del ciclo y la facilidad para romperla: diez matrices de longitud 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 dan una longitud de ciclo de 6,469,693,230, pero solo requiere 129 valores para romper.

Es posible que un atacante que ya conoce el contenido de las matrices rompa la seguridad con menos valores, pero no estoy seguro de cómo se haría.

NUNCA ROLLAS TU PROPIO CRIPTO . Ok, ahora que está fuera del camino.

Hola,

Ya respondiste tu pregunta cuando la hiciste, este es un PRNG. PRNG no es lo mismo que CSPRNG (generador de números pseudoaleatorios seguro criptográficamente), lo que significa un generador de números pseudoaleatorios para el que se cree que es imposible predecir su producción sin conocer las semillas. Incluso si su solución es tan buena como la de los PRNG predeterminados en las bibliotecas integradas, no importa. El pseudoaleatorio implica cierto nivel de previsibilidad que permitiría a los atacantes predecir los valores futuros de sal y nonce (entre otras cosas, como las cookies de sesión) y permitirles eludir muchos de sus mecanismos de defensa, como los tokens anti-CSRF, las ID de sesión en las cookies. y contraseña salada en su base de datos.

Por lo tanto, nada de lo que se conoce como pseudoaleatorio es seguro. Además, casi puedo garantizar que cualquier solución CSPRNG que usted, yo o casi cualquiera tenga, tiene algún nivel de previsibilidad y un matemático se reiría de nosotros.

Entonces no, en realidad no sería seguro. Sin embargo, tengo una idea interesante y, de acuerdo con tu comentario, no planeabas usarla en aplicaciones del mundo real, así que acabaré con mi perorata.

EDITAR: Siguiendo el comentario de AndrolGenhald sobre mi mala terminología de "crypto-random", actualicé el lenguaje para confiar en el término preciso, CSPRNG. Disculpas.