En criptografía , un cifrado Feistel (también conocido como cifrado de bloque Luby-Rackoff ) es una estructura simétrica utilizada en la construcción de cifrados de bloque , llamada así por el físico y criptógrafo alemán Horst Feistel , quien realizó una investigación pionera mientras trabajaba para IBM ; también se conoce comúnmente como red Feistel . Una gran cantidad de cifrados de bloque utilizan el esquema, incluido el Estándar de cifrado de datos de EE. UU., el GOST soviético/ruso y los cifrados Blowfish y Twofish más recientes . En un cifrado Feistel, el cifrado y el descifrado son operaciones muy similares, y ambas consisten en ejecutar iterativamente una función llamada " función de ronda " un número fijo de veces.
Muchos cifrados de bloques simétricos modernos se basan en redes Feistel. Las redes Feistel se vieron por primera vez comercialmente en el cifrado Lucifer de IBM , diseñado por Horst Feistel y Don Coppersmith en 1973. Las redes Feistel ganaron respetabilidad cuando el gobierno federal de los EE. UU. adoptó el DES (un cifrado basado en Lucifer, con cambios realizados por la NSA ) en 1976. Al igual que otros componentes del DES, la naturaleza iterativa de la construcción de Feistel hace que la implementación del criptosistema en hardware sea más fácil (particularmente en el hardware disponible en el momento del diseño de DES).
Una red Feistel utiliza una función de ronda , una función que toma dos entradas (un bloque de datos y una subclave) y devuelve una salida del mismo tamaño que el bloque de datos. [1] En cada ronda, la función de ronda se ejecuta en la mitad de los datos que se van a cifrar y su salida se combina con la otra mitad de los datos mediante una operación XOR. Esto se repite un número fijo de veces y la salida final son los datos cifrados. Una ventaja importante de las redes Feistel en comparación con otros diseños de cifrado, como las redes de sustitución-permutación, es que se garantiza que toda la operación sea invertible (es decir, los datos cifrados se pueden descifrar), incluso si la función de ronda no es en sí misma invertible. La función de ronda se puede complicar arbitrariamente, ya que no necesita estar diseñada para ser invertible. [2] : 465 [3] : 347 Además, las operaciones de cifrado y descifrado son muy similares, incluso idénticas en algunos casos, y solo requieren una inversión del programa de claves . Por lo tanto, el tamaño del código o circuito necesario para implementar un cifrado de este tipo se reduce casi a la mitad. A diferencia de las redes de sustitución-permutación, las redes de Feistel tampoco dependen de una caja de sustitución que podría causar canales secundarios de temporización en las implementaciones de software.
La estructura y las propiedades de los cifrados Feistel han sido ampliamente analizadas por los criptógrafos .
Michael Luby y Charles Rackoff analizaron la construcción del cifrado de Feistel y demostraron que si la función de ronda es una función pseudoaleatoria criptográficamente segura , con K i utilizada como semilla, entonces 3 rondas son suficientes para hacer que el cifrado de bloque sea una permutación pseudoaleatoria , mientras que 4 rondas son suficientes para convertirlo en una permutación pseudoaleatoria "fuerte" (lo que significa que sigue siendo pseudoaleatoria incluso para un adversario que obtiene acceso de oráculo a su permutación inversa). [4] Debido a este resultado muy importante de Luby y Rackoff, los cifrados de Feistel a veces se denominan cifrados de bloque de Luby-Rackoff.
Trabajos teóricos posteriores han generalizado un poco la construcción y han proporcionado límites más precisos para la seguridad. [5] [6]
Sea la función de ronda y sean las subclaves para las rondas respectivamente.
Entonces el funcionamiento básico es el siguiente:
Divida el bloque de texto simple en dos partes iguales: ( , ).
Para cada ronda , calcule
donde significa XOR . Entonces el texto cifrado es .
El descifrado de un texto cifrado se logra calculando
Luego está el texto simple nuevamente.
El diagrama ilustra tanto el cifrado como el descifrado. Observe la inversión del orden de las subclaves para el descifrado; esta es la única diferencia entre el cifrado y el descifrado.
Los cifrados Feistel no balanceados utilizan una estructura modificada donde y no tienen la misma longitud. [7] El cifrado Skipjack es un ejemplo de este tipo de cifrado. El transpondedor de firma digital de Texas Instruments utiliza un cifrado Feistel no balanceado patentado para realizar la autenticación de desafío-respuesta . [8]
El barajado de Thorp es un caso extremo de un cifrado Feistel desequilibrado en el que un lado es un solo bit. Este método ofrece una seguridad demostrable mejor que un cifrado Feistel equilibrado, pero requiere más rondas. [9]
La construcción Feistel también se utiliza en algoritmos criptográficos distintos de los cifrados por bloques. Por ejemplo, el esquema de relleno de cifrado asimétrico óptimo (OAEP) utiliza una red Feistel simple para aleatorizar los textos cifrados en ciertos esquemas de cifrado de clave asimétrica .
Se puede utilizar un algoritmo Feistel generalizado para crear permutaciones fuertes en dominios pequeños de tamaño no mayor que una potencia de dos (véase cifrado con preservación de formato ). [9]
Independientemente de si todo el cifrado es un cifrado Feistel o no, las redes similares a Feistel se pueden utilizar como un componente del diseño de un cifrado. Por ejemplo, MISTY1 es un cifrado Feistel que utiliza una red Feistel de tres rondas en su función de ronda, Skipjack es un cifrado Feistel modificado que utiliza una red Feistel en su permutación G, y Threefish (parte de Skein ) es un cifrado de bloque no Feistel que utiliza una función MIX similar a Feistel.
Feistel o Feistel modificado:
Feistel generalizado:
