Con este artículo espero empezar una serie dedicada a criptografía, ya que es un tema que suele despertar bastante curiosidad y no es algo de lo que se suelan publicar muchos artículos. Pensando en aquellos que no tengan ningún tipo de conocimiento sobre el tema intentaré no dejarme ningún detalle para que la explicación sea lo más completa posible.
1. Introducción.
Empecemos introduciendo un poco de terminología:
- Texto en claro o plain text: es la
información original, el mensaje, que se quiere cifrar. - Texto cifrado o criptograma: es la
información resultante una vez se ha cifrado el mensaje.
A continuación clasificaremos los distintos
típos de mecanismos de cifrado, indicando sus diferencias,
pros y contras. Por una parte podemos dividir los sistemas de cifrado
según operen sobre bloques o sobre streams (flujos de bits).
Los primeros dividen la información a cifrar en bloques de un
determinado tamaño y aplican una serie de operaciones sobre
ese bloque para producir el criptograma. Los segundos, cifran la
información bit a bit.
Por otra parte, podemos dividir los sistemas de
cifrado en simétricos y asimétricos. En los primeros,
también conocidos como sistemas de clave secreta, se utiliza
la misma clave tanto para cifrar como para descifrar, por lo tanto,
las distintas partes involucradas en la comunicación de los
datos cifrados (emisor y receptor) deben compartir el conocimiento de
esta clave. Los sistemás asimétricos o sistemas de
clave pública utilizan dos claves, una para cifrar y la otra
para descifrar, de tal manera que el criptograma producido por una de
ellas sólo puede ser descifrado por la otra. Esta división
de dos claves permite la existencia de lo que se ha venido a conocer
como firmas digitales, pero esto lo dejamos para un futuro artículo.
Centremonos en los sistemas de cifrado simétricos, y más
concretamente en los de bloque.
2. Esquema de los sistemas de cifrado de bloques.
El esquema de funcionamiento general es bastante
simple, se divide la información a cifrar en bloques de un
mismo tamaño y a cada uno de ellos se le aplican una serie de
transformaciones para producir el correspondiente bloque de texto
cifrado. Esquemáticamente:
Ilustración1 – Esquema de cifrado por bloques
Dentro de este tipo de sistemas criptográficos,
el más conocido es el DES o Data Encryption Standar. Este
sistemas fue desarrollado a principio de los años ’70 por un
grupo de trabajo de IBM. En 1981 la ANSI aprovó el DES como
estándar, el X3.92. Por su parte, la ISO hizo lo mismo en 1987
dandole el nombre de DEA-1. Las principales características de
este sistema de cifrado es que utiliza operaciones lógicas
simples (transposiciones, desplacamientos y XOR’s) sobre grupos
reducidos de bits, lo que permite una fácil y eficiente
implementación del algoritmo en hardware.
3. Data Encryption Standar.
Como ya hemos dicho, el DES es un sistema de
cifrado de bloques. En este caso, el algoritmo toma la información
en bloques de 64 bits produciento un bloque de texto cifrado también
de 64 bits. Las claves utilizadas por este sistema son de 56 bits,
aunque se suelen distribuir en forma de un número de 64 bits,
donde cada octavo bit (el lsb o less-significant bit) de cada uno de
los ocho bytes de la calve es un bit de paridad.
Ilustración 2 – Esquema clave DES
3.1. Algoritmo de cifrado.
Centremonos ahora en el algoritmo de cifrado.
Ilustración 3 – Esquema del DES
Lo primero que se realiza es una permutación
de los 64 bits del bloque de entrada. Realmente, esta permutación
no añade seguridad alguna y su principal función es la
de facilitar la carga de los bits de información en bloques de
8 bits a un chip especializado en DES (debemos recordar que el
desarrollo del DES es anterior a los procesadores de 16 o 32 bits).
Al final del algoritmo hay otra permutación que es la inversa
de esta, lo que vuelve a dejar a los bits en su posición
inicial.
5850423426181002
6052443628201204
6254463830221406
6456484032241608
5749413325170901
5951433527191103
6153453729211305
6355473931231507
Tabla 1 – Permutación inicial
Esta tabla debe leerse de izquiera a derecha y de
arriba a bajo. Esto quiere decir, que el primer bit a la salida de la
permutación es el que en la entrada ocupa la posición
58; el segundo, el que ocupaba la 50; y así sucesivamente.
Despues de esta permutación inicial, los 64
bits resultantes se dividen en dos partes de 32 bits cada una. Lo que
viene a continuación se repite diecisesis veces:
(Li+1) y el resultado de la XOR anterior pasará
a ser la parte de la derecha de la ronda siguiente (Ri+1).
Li+1 = Ri
Ri+1 = Li XOR f(Ri, K)
La única excepción a este proceso
está en la última ronda, en la que el entrecruce de las
dos partes no se produce.
El esquema de esta función f es el siguiente:
Ilustración 4 – Esquema de la función f
En cada ronda, se genera una subclave Ki
distinta de la siguiente manera: como ya habiamos dicho, de los 64
bit de la clave, se descartan los 8 bits de paridad quedando una
clave de 56 bits. Esto se realiza mediante la siguiente permutación:
57494133251709
01585042342618
10025951433527
19110360524436
63554739312315
07625446383022
14066153453729
21130528201204
Tabla 2 – Permitación de la calve
Como se puede observar, no aparecen los bits 8, 16, 24, 32, 40, 48, 56 ni 64, que
son los que hacen la función de bits de paridad.
La clave resultante se divide en dos mitades de 28
bits que alimentan unos registros que rotan hacia la izquierda cada
una de las mitades un número de bits que viene determinado por
la ronda en la que nos encontramos (recordar que en el DES existen 16
rondas)
Ronda01020304050607
080910111213141516
Desplazamiento
11222222
12222221
Tabla 3 – Desplazamientos según la ronda para el cifrado
De los 56 bits resultantes se seleccionan 48
modificando su orden. Esta operación es denominada permutación
de compresión.
141711240105
032815062110
231912042608
160727201302
415231374755
304051453348
444939563453
464250362932
Tabla 4 – Permutación de compresión
En la salida de la permutación de
compresión tendríamos la subclave Ki de 48
bits correspondiente a la ronda i-ésima del algoritmo. Una vez
ya hemos explicado como se obtienen las subclaves de las rondas,
centremonos en las modificaciones que sufre la parte de la derecha Ri
dentro de la función. Primero, mediante la permutación
de expansión, se expanden los 32 bits de Ri a 48
bits (repitiendo alguno de los bits) cambiando, además, su
posición. Esto se hace para que este operando tenga el mismo
tamaño que la subclave de la ronda, y además hace que
los bits del criptograma dependan todavía con más
fuerza de los bits de la entrada. Esto hecho se conoce como el efecto
avalancha: un pequeño cambio en el mensaje de entrada provoca
grandes modificaciones en la sequencia de bits de salida.
320102030405
040506070809
080910111213
121314151617
161718192021
202122232425
242526272829
282930313201
Tabla 5 – Permutación de expansión
Los 48 bits resultantes de la XOR entre la parte
derecha Ri expandida y la subclave Ki se
introducen de seis en seis en ocho bloques que son conocidos como
S-Box, de tal manera que el primer bloque de 6 bits se introduce en
la S-Box 1, el segundo en la S-Box 2, y así sucesivamente.
Como cada S-Box toma 6 bits como entrada y produce 4 bits como
salida, al final obtenemos 32 bits (8 S-Box · 4 bits/S-Box =
32 bits)
Cada S-Box es una tabla de cuatro filas y
dieciseis columnas, donde cada posición de la tabla es un
número de 4 bits. De los 6 bits de la entrada b1 b2 b3 b4 b5
b6, los bits b1 y b6 indican la fila, mientras que los otros cuatro
indican la columna. Es decir, si la entrada de una S-Box es 35, esto
en binario es 100011, lo que significa que hemos de tomar el valor de
la fila 3 (11) y columna 1 (0001). El contenido de cada una de las
S-Box es distinta del de las demás.
Contenido de las S-Box
1404130102151108
0310061205090007
0015070414021301
1006121109050308
0401140813060211
1512090703100500
1512080204090107
0511031410000613
Tabla 6 – S-Box 1
1501081406110304
0907021312000510
0313040715020814
1200011006091105
0014071110041301
0408120609030215
1308100103150402
1106071200051409
Tabla
7 – S-Box 2
1000091406031505
0113120711040208
1307000903040610
0208051412111501
1306040908150300
1101021205101407
0110130006090807
0415140311050212
Tabla 8 – S-Box 3
0713140300060910
0102080511120415
1308110506150003
0407021201101409
1006090012110713
1501031405020804
0315000610011308
0904051112070214
Tabla 9 – S-Box 4
0212040107101106
0805031513001409
1411021204071301
0500151003090806
0402011110130708
1509120506030014
1108120701140213
0615000910040503
Tabla 10 – S-Box 5
1201101509020608
0013030414070511
1015040207120905
0601131400110308
0914150502081203
0700041001131106
0403021209051510
1114010706000813
Tabla 11 – S-Box 6
0411021415000813
0312090705100601
1300110704090110
1403051202150806
0104111312030714
1015060800050902
0611130801041007
0905001514020312
Tabla 12 – S-Box 7
1302080406151101
1009031405001207
0115130810030704
1205061100140902
0711040109121402
0006101315030508
0201140704100813
1512090003050611
Tabla 13 – S-Box 8
Los 32 bits resultantes de la anterior operación
entran en la permutación P, en la que los bits son permutados
otra vez pero esta vez no se eliminan ni añaden bits como se
habia hecho en las permutaciónes de compresión y
expansión.
1607202129122817
0115232605183110
0208241432270309
1913300622110425
Tabla 14 – Permutación P
Para finalizar la ronda, la salida de la
permutación P alimenta una XOR en la que el otro operando es
la parte izquiera Li. Si no estamos en la ronda 16, el
resultado de la XOR anterior se convierte en la parte derecha de la
siguiente ronda Ri+1, y la parte derecha de la ronda en la
que estamos Ri pasará a ser la parte izquiera de la
siguiente Li+1. Y así sucesivamente hasta completar
las 16 rondas.
Finalmente, la concatenación de L16 y R16
se introduce en una permutación final, que ya habiamos
comentado al inicio de la explicación del algoritmo. Esta
permutación es la inversa de la permutación inicial
quedando de la siguiente manera:
4008481656246432
3907471555236331
3806461454226230
3705451353216129
3604441252206028
3503431151195927
3402421050185826
3301410949175725
Tabla 15 – Permutación final
Se podría haber hecho que en la ronda final
se intercambiaran las partes derecha e izquierda, y adaptar la
permutación final para que tuviera en cuenta este intercambio
de más. Pero no se hizo porque de esta manera se puede
utilizar el mismo algoritmo tanto para el cifrado como para el
descifrado.
3.2. Algoritmo de descifrado.
El algoritmo de descifrado es el mismo que el de
cifrado, con la única matización de que las subclaves
deben utilizarse en el orden inverso. Es decir, si en el algoritmo de
cifrado las subclaves de cada ronda eran K1, K2, …, K16, en el
descifrado las subclaves son K16, K15, …, K1, entendiendo que la
primera subclave (K1 en el cifrado y K16 en el descifrado) es la que
se utiliza en la primera ronda; la segunda subclave (K2 en el cifrado
y K15 en el descifrado), en la segunda ronda; etc.
Además, el algoritmo mediante el cual se
generan las subclaves es circular. Así que para generar las
subclaves necesarias para el descifrado, los registros de rotación
en lugar de desplazar hacia la izquierda, lo deben hacer hacia la
derecha y el número de desplazamientos viene dado por la
siguiente tabla:
Ronda01020304050607
080910111213141516
Desplazamiento012222
2212222221
Tabla 16 – Desplazamientos según la ronda para el descifrado
3.3. Consideraciones sobre las claves.
Debido al modo en el que se generan las subclaves
en las diferentes rondas, existen una serie de claves que no son
aptas para ser utilizadas. Las primeras de estas claves son conocidas
como claves débiles (o weak keys). La debilidad de
estas claves es que todos los bits de cada una de las dos mitades que
entran en los registros de rotación son todo unos o todo
ceros. Entonces, por mucho que rotemos estas palabras de bits,
siempre obtendremos la misma subclave.
Claves Débiles
Subclave
101010101010101
0000000 0000000
1F1F1F1F0E0E0E0E
0000000 FFFFFFF
E0E0E0E0F1F1F1F1
FFFFFFF 0000000
FEFEFEFEFEFEFEFE
FFFFFFF FFFFFFF
También es posible encontrar pares de
claves de tal manera que el criptograma generado por una de las
claves del par puede ser descifrado por la otra clave. O lo que es
lo mismo, las dos claves del par generan el mismo criptograma a
partir del mismo texto en claro. Esto se debe a que esas claves, en
lugar de generar 16 subclaves distintas, sólo generan dos
subclaves, y cada una es usada ocho veces. A estas claves se le
llaman claves semidébiles (semiweak keys) y existen 12
claves que cumplen esta condición.
Para finalizar, existen otras claves que producen
únicamente cuatro subclaves distintas, que son usadas cuatro
veces cada una. Estas son conocidas como claves posiblemente débiles
(possibly weak keys). De este tipo de claves, existen 48.
Pero a pesar de la existencia de estas 64 claves
débiles (4 + 12 + 48), hay que decir que son una minuscula
porcion de las 256 = 72.057.594.037.927.936 claves que
puede utilizar el DES.
4. Conclusiones
Como se ha podido ver, las operaciones utilizadas
en el sistema de cifrado DES son muy simples, permutaciones, XORs e
indexado de tablas; siendo estas tres operaciones muy simples de
realizar utilizando hardware: las permutaciones se pueden conseguir
simplemente cambiando el orden de las pistas, para las XOR disponemos
de circuitos integrados que ejecutan esa función, y el
indexado de tablas se puede conseguir mediante ROM’s. Este criterio,
el de simplicidad de implementación, es uno de los que se
tuvieron en cuenta durante el desarrollo del algoritmo. Y el hecho de
que se pudiera implementar a nivel de hardware permitió que se
puediera usar en aplicaciones en las que la latencia es un factor
importante. Otro de los criterios es que la robustez del sistema no
debía depender de que el algoritmo fuera secreto, y en este
caso toda la seguridad del sistema reside en la clave.
Espero que este artículo os haya parecido interesante. Ya estoy preparando
el siguiente que tratará los sistemas de cifrado asimétricos.
Articulo basado en el capítulo
12 de “Applied Criptography” de Bruce Schneier
Este post ha sido traido de forma automatica desde https://web.archive.org/web/20140625063149/http:/bulma.net/body.phtml?nIdNoticia=1679 por un robot nigromante, si crees que puede mejorarse, por favor, contactanos.