Cifrado Feistel

En criptografía, un cifrado Feistel (también conocido como cifrado en bloque Luby-Rackoff) es una estructura simétrica utilizada en la construcción de cifrados en bloque, que lleva el nombre del alemán- el físico y criptógrafo nato Horst Feistel, que realizó investigaciones pioneras mientras trabajaba para IBM; también se la conoce comúnmente como red Feistel. Una gran proporción de cifrados en bloque utilizan el esquema, incluido el estándar de cifrado de datos de EE. UU., el GOST soviético/ruso y los cifrados más recientes Blowfish y Twofish. En un cifrado Feistel, el cifrado y el descifrado son operaciones muy similares y ambas consisten en ejecutar de forma iterativa 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 Feistel. Las redes Feistel se vieron comercialmente por primera vez 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. Al igual que otros componentes del DES, la naturaleza iterativa de la construcción de Feistel facilita la implementación del criptosistema en hardware (particularmente en el hardware disponible en el momento del diseño de DES).

Diseño

Una red Feistel utiliza 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. 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 realiza 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 será 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 puede complicarse arbitrariamente, ya que no es necesario diseñarla para que sea invertible. Además, las operaciones de cifrado y descifrado son muy similares, incluso idénticas en algunos casos, y sólo requieren una inversión del programa de claves. Por lo tanto, el tamaño del código o circuito necesario para implementar dicho cifrado se reduce casi a la mitad.

Trabajo teórico

Los criptógrafos han analizado exhaustivamente la estructura y propiedades de los cifrados Feistel.

Michael Luby y Charles Rackoff analizaron la construcción del cifrado Feistel y demostraron que si la función redonda 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 "fuerte" permutación pseudoaleatoria (lo que significa que sigue siendo pseudoaleatoria incluso para un adversario que obtiene acceso oráculo a su permutación inversa). Debido a este resultado tan importante de Luby y Rackoff, los cifrados de Feistel a veces se denominan cifrados de bloques de Luby-Rackoff.

Trabajos teóricos posteriores han generalizado un poco la construcción y han dado límites más precisos para la seguridad.

Detalles constructivos

Vamos F{displaystyle mathrm {F} ser la función redonda y dejar K0,K1,...... ,Kn{displaystyle K_{0},K_{1},ldots K_{n} ser los sub-keys para las rondas 0,1,...... ,n{displaystyle 0,1,ldotsn} respectivamente.

Entonces la operación básica es la siguiente:

Dividir el bloque de texto en dos partes iguales: (L0{displaystyle L_{0}, R0{displaystyle R_{0}).

Para cada ronda i=0,1,...... ,n{displaystyle i=0,1,dotsn}, computación

Li+1=Ri,{displaystyle L_{i+1}=R_{i},}

Ri+1=Li⊕ ⊕ F()Ri,Ki),{displaystyle R_{i+1}=L_{i}oplus mathrm {F} (R_{i},K_{i}),}

Donde ⊕ ⊕ {displaystyle oplus } significa XOR. Entonces el cifertexto es ()Rn+1,Ln+1){displaystyle (R_{n+1},L_{n+1})}.

Decryption of a ciphertext ()Rn+1,Ln+1){displaystyle (R_{n+1},L_{n+1})} se logra por computación para i=n,n− − 1,...... ,0{displaystyle i=n,n-1,ldots0}

Ri=Li+1,{displaystyle R_{i}=L_{i+1}

Li=Ri+1⊕ ⊕ F⁡ ⁡ ()Li+1,Ki).{displaystyle L_{i}=R_{i+1}oplus operatorname {F} (L_{i+1},K_{i}).}

Entonces... ()L0,R0){displaystyle (L_{0},R_{0})} es el texto 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; ésta es la única diferencia entre cifrado y descifrado.

Cifrado Feistel desequilibrado

Cifras de Feistel desequilibradas utilizan una estructura modificada L0{displaystyle L_{0} y R0{displaystyle R_{0} no son de igual longitud. El código Skipjack es un ejemplo de tal cifrado. El transpondedor digital de firmas de Texas Instruments utiliza un cifer Feistel desequilibrado propietario para realizar la autenticación de respuesta al desafío.

La combinación Thorp es un caso extremo de un cifrado Feistel desequilibrado en el que un lado es un solo bit. Esto tiene una mayor seguridad demostrable que un cifrado Feistel equilibrado, pero requiere más rondas.

Otros usos

La construcción de Feistel también se utiliza en algoritmos criptográficos distintos del cifrado 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 utilizar un algoritmo generalizado de Feistel para crear permutaciones fuertes en dominios pequeños de tamaño no una potencia de dos (consulte cifrado que preserva el formato).

Las redes Feistel como componente de diseño

Ya sea que todo el cifrado sea un cifrado Feistel o no, las redes similares a Feistel se pueden utilizar como 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 redonda, Skipjack es un cifrado Feistel modificado que utiliza una red Feistel en su permutación G, y Threefish (parte de Skein) es un cifrado en bloque que no es Feistel y que utiliza una función MIX similar a Feistel.

Lista de cifrados Feistel

Feistel o Feistel modificado:

Feistel generalizado:

• CAST-256
• CLEFIA
• MacGuffin
• RC2
• RC6
• Skipjack
• SMS4