En criptografía , un cifrado Feistel (también conocido como Luby-Rackoff cifrado de bloques ) es una estructura simétrica utilizada en la construcción de sistemas de cifrado en bloque , llamado así por el alemán -nacido físico y criptógrafo Horst Feistel que no investigación pionera, mientras trabajaba para IBM (EE.UU.) ; también se conoce comúnmente como red Feistel . Una gran proporción de cifrados en bloque utiliza el esquema, incluido el Estándar de cifrado de datos de EE. UU . , El GOST soviético / ruso y los más recientes Blowfish y Twofish.cifrados. En un cifrado de Feistel, el cifrado y el descifrado son operaciones muy similares, y ambas consisten en ejecutar iterativamente una función llamada "función redonda" un número fijo de veces.
Historia
Muchos cifrados de bloques simétricos modernos se basan en redes de 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 EE. UU. Adoptó el DES (un cifrado basado en Lucifer, con cambios realizados por la NSA ) en 1976. Como otros componentes del DES, la naturaleza iterativa de la construcción de Feistel facilita la implementación del criptosistema en el hardware (particularmente en el hardware disponible en el momento del diseño del DES).
Diseño
Una red Feistel usa una función redonda , 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 XOR con la otra mitad de los datos. Esto se repite un número fijo de veces y el resultado 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 es invertible (es decir, los datos cifrados se pueden descifrar), incluso si la función redonda no es invertible en sí misma. La función redonda se puede complicar arbitrariamente, ya que no es necesario diseñarla para que sea 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 de la programación de claves . Por lo tanto, el tamaño del código o los circuitos necesarios para implementar dicho cifrado se reduce casi a la mitad.
Trabajo teórico
Los criptógrafos han analizado exhaustivamente la estructura y las propiedades de los cifrados de Feistel .
Michael Luby y Charles Rackoff analizaron la construcción de cifrado Feistel, y demostraron que si la función de ronda es un criptográficamente seguro función pseudoaleatoria , con K i utiliza como la semilla, a continuación, 3 rondas son suficientes para hacer que el cifrado de bloques una permutación pseudoaleatoria , mientras que 4 rondas son suficientes para convertirlo en una permutación pseudoaleatoria "fuerte" (lo que significa que sigue siendo pseudoaleatorio 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.
El trabajo teórico posterior ha generalizado un poco la construcción y ha dado límites más precisos para la seguridad. [5] [6]
Detalles de construcción
Dejar ser la función redonda y dejar ser las subclaves para las rondas respectivamente.
Entonces la operación básica es la siguiente:
Divida el bloque de texto sin formato en dos partes iguales, (, )
Para cada ronda , calcular
Dónde significa XOR . Entonces el texto cifrado es.
Descifrado de un texto cifrado se logra computando para
Luego es el texto sin formato de nuevo.
El diagrama ilustra tanto el cifrado como el descifrado. Tenga en cuenta la inversión del orden de las subclaves para el descifrado; esta es la única diferencia entre cifrado y descifrado.
Cifrado de Feistel desequilibrado
Los cifrados Feistel desequilibrados utilizan una estructura modificada donde y no son de igual longitud. [7] El cifrado Skipjack es un ejemplo de dicho 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 shuffle de Thorp es un caso extremo de un cifrado Feistel desequilibrado en el que un lado es un solo bit. Esto tiene una mejor seguridad demostrable que un cifrado de Feistel equilibrado, pero requiere más rondas. [9]
Otros usos
La construcción de Feistel también se utiliza en algoritmos criptográficos distintos de los cifrados en bloque. Por ejemplo, el esquema de relleno de cifrado asimétrico óptimo (OAEP) utiliza una red Feistel simple para aleatorizar textos cifrados en ciertos esquemas de cifrado de clave asimétrica .
Se puede usar un algoritmo de Feistel generalizado para crear fuertes permutaciones en dominios pequeños de tamaño que no sea una potencia de dos (ver cifrado que preserva el formato ). [9]
Redes Feistel como componente de diseño
Ya sea que el cifrado completo sea un cifrado de Feistel o no, las redes similares a Feistel se pueden usar como un componente del diseño de un cifrado. Por ejemplo, MISTY1 es un cifrado Feistel que usa una red Feistel de tres vueltas en su función redonda, Skipjack es un cifrado Feistel modificado que usa una red Feistel en su permutación G, y Threefish (parte de Skein ) es un cifrado de bloque que no es Feistel utiliza una función MIX similar a Feistel.
Lista de cifrados de Feistel
Feistel o Feistel modificado:
|
|
|
Feistel generalizado:
- CAST-256
- CLEFIA
- MacGuffin
- RC2
- RC6
- Barrilete
- SMS4
Ver también
- Criptografía
- Cifrado de flujo
- Red de sustitución-permutación
- El esquema de elevación para la transformada de ondículas discretas tiene prácticamente la misma estructura
- Cifrado que conserva el formato
- Esquema de Lai-Massey
Referencias
- ^ Menezes, Alfred J .; Oorschot, Paul C. van; Vanstone, Scott A. (2001). Manual de criptografía aplicada (Quinta ed.). pag. 251 . ISBN 978-0849385230.
- ^ Schneier, Bruce (1996). Criptografía aplicada . Nueva York: John Wiley & Sons. ISBN 0-471-12845-7.
- ^ Stinson, Douglas R. (1995). Criptografía: teoría y práctica . Boca Ratón: CRC Press. ISBN 0-8493-8521-0.
- ^ Luby, Michael; Rackoff, Charles (abril de 1988), "Cómo construir permutaciones pseudoaleatorias a partir de funciones pseudoaleatorias", SIAM Journal on Computing , 17 (2): 373–386, doi : 10.1137 / 0217022 , ISSN 0097-5397
- ^ Patarin, Jacques (octubre de 2003), Boneh, Dan (ed.), "Luby-Rackoff: 7 rondas son suficientes para una seguridad de 2 n (1 − ε) " (PDF) , Advances in Cryptology — CRYPTO 2003 , Lecture Notes in Computer Science, 2729 : 513–529, doi : 10.1007 / b11817 , ISBN 978-3-540-40674-7, S2CID 20273458 , recuperada 2009-07-27
- ^ Zheng, Yuliang; Matsumoto, Tsutomu; Imai, Hideki (20 de agosto de 1989). En la construcción de cifrados en bloque demostrablemente seguros y sin depender de hipótesis no probadas . Avances en criptología - Actas de CRYPTO '89 . Apuntes de conferencias en Ciencias de la Computación. 435 . págs. 461–480. doi : 10.1007 / 0-387-34805-0_42 . ISBN 978-0-387-97317-3.
- ^ Schneier, Bruce; Kelsey, John (21 de febrero de 1996). Redes Feistel desequilibradas y diseño de cifrado de bloques . Cifrado de software rápido . Apuntes de conferencias en Ciencias de la Computación. 1039 . págs. 121-144. doi : 10.1007 / 3-540-60865-6_49 . ISBN 978-3-540-60865-3. Consultado el 21 de noviembre de 2017 .
- ^ Bono, Stephen; Green, Matthew; Stubblefield, Adam; Juels, Ari; Rubin, Aviel; Szydlo, Michael (5 de agosto de 2005). "Análisis de seguridad de un dispositivo RFID habilitado criptográficamente" (PDF) . Actas del Simposio de seguridad de USENIX . Consultado el 21 de noviembre de 2017 .
- ^ a b Morris, Ben; Rogaway, Phillip; Stegers, Till (2009). Cómo cifrar mensajes en un dominio pequeño (PDF) . Avances en criptología - CRYPTO 2009 . Apuntes de conferencias en Ciencias de la Computación. 5677 . págs. 286-302. doi : 10.1007 / 978-3-642-03356-8_17 . ISBN 978-3-642-03355-1. Consultado el 21 de noviembre de 2017 .