Recientemente estuve viendo Poker shuffles que fueron pirateados y hechos para ser adivinables en un grado razonable y esto se debió a la debilidad de los shuffles. ¿Es posible hacer una reproducción aleatoria segura, incluso si el código para el cliente y el servidor está disponible?
Sí. De hecho, la mayoría de estos mecanismos rotos se barajan porque están usando algoritmos de barajado "secretos".
En términos generales, un mecanismo de barajado tiene dos componentes:
Si bien el algoritmo de barajado puede tener un cierto sesgo propio, todo el mecanismo de barajado no puede tener un sesgo menor al del PRNG. En otras palabras, un algoritmo de barajado no puede ser más aleatorio que su PRNG. Veamos uno de los algoritmos de barajado más eficientes que existen, el shuffle de Fisher – Yates .
El código fuente (o, más bien, el pseudocode ) de la mezcla aleatoria moderna de Fisher-Yates ha estado disponible públicamente desde 1964, con implementaciones en decenas de idiomas.
To shuffle an array a of n elements (indices 0..n-1):
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
Sin embargo, sigue siendo uno de los algoritmos más utilizados para este propósito.
Si te fijas bien, el algoritmo depende de random integer . Aquí es donde el PRNG entra en juego. Si su PRNG es imparcial y su implementación es correcta, entonces sus aleatorias también deben ser imparciales.
Hay disponibles muchos PRNG buenos que están bien examinados, probados en el tiempo y que han demostrado ser imparciales. Dado que un PRNG es determinista (para el mismo estado inicial, siempre devuelve el mismo valor), la seguridad / aleatoriedad de todo el mecanismo de mezcla aleatoria depende de la aleatoriedad del estado inicial del PRNG, su seed . Esta confianza en la calidad de la semilla es una extensión del Kerckhoffs 'Principle , ya que sin conocer el conocimiento de la semilla de El algoritmo no te dice nada. Afortunadamente, la mayoría de los PRNG buenos utilizan buenas "fuentes de aleatoriedad" proporcionadas por el sistema operativo, como /dev/urandom .
Para completar la respuesta de @Adnan: hay un código y hay datos. "Barajar" es aplicar una permutación en un espacio dado, que es muy parecido al cifrado. Entonces su pregunta puede ser reformulada como: ¿es posible cifrar los datos de manera segura, cuando el atacante conoce el código? Y la respuesta es: sí, siempre que el atacante no conozca la clave . La clave concentra el secreto. Separamos la clave del código precisamente para que el código no tenga que ser secreto, y lo hacemos porque es muy difícil mantener el código en secreto.
El algoritmo de Fisher-Yates (también conocido, incorrectamente, como "Knuth shuffle") se puede ver como un algoritmo de cifrado, cuya clave es la secuencia de valores aleatorios obtenidos de la fuente aleatoria. El código es bien conocido, pero se asume que el atacante no conoce estos valores. Siempre que los enteros aleatorios devueltos se obtengan de una fuente criptográficamente sólida e imparcial, esto es "perfecto" (cada permutación entre las 52! posibles permutaciones de un espacio de tamaño 52 se puede seleccionar con probabilidad uniforme ). La generación de enteros no sesgados en un rango dado, desde una fuente que produce bytes, está sujeta a algunas sutilezas, que pueden superarse (vea lo que escribí en la página 3 de este artículo ).
El caso general (permutar de forma segura un espacio de un tamaño arbitrario, no necesariamente una potencia de 2) está cubierto por Conservación de formato Cifrado . Cuando desea el libro de códigos completo, es decir, desea la permutación completa (ese es el caso de una baraja aleatoria, donde necesita saber dónde fue la tarjeta cada ), la baraja de Fisher-Yates es tan buena como la suya. puede conseguir Otras soluciones para FPE permiten una evaluación parcial (es decir, sin tener una matriz que contenga la mezcla completa) pero pueden inducir sesgos (en particular, los esquemas de Feistel siempre son permutaciones uniformes). No tiene sentido intentar hacer otra cosa que no sea Fisher-Yates para las tarjetas.
Un generador de números pseudoaleatorios criptográficamente seguro, con fuentes adecuadas de entropía, debe cumplir con sus requisitos bastante bien. Un CSPRNG debe comportarse de la misma manera, porque ser capaz de predecir valores futuros o determinar valores anteriores causaría que muchos sistemas de encriptación se vuelvan vulnerables. Poder predecir números aleatorios estaba en el corazón del infame error de Netscape.
Aquí hay una lista: enlace
Lea otras preguntas en las etiquetas cryptography random