Explicación del Cifrado en Bloques Simétrico DES (página 2)

1.2. Generación de la subclave Ki

La clave Ki tiene un valor inicial de 64 bits, su longitud es fija.

La tabla de la Permutación PC1, se utiliza para realizar la permutación inicial en la generación de la subclave Ki , para cada vuelta. Una vez realizada la permutación, los 56 bits se dividen en dos sub-bloques Ci y Di de 28 bits. En estas condiciones, la clave esta definida por las ecuaciones:

Ci = LS (Ci-1) Di = LS(Di -1)

Ki = PC2 (Ci , Di)

Ejemplo Permutación PC1

Clave K: Santiago

Utilizando la Permutación PC1 obtenemos:

Sub-bloque C0 = 0000000 0111111 1111111 1100000

Sub-bloque D0 = 1100010 1110011 0010010 1001001

Sub-bloques iniciales

1.2.1. Desplazamiento LS(…)

El desplazamiento LS(…) se aplica a los sub-bloques de longitud fija de 7 bits (Ci y Di), donde LS(…) es un desplazamiento circular a la izquierda de 1 o 2 bits del entero binario que toma el argumento de acuerdo a la siguiente tabla:

Con el propósito de comprender mejor el desplazamiento LS(…) se realizara el proceso.

Ejemplo Permutación LS(..)

Al tener los sub-bloques C0 y D0, el siguiente paso es el desplazamiento LS, se marcan los dos primeros bits, con el propósito de poder identificar el resultado del desplazamiento.

Sub-bloque C0 = 0000000 0111111 1111111 1100000

Sub-bloque D0 = 1100010 1110011 0010010 1001001

Al ser la primer vuelta, el desplazamiento es de un bit a la izquierda como se indica en la tabla, dando como resultado C1 y D1.

Sub-bloque C1 = 0000000 1111111 1111111 1000000

Sub-bloque D1 = 1000101 1100110 0100101 0010011

Sub-bloques después del desplazamiento LS(..)

1.2.2. Permutación PC2

La permutación PC2 se conoce como permutación de compresión, dada por las operaciones de concatenar y permutar Ci y Di, se va a comprimir de 56 bits a 48 bits para obtener la clave Ki, posteriormente será utilizada en la función (f(Ri-1, Ki))

El orden de concatenar Ci y Di, es utilizando primero los 28 bits de Ci y posteriormente los 28 bits de Di, la tabla PC2 es una tabla de 8 x 6, dando como resultado 8 bloques de 6 bits.

Ejemplo Permutación PC2

Continuando con el ejemplo se mostrará el proceso utilizado en la permutación PC2, para obtener la clave Ki.

Concatenando Ci, Di

0000000 1111111 1111111 1000000 1000101 1100110 0100101 0010011

Los 56 bits de entrada en la permutación PC2

Para ver la tabla seleccione la opción "Descargar" del menú superior 

El resultado de haber realizado la permutación PC2 es la generación de la clave K1 siendo:

K1 = PC2 (C1, D1) =

111000 001011 011001 100110 110111 010010 110100 000110

Clave K1

Las operaciones LS(..) y PC2, se repiten 15 veces para así obtener las 15 subclaves de cifrado restantes. Los procesos de cifrado y generación de claves se representan esquemáticamente en la siguiente imagen.

1.3. Función f(Ri-1 , Ki)

Al tener la clave Ki y la expansión de (R0), el siguiente paso es la función f(Ri-1 , Ki), la cual consta de tres procesos (Suma OR exclusivo, ocho funciones no lineales, Permutación P), siendo las ocho funciones lineales la mayor virtud del algoritmo, se han propuesto modificaciones en varios procesos, pero cualquier modificación realizada, en las funciones lineales hace débil al algoritmo. A continuación se explican los procesos.

1.3.1. Suma OR exclusiva

Con la clave Ki y E(Ri-1), se procede a realizar la suma OR exclusiva, al realizar la operación se tiene un 50% de certeza que el siguiente bit sea 1, con lo cual aumenta la dificultad de poder descifrar el mensaje. La operación OR exclusiva se ejemplifica en la siguiente tabla:

Se encuentra definido por la ecuación.

E(Ri-1) Ki

La clave Ki y Ri-1 se encuentra formado por 8 bloques de 6 bits cada, con lo cual es posible realizar la suma OR exclusiva como se muestra a continuación.

Ejemplo Suma OR exclusiva

Retomando los bits de la expansión del sub-bloque R0 y la subclave K1, se procede a realizar la suma OR exclusiva.

E(R0) = 000000 000001 011111 111101 011001 011001 010000 001000

K1 = 111000 001011 011001 100110 110111 010010 110100 000110

111000 001010 000110 011011 101110 001011 100100 001110

Resultado de la suma OR exclusiva E(R0) K1

1.3.2. Funciones no lineales

La cadena de bits obtenida de la suma OR exclusiva, se subdivide en 8 bloques de 6 bits, como se puede apreciar en el ejemplo anterior, siendo cada bloque (b6b5b4b3b2b1) la entrada a una de las funciones no lineales, conocidas como cajas, el resultado de la operación es un numero con valor entre 0 a 15, representado con cuatro bits, concatenados forman una cadena de 32 bits, la cual será la entrada para la permutación P. La posición de los bits dentro de cada caja se encuentra definida por la fila b6b1 y la columna b5b4b3b2 de la caja, el orden de los valores numéricos de las cajas se puede ver en la siguiente imagen.

Ejemplo función no lineal (cajas)

E(R0) K1 = 111000 001010 000110 011011 101110 001011 100100 001110

En la Caja S1 se utiliza el primer bloque 111000, en la Caja S2 se utiliza el segundo bloque y así sucesivamente.

Para ver la tabla seleccione la opción "Descargar" del menú superior

La salida del bloque 1 es: 3 (0011), el procedimiento se repite en las siguientes 7 cajas obteniendo como resultado:

E(R0) K1 = 0011 1011 1110 1010 1000 1100 1011 0001

3 11 14 10 8 12 11 1

Resultado de las funciones no lineales

1.3.3. Permutación P

El ultimo paso de la función f(Ri-1 , Ki), es una permutación P, cuyo resultado se sumara con la salida del sub-bloque Li, dando origen a la entrada del sub-bloque Ri

Para ver la tabla seleccione la opción "Descargar" del menú superior

 Ejemplo Permutación P

Retomando el ejemplo se realiza el ultimo paso de la f(Ri-1 , Ki), recordando que dicho proceso se repite 15 veces.

E(R0) K1 = 0011 1011 1110 1010 1000 1100 1011 0001

Resultado de las funciones no lineales

Para ver la tabla seleccione la opción "Descargar" del menú superior

1.4. Suma Li Ri

El registro de bits obtenido por la función f(Ri-1 , Ki), es sumado con un OR exclusivo con el registro de bits de L0, dando como resultado la entrada para el siguiente sub-bloque de Ri. El registro de bits realizado en la permutación inicial P1, que origino al sub-bloque R0, es la entrada para el siguiente sub-bloque Li, el proceso se repite 15 veces, siendo el ultimo proceso la permutación P1-1.

Ejemplo Suma Li f(Ri-1 , Ki)

f(Ri-1 , Ki) = 0101 0011 0100 1001 0100 1111 0100 1111

L0 = 1111 1111 0001 1000 1101 0111 1110 1010

1010 1100 0101 0001 1001 1000 1010 0101

Resultado de la suma OR exclusiva L0 f(R0 , K1)

Obteniendo los registros de 32 bits para el siguiente sub-bloque Li y Ri como se muestra a continuación:

L1 = 0000 0000 1111 1110 1100 1100 1000 0100

R1 = 1010 1100 0101 0001 1001 1000 1010 0101

Donde se verifican las ecuaciones:

L1 = R0

00000000111111101100110010000100 = 00000000111111101100110010000100

R1 = L0 f(R0 , K1)

10101100010101011001100010100101 =

1111111100011000110101111110101001010011010011010100111101001111

1.5. Permutación P1-1

La permutación inversa se define por la siguiente tabla, siendo la salida, el cifrado del mensaje.

Para ver la tabla seleccione la opción "Descargar" del menú superior

Ejemplo Permutación P1-1

Si tomamos los valores que tenemos de L1 y R1, suponiendo los valores de L16 y R16, podemos realizar el procedimiento, como muestra del resultado final, cabe mencionar si el mensaje es mayor de 64 bits, se utilizan los bloques necesarios para dividir el mensaje original, si un bloque formado por un mensaje, no tiene la longitud de 64 bits, se rellena utilizando 0.

L16 = 10101100 01010001 10011000 10100101

R16 = 00000000 11111110 11001100 10000100

Concatenando L16 , R16

10101100 01010001 10011000 10100101 00000000 11111110 11001100 10000100

Para ver la tabla seleccione la opción "Descargar" del menú superior

El cifrado del mensaje es: ◄(spacio){l4a8o

00010001 00100000 01101011 01101100 00110100 01100001 00111000 01101111

1.6. Descifrado

El algoritmo se utiliza para obtener el mensaje original, con un sentido inverso al inicial, esto es, empezando con la entrada del mensaje cifrado de 64 bits, aplicando la permutación P1, dividir el mensaje en dos sub-bloques L16 y R16, teniendo la subclaves calculadas previamente, se realiza el procedimiento descrito anteriormente la f(Ri-1 , Ki), realizando las 16 vueltas hasta obtener el mensaje en claro.

Ejemplo Permutación P1 Descifrado

Mensaje a Descifrar = ◄(spacio){l4a8o

Para ver la tabla seleccione la opción "Descargar" del menú superior 

L16 = 10101100 01010001 10011000 10100101

R16 = 00000000 11111110 11001100 10000100

Ejemplo Permutación E Descifrado

Al tener la secuencia de R16 de 32 bits, es necesario aplicar la permutación E, la cual se muestra a continuación.

R16 = 00000000 11111110 11001100 10000100

Para ver la tabla seleccione la opción "Descargar" del menú superior

E(R16) = 000000 000001 011111 111101 011001 011001 010000 001000

Ejemplo Suma OR exclusiva Descifrado

La suma OR exclusiva se realiza utilizando la ultima clave generada (K16), en nuestro ejemplo utilizaremos la clave K1, como la clave K16.

E(R16) = 000000 000001 011111 111101 011001 011001 010000 001000

K16 = 111000 001011 011001 100110 110111 010010 110100 000110

111000 001010 000110 011011 101110 001011 100100 001110

Resultado de la suma OR exclusiva E(R16) K16

Ejemplo función no lineal (cajas) Descifrado

E(R0) K1 = 111000 001010 000110 011011 101110 001011 100100 001110

Como resultados de las operaciones no lineales (cajas) tenemos los siguientes:

E(R0) K1 = 0011 1011 1110 1010 1000 1100 1011 0001

3 11 14 10 8 12 11 1

Resultado de las funciones no lineales

Ejemplo Permutación P Descifrado

Retomando el ejemplo se realiza el ultimo paso de la f(Ri-1 , Ki), recordando que dicho proceso se repite 15 veces mas.

E(R0) K1 = 0011 1011 1110 1010 1000 1100 1011 0001

Para ver la tabla seleccione la opción "Descargar" del menú superior

Ejemplo Suma Li f(Ri-1 , Ki) Descifrado

f(Ri-1 , Ki) = 0101 0011 0100 1001 0100 1111 0100 1111

L16 = 1010 1100 0101 0001 1001 1000 1010 0101

1111 1111 0001 1000 1101 0111 1110 1010

Resultado de la suma OR exclusiva L0 f(Ri-1 , Ki)

Obteniendo los registros de 32 bits para el siguiente sub-bloque Li y Ri como se muestra a continuación:

L15 = 0000 0000 1111 1110 1100 1100 1000 0100

R15 = 1111 1111 0001 1000 1101 0111 1110 1010

Donde se verifican las ecuaciones:

L15 = R16

00000000111111101100110010000100 = 00000000111111101100110010000100

R1 = L16 f(R16 , K16)

11111111000110001101011111101010 =

1010110001010001100110001010010101010011010010010100111101001111

Ejemplo Permutación P1-1 Descifrado

Si tomamos los valores que tenemos de L1 y R1, suponiendo los valores de L16 y R16, podemos realizar el procedimiento, como muestra del resultado final, cabe mencionar si el mensaje es mayor de 64 bits, se utilizan los bloques necesarios para dividir el mensaje original, si un bloque formado por un mensaje y este no tiene la longitud de 64 bits, se rellena utilizando 0.

L1 = 1111 1111 0001 1000 1101 0111 1110 1010

R1 = 0000 0000 1111 1110 1100 1100 1000 0100

Concatenando L1 y R1, da como resultado:

11111111 00011000 11010111 11101010 00000000 11111110 11001100 10000100

 Para ver la tabla seleccione la opción "Descargar" del menú superior

 En la siguiente sección se definirán, los ataques activos y pasivos, se mencionarán los ataques al algoritmo DES.

2.Ataques a la seguridad criptográfica

La seguridad criptográfica sufre, dos tipos de ataques pasivosIII y activosIV, la finalidad de realizar un ataque pasivo, es obtener información y evitar ser detectado, a diferencia de los ataques activos, cuya finalidad es captar la información, modificarla, obtener claves, entre otras actividades no legales.

Los ataques activos se dividen en Ataques a los Operadores Criptográficos y Ataques a los protocolos, a continuación se mencionan algunos ataques a los operadores criptográficos.

• Ataque a partir del cifrado: El atacante tiene acceso al texto cifrado y de ahí trata de encontrar la clave secreta.
• Ataque a partir del texto en claro: El atacante tiene acceso al texto en claro y al cifrado con los cuales intenta obtener la clave secreta.
• Ataque a partir del texto en claro elegido: El atacante puede elegir un texto en claro y su cifrado.
• Ataque a partir de texto en claro condicionado: El atacante puede elegir un texto en claro condicionado a los cifrados previamente obtenidos.

Ataques a los protocolos.

• Ataque con clave conocida: El atacante obtiene algunas claves utilizadas en cifrados previos para determinar nuevas claves.
• Reutilización del protocolo: El atacante, ataca utilizando una comunicación captada previamente, insertándola en la comunicación.
• Suplantación de Identidad: El atacante toma la identidad de un usuario registrado en la red de comunicaciones.

Otros ataques.

• Ataque de fuerza bruta: El ataque por fuerza bruta consiste en un ejercicio de combinación, donde se van cifrando todas las posibles contraseñas y comparándolas con las existentes en el registro, buscando también coincidencias. Este método, por definición, siempre consigue su meta, si bien el problema que tienen es de recursos y tiempo.

2.1 Ataques al Algoritmo DES

Criptoanálisis Diferencial

El criptoanálisis diferencial fue introducido por E. Biham y A. Shamir, es un ataque en texto claro escogido y esta basado en comparaciones del OR exclusivo de dos textos en claro escogidos con el OR exclusivo de sus correspondientes cifrados. Este método de análisis permite romper el DES utilizando en teoría alrededor de 247 parejas de textos en claro seleccionados, siendo aproximadamente 236 las útiles para el criptoanálisis, con un tiempo de calculo equivalente a unos 237 cifrados. El problema básico de este ataque es obtener los cifrados de los textos en claro, ya que para obtenerlos es necesario engañar a la entidad que realiza el cifrado o violar la seguridad física del lugar donde se realiza el cifrado, lo cual en la practica es casi imposible.

Criptoanálisis Lineal

El criptoanálisis lineal fue introducido por M. Matsui, se basa en un ataque en texto en claro escogido y consiste en la obtención de ecuaciones lineales que representen la probabilidad existente entre algunos bits del mensaje en claro y otros del cifrado DES del mismo mensaje. La ecuación utilizada es la siguiente:

F(P[i1,…ip] , C[j1,…jp]) = k[k1, k2,…kk]

Donde F(…) es una función lineal y [i1,…ip] ,[j1,…jp]) ,[k1, k2,…kk] son bits que ocupan posiciones fijas respectivamente en P, C y K.

3. Bibliografía

http://csrc.nist.gov/cryptval/des.htm

http://cereal.rutgers.edu/~xylu/519_hw4.html

http://www.infoworld.com/article/04/07/29/HNdesinadequate_1.html

Criptografía Digital Fundamentos y Aplicaciones

José Pastor Franco, Miguel Ángel Sarasa López

2da, Edición

Rafael Martinez