El criptoanálisis del método Vigenère

Por fin, con un retraso digno de Lucia alguien que se retrase mucho, llega el post sobre criptoanálisis.

Bueno, supongo que tod@s vosotr@s, querid@s lector@s (la chorradita esta de la @ para hacerse el políticamente correcto a veces tiene su punto, pero cansa mogollón), tendréis estudiado el método de cifrado polialfabético Vigenère, ya que debéis entenderlo para seguir esta explicación.

Como recordareis, se habló de que el método César se puede descifrar sin conocer la clave haciendo un análisis de frecuencias (un criptofante para Gema), cosa que inmediatamente nos revela el desplazamiento (la clave) utilizado. Como el método Vigenère utiliza múltiples desplazamientos y no tiene una longitud fija de clave, esa frecuencia relativa queda difuminada, de manera que un análisis de frecuencia no nos revelará nada.

Pero si que existen patrones que nos pueden dar pistas sobre cómo romper el algoritmo. Y es que, en los idiomas no sólo se repiten mas unas letras que otras, sino que también se repiten mas unas secuencias que otras. En español, por ejemplo, se repetirá mucho mas la secuencia "los" que la secuencia "wes" sin ninguna duda. ¿Y cómo podemos aprovechar esto? Pues fácil, si tenemos la suerte de que dichas secuencias coinciden con que estén cifradas con los mismos caracteres de la clave, ya que producirán criptogramas iguales que se repetirán a lo largo de todo el texto cifrado. Entonces, mirando las distancias entre dichas repeticiones tendremos información sobre la longitud de la clave, ya que deben ser múltiplos de la misma.

De esto se dió cuenta un criptógrafo militar prusiano a mediados del siglo XIX (fijaos lo que duró la consideración de "indescifrable" del método Vigenère) llamado Friedrich Kasiski.

Vamos a ver un ejemplo de la utilización del método:

mensaje:"Shut up. Shut up! Shut up! You can't have egg, bacon, spam and sausage without the spam"
clave: "abcd"
criptograma: "SIWWUQUKUUWSSIWWUQARUDCQTICYEF IJBBERNTRDMBPGSBWVAHGZIUJRUUVKETRDM"

He señalado en negrita las secuencias que se repiten. Podemos ver que se repite "SIWWUQ", que corresponde al primer y tercer "Shut up", y "TRDM" correspondiente a las dos apariciones de "spam". La separación entre las primeras repeticiones es de 12 posiciones, y de 24 entre las últimas. Como hemos dicho antes, estos números deben ser múltiplos de la longitud de la clave. Por lo tanto, descomponemos los números en factores primos: 12 = 2x2x3, 24= 2x2x2x3. Esto nos indica que la clave puede tener las longitudes de 2, 3, 4 (2x2), 6 (2x3) o 12 (2x2x3).

Debemos elegir una de las longitudes, y no queda mas remedio que hacerlo por prueba y error. Descomponemos el criptograma en subconjuntos en función de la longitud elegida y luego hacemos un análisis de frecuencia de letras para determinar el desplazamiento utilizado en cada uno. Es decir, si probamos con una longitud de 2, tendremos que las posiciones pares están cifradas con un alfabeto y las impares con otro y sabemos atacar a ambos conjuntos por separado, ya que no son mas que dos cifrados César. Una vez que tengamos todos nuestros subconjuntos resueltos tendremos la clave final.

Voy a dejarlo aquí porque el post ya me está quedando muy largo, asi que dejaré para los próximos algunas cosas que quería comentar. Lo que si que no me aguanto a decir es que la frase elegida para cifrar, por si os lo habeis preguntado, es de un sketch de Monty Python. Este sketch tiene la curiosidad de que es la causa por la que al correo basura se le conoce como "spam".

Bailando

Las navidades tienen algo bueno, y es que me permiten practicar una de mis aficiones: bailar y grabarme en video interpretando temas navideños.

Vehículos

Algún gracioso puso ayer a funcionar este script en mi familia:

for coche in cochesFamilia:
      coche.funciona=false
      time.sleep(43200)

Al menos nos quedan las bicicletas (pero son para el verano).

El principio de Kerckhoff

Como comentaba hace dos posts, sí es posible romper el cifrado Vigénere. Aunque pueda parecer que esto tiene tan solo un carácter educativo en realidad no es así. Ocurre que la gente que no está familiarizada con la criptografía suelen pensar que es sencillo crear su propio algoritmo criptográfico basando gran parte de la seguridad en hacerlo secreto, y en la mayoría de las ocasiones pasa por ser, a lo sumo, una variación de un cifrado polialfabético. En estos casos se puede llegar a romper este tipo de códigos con un simple criptoanálisis clásico. No voy a hablar aquí de momento sobre estos métodos (lo dejaré para el siguiente artículo).

Sí quería comentar en este post una de las máximas de la criptografía, conocida como el principio de Kerckhoff: "un criptosistema debe ser seguro incluso si todo lo relacionado con el funcionamiento del sistema, excepto la clave, es de conocimiento público". Es decir, que un algoritmo no debe basar su seguridad en que no se conozca por completo su funcionamiento, sino que la seguridad debe residir estríctamente en un secreto compartido en forma de clave entre emisor y receptor. Lo contrario es lo que se conoce por "security through obscurity" y es un error de principiante. Por ejemplo, la escritura con jugo de limón que todos hemos hecho de pequeños (aunque según cómo se haga podría llegar a entrar en el terreno de la esteganografía).

Lo triste es cuando el que busca seguridad con jugo de limón no es un niño jugando al amigo invisible sino una empresa de software que pretende ofrecer soluciones serias en el campo de la seguridad. Hay innumerables casos de estas malas práxis (seguramente algunos leereis esto desde un sistema operativo de Microsoft, todo un ejemplo de "insecurity" a pesar de la "obscurity"). También podemos encontrar entre ellos el famoso cifrado A5 con el que funcionan los móviles GSM, que quedó roto cuando se comprendió su funcionamiento mediante técnicas de ingeniería inversa; por lo que hoy en día cualquiera que se pueda permitir la compra del equipo necesario (que se vende por internet) puede escuchar el contenido de cualquier conversación realizada con un teléfono móvil. Quizá no tan cercano a nosotros pero con implicaciones muy serias en la sociopolítica internacional podemos hablar sobre las máquinas de voto utilizadas en las elecciones en el país autoproclamado líder del mundo libre; las cuales, por cierto, llegaron a contabilizar totales negativos para el candidato demócrata Al Gore en algunos colegios de Florida (recomiendo a este respecto un documental, titulado "Hacking democracy", en el que además de comentar ésto demuestran la facilidad con la que se pueden manipular dichas máquinas).

Bueno lo dejamos aquí por hoy, que es nochebuena y tampoco quiero saturar.

Navidades

No sé quien inventaría esto de las navidades, pero estoy hasta las narices desde el primer día que vi las lucecitas colocadas en un centro comercial, allá por el mes de noviembre. Tengo poco aguante. A ver si hay suerte y el año que viene las navidades no caen en estas fechas, porque me viene fatal.

Además, el robin hood invertido que es esto de la lotería no se ha dignado a visitarme (a visitarme hoy, porque cuando vino a recaudar si que lo hizo).

El cifrado polialfabético Vigenère

Ahora me gustaría escribir una serie de posts con los que espero que disfruteis tanto como yo lo hice en su momento. En este explicaré el cifrado polialfabético, en el siguiente explicaré una técnica de criptoanálisis para este tipo de cifrados (vereis lo tremendamente divertido que es romper un texto cifrado). Del tercero aún no diré nada. Con esto dejaremos atrás mas de dos mil años de criptografía y comenzaré con cosas mas modernas.

Es curioso que hasta el siglo XVI no surgiera este cifrado, cuando no es mas que una extensión lógica del cifrado César; este hecho dice mucho sobre la sociedad europea desde la caida del imperio romano hasta ese momento.

La diferencia principal con el método César radica en que si antes utilizábamos un desplazamiento igual para todos los caracteres del mensaje, en este nuevo método utilizaremos uno distinto para cada carácter en función de la clave. Dicha clave además adquiere una longitud arbitraria en lugar de ser de longitud uno exclusivamente. Un ejemplo:

Mensaje: "a la de tres atacamos"
Clave: "bletchley"

Pues bien, para cifrar este texto hacemos lo siguiente: para la 'a' utilizamos el alfabeto indicado por la letra 'b' de la clave, para la 'l' el indicado por la 'l' de la clave... Cuando nuestra clave se agote (al cifrar la 's' con el alfabeto de la 'y') volvemos a empezar la clave (cifrando la 'a' de "atacamos" con la 'b' de la clave). Perfecto, pero nos falta saber cómo se aplica dicha clave. Es sencillo, basta con mirar en esta tabla el carácter que aparezca en la unión de la fila (o columna) del del texto en claro con la columna (o fila) del correspondiente en la clave:



El texto cifrado quedaría así:

Texto: "aladetresatacamos"
Clave: "BLETCHLEYBLETCHLE"
Criptograma: "BWEWPACIQBE..." (me da pereza seguir ^_^)

Para descifrar basta con mirar en la columna (o fila) correspondiente a la letra de la clave en qué posición aparece la letra del criptograma y ver a que fila (o columna) corresponde.

Como podeis ver, este método, como los anteriores, tan solo proporciona confidencialidad. A pesar de ésto, el cifrado de Vigenère supone un gran avance con respecto al César ya que al no conservar las frecuencias relativas de las letras el ataque no es tan trivial (de hecho se llegó a considerar como indescifrable en un principio). No obstante, se puede atacar también mediante métodos estadísticos. Pero eso es otra historia y debe ser contada en otra ocasión (en el siguiente post).

NOTA: La imágen está sacada de la wikipedia.

El cifrado César

Aunque es conocido por el nombre del famoso Julio César se sospecha que en realidad no fué utilizado por él, aunque si por otros emperadores menos famosos.

La mecánica del método es muy sencilla. Tan simple como ir cogiendo uno a uno los caracteres del mensaje e irlos sustituyendo por el que corresponda a un desplazamiento determinado. Es decir, miramos la posición que ocupa dicho carácter en el alfabeto, le sumamos el desplazamiento y escribimos el carácter que se encuentra en la posición resultante. Evidentemente esto lo hacemos de manera circular, es decir, si tenemos un alfabeto de 27 letras y la suma de la posición mas el desplazamiento es, por ejemplo, 28, corresponderá a la letra en posición 1.

Un ejemplo:

Alfabeto: abcdefghijklmnñopqrstuvwxyz
Clave: 2
Mensaje: "bletchley park es un blog muy chulo"
Criptograma: "DNGVEJNGARCTMGUWODNQIÑWAEJWNQ"

Para descifrar el mensaje basta con conocer la clave ("2") y hacer el proceso inverso: restar la clave a cada carácter.

Mensaje descifrado: "bletchleyparkesunblogmuychulo"

Como podeis ver, también es un método tremendamente sencillo (y poco seguro), pero al contrario que el método de la escitala espartana, que era de trasposición, este es un método de sustitución. Y en relación a esto os hago una pregunta:
Si interceptais a un mensajero con un criptograma, ¿cómo podríais saber si está cifrado con cifrado César o con el método de la escitala espartana? De manera mas general: ¿cómo reconoceríais la diferencia entre un texto cifrado por un método de trasposición y por otro de sustitución? No hace falta utilizar métodos de CSI para saberlo... ni tampoco hace falta ser violentos con el mensajero.

Funcionalidades

Hasta el momento no he planteado este problema: ¿qué podemos pedirle a la criptografía? Me explico: hasta ahora sólo he hablado de que la criptografía permitía el envio de mensajes de manera que unicamente un destinatario legítimo pueda leer el conenido. Esto se conoce como confidencialidad, y obviamente es el primer objetivo que queremos conseguir.

Pero también hay otras cosas importantes cuando hablamos de enviar mensajes. Por ejemplo, mirando el método anterior (la escitala espartana) vemos claramente que proporciona confidencialidad (de una manera mas o menos fiable). Pero si nos ponemos en el lado del receptor del mensaje ¿estamos seguros de quien nos envia el mensaje? Si un adversario intercepta al mensajero y, de alguna forma, consigue descubrir el método de cifrado y el grosor del bastón (la clave), bien puede enviarnos otro mensaje haciéndose pasar por nuestro amigo. En ese caso no hay forma de saber que estamos siendo engañados. Esto es porque el método no ofrece autenticidad.

Pero no nos vayamos tan lejos. Imaginad que quien ha interceptado el mensaje no ha sido capaz de saber cual es el método ni la clave. Al menos puede coger el mensaje y cortarle un trozo asegurándose de que lo que nos va a llegar es algo incomprensible. Como destinatarios no tendríamos forma de saberlo. El método tampoco asegura integridad en los mensajes.

Ahora poneos en la situación en la que ni siquiera nos han interceptado al mensajero. Nuestro colega militar ha decidido hacer un movimiento que no es muy inteligente, pero como tenemos un rango inferior tenemos que hacerle caso (ya sabeis como son los militares: si no lo hacemos aparecerá algún héroe y dirá eso de: "señor, queda usted relevado del mando de esta unidad" y no podremos hacer nada por mucho que gritemos eso de "¡ya nos veremos en su consejo de guerra!"). Cuando vayamos a rendir cuentas a nuestra ciudad y nos quieran cargar con la responsabilidad podríamos decir que el fallo ha sido suyo... pero no sería muy inteligente ya que él puede argumentar que el mensaje que hemos recibido no ha sido escrito por él sino por el enemigo (utilizando la misma clave). Y lo que es peor: en realidad no podemos saber si esto es cierto o no. El método no ofrece la funcionalidad de "no repudio" (que se conseguiría firmando de alguna manera el mensaje).


Pero hay otra cosa mas que el método no nos ofrece (y realmente es difícil de ofrecer en cualquier caso) y es la disponibilidad de la información (los escasos comentarios de la anterior entrada proponían métodos de ataque sobre esta funcionalidad). Es muy fácil capturar a los mensajeros y, aunque no descifremos el mensaje ni simulemos ser el origen autorizado, siempre podemos matarlos y quemar el mensaje, haciendo que no esté disponible para el destino legítimo (es uno de los famosos ataques por denegación de servicio).

La escitala espartana

Dejamos de momento mas conceptos que tengo que explicar y paso a contar una técnica muy primitiva de enviar mensajes secretos, conocida como la escitala espartana. El orginen parece que se remonta al año 400 antes de Cristo en la antigua Grecia y fue inventado, o al menos utilizado de manera regular, por los ejércitos espartanos.

Es un método de transposición. Esto quiere decir que el algoritmo de cifrado no sustituye letras o conjuntos de letras por otras sino que "baraja" el mensaje para hacerlo irreconocible.

¿Y cómo consiguen hacerlo? Imaginad una vara sobre la que enrollais una cinta de papel. Si el mensaje se escribe longitudinalmente, y teniendo la precaución de escribir un solo carácter por línea, quedará desordenado sobre la cinta de papel. Si el mensajero es interceptado sólo encontrarán una cinta de papel con caracteres que no tienen ningún sentido. Para recuperar el mensaje basta con tener un bastón del mismo diámetro.

Vale, ahora me pregunto: ¿qué ofrecía este método a los militares griegos? Pues ofrecía cierta confidencialidad en el envío de mensajes. ¿Pero en qué se basaba dicha confidencialidad? Pues en realidad en el conocimiento del grosor del bastón.

Y ahora una pregunta que dejo al aire: si soy de un ejército rival e intercepto un mensajero ¿qué puedo hacer con el criptograma en mis manos?

Susto

¡Qué susto me ha dado el 20 minutos! Pensé que nos habíamos sin un gran actor...



Resulta que quien ha muerto es su mascota...

Actualización: Joder, sigo leyendo la noticia y me encuentro esta otra perla al final:

El animal no será sustituido por otro ejemplar de la raza porcina ya que, según ha manifestado el actor, "¡Max cubrió todas mis necesidades de cerdo para siempre !".

No quiero leer mas sobre este asunto...

Una pequeña reflexión

Con la reelección de Hugo Chavez en Venezuela (aplastante y con unas elecciones con observadores internacionales, no como en EEUU o en Méjico) y el cambio en Ecuador no puedo evitar pensar sobre el giro a la izquierda que se está llevando a cabo en sudamérica desde hace unos años (Brasil, Bolivia, Ecuador...). ¿Tendrá algo que ver que George W. Bush tenga su mirada (y sus recursos) estrictamente en oriente próximo?

Yo lo veo bastante claro, pero es tan solo una opinión.