Las armas las carga el Diablo, y este algoritmo también

Este post participa en la VII edición del Carnaval de Tecnología, alojado este mes por el blog (muy bueno, por cierto) Zemiorka.

El cifrado, común y en ocasiones incorrectamente llamado, encriptación, es una de esas cosas que nunca te percatas que está hasta que falla. Es uno de esos eslabones de la cadena que evita que alguien tenga dificultades en robar tus datos cuando accedes a tu cuenta bancaria desde el ordenador, por ejemplo. Sus aplicaciones son múltiples, aunque sobre todo se utiliza en la transmisión de información, ya sea de mensajes, o de señales que llevan tales extractos de información. Sobre todo se usa en términos informáticos hoy en día, y es de esto de lo que hablaremos.

Concretamente, quería hablar del cifrado de Feistel, también llamado estructura o red de Feistel. Vamos a entender por cifrado la conversión de unos bits en otros distintos, y en la inmensa mayoría de aplicaciones informáticas, estos bits usan el código binario o hexadecimal. Pongamos que la información se compone de 4 bits, por ejemplo 0000. El código binario toma el valor 0 ó 1, en consecuencia, nuestro ejemplo tiene 16 combinaciones posibles. Es decir, se podría transformar en 15 maneras. Eso sería el cifrado ideal.

Horst Feistel a finales de los sesenta creó uno de los sistemas de cifrado más famosos que ha llegado hasta nuestros días. Lo creó cuando era trabajador de la compañía IBM, e ideó un cifrado simétrico por rondas, ya que realiza los mismos pasos durante un número de rondas y este algoritmo es reversible. Es decir, el algoritmo de cifrado y descifrado es el mismo. El primer algoritmo en el que Feistel aplicó sus pasos fue en el algoritmo Lucífer.

Los pasos de este cifrado son los siguientes (normalmente aplicado a cadenas de 8 bits) y a 8 rondas:

1- Se divide el bit por la mitad, de manera que tenemos 4 en la izquerda (L) y 4 en la derecha (R)

2- En cada ronda, hay una función F de Feistel y una clave distinta, Ki, de tal manera que en cada ronda se realiza la siguiente operación:

Por cierto, recordamos cómo es la tabla lógica de XOR:

Recordemos que partimos de L0 y R0. Tal y como hemos explicado, el proceso de descifrado y cifrado sería como lo muestra el siguiente gráfico.

La función F realiza los siguientes pasos:

Sin ánimo de entrar mucho en detalle, vemos que desde la izquierda llega un semibloque de 32 bits, que corresponde a la mitad del byte, es decir, a L o R. Y por la derecha, llega la subclave (de 48 bits), lo que llamamos Ki. Debido a esta diferencia de tamaño, lo primero que ocurre es que el semibloque se expande (mediante permutación de expansión) a 48 bits, y a continuación se mezclan en una función XOR. Tras mezclarlo con la subclave, el bloque es dividido en ocho trozos de 6 bits antes de ser procesados por las S-cajas, o cajas de sustitución. En cada S-caja entran seis bits de entrada y salen cuatro, de acuerdo con una trasformación no lineal, especificada por una tabla de búsqueda. Las S-cajas constituyen el núcleo de la seguridad de DES — sin ellas, el cifrado sería lineal, y fácil de romper. Aunque en la actualidad ya ha sido sobradamente estudiado y vencido.

Finalmente las 32 salidas de las S-cajas se reordenan de acuerdo a una permutación fija, y se obtienen 32 bits.

Omitimos la generación de subclaves para no sobrecargar matemáticamente el post, aunque para quien lo desee, lo puede encontrar aquí (pág10). Para quien tenga curiosidad: Ésta es una calculadora que implementa el Lucifer.

A pesar de que algún lector pueda pensar "vaya chorrada, ¿a dónde vamos con esto?", no pensó así la NBS (National Bureau of Standards, el actual NIST) americana, quien pidió a IBM un cifrado nacional estándar para cifrar información a nivel gubernamental. Y ellos le dieron el algoritmo Lucifer, el cual fue desarrollado por Horst entre 1973-74.

Esta creación terminó por denominarse Data Encryption Standard en 1975, y sólo por el nombre se da a entender que es una cosa que usa mucha gente. Está oficialmente descrito aquí. Este tipo de cifrado ha llegado hasta nuestros días, y por ejemplo, es la base del cifrado y seguridad de las redes GSM de telefonía móvil, donde el algoritmo KASUMI o A5/3 tiene la arquitectura de una red de Feistel. Aunque otros algoritmos famosos también tienen su base en Feistel, como los siguientes Blowfish, Camelia, CAST-128, FEAL, HIELO,  LOKI97, MARTE, MAGENTA, RC5, TÉ, Twofish, XTEA o GOST_28147-89