Serpiente (cifra)

Serpiente

Etapa de mezcla lineal de Serpent
General
Diseñadores	Ross Anderson , Eli Biham , Lars Knudsen
Primera publicación	21 de agosto de 1998
Derivado de	Cuadrado
Proceso de dar un título	Finalista de la AES
Detalle del cifrado
Tamaños de claves	128, 192 o 256 bits
Tamaños de bloque	128 bits
Estructura	Red de sustitución-permutación
Rondas	32
El mejor criptoanálisis público
Todos los ataques conocidos públicamente son computacionalmente inviables, y ninguno de ellos afecta a la Serpent completa de 32 rondas. Un ataque de 2011 rompe la Serpent de 11 rondas (todos los tamaños de clave) con 2 116 textos planos conocidos, 2 107,5 de tiempo y 2 104 de memoria (como se describe en [1] ). El mismo artículo también describe dos ataques que rompen 12 rondas de Serpent-256. El primero requiere 2 118 textos planos conocidos, 2 228,8 de tiempo y 2 228 de memoria. El otro ataque requiere 2 116 textos planos conocidos y 2 121 de memoria, pero también requiere 2 237,5 de tiempo.

Serpent es un cifrador de bloques de clave simétrica que fue finalista en el concurso Advanced Encryption Standard (AES) , en el que quedó en segundo lugar detrás de Rijndael . ^[2] Serpent fue diseñado por Ross Anderson , Eli Biham y Lars Knudsen . ^[3]

Al igual que otras presentaciones 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 se puedan ejecutar en paralelo , utilizando porciones 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 serían suficientes contra los tipos conocidos de ataques, pero especificaron 32 rondas como seguro contra futuros descubrimientos en criptoanálisis. ^[5] El informe oficial del NIST sobre la competencia de AES clasificó a Serpent como poseedor de un alto margen de seguridad como 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 tuvo la menor cantidad de votos negativos entre los finalistas, pero se clasificó en segundo lugar en general porque Rijndael tuvo sustancialmente más votos positivos, siendo el factor decisivo que Rijndael permitió una implementación de software mucho más eficiente. ^{[ cita requerida ]}

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 gravámenes en cuanto a su uso. Como resultado, cualquiera es libre de incorporar Serpent en su software (o en implementaciones de hardware) sin pagar tarifas de licencia.

El programa de claves Serpent consta de tres etapas principales. En la primera etapa, la clave se inicializa agregando relleno si es necesario. Esto se hace para que las claves cortas se asignen a claves largas de 256 bits; se agrega un bit "1" al final de la clave corta seguido de bits "0" hasta que la clave corta se asigne a una clave larga. ^[4]

En la siguiente fase, las "preclaves" se derivan utilizando la clave inicializada previamente. Las partes de la clave de 32 bits se XORizan, el FRAC que es la fracción de la proporción áurea y el índice de redondeo se XORizan con las partes de la clave, el resultado de la operación XOR se gira a la izquierda por 11. El FRAC y el índice de redondeo se agregaron para lograr una distribución uniforme de los bits de las claves 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 redonda o “subclave” se coloca en la “IP de permutación inicial” para colocar los bits de la 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 ]; // roundkeys const uint8_t S [ 8 ][ 16 ] = {}; // S-boxes         /* programación de claves: obtener claves previas */ void get_pre ( uint32_t w [ 4 * 33 ], const uint32_t k [ 8 ]) { uint32_t x [ 4 * 33 + 8 ]; para ( int i = 0 ; i < 8 ; i ++ ) x [ i ] = k [ i ]; para ( 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 claves: 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 ) y 0x1 ) << 0 | (( w [ 4 * i + 1 ] >> k ) y 0x1 ) << 1 | (( w [ 4 * i + 2 ] >> k ) y 0x1 ) << 2 | (( w [ 4 * i + 3 ] >> k ) y 0x1 ) << 3 ]; for ( j = 0 ; j < 4 ; j ++ ) { sk [ i ][ j ] |= (( s >> j ) & 0x1 ) << k ; } } } }                                                                                                         void key_schedule () { uint32_t w [ 4 * 33 ]; obtener_pre ( w , clave ); obtener_sk ( w , subclave ); }        

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 conducirá a una diferencia de salida de 1 bit, una característica diferencial tiene una probabilidad de 1:4 o menos. ^[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 cajas-s de Serpent se han construido a partir de las 32 filas de las cajas-s de DES . Estas se transformaron intercambiando entradas y las matrices resultantes con las propiedades deseadas se almacenaron como cajas-s de Serpent. Este proceso se repitió hasta que se encontró un total de 8 cajas-s. En este proceso se utilizó la siguiente clave: "sboxesforserpent". ^[4]

La permutación inicial funciona con 128 bits a la vez, moviendo los bits de un lado a otro.

para i en 0 .. 127 intercambiar ( bit ( i ), bit (( 32 * i ) % 127 ) )             

La permutación final funciona con 128 bits a la vez, moviendo los bits de un lado a otro.

para i en 0 .. 127 intercambiar ( bit ( i ), bit (( 4 * i ) % 127 ) )             

Consta de operaciones XOR, S-Box, desplazamiento de bit a la izquierda y rotación de bit a la izquierda. Estas operaciones se realizan en 4 palabras de 32 bits.

para ( corto i = 0 ; i < 4 ; i ++ ) { X [ i ] = S [ i ][ B [ i ] ^ K [ i ]]; } X [ 0 ] = ROTL ( X [ 0 ], 13 ); X [ 2 ] = ROTL ( X [ 2 ], 3 ); X [ 1 ] = X [ 1 ] ^ X [ 0 ] ^ X [ 2 ]; X [ 3 ] = X [ 3 ] ^ X [ 2 ] ^ ( X [ 0 ] << 3 ); X [ 1 ] = ROTL ( X [ 1 ], 1 ); X [ 3 ] = ROTL ( X [ 3 ], 7 ); X [ 0 ] = X [ 0 ] ^ X [ 1 ] ^ X [ 3 ]; X [ 2 ] = X [ 2 ] ^ X [ 3 ] ^ ( X [ 1 ] << 7 ); X [ 0 ] = ROTL ( X [ 0 ], 5 ); X [ 2 ] = ROTL ( X [ 2 ], 22 ); para ( corto i = 0 ; i < 4 ; i ++ )                                                                         { B [ i + 1 ] = X [ i ]; }     

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 sustitución-permutació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 S-box 4×4 y una transformación lineal, excepto en la última ronda, en la que otro XOR de mezcla de claves reemplaza la transformación lineal. La capa no lineal en Rijndael usa una S-box 8×8 mientras que Serpent usa ocho S-boxes 4×4 diferentes. Las 32 rondas significan que Serpent tiene un margen de seguridad más alto que Rijndael; Sin embargo, Rijndael con 10 rondas es más rápido y más fácil de implementar para bloques pequeños. ^[9] Por lo tanto, Rijndael fue seleccionado como el ganador en la competencia AES.

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

El ataque XSL , si es efectivo, debilitaría a Serpent (aunque no tanto como debilitaría a Rijndael , que se convirtió en AES ). Sin embargo, muchos criptoanalistas creen que una vez que se tengan en cuenta las consideraciones de implementación, el ataque XSL sería más costoso que un ataque de fuerza bruta . ^{[ cita requerida ]}

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 de 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 claros conocidos y 2 ⁸⁹ tiempos, y 11 rondas de Serpent-192/256 con 2 ¹¹⁸ textos claros conocidos y 2 ¹⁸⁷ tiempos. ^[11]

Un artículo de 2009 observó que el orden no lineal de las cajas S de Serpent no era 3, como afirmaban los diseñadores. En concreto, cuatro elementos tenían un 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 simples conocidos, 2 ^107,5 de tiempo y 2 ¹⁰⁴ de memoria. ^[1]

El mismo artículo también describe dos ataques que rompen 12 rondas de Serpent-256. El primero requiere 2 ¹¹⁸ textos en claro conocidos, 2 ^228,8 de tiempo y 2 ²²⁸ de memoria. El otro ataque requiere 2 ¹¹⁶ textos en claro conocidos y 2 ¹²¹ de memoria, pero también requiere 2 ^237,5 de 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 – ​​A New Block Cipher Proposal for AES». Archivado desde el original el 17 de junio de 2014. Consultado 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