Isaac

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 18 de septiembre de 2018; las comprobaciones requieren 2 ediciones .

ISAAC (Indirection, Shift, Accumulate, Add and Count) es un generador de números pseudoaleatorios , desarrollado en 1996 por Robert J. Jenkins Jr., como un desarrollo de los algoritmos IA e IBAA desarrollados por él. Este generador está catalogado como generador de números pseudoaleatorios criptorresistentes , aunque no se ha realizado una prueba completa y rigurosa.

Historial de creación

El programador estadounidense Robert John Jenkins Jr. fue a Berkeley en 1993 para obtener un doctorado en informática teórica , después de graduarse de la Universidad Carnegie Mellon en 1989 y cuatro años en Oracle . A pesar de que estudiar en Berkeley fue una prueba seria para Jenkins -tuvo que dejarlo después de un año- fue aquí donde comenzó su trabajo en el estudio de generadores de números pseudoaleatorios como parte del curso de criptografía de Manuel Blum . . En julio de 1993, Jenkins comenzó a experimentar con números pseudoaleatorios para los procesadores Intel 486 y, en abril de 1994, se había desarrollado ISAAC. Es cierto que el artículo que describe su trabajo se publicó solo dos años después, en febrero de 1996. [una]

Los predecesores de ISAAC

RC4

El algoritmo de cifrado RC4 [2] [3] consta de dos pasos: la generación de una secuencia de bits pseudoaleatorios y el módulo dos de suma bit a bit de esta secuencia de texto sin formato .

En la etapa de generar una secuencia pseudoaleatoria, n juega un papel importante : el tamaño del S-box , la matriz de datos, que en realidad determina el estado interno de RC4 . Las siguientes variables también se usan en RC4: i y j son iteradores que se ejecutan a través de valores, una clave de matriz de longitud de longitud , en la que la clave se almacena de una manera especial, y una matriz S (también conocida como bloque S). Datos de salida: la matriz z es una secuencia pseudoaleatoria . $2^{n}$

Considere el algoritmo usando n = 8 como ejemplo . Primero , la matriz S se llena con números del 0 al , la matriz Key se llena con una secuencia de palabras de n bits. Si la longitud de la clave es menor que la longitud de S, entonces la secuencia se repite hasta que su longitud sea igual a . Entonces el algoritmo funciona así: $2^{n}-1$ $2^{n}$

yo = 0; j = 0; mientras yo < 256 //256 = 2^n j = (j + S[i] + Clave[longitud de mod i]) mod 256; intercambiar S[i] y S[j]; yo++;

Después de esta etapa, la etapa de inicialización, sigue la etapa de la generación real de la secuencia pseudoaleatoria:

yo = 0; j = 0; mientras yo < 256 j = (j + S[i]) módulo 256; intercambiar S[i] y S[j]; z[i] = S[(S[i] + S[j]) módulo 256]; yo++;

La salida es una secuencia de longitud n, con la ayuda de la cual se cifra el texto sin formato.

AI

IA (Indirection, Addition) es un algoritmo desarrollado por Jenkins para que pueda cumplir con los siguientes requisitos [4] :

la imposibilidad de obtener un estado interno a partir de los resultados de salida disponibles;
código fácil de recordar;
la mayor velocidad posible;

Datos de entrada del algoritmo IA: matriz S , compuesta por elementos de 0 a , distribuidos aleatoriamente en la matriz, iteradores i y j . La matriz de datos de salida z es el resultado del algoritmo. Además, los valores de las celdas en la matriz, es decir, la longitud de las palabras, debe ser mayor que el bit, Jenkins en su trabajo toma K = 32 bits, esta es la longitud de la palabra que se usa en todos los algoritmos descritos aquí. $2^{n}$ $2^{n}-1$ ${\ estilo de visualización 2 * n}$

IBAA

IBAA (Indirection, Barrelshift, Accumulate and Add) es un algoritmo creado por Jenkins basado en IA. El autor cree que IBAA tiene las siguientes ventajas además de las ventajas ya disponibles para IA [5] :

Seguridad criptográfica
No se deben detectar compensaciones en toda la duración del ciclo.
Los ciclos cortos deberían ser increíblemente raros.

A diferencia de RC4 e IA, IBAA se basa en cambios cíclicos de datos de bits hacia la izquierda. La implementación de IBAA utiliza el mismo conjunto de variables que IA, con la única diferencia de que se suman los acumuladores a y b , así como la función de desplazamiento de barril , función que realiza el desplazamiento cíclico mencionado anteriormente.

barril (j) : desplaza cíclicamente todos los bits en una matriz de 32 bits hacia la izquierda en 19 bits. También se puede dar por la fórmula , donde $(j<<19)\oplus (j>>13)$

$\oplus$ - XOR bit a bit

La operación >> aquí significa desplazamiento aritmético a la derecha .

ISAAC

Descripción

ISAAC (Indirection, Shift, Accumulate, Add and Count) es un algoritmo de números pseudoaleatorios, cuyo principio es más difícil de recordar que los principios de IA e IBAA, pero tiene una serie de ventajas sobre ellos [6] . Al diseñar ISAAC, se le presentó la siguiente lista de requisitos:

fuerza criptográfica ;
la imposibilidad de obtener un estado interno a partir de los resultados de salida disponibles;
falta de ciclos cortos;
la ausencia de tendencias en la distribución de bits a lo largo del ciclo;
los estados ordenados deben convertirse rápidamente en caóticos.

A diferencia de la mayoría de los generadores de números pseudoaleatorios, que se basan en cifrados de flujo , ISAAC está diseñado sin el uso de registros de desplazamiento de retroalimentación lineal.

El número medio de instrucciones de máquina necesarias para obtener un valor de 32 bits es 18,75. La versión de 64 bits de ISAAC (ISAAC-64) requiere 19 instrucciones para obtener un valor de 64 bits.

Algoritmo de operación

Al igual que en los algoritmos anteriores, ISAAC cuenta con un arreglo S que define el estado interno del sistema, compuesto también por elementos ubicados aleatoriamente en el arreglo desde 0 hasta una longitud de K bits, un iterador i y tres variables a , b y c , responsable de los estados anteriores del generador, la matriz de datos de salida z tiene la misma longitud que S . Sin embargo, además de estas variables, aquí también se introducen variables , que determinan el valor de la función que depende de ambos iteradores: $2^{n}$ $2^{n}-1$ ${\displaystyle p_{0},p_{1},p_{2},p_{3))$

$f(a,i)={\begin{cases}a<<p_{0},&{\text{if }}i\equiv 0{\text{ mod 4}}\\a>>p_ {1},&{\text{si}}i\equiv 1{\text{ mod 4}}\\a<<p_{2},&{\text{if}}i\equiv 2{\text{ mod 4}}\\a>>p_{3},&{\text{si}}i\equiv 3{\text{ mod 4}}\end{casos}}$ .

En su artículo, Jenkins sugiere . $p_{0}=13,p_{1}=6,p_{2}=2,p_{3}=16$

El esquema de operación del generador en un paso arbitrario para n = 8, K = 32 es el siguiente:

c = c + 1; b = b + c; yo = 0; mientras yo < 255 x = S[i]; a = f(a, i) + S[i + 128 mod 256]; S[i] = a + b + S[x>>2 mod 256]; z[i] = x + S[S[i]>>10 mod 256]; b = z[i]; yo++;

Criptoanálisis por ISAAC

En su sitio web personal, el autor de ISAAC anunció una competencia para piratear el generador: el primero que pueda especificar el número utilizado como semilla ( semilla en inglés ) para generar los primeros 2560 valores emitidos por el generador recibirá $ 1000 premio de Jenkins. Sin embargo, hasta ahora nadie ha sido capaz de hacer frente a esta tarea. Sin embargo, ISAAC ha sido considerado en los escritos de varios criptoanalistas.

El ataque de Pudovkina

En 2001, se publicó un artículo [7] , en el que Marina Pudovkina describía un ataque basado en textos sin formato , con el que se puede encontrar el estado inicial del generador a partir de un pequeño segmento de los datos de salida, y también daba una estimación precisa de la complejidad de tal ataque. Usando el algoritmo descrito en el artículo, Pudovkina logró reducir la complejidad de la piratería a , mientras que la complejidad de la búsqueda exhaustiva [8] . Según sus cálculos, para , la complejidad del descifrado por búsqueda exhaustiva es , mientras que usando el algoritmo de Pudovkina, este número podría reducirse a . Tal complejidad, sin embargo, sigue siendo demasiado grande para llamar a ISAAC un generador de números pseudoaleatorios vulnerable, resume el criptoanalista en su artículo. $T_{met}=2^{(2n+\theta _{2})(m-1)}(K-2n-\theta _{2}){\frac {2}{3}}m$ $T_{br}=2^{Km-1}$ $m=256,n=8,K=32,p_{\theta }=13,p_{1}=6,p_{2}=2,p_{3}=16,\theta _{1} = \ theta _ {2} = 2$ $T_{br}=5,91*10^{2446}$ $T_{met}=4,67*10^{1240}$

Análisis de Jean-Philippe Aumasson

En su artículo de 2006 [9] , Omasson describe cuatro conjuntos de estados iniciales "débiles" que pueden cruzarse entre sí. Los estados débiles son aquellos estados en los que algunos de los elementos son aleatorios y los elementos restantes tienen el mismo valor. Si es el estado inicial, entonces se puede definir usando la relación: , luego se define como , el conjunto se define como , mientras que se especifica de la siguiente manera: . El autor consideró el algoritmo ISAAC con los mismos valores dados anteriormente (es decir , n = 8, K = 32) y calculó el número de estados débiles para cada uno de los conjuntos. Porque este número era estados, para - estados, para - , pero es un subconjunto de . La presencia de tales estados aún no significa que ISAAC pueda ser pirateado fácilmente, pero son debilidades potenciales del algoritmo, por lo que Omasson propuso una versión modificada de ISAAC - ISAAC + [10] . ${\ estilo de visualización W_{1},W_{2},W_{3},W_{4))$ $\alfa$ $W_{1}$ ${\ estilo de visualización \ alfa \ en W_ {1} \ Longleftrightarrow \ alfa _ {0} = \ alfa _ {1}}$ $W_2$ $\alpha \in W_{2}\Longleftrightarrow \exists N\in \{2,...,256\},\exists X\in \{0,...,2^{32}-1 \},\alpha _{0}=X,\{0<i<256,\alpha _{i}=X\}=N-1$ ${\ estilo de visualización W_ {3}}$ $\alpha \in W_{3}\Longleftrightarrow \exists N\in \{2,...,256\},\exists X\in \{0,...,2^{32}-1 \},\para todo i\en \{0,...,N-1\},\alpha _{i}=X$ ${\ estilo de visualización W_ {4}}$ $\alpha \in W_{4}\Longleftrightarrow \exists X\in \{0,...,2^{32}-1\},\forall i\in \{0,...,255 \},\alfa _{i}=X$ $W_{1}$ ${\ estilo de visualización 2^{8160}}$ $W_2$ ${\ estilo de visualización 2^{8167.99}}$ ${\ estilo de visualización W_ {4}}$ $2^{32}$ ${\ estilo de visualización W_ {3}}$ $W_2$

ISAAC+

La entrada en algún paso es la misma que en ISAAC, los números a , b y c , el arreglo S , compuesto por 256 palabras de 32 bits, la salida es un arreglo z de la misma dimensión que S. En la descripción de la función, en lugar de desplazamientos de bits lógicos >> y <<, se utilizan >>> y <<< cíclicos, es decir, se utiliza la función ${\ estilo de visualización f (a, i)}$

$f'(a,i)={\begin{cases}a<<<p_{0},&{\text{if }}i\equiv 0{\text{ mod 4}}\\a> >>p_{1},&{\text{si}}i\equiv 1{\text{ mod 4}}\\a<<<p_{2},&{\text{if}}i\equiv 2 {\text{ mod 4}}\\a>>>p_{3},&{\text{if}}i\equiv 3{\text{ mod 4}}\end{casos}}$

La forma en que S[i] y z[i] se inician en cada paso también ha cambiado; en ambos casos, se utiliza XOR bit a bit. Es decir, en lugar de

S[i] = a + b + S[x>>2 mod 256]; z[i] = x + S[S[i]>>10 mod 256];

ISAAC+ utiliza:

S[i] = a ⊕ b + S[x>>>2 mod 256]; z[i] = x + a ⊕ S[S[i]>>>10 mod 256]; Ataque de Paul-Pranil. Crítica

En el mismo 2006, Paul y Praenil publicaron un artículo [11] en el que estudiaron un ataque distintivo en algunos generadores similares a RC4 de transmisión, incluidos IA e ISAAC . En su trabajo, muestran que la complejidad de romper ISAAC es solo [12] . Omasson no descartó este ataque [13] y señaló el inicio erróneo del algoritmo por parte de Paul y Prenil, por lo que se hizo posible reducir tanto la complejidad de romperlo. $T\aproximadamente 2^{17}$

Aplicación

Muchas implementaciones de ISAAC son lo suficientemente rápidas y confiables como para que este generador de números pseudoaleatorios se haya vuelto bastante común. ISAAC se utiliza, por ejemplo, en la utilidad de Unix shred (Unix) [14] para cifrar datos reescritos. El generador de números aleatorios basado en ISAAC se implementa en una de las bibliotecas matemáticas de Java más comunes, Apache Commons Math [15] .

Notas

↑ Breve autobiografía de Robert Jenkins . burtleburtle.net. Consultado el 25 de noviembre de 2016. Archivado desde el original el 9 de agosto de 2016. (indefinido)
↑ Schneier B., 2002 , pág. 236.
↑ Paul G., Sabemoy M., 2001 , pág. 16-19.
↑ Jenkins R.J., 1996 , p. 41, 42-43.
↑ Jenkins R.J., 1996 , p. 41, 43-45.
↑ Jenkins R.J., 1996 , p. 41, 46-49.
↑ Pudovkina MA, 2001 .
↑ Pudovkina MA, 2001 , p. 9.
↑ Omasson JF, 2006 .
↑ Omasson JF, 2006 , p. 5.
↑ Paul S., Preneel B., 2006 .
↑ Paul S., Preneel B., 2006 , pág. 9-10.
↑ Omasson JF, 2006 , p. 6.
↑ GNU coreutils git . Consultado el 3 de diciembre de 2016. Archivado desde el original el 21 de septiembre de 2019. (indefinido)
↑ Documentos de Apache Common Math . Consultado el 3 de diciembre de 2016. Archivado desde el original el 22 de abril de 2017. (indefinido)

Literatura

Schneier B. RC4 // Criptografía aplicada. Protocolos, algoritmos, código fuente en lenguaje C = Criptografía Aplicada. Protocolos, Algoritmos y Código Fuente en C. - M. : Triumf, 2002. - S. 236. - 816 p. - ISBN 5-89392-055-4 .
Paul G., Sabamoy M. RC4 Stream Cipher // RC4 Stream Cipher y sus variantes = RC4 Stream Cipher y sus variantes. - Boca Ratón: CRC Press, 2001. - S. 16-19. — 285 págs.
Jenkins R.J. ISAAC // Apuntes de clase en informática. - Cifrado rápido de software, 1996. - Vol. 1039 . - P. 41-49 .
Pudovkina M. A. Un conocido ataque de texto sin formato en el generador de flujo de claves ISAAC (ing.) . — Archivo de impresión electrónica de IACR, 2001.
Paul S., Pranil B. Sobre la (in)seguridad de los cifrados de flujo basados en matrices y adición modular (inglés) // Avances en criptología - Asiacrypt 2006. - Asiacrypt, 2006.
Omasson J.F. Sobre el generador pseudoaleatorio ISAAC . — Archivo de impresión electrónica de IACR, 2006.

Enlaces

Web oficial del proyecto ISAAC
Math::Random::ISAAC - Implementación Perl del algoritmo
http://guilload.com/pyisaac/ - implementación del algoritmo en Python
https://rosettacode.org/wiki/The_ISAAC_Cipher : implementación del algoritmo en 19 lenguajes de programación diferentes