Cripto Serie: Cifrado de Bloques - Data Encryption Standard (DES)

Seifreed · 19-Jul-2009, 16:40

El cifrado DES (Data Encryption Standard) fue diseñado por IBM en 1973 como una de los envíos para el call for proposals de la NBS (National Bureu of Standards) estadounidense. Hubo cierta controversia debido a la implicación de la NSA en el desarrollo del cifrado, especialmente en las misteriosas cajas S (S-boxes) y el tamaño reducido de la clave, pero años más tarde se demostró que las S-boxes usadas eran más resistentes al criptoanálisis diferencial que si hubiesen sido seleccionadas aleatoriamente.
El algoritmo se aprobó como un estándar FIPS en 1976, y ha sido revisado hasta tres veces en 1988, 1993 y 1999. La última versión, FIPS-46-3, describe la extensión 3DES como un método para alargar el tamaño de clave del cifrado DES usando 3 operaciones DES consecutivas, cifrando, descfirando y cifrando de nuevo. Esto se hizo como consecuencia de un ataque de fuerza bruta publicado en 1998.
Después de la pausa (click en Leer más!) veremos cómo funciona el algoritmo y sus componentes principales.
NOTA: Las imágenes de esta entrada están enlazadas a Wikipedia. Si no funcionan, dejad un comentario y subiré mis propias imagenes.
Estructura de DES

DES es un cifrado de bloques que cifra bloques de 64 bits con una clave de 56 bits. En realidad, normalmente se proporciona al algoritmo una clave de 64 bis, pero el bit menos significativo de cada byte de la clave no se usa para el cifrado y podría ser usado como bit de paridad.
La estrucutra general de DES se muestra en la siguiente figura:

Estructura de DES

Empieza por la llamada Permutación Inicial (IP), que obviamente realiza una permutación, es decir simplemente desordena los bits de entrada. Después, el bloque de datos se divide en los 32 bits más significativos (L0) y los 32 bits menos significativos (R0) creando una parte izquierda (L) y derecha (R). Tras esto, se aplican 16 rondas idénticas: una función F (función de Feistel) se aplica a la mitad derecha y a la clave de ronda, y el resultado se XORea con la parte izquierda. Seguidamente se intercambian las dos partes.
Después de aplicar las 16 rondas, se realiza la Permutación Final (FP). Esta permutación realmente es la inversa de la inicial, IP ( $FP = IP^{-1}$ ). Todos estos elementos conforman lo que llamamos una red de Feistel, con una propiedad interesante: podemos descifrar el criptograma usando el mismo algoritmo, pero usando las claves de ronda en orden inverso.
Es decir, el proceso de descifrado para DES es idéntico al proceso de cifrado. Sólo que la clave de ronda 16 se aplica en la primera ronda, luego la clave de ronda 15, y así sucesivamente.
La función F
La función F se encuentra en el nucleo del cifrado DES. Como se ha explicado antes, esta función se aplica en cada ronda a la parte derecha y a la clave de ronda, y con su resultado se realiza un XOR con la parte izquierda. El primer componente de la función F es una función de Expansión (E), que expande los 32 bits de entrada en 48 bits. Luego se hace un XOR de estos 48 bits con la clave de ronda (48 bits) proveniente del algoritmo de generación de claves.
Seguidamente, esos 48 bits se proporcionan en grupos de 6 bits a las cajas S (S-boxes). Estas cajas S son simples funciones de sustitución, implementadas como una tabla de sustituciones, y producen 4 bits cada una de ellas. Por tanto, a la salida de las 8 cajas S tenemos de nuevo 32 bits, el mismo tamaño que la entrada y la salida de la función F. Después de las cajas S, se realiza una nueva permutación (P). La salida de esta permutación es el resultado de la función F.

Función de Feistel

Generación de claves Para tener una visión completa de cómo funciona DES, todavía necesitamos saber cómo se generan las claves de ronda en base a la clave proporcionada al cifrado. Esto se hace mediante un algoritmo de generación de claves (key scheduling), que puede realizarse al mismo tiempo que se va relaizando el cifrado o puede precalcularse y almacenar cada una de las claves de ronda en una tabla.
El proceso tiene la siguiente pinta:

DES key schedule

Primero, se realiza una permutación (PC1). El nombre viene de Permuted Choice, puesto que esta permutación además descarta algunos bits de la clave: como dijimos antes, el último bit de cada byte es descartado y el resto son usados para la permutación.

Después, la estructura se repite para cada ronda: el resultado de PC1 se divide en dos partes (izquierda y derecha), a las que se realiza un desplazamiento cíclico de bits un número de veces que depende del número de ronda. Después, esta clave desplazada se proporciona a una segunda permutación (PC2) que selecciona 48 bits de los 56 bits de entrada.

Información detallada

Aunque ya hemos visto como funciona DES, no seríamos capaces de implementar el algoritmo sin saber exactamente cómo modifican los datos las permutaciones, expansiones y cajas S. Para ello, puedes consultar el estándar directamente o ir al

DES_supplementary_material

de Wikipedia.

Como siempre, implementar tus propios algoritmos criptográficos NO es aconsejable. Hazlo únicamente con fines educativos, o las cosas pueden salir MUY mal con bastante facilidad.

Triple DES
Como se comentó en la introducción, un ataque de fuerza bruta a DES fue presentado hace ya tiempo. Este ataque motivó la introducción de una nueva variante de DES. Esta variante, llamada triple DES, usa tres operaciones DES consecutivas para aumentar el tamaño del espacio de claves.
Típicamente, los datos son cifrados con DES usando una clave K1, después descifrados usando K2, y finalmente cifrados de nuevo usando K1. Esto aumenta el tamaño de clave a 112 bits (8 bits de K1 y 8 bits de K2 son descartados por PC1), lo cual dificulta el ataque de fuerza bruta.

Además, existe otra variante de 3DES que usa tres claves diferentes, consiguiendo un tamaño de clave de 168 bits. Y por supuesto, también se puede usar 3DES con tres claves idénticas. Esto resulta en un simple cifrado DES, lo que permite usar dispositivos que no implementan 3DES con dispositivos que sí lo implementan.
Fuente