Cómo una sola construcción resolvió un viejo problema del cifrado — y se convirtió en la base del DES, el Magma ruso y decenas de otros algoritmos
Para descifrar un cifrado de bloque hay que deshacer de algún modo la mezcla con la que se cifró. Diseñar una buena función de mezcla ya es difícil. Diseñar además una función inversa matemáticamente limpia, e implementar ambas, duplica el trabajo — y duplica las probabilidades de cometer un error.
A principios de los años 70, en IBM, Horst Feistel propuso un truco estructural: cortar el bloque de datos por la mitad en L y R, hacer pasar una mitad — junto con una subclave de ronda — por una función F que puede ser tan compleja e irreversible como se quiera, sumar el resultado a la otra mitad y luego intercambiar las mitades. Repetir varias veces.
Desglosada en pasos, toda la construcción resulta sorprendentemente simple:
El bloque de datos se corta por la mitad en una mitad izquierda L y una derecha R. En el DES son 32 y 32 bits de un bloque de 64 bits; en el juego de Ludus Lab son 4 y 4 bits de un solo byte.
La mitad derecha R se combina con la subclave de esta ronda y pasa por la función F — en el DES y el Magma es un conjunto de S-boxes, tablas de sustitución que le dan al cifrado su no linealidad.
El resultado de F se suma con XOR a la mitad izquierda L, produciendo la nueva mitad derecha. Después las mitades se intercambian.
Todo se repite una y otra vez, cada vez con una subclave nueva: 16 veces en el DES, 32 en el Magma. Cuantas más rondas, más difícil es encontrar un patrón entre el texto claro y el cifrado.
Tras la última ronda las mitades se intercambian una vez más — y esto es lo que da a una red de Feistel su propiedad principal: para descifrar, Bob ejecuta exactamente el mismo algoritmo, solo que con las subclaves en orden inverso.
F puede ser tan compleja e irreversible como se quiera — lo reversible es el propio esquema «divide, mezcla, intercambia».
La idea de Feistel no se quedó en teoría — buena parte de la criptografía simétrica del siglo XX se construyó sobre ella:
El primer cifrado con estructura de Feistel, creado por el propio Horst Feistel y su equipo en IBM.
Antecesor directo del DES
Un Lucifer perfeccionado se convirtió en el estándar de EE. UU. durante un cuarto de siglo — bloque de 64 bits, clave de 56 bits, 16 rondas.
Clave: 56 bits — hoy insuficiente
Un diseño soviético independiente sobre la misma idea: bloque de 64 bits, pero clave de 256 bits y 32 rondas.
Hoy: GOST R 34.12-2015
El esquema de Feistel resultó tan exitoso que se convirtió en la base de varias generaciones más de cifrados:
En la demostración interactiva de Ludus Lab podrás:
Ambos algoritmos son redes de Feistel, pero a escalas y con destinos muy distintos:
| Parámetro | DES | Magma (GOST 28147-89) |
|---|---|---|
| País de origen | EE. UU. | URSS / Rusia |
| Año de adopción | 1977 | 1989 (hoy GOST R 34.12-2015) |
| Arquitectura | Red de Feistel | Red de Feistel |
| Tamaño del bloque | 64 bits | 64 bits |
| Longitud de la clave | 56 bits | 256 bits |
| Número de rondas | 16 | 32 |
| S-boxes | Fijadas por el estándar desde 1977 | Al principio era un secreto de cada organismo; un único conjunto fijo llegó recién en 2015 |
| Regulador | NIST (EE. UU.) | FSB de Rusia |
En 1990, los criptógrafos Eli Biham y Adi Shamir publicaron el criptoanálisis diferencial, un potente ataque contra los cifrados de bloque. La comunidad quedó asombrada: las S-boxes del DES resultaron ser sorprendentemente resistentes justo a ese ataque.
La explicación llegó después: según el ingeniero de IBM Don Coppersmith, el equipo de IBM conocía el criptoanálisis diferencial desde principios de los 70 y diseñó deliberadamente las S-boxes del DES para resistirlo — pero, a petición de la NSA, lo mantuvo en secreto durante casi dos décadas.
Una clave DES de 56 bits tiene unos 7×1016 valores posibles — de sobra en 1977. Para 1998, la Electronic Frontier Foundation había construido una máquina dedicada, «Deep Crack», de unos 250 000 dólares, que encontró una clave por fuerza bruta en unas 56 horas.
Eso demostró públicamente que 56 bits ya no bastaban. El parche fue el 3DES (DES aplicado tres veces), seguido en 2001 por el AES, elegido tras un concurso internacional abierto.
Alternativas abiertas al DES, sin restricciones de patente, diseñadas por Bruce Schneier en los años 90
Desarrollo conjunto de empresas japonesas, estándar internacional ISO/IEC, usado en TLS
Una red de Feistel en el corazón de los algoritmos de confidencialidad de las redes 3G/UMTS
Ahora entiendes por qué la función F no tiene que ser invertible, y cómo de esa sola idea salieron el DES, el Magma y decenas de otros cifrados
En la demostración recorrerás un solo byte desde el texto claro hasta el cifrado y de vuelta — y verás exactamente por qué funciona esta estructura