Dos peces | |
---|---|
Creador | un grupo de especialistas dirigido por Bruce Schneier |
Creado | 1998 |
Tamaño de clave | 128/192/256 bits |
Tamaño de bloque | 128 bits |
Número de rondas | dieciséis |
Tipo de | Red Feistel |
Twofish es un cifrado de bloque simétrico con un tamaño de bloque de 128 bits y una longitud de clave de hasta 256 bits. Número de rondas 16. Desarrollado por un grupo de especialistas liderado por Bruce Schneier . Fue uno de los cinco finalistas de la segunda etapa del concurso AES . El algoritmo se basa en los algoritmos Blowfish , SAFER y SQUARE .
Las características distintivas del algoritmo son el uso de nodos de reemplazo precalculados y dependientes de la clave y un esquema complejo para desenvolver las subclaves de cifrado. La mitad de la clave de cifrado de n bits se usa como la clave de cifrado real, la otra mitad se usa para modificar el algoritmo (los nodos de sustitución dependen de ello).
Twofish fue desarrollado específicamente para cumplir con los requisitos y recomendaciones de NIST para AES [1] :
Sin embargo, fue la complejidad de la estructura del algoritmo y, en consecuencia, la complejidad de su análisis de claves débiles o enlaces ocultos, así como el tiempo de ejecución bastante lento en comparación con Rijndael en la mayoría de las plataformas, lo que no jugó a su favor [2 ] .
El algoritmo Twofish se originó a partir de un intento de modificar el algoritmo Blowfish para un bloque de entrada de 128 bits. El nuevo algoritmo tenía que ser fácilmente implementable en hardware (incluido el uso de tablas más pequeñas), tener un sistema de expansión de claves más avanzado ( programación de claves en inglés ) y tener una función F de un solo valor.
Como resultado, el algoritmo se implementó como una red Feistel mixta con cuatro ramas que se modifican entre sí mediante la transformación criptográfica Hadamar ( ing. pseudo-Hadamar transform, PHT ).
La posibilidad de una implementación eficiente en procesadores modernos (para ese momento) de 32 bits (así como en tarjetas inteligentes y dispositivos similares) es uno de los principios clave que guiaron a los desarrolladores de Twofish.
Por ejemplo, la función F, al calcular PHT y sumar a la parte clave K, usa intencionalmente la suma en lugar del xor tradicional . Esto hace posible utilizar la instrucción LEA de la familia de procesadores Pentium, que permite calcular la transformada de Hadamard en un ciclo de reloj . (Sin embargo, en este caso, el código debe compilarse para un valor clave específico).
El algoritmo de Twofish no está patentado y puede ser utilizado por cualquier persona sin pagar tarifas ni regalías. Se usa en muchos programas de encriptación, aunque es menos común que Blowfish .
Twofish divide el bloque de datos de entrada de 128 bits en cuatro subbloques de 32 bits, en los que, después del procedimiento de blanqueamiento de entrada, se realizan 16 rondas de transformaciones. Después de la última ronda, se realiza el blanqueamiento de salida.
El blanqueamiento es un procedimiento para extraer datos con subclaves antes de la primera ronda y después de la última ronda. Esta técnica fue utilizada por primera vez en el cifrado Khufu / Khare e independientemente por Ron Rivest en el algoritmo de cifrado DESX . Joe Killian (NEC) y Phillip Rogaway (Universidad de California) han demostrado que el blanqueamiento dificulta la tarea de búsqueda exhaustiva de claves en DESX [3] . Los desarrolladores de Twofish argumentan [4] que en Twofish el blanqueamiento también complica significativamente la tarea de adivinar la clave, ya que el criptoanalista no puede averiguar qué datos entran en la entrada de la función de primera ronda F.
Sin embargo, también hubo aspectos negativos. Un estudio interesante fue realizado por especialistas del IBM Research Center. [5] Implementaron el algoritmo Twofish en una tarjeta inteligente CMOS típica y analizaron la posibilidad de un ataque mediante el análisis de potencia diferencial (DPA). Fue el procedimiento de blanqueo de entrada el que fue atacado, ya que utiliza directamente el xor de subclaves con los datos de entrada. Como resultado, los investigadores demostraron que es posible calcular completamente una clave de 128 bits analizando solo 100 operaciones de cifrado de bloques aleatorios.
La función g es la base del algoritmo Twofish. La entrada de la función es un número X de 32 bits, que luego se divide en cuatro bytes x0, x1, x2, x3. Cada uno de los bytes resultantes se pasa a través de su S-box. (Cabe señalar que los S-boxes en el algoritmo no son fijos, sino que dependen de la clave). Los 4 bytes resultantes en las salidas de las cajas S se interpretan como un vector con cuatro componentes. Este vector se multiplica por una matriz MDS (distancia máxima separable) fija de 4x4, y los cálculos se realizan en el campo de Galois módulo el polinomio irreducible
Una matriz MDS es una matriz sobre un campo finito K que si la tomamos como una matriz de una transformación lineal de espacio a espacio , entonces dos vectores cualesquiera del espacio de la forma (x, f(x)) serán tener al menos m + 1 diferencias en los componentes. Es decir, un conjunto de vectores de la forma (x, f(x)) forma un código con la propiedad de código separable de distancia máxima. Tal código, por ejemplo, es el código Reed-Solomon .
En Twofish, la propiedad de máxima diversidad de la matriz MDS significa que el número total de bytes cambiantes del vector a y el vector es al menos cinco. En otras palabras, cualquier cambio en un solo byte en a cambia los cuatro bytes en b.
La transformación Crypto Hadamard es una transformación reversible de una cadena de bits de longitud 2n. La cadena se divide en dos partes a y b de la misma longitud en n bits. La transformación se calcula de la siguiente manera:
Esta operación se usa a menudo para "dispersar" el código (por ejemplo, en el cifrado SAFER ).
En Twofish, esta transformación se usa al mezclar los resultados de dos funciones g (n = 32).
En cada ronda, los dos bloques de 32 bits de la derecha que se extraen con los resultados de la función F se rotan adicionalmente un bit. El tercer bloque se desplaza antes de la operación xor, el cuarto bloque después. Estos cambios se agregan deliberadamente para romper la alineación de bytes que es inherente a las cajas S y las multiplicaciones de matrices MDS. Sin embargo, el cifrado deja de ser completamente simétrico, ya que durante el cifrado y el descifrado los cambios deben realizarse en direcciones opuestas.
Twofish está diseñado para trabajar con claves de 128, 192 y 256 bits. A partir de la clave inicial se generan 40 subclaves de 32 bits, de las cuales las ocho primeras se utilizan únicamente en las operaciones de blanqueo de entrada y salida, y las 32 restantes se utilizan en rondas de cifrado, dos subclaves por ronda. Una característica de Twofish es que la clave original también se utiliza para cambiar el propio algoritmo de cifrado, ya que las cajas S utilizadas en la función g no son fijas, sino que dependen de la clave.
Para formar subclaves redondas, la clave original M se divide con una permutación de bytes en dos bloques idénticos y . Luego, usando el bloque y la función h, se encripta el valor 2*i, y usando el bloque , se encripta el valor 2*i+1, donde i es el número de la ronda actual (0 - 15). Los bloques cifrados resultantes se mezclan mediante la criptotransformación de Hadamard y luego se usan como subclaves redondas.
Consideremos con más detalle el algoritmo para generar subclaves redondas, así como la función dependiente de clave g. Tanto la generación de subclaves como la formación de funciones g en Twofish utilizan una función principal: h(X, L 0 , L 1 , … , L k ). Aquí X, L 0 , L 1 , … , L k son palabras de 32 bits y k = N / 64, donde N es la longitud de la clave original en bits. El resultado de la función es una palabra de 32 bits.
La función se ejecuta en k etapas. Es decir, para una longitud de clave de 256 bits habrá 4 etapas, para una clave de 192 bits - 3 etapas, para 128 bits - 2 etapas.
En cada etapa, la palabra de entrada de 32 bits se divide en 4 bytes, y cada byte está sujeto a una permutación de bits fija q 0 o q 1
El resultado se representa como un vector de 4 bytes y se multiplica por la matriz MDS. Los cálculos se realizan en el campo de Galois GF(2 8 ) módulo el polinomio irreducible .
La matriz MDS tiene la forma:Permutaciones q 0 yq 1
q 0 yq 1 son permutaciones fijas de 8 bits del byte de entrada x.
El byte x se divide en dos mitades de 4 bits a 0 y b 0 , sobre las cuales se realizan las siguientes transformaciones:
Aquí hay un desplazamiento cíclico de 4 bits hacia la derecha, y t 0 , t 1 , t 2 , t 3 son reemplazos de tablas de números de 4 bits.
Para q 0 las tablas se ven como:
t 0 = [ 8 1 7 D 6 F 3 2 0 B 5 9 ECA 4 ] t 1 = [ BCE 8 1 2 3 5 F 4 A 6 7 0 9 D ] t 2 = [ BA 5 mi 6 re 9 0 C 8 F 3 2 4 7 1 ] t 3 = [ re 7 F 4 1 2 6 mi 9 segundo 3 0 8 5 CA ]Para q 1 las tablas se ven así:
t 0 = [ 2 8 BDF 7 6 E 3 1 9 4 0 CA 5 ] t 1 = [ 1 mi 2 segundo 4 C 3 7 6 AD 5 F 9 0 8 ] t 2 = [ 4 C 7 5 1 6 9 UN 0 ED 8 2 B 3 F ] t 3 = [ segundo 9 5 1 C 3 DE 6 4 7 F 2 0 8 UN ]Sea M la clave original, N su longitud en bits. Las subclaves se generan de la siguiente manera:
Las subclaves para la i-ésima ronda se calculan mediante las fórmulas:
La función g se define en términos de la función h : .
El vector S , como los vectores M e y M o , también se forma a partir de la clave original y consta de k palabras de 32 bits. Los bytes de la clave original se dividen en k grupos de ocho bytes. Cada uno de estos grupos se trata como un vector con 8 componentes y se multiplica por una matriz RS fija de 4 × 8 bytes. Como resultado de la multiplicación, se obtiene un vector que consta de cuatro bytes. Los cálculos se realizan en el campo de Galois módulo un polinomio irreducible . La matriz RS tiene la forma
Un estudio de Twofish con un número reducido de rondas mostró que el algoritmo tiene un gran margen de seguridad y, en comparación con el resto de finalistas de la competencia AES, resultó ser el más persistente. Sin embargo, su estructura inusual y relativa complejidad han planteado algunas dudas sobre la calidad de esta fortaleza.
La división de la clave original en dos mitades durante la formación de subclaves redondas provocó críticas. Los criptógrafos Fauzan Mirza y Sean Murphy sugirieron que tal división hace posible organizar un ataque de acuerdo con el principio de "divide y vencerás", es decir, dividir la tarea en dos similares, pero más simples [6] . Sin embargo, tal ataque en realidad no se llevó a cabo.
Para 2008, la mejor variante del criptoanálisis Twofish es una variante del criptoanálisis diferencial truncado, que fue publicada por Shiho Moriai y Yiqun Lisa Yin en Japón en 2000 [7] . Demostraron que se requieren 251 textos sin formato coincidentes para encontrar los diferenciales necesarios . Sin embargo, los estudios eran de naturaleza teórica, no se llevó a cabo ningún ataque real. En su blog, el creador de Twofish, Bruce Schneier , argumenta que tal ataque es imposible en la realidad [8] .
Criptosistemas simétricos | |
---|---|
Cifrados de flujo | |
Red Feistel | |
red SP | |
Otro |