Serpiente (cifrado)

Serpent es un cifrador de bloques de clave simétrica que fue finalista en el concurso del Estándar de Cifrado Avanzado (AES) , en el que ocupó el segundo lugar después de Rijndael . ^{[ 2 ]} Serpent fue diseñado por Ross Anderson , Eli Biham y Lars Knudsen . ^{[ 3 ]}

Al igual que otras propuestas de AES , Serpent tiene un tamaño de bloque de 128 bits y admite un tamaño de clave de 128, 192 o 256 bits. ^{[ 4 ]} El cifrado es una red de sustitución-permutación de 32 rondas que opera en un bloque de cuatro palabras de 32 bits . Cada ronda aplica una de las ocho cajas S de 4 bits a 4 bits 32 veces en paralelo. Serpent fue diseñado para que todas las operaciones puedan ejecutarse en paralelo , utilizando segmentos de 32 bits . Esto maximiza el paralelismo, pero también permite el uso del extenso trabajo de criptoanálisis realizado en DES .

Serpent adoptó un enfoque conservador en materia de seguridad, optando por un amplio margen de seguridad: los diseñadores consideraron que 16 rondas eran suficientes contra los tipos de ataque conocidos, pero especificaron 32 rondas como seguro contra futuros descubrimientos en criptoanálisis. ^{[ 5 ]} El informe oficial del NIST sobre la competición AES clasificó a Serpent con un margen de seguridad alto, similar al de MARS y Twofish , y en contraste con el margen de seguridad adecuado de RC6 y Rijndael (actualmente AES). ^{[ 2 ]} En la votación final, Serpent obtuvo la menor cantidad de votos negativos entre los finalistas, pero se clasificó en segundo lugar en general porque Rijndael obtuvo sustancialmente más votos positivos, siendo el factor decisivo que Rijndael permitió una implementación de software mucho más eficiente.

El algoritmo de cifrado Serpent es de dominio público y no ha sido patentado . ^{[ 6 ]} El código de referencia es software de dominio público y el código optimizado está licenciado bajo la GPL . ^{[ 7 ]} No existen restricciones ni limitaciones respecto a su uso. Por lo tanto, cualquiera puede incorporar Serpent en su software (o en implementaciones de hardware) sin pagar tarifas de licencia.

El esquema de claves Serpent consta de 3 etapas principales. En la primera etapa, la clave se inicializa añadiendo relleno si es necesario. Esto se hace para que las claves cortas se correspondan con claves largas de 256 bits; se añade un bit "1" al final de la clave corta, seguido de bits "0", hasta que la clave corta se corresponde con la longitud de una clave larga. ^{[ 4 ]}

En la siguiente fase, las "preclaves" se derivan utilizando la clave previamente inicializada. Se realiza una operación XOR entre las partes de la clave de 32 bits, la fracción de la proporción áurea (FRAC) y el índice de ronda. El resultado de la operación XOR se rota 11 posiciones a la izquierda. La FRAC y el índice de ronda se añadieron para lograr una distribución uniforme de los bits de la clave durante las rondas. ^{[ 4 ]}

Finalmente, las "subclaves" se derivan de las "preclaves" generadas previamente. Esto da como resultado un total de 33 "subclaves" de 128 bits. ^{[ 4 ]}

Al final, la clave de ronda o "subclave" se coloca en la "permutación inicial IP" para colocar los bits de clave en la columna correcta. ^{[ 4 ]}

#define FRAC 0x9e3779b9 // parte fraccionaria de la proporción áurea #define ROTL(A, n) ((A) << n | (A) >> 32-n)uint32_t key [ 8 ]; // clave proporcionada por el usuario uint32_t subkey [ 33 ][ 4 ]; // claves redondas const uint8_t S [ 8 ][ 16 ] = {}; // cajas S/* Programación de teclas: obtener preclaves */ void get_pre ( uint32_t w [ 4 * 33 ], const uint32_t k [ 8 ]) { uint32_t x [ 4 * 33 + 8 ]; for ( int i = 0 ; i < 8 ; i ++ ) x [ i ] = k [ i ]; for ( int i = 8 ; i < 140 ; ​​i ++ ) { x [ i ] = ROTL ( x [ i -8 ] ^ x [ i -5 ] ^ x [ i -3 ] ^ x [ i -1 ] ^ FRAC ^ ( i -8 ), 11 ); w [ i -8 ] = x [ i ]; } }/* Programación de teclas: obtener subclaves */ void get_sk ( const uint32_t w [ 4 * 33 ], uint32_t ( * sk )[ 4 ]) {uint8_t i , p , j , s , k ; para ( i = 0 ; i < 33 ; i ++ ) { p = 32 + 3 - i ; para ( j = 0 ; j < 4 ; j ++ ) sk [ i ][ j ] = 0 ; para ( k = 0 ; k < 32 ; k ++ ) { s = S [ p % 8 ][(( w [ 4 * i + 0 ] >> k ) & 0x1 ) << 0 | (( w [ 4 * i + 1 ] >> k ) & 0x1 ) << 1 | (( w [ 4 * i + 2 ] >> k ) & 0x1 ) << 2 | (( w [ 4 * i + 3 ] >> k ) & 0x1 ) << 3 ]; for ( j = 0 ; j < 4 ; j ++ ) { sk [ i ][ j ] |= (( s >> j ) & 0x1 ) << k ; } } } }void key_schedule () { uint32_t w [ 4 * 33 ]; get_pre ( w , key ); get_sk ( w , subkey ); }

Las cajas s de Serpent son permutaciones de 4 bits y están sujetas a las siguientes propiedades:

• Una diferencia de entrada de 1 bit nunca dará lugar a una diferencia de salida de 1 bit; una característica diferencial tiene una probabilidad de 1:4 o menor. ^{[ 8 ]}
• Las características lineales tienen una probabilidad entre 1:2 y 1:4, la relación lineal entre los bits de entrada y salida tiene una probabilidad entre 1:2 y 1:8. ^{[ 8 ]}
• El orden no lineal de los bits de salida en función de los bits de entrada es 3. Sin embargo, se han encontrado bits de salida que, en función de los bits de entrada, tienen un orden de solo 2. ^{[ 8 ]}

Las s-cajas de Serpent se construyeron a partir de las 32 filas de las s-cajas DES . Estas se transformaron intercambiando entradas, y los arreglos resultantes con las propiedades deseadas se almacenaron como las s-cajas de Serpent. Este proceso se repitió hasta encontrar un total de 8 s-cajas. La siguiente clave se utilizó en este proceso: "sboxesforserpent". ^{[ 4 ]}

Rijndael es una red de transformación lineal por sustitución con diez, doce o catorce rondas, dependiendo del tamaño de la clave, y con tamaños de clave de 128 bits, 192 bits o 256 bits, especificados independientemente. Serpent es una red de permutación por sustitución que tiene treinta y dos rondas, más una permutación inicial y una final para simplificar una implementación optimizada. La función de ronda en Rijndael consta de tres partes: una capa no lineal, una capa de mezcla lineal y una capa XOR de mezcla de claves. La función de ronda en Serpent consta de XOR de mezcla de claves, treinta y dos aplicaciones paralelas de la misma caja S de 4×4 y una transformación lineal, excepto en la última ronda, donde otra XOR de mezcla de claves reemplaza la transformación lineal. La capa no lineal en Rijndael utiliza una caja S de 8×8 mientras que Serpent utiliza ocho cajas S de 4×4 diferentes. Las 32 rondas significan que Serpent tiene un margen de seguridad mayor que Rijndael; Sin embargo, Rijndael con 10 rondas es más rápido y fácil de implementar para bloques pequeños. ^{[ 9 ]} Por lo tanto, Rijndael fue seleccionado como el ganador en la competencia AES.

La versión original de Serpent, Serpent-0, se presentó en el quinto taller sobre cifrado rápido de software , pero una versión ligeramente modificada, Serpent-1, se presentó a la competición AES. El documento presentado a AES analiza los cambios, que incluyen diferencias en la programación de claves.

El ataque XSL , de ser efectivo, debilitaría a Serpent (aunque no tanto como a Rijndael , que se convirtió en AES ). Sin embargo, muchos criptoanalistas creen que, una vez consideradas las implicaciones de la implementación, el ataque XSL sería más costoso que un ataque de fuerza bruta .

En 2000, un artículo de Kohno et al. presenta un ataque de encuentro en el medio contra 6 de 32 rondas de Serpent y un ataque de bumerán amplificado contra 9 de 32 rondas en Serpent. ^{[ 10 ]}

Un ataque de 2001 realizado por Eli Biham , Orr Dunkelman y Nathan Keller presenta un ataque de criptoanálisis lineal que rompe 10 de 32 rondas de Serpent-128 con 2 ¹¹⁸ textos planos conocidos y 2 ⁸⁹ de tiempo, y 11 rondas de Serpent-192/256 con 2 ¹¹⁸ textos planos conocidos y 2 ¹⁸⁷ de tiempo. ^{[ 11 ]}

Un artículo de 2009 señaló que el orden no lineal de las cajas S de Serpent no era 3 como afirmaban los diseñadores. Específicamente, cuatro elementos tenían orden 2. ^{[ 8 ]}

Un ataque de 2011 realizado por Hongjun Wu, Huaxiong Wang y Phuong Ha Nguyen, también utilizando criptoanálisis lineal, rompe 11 rondas de Serpent-128 con 2 ¹¹⁶ textos planos conocidos, 2 ^107,5 de tiempo y 2 ¹⁰⁴ de memoria. ^{[ 1 ]}

El mismo documento describe dos ataques que logran superar 12 rondas de Serpent-256. El primero requiere ^2¹¹⁸ textos planos conocidos, ^2²²⁸, ⁸ tiempo y ^2²²⁸ memoria. El otro ataque requiere ^2¹¹⁶ textos planos conocidos y ^2¹²¹ memoria, pero también requiere ^2²³⁷, ⁵ tiempo.

• Tiger – función hash de los mismos autores

• Anderson, Ross; Biham, Eli; Knudsen, Lars (1998). "Criptografía: cifrados de 256 bits: implementación de referencia (envío AES)" .
• Biham, Eli. "Serpent: una nueva propuesta de cifrado por bloques para AES" . Archivado del original el 17 de junio de 2014. Recuperado el 15 de enero de 2013 .
• Halbfinger, David M (5 de mayo de 2008). "En el caso Pellicano, lecciones sobre técnicas de escuchas telefónicas" . The New York Times .
• Stajano, Frank (10 de febrero de 2006). "Implementación de referencia de Serpent" . Laboratorio de Computación de la Universidad de Cambridge.

• Sitio web oficial
• Cifrados de 256 bits : implementación de referencia de SERPENT y código derivado.