Redes de Feistel: componentes básicos de los cifrados modernos

A principios de la década de 1970, Horst Feistel trabajaba en IBM Research con el cifrado Lucifer cuando desarrolló una idea fundamental: se puede construir un cifrado invertible utilizando una función de ronda no invertible.

Esto fue revolucionario porque resulta difícil diseñar funciones invertibles que también sean seguras. La construcción de Feistel evita por completo este requisito y permite utilizar funciones de ronda unidireccionales y de complejidad arbitraria.

En un cifrado de Feistel, el bloque de entrada se divide en dos mitades iguales: L, la izquierda, y R, la derecha. En cada ronda, se aplica la función de ronda F a R, se combina el resultado con L mediante XOR y después se intercambian las mitades.

Después de n rondas, las dos mitades se vuelven a combinar para producir el texto cifrado. El intercambio garantiza que ambas mitades se procesen en rondas alternas y se mezclen por completo.

La función de ronda F de una red de Feistel recibe como entradas la mitad derecha y la subclave de ronda, y produce una salida que se combina mediante XOR con la mitad izquierda. Lo esencial es que F no tiene que ser invertible.

F puede tener una complejidad arbitraria: cualquier combinación de sustituciones, permutaciones, operaciones XOR y aritmética modular. Cuanto más compleja y no lineal sea F, más fuerte será el cifrado, porque el descifrado nunca necesita invertir F.

El descifrado en un cifrado de Feistel utiliza exactamente la misma estructura que el cifrado, pero aplica las subclaves de ronda en orden inverso. Esto es posible porque XOR es su propia inversa: si A XOR B = C, entonces C XOR B = A.

Como el descifrado nunca invoca F^-1, la inversa de F, la función de ronda puede ser un hash irreversible, una tabla de consulta o cualquier operación compleja sin afectar a la invertibilidad del cifrado.

La elegancia matemática de las redes de Feistel reside en que la estructura XOR garantiza la invertibilidad independientemente de lo que haga F. Aunque F sea una función unidireccional como SHA-256, el cifrado de Feistel completo sigue siendo invertible.

Esto hace que los cifrados de Feistel sean extremadamente flexibles. Los criptógrafos pueden centrarse por completo en hacer que F proporcione la mayor confusión y difusión posibles, sabiendo que la invertibilidad está gestionada por la propia estructura de la red.

El Data Encryption Standard (DES), publicado en 1977, es un cifrado de Feistel de 16 rondas que opera con bloques de 64 bits y una clave de 56 bits. Cada ronda utiliza una subclave diferente de 48 bits derivada de la clave principal.

La función de ronda de DES incluye una permutación de expansión, una operación XOR con la subclave, ocho cajas S que proporcionan no linealidad y una permutación mediante una caja P. Esta combinación proporciona confusión y difusión, tal como exigen los principios de diseño de cifrados de Shannon.

Blowfish, diseñado por Bruce Schneier en 1993, es un cifrado de Feistel con una longitud de clave variable, de 32 a 448 bits, y 16 rondas. Utiliza cajas S dependientes de la clave, lo que hace impracticables los ataques basados en cálculos precomputados.

Twofish, finalista en la competición AES, amplía las ideas de Blowfish con bloques de 128 bits y 16 rondas. Ambos siguen sin haber sido descifrados y se utilizan en aplicaciones como el hash de contraseñas bcrypt, que emplea una versión modificada de Blowfish.

Un cifrado de Feistel equilibrado divide el bloque en dos mitades iguales. Un Feistel no equilibrado utiliza mitades desiguales, como una división de 3/4 y 1/4.

Las redes de Feistel no equilibradas pueden ofrecer ventajas de seguridad en determinados contextos y se utilizan en algunos cifrados especializados. La familia de cifrados CAST utiliza una estructura de Feistel equilibrada de 64 bits.

En 1988, Michael Luby y Charles Rackoff demostraron que una red de Feistel de 3 rondas que utiliza funciones de ronda seudoaleatorias es una permutación seudoaleatoria segura (PRP), y que una versión de 4 rondas es una PRP fuerte.

Este resultado teórico proporcionó a las redes de Feistel una base sólida de seguridad demostrable, más allá de la confianza basada únicamente en la experiencia. Confirmó que la propia estructura de Feistel contribuye a la seguridad, además de hacerlo la función de ronda.

La red de sustitución-permutación (SPN) utilizada por AES aplica sustituciones y permutaciones a todo el bloque simultáneamente, en lugar de hacerlo a la mitad del bloque en cada ronda. Esto proporciona una difusión más rápida.

AES consigue una difusión completa en solo 4 rondas, mientras que la estructura de Feistel de DES necesita más rondas para alcanzar una difusión comparable. La SPN de AES también se adapta mejor a las arquitecturas de procesadores modernos con instrucciones SIMD.

El teorema de Luby-Rackoff trata la función de ronda F como una función verdaderamente aleatoria. En la práctica, F es una función seudoaleatoria, como un cifrado basado en una clave o un hash, no un oráculo aleatorio verdadero.

Esta diferencia entre las demostraciones teóricas y las implementaciones prácticas es un tema recurrente en criptografía. Las demostraciones aportan confianza, pero se basan en modelos idealizados. La seguridad en el mundo real también depende de implementaciones seguras y libres de vulnerabilidades de canales laterales.

Compruebe su comprensión del diseño de las redes de Feistel.

Las redes de Feistel son estructuras de cifrado por bloques que utilizan una función de ronda que no tiene que ser invertible. El descifrado funciona ejecutando la misma estructura en orden inverso, con las subclaves en el orden contrario.

DES, Blowfish y Twofish son cifrados de Feistel. El teorema de Luby-Rackoff proporciona garantías teóricas de seguridad. AES utiliza una estructura SPN en su lugar, lo que ofrece una mejor difusión por ronda.