miércoles, 21 de octubre de 2015

Criptografía (XVIII): criptología para todos (II)

Continúo en este post el repaso a los criptosistemas clásicos que inicié en el anterior y que me permitirá introducir nuevos conceptos que entiendo ayudarán a comprender mejor los sistemas criptográficos modernos que serán objeto de próximas entradas.

Pero antes sentemos algunas definiciones y conceptos relativos, esta vez, al criptoanálisis.

- Ataque de fuerza bruta: es el tipo de ataque más simple a un criptosistema y consiste en su caso más extremo en ir probando una a una todas las claves posibles hasta encontrar la correcta. En definitiva, se conocen con este nombre a todos los métodos que prueban exhaustivamente las claves del espacio K (conjunto finito de todas las claves que se pueden emplear).

Actualmente el espacio de claves (K) de cualquier criptosistema que se precie ha de ser lo suficientemente grande para hacer inviable un ataque de este tipo, aunque el gran avance de la potencia de cálculo de los ordenadores en la actualidad y en un futuro próximo, e incluso la aplicación de nuevas tecnologías ahora en ciernes (criptografía cuántica), podría hacer a algunos de ellos, e incluso a todos ellos, vulnerables frente a este tipo de ataques.

Esto no ocurría en gran parte de los criptosistemas clásicos, por lo que la mayoría de ellos son actualmente susceptibles de ser atacados con éxito mediante el empleo de la fuerza bruta (en algunos casos, los más simples, ni siquiera nos harían falta los ordenadores).

- Análisis de frecuencias: técnica que consiste en explotar la frecuencia de aparición de las letras y grupos de letras en el idioma en el que está escrito un mensaje en claro para poder descifrar los mensajes cifrados sin disponer de la clave.

Al Kindi, en el siglo IX, fue el primero en documentar este tipo de ataque para "romper" cifrados clásicos de sustitución monoalfabética.

En los criptosistemas de sustitución monoalfabética ciertas características del idioma en el que está escrito el texto en claro se trasladan al texto cifrado; tal es el caso de la frecuencia relativa de aparición de las letras y de grupos de letras (bigramas, trigramas, etc.). Es decir, en un texto cifrado mediante un sistema de este tipo, el carácter, dígrafo, etc. que aparezca con mayor frecuencia será el candidato a corresponderse con la letra de mayor frecuencia en el idioma en el que se encuentra escrito el texto en claro (en español la "E") y así sucesivamente (en español: "A", "O",...), y, de la misma forma, los grupos de mayor frecuencia serán los candidatos a corresponderse con los bigramas, trigramas, etc. más frecuentes en dicho idioma (en español: "DE", "EN",... "ENE", "ESE",...).

A lo largo de la historia los criptógrafos han ido ideando diversos métodos para evitar este tipo de ataque (sustitución polialfabética, combinación de sustitución y transposición, etc.), algunos de ellos, como veremos más adelante en el repaso de algunos de los criptosistemas clásicos, con mayor o menor éxito que otros.

- Ataque sólo al criptograma: el criptoanalista conoce el algoritmo de cifrado pero sólo tiene acceso a textos cifrados o criptogramas.

El análisis de frecuencias podría considerarse como un ataque de este tipo.

- Ataque con texto claro conocido: las mismas características que el anterior pero, además, el criptoanalista conoce o infiere parte del texto en claro correspondiente al texto cifrado del que dispone.

Entiendo que el criptoanálisis que realizó Alan Turing al cifrado de la máquina Enigma, basado en la conjetura de que ciertos textos sin cifrar ("cribs") se encontraban en el texto cifrado, puede ser catalogado como un ataque de este tipo.

- Ataque con texto claro (cifrado) escogido: se denomina así al tipo de ataque en el que el criptoanalista puede obtener los textos cifrados (en claro) correspondientes a un conjunto de textos en claro (cifrados) de su elección.

Aunque hablaré de este tipo de criptoanálisis en un post posterior, incluyendo algunas definiciones a las que todavía no he hecho referencia, adelanto que se puede considerar un ataque de este tipo al criptoanálisis diferencial inventado por Eli Biham y Adi Shamir en 1990, aplicable fundamentalmente a los algoritmos simétricos de cifrado por bloques tipo DES (Data Encryption Standard) y que parte de pares de mensajes en claro con diferencias mínimas, estudiando las variaciones que se producen en los correspondientes mensajes cifrados.

Continuemos ahora con el repaso a algunos métodos de criptografía clásica:

1.- Cifrado por sustitución homofónica: con este tipo de cifrado se pretendía "aplanar" o "suavizar" la frecuencia de aparición de los caracteres, símbolos o grupos de éstos en un criptograma. De esta forma se perseguía que las características propias de un idioma en cuanto a la frecuencia de aparición de las letras no se trasladara al criptograma y evitar así el análisis de frecuencias.

Por ejemplo: supongamos que nuestro alfabeto de entrada está constituido por las 27 letras del alfabeto español y nuestro alfabeto de salida por los números del "00" al "99". Así, podríamos asignar a cada letra uno o varios números en función de su frecuencia de aparición en un texto escrito en español, construyendo una tabla, por ejemplo, como la siguiente:
Si sólo utilizáramos un número para sustituir cada carácter de un texto en claro, supongamos que los que figuran en la primera fila de nuestra tabla, para cifrar: "ESTE ES UN EJEMPLO DE CIFRADO", obtendríamos el siguiente criptograma (en grupos de dos dígitos): "21 06 02 21 21 06 14 38 21 37 21 12 13 11 01 04 21 09 08 15 18 05 04 01".

Con lo que en el análisis de frecuencias obtendríamos que "21" aparece en 6 ocasiones y el criptoanalista llegaría a la conclusión de que probablemente se corresponda con la "E" (la letra más frecuente en español), y con mayor cantidad de texto cifrado y el análisis de frecuencias de bigramas, trigramas, etc. no sería muy difícil descifrar los mensajes.

Sin embargo, si utilizamos todas las filas de la tabla anterior el criptograma resultante podría ser el siguiente (en grupos de dos dígitos): "73 06 32 36 29 89 14 80 98 37 48 12 13 51 75 82 44 93 60 15 95 79 04 66", con lo que el criptoanalista no tendría ninguna pista sobre la correspondencia de estos grupos de dos dígitos con las letras del alfabeto español, y con mayor cantidad de texto cifrado tendría serias dificultades al estar "aplanada" o "suavizada" su frecuencia de aparición.

Sin embargo, si se dispone de una gran cantidad de texto cifrado se podrían encontrar secuencias repetidas de caracteres, símbolos o grupos de éstos (en nuestro ejemplo números de dos dígitos) y realizar con éxito un ataque basado en el análisis de frecuencias de bigramas, trigramas, etc.

Conforme a las definiciones que hemos ido incluyendo en estos posts, los sistemas por sustitución homofónica son sistemas de sustitución polialfabética.

2.- Cifrado de Vigenère:
Sobre este método clásico de cifrado, recogido en una obra del siglo XVI escrita por Blaise de Vigenère (aunque quien ideó el método original fue realmente Giovan Battista Bellaso), ya he escrito una entrada en este blog en la que cuento brevemente en qué consistía y también el método Kasiski para criptoanalizar mensajes cifrados con este método.

Se trataba de un sistema de sustitución polialfabética que utilizaba una clave para cambiar de alfabeto, lo que, en principio, imposibilita el ataque mediante el método de análisis de frecuencias, ya que un carácter del texto en claro no se sustituía siempre por la misma letra en el texto cifrado.

Ya vimos en el citado post anterior cómo se cifraba y descifraba un mensaje utilizando este método (muy fácil: carácter que se encuentra en la intersección de la fila del carácter que corresponde al carácter de la clave y de la columna del carácter del texto en claro. Vamos, como en el juego de los barcos).

Sin embargo su vulnerabilidad residía en su naturaleza cíclica (aplicación cíclica de n cifrados de sustitución monoalfabética), de tal manera que si era posible determinar la longitud de la clave observando patrones comunes o repeticiones de caracteres (de 3 o más) en el texto cifrado bastaba con dividir el criptograma en tantos subcriptogramas como número de caracteres tuviera la clave (cada uno de ellos habría sido cifrado utilizando la misma letra de la clave o, lo que es lo mismo, el mismo alfabeto) para poder realizar un análisis de frecuencias sobre cada uno de ellos y obtener la clave empleada.

3.- Cifrado de Playfair:
Se trata de un criptosistema inventado por Charles Wheatstone en el siglo XIX, aunque su nombre se debe a Lyon Playfair que fue quien contribuyó a darlo a conocer.

Este sistema consistía en utilizar una matriz de 5x5 caracteres que se iba rellenando, de izquierda a derecha y de arriba abajo, con las letras de la clave (eliminando las posibles letras repetidas de la misma) y se completaba con el resto de las letras del alfabeto (las que no figurasen en la clave), excluidas la "J" y la "Ñ".

Por ejemplo, utilizando la palabra "PLAYFAIR" como clave, obtendríamos la matriz que se muestra en la figura que ha servido para ilustrar este método.

Cada grupo de dos letras del texto en claro era sustituido por otras dos letras en el texto cifrado, de la siguiente manera (utilizaré como ejemplo el mensaje en claro: "CIFRADO PLAYFAIR" y la clave "PLAYFAIR"):

a) Se agrupaban los caracteres del texto a cifrar dos a dos.

En nuestro ejemplo:

"CI FR AD OP LA YF AI RX".

Si el número de caracteres era impar, como es nuestro caso, se añadía como último carácter una letra sin significado en el mensaje en claro, por ejemplo: "X".

b) Para cada par de caracteres:

b.1) Si ambos caracteres estaban situados en la misma fila cada uno de ellos se sustituía por el carácter situado inmediatamente a su derecha (si el carácter a sustituir era el último de la fila se sustituía por el primero de la fila).

En nuestro ejemplo:
b.2) Si ambos caracteres estaban situados en la misma columna cada uno de ellos se sustituía por el carácter situado inmediatamente debajo de él (si el carácter a sustituir era el último de la columna se sustituía por el primero de la columna).

En nuestro ejemplo ningún par de las letras agrupadas en el texto en claro coinciden en una misma columna, pero suponiendo que hubieran coincidido la "E" y la "U":
b.3) Si ambos caracteres estaban situados en diferente fila y columna, la primera letra se sustituía por aquella situada en su misma fila y la misma columna que la segunda, y la segunda por aquella situada en su misma fila y la misma columna que la primera.

En nuestro ejemplo:
b.4) Si ambos caracteres eran el mismo, es decir, la pareja estaba formada por la misma letra, había que descomponer ese par de letras para formar dos nuevas parejas, lo que se hacía añadiendo una letra sin significado tanto al primer carácter como al segundo, y después se cifraban ambos nuevos pares de letras conforme a las reglas anteriores.

En nuestro ejemplo ningún par de las letras agrupadas en el texto en claro está formado por dos letras iguales, pero suponiendo que uno de ellos fuera, por ejemplo, "AA" habría que formar dos nuevas parejas, por ejemplo: "AX" y "AX" y aplicarles las reglas de cifrado anteriores.

Conforme a todo lo indicado, en nuestro ejemplo, se obtendría:

Texto en claro    ---> "CIFRADO PLAYFAIR".
Pares de letras  ---> "CI  FR AD OP LA  YF  AI  RX".
Criptograma      ---> "DR LD FB NL  AY FP PB CV".

Por tanto, se trataba de un criptosistema de sustitución monoalfabética, ya que cada pareja de letras del mensaje en claro se sustituía siempre por el mismo dígrafo (grupo de dos letras) en el texto cifrado.

En este caso, aunque el cifrado de pares de caracteres imposibilitaba el análisis de frecuencias de las letras en el idioma en el que estuviera escrito el mensaje en claro, la vulnerabilidad venía dada porque algunas características propias del idioma, en este caso la frecuencia de aparición de bigramas, persistían en el texto cifrado.

4.- Cifrado de Vernam:
Este criptosistema inventado en 1917 por Gilbert S. Vernam, aunque posteriormente Joseph Mauborgne hizo una contribución decisiva al mismo, consistía en utilizar como clave una secuencia aleatoria de igual longitud que el mensaje, combinándola carácter a carácter con el texto mediante una función reversible. Dicha secuencia se usaba una única vez (lo que se conoce en inglés como one-time pad) y tras su uso se destruía.

La función era una XOR u o-exclusivo (suma módulo 2, ver figura) aplicada a los bits utilizados para codificar los caracteres en código Baudot de teletipos.

El código de Baudot representaba las letras, dígitos y algunos caracteres especiales mediante cinco posiciones con un espacio o una marca, es decir, cinco bits (25 caracteres), de la siguiente manera:
Por tanto, la función de cifrado podría expresarse en este caso como: Ek(mi) = (mi + ki) mod 2 = mi XOR ki, mientras que la de descifrado sería: Dk(ci) = (ci + ki ) mod 2 = ci XOR ki.

Veamos un ejemplo de cifrado:
Por tanto, conforme a las definiciones comentadas hasta este momento, se trataba de otro criptosistema de sustitución polialfabética, ya que cada carácter del mensaje en claro no se sustituía siempre por el mismo carácter en el texto cifrado.

Para descifrar un criptograma bastaba con volver a combinar la clave carácter a carácter con el texto cifrado mediante la función XOR u o-exclusivo (suma módulo 2). En nuestro ejemplo de la siguiente manera:
5.- Cifrado ADFGVX:
Sobre este cifrado, así como sobre su criptoanálisis, ya he escrito algunas entradas en este blog, por lo que me limitaré a decir que era un criptosistema que combinaba la sustitución monoalfabética con la transposición. Esto último, precisamente, para evitar una ataque mediante el análisis de frecuencias.

Este cifrado fue "roto" muy pocas veces durante la I Guerra Mundial, si bien es cierto que se empezó a utilizar al final de la misma.

Como comento en las entradas a las que he hecho referencia, las labores de criptoanálisis que llevó a cabo en ese momento Georges Painvin se centraron en mensajes interceptados muy esteriotipados, con comienzos y/o finales de los mismos muy similares, y podemos decir que se trató de un ataque sólo al criptograma, eso sí, basado en la inestimable ayuda que le brindaban los alemanes al transmitir mensajes cifrados con la misma clave (todos los de un día) con secuencias de caracteres comunes entre ellos.

Mediante esas secuencias de caracteres comunes entre criptogramas, Georges Painvin era capaz de deducir la longitud de la clave con la que se habían cifrado los mensajes de un mismo día y deshacer la transposición de las columnas que se había realizado ordenando alfabéticamente los caracteres de la clave. Una vez hecho esto, con el suficiente número de mensajes interceptados, bastaba con realizar un análisis de frecuencias de los dígrafos del mensaje (letras, bigramas, trigramas,...) para obtener el texto en claro de todos los mensajes de un mismo día.

Esto nos recuerda que en la seguridad de la información, y la criptografía no es una excepción, el eslabón más débil de la cadena de seguridad lo constituyen las personas; podemos tener un criptosistema muy robusto, el cifrado ADFGVX lo era para su época, pero éste será finalmente "roto" si las personas que lo utilizan hacen un uso no adecuado de él.

6.- Máquinas de cifrado del siglo XX:
Sobre la máquina más famosa de este tipo, la máquina Enigma, también he escrito varios posts en este blog, por lo que en éste también me limitaré a decir que se trataba de un criptosistema de sustitución polialfabética, pero esta vez con tal número de alfabetos involucrados que lo hacían prácticamente invulnerable a los métodos de criptoanálisis conocidos hasta la fecha, o, al menos, así lo creían los alemanes.

El cifrado de esta máquina también fue criptoanalizado con éxito o, al menos, con un relativo acierto, en primer lugar por los polacos y después por los británicos, pero en mi opinión lo que llevó a ello tampoco fue, otra vez y al menos en lo fundamental, una vulnerabilidad propia del sistema, sino el uso inadecuado que de él hicieron las personas (repetición al inicio del mensaje de los caracteres correspondientes a la clave de sesión, falta de disciplina de los operadores alemanes al elegir estos caracteres - repetidos, consecutivos,... -, excesivo formalismo de los mensajes con comienzos o finales muy esteriotipados, envío de mensajes a la misma hora con contenido y estructura muy similares - partes metereológicos - ,...).

No obstante, en el siglo XX se inventaron y utilizaron otras máquinas de cifrado, tales como: Purple, Typex, SIGABA,...

Hasta aquí este post, en el que he repasado algunos de los criptosistemas clásicos y que me ha servido adicionalmente para introducir algún nuevo concepto, y en el siguiente introduciré ciertos conceptos relativos a los criptosistemas modernos.

No hay comentarios:

Publicar un comentario