Cita

"Those who are willing to pay a penny of security for a penny of usability will eventually have neither"

14 enero 2015

Resolviendo un enigma



... o, al menos, intentándolo.

Durante las vacaciones, ElevenPaths presentó un reto criptológico con premio. Como desde que realicé el estupendo Curso de Especialidades Criptológicas del CCN, soy una aficionada a la materia, me puse a ello. La verdad es que lo resolví a medias. Y, en todo caso, no a tiempo. No obstante, me parece interesante compartir el proceso que seguí: sirve para repasar algunas ideas de criptología y, para los legos en la materia, quizá para aproximarse a ella.

El criptograma consistía en un gif animado, con el siguiente texto:

C1UQTMO6GZ

Al principio no dieron ninguna pista y, viendo que ninguna letra se repetía, pensé que en el texto original tampoco habría letras repetidas. Esto, claro está, si se tratara de un cifrado de sustitución monoalfabética, en el cual cada símbolo del texto en claro, se corresponde siempre con el mismo símbolo en texto cifrado, en una relación biunívoca. Un ejemplo de este tipo de cifrado es el de César (sí, por Julio César, que ya lo usaba), en el que cada letra se sustituye por la que ocupa un número dado de desplazamientos en el alfabeto (normalmente 3), siendo este número la clave del criptograma. Estaba claro que, en este caso no se estaba utilizado dicho algoritmo (si no, podéis probar a sustituir la C por la Z, la U por la R, etc. y veréis que no sale nada coherente). Pero, como no tenía mucho tiempo y está aferrada a la hipótesis del monoalfabeto, pensé que, fuera cual fuera el algoritmo, debía buscar un texto en el que los símbolos no se repitieran, que incluyera números y letras y que tuviera algo que ver con las fechas en las que estábamos (en criptología, la imaginación también vale); así es que me dije: "FELIZ 2015". ¿Verdad que es genial? Pues no, no era eso.

Parece ser que nadie pudo resolverlo, porque prorrogaron la fecha de la solución y ofrecieron una pista. Y aquí es donde llegamos a otro punto importante en criptología: para romper un criptograma siempre necesitamos "algo" (una pista sobre el algoritmo, un trozo de algo cifrado cuyo claro conozcamos, alguna idea sobre alguna palabra que pueda incluir el texto original, el contexto en el que se usa...). No se puede criptoanalizar un texto sin tener absolutamente ni idea de qué va la cosa. Si leéis "La isla del tesoro" o veis "The imitation game", comprenderéis mejor lo que digo.


La pista que dieron fue "Vigenere protege tus dulces". Y ahí ya tenemos dos: el algoritmo utilizado (Vigenère) y "algo" sobre el texto cifrado (está en plural y tiene que ver con los dulces).

El de Vigenère es un cifrado de sustitución polialfabética, en el que un misma letra del claro no siempre devuelve la misma letra en el cripto y que utiliza una tabla como la siguiente:

(fuente: wikipedia)
Las letras de las columnas, arriba, corresponden con las del texto en claro y las de las filas, a la izquierda, con las de la clave. La clave se pone debajo del claro, repitiéndose si fuera necesario por ser más corta que éste. Así pues, si en nuestro claro tenemos una M y la letra de clave que hay debajo es una K, tendremos que buscar la intersección entre la columna M y la fila K, que vemos que es una W. 

Para descifrar hacemos al revés: conociendo la clave, buscamos en la fila de la letra correspondiente (en este caso, la de la K) dónde está la letra del cripto (la W) y subimos para arriba en esa columna, para ver qué letra del claro es (la M). 

Otra manera de ver esto es pensar que Vigenère es un César mejorado en el que el desplazamiento no es fijo, sino que para cada letra del claro viene marcado por la letra de la clave que está debajo. En el ejemplo anterior, la K indica que hay que sumar 10 a la posición de la letra M, lo que nos da la W. Y para descifrar, restamos.

Pero claro, descifrar presupone que conocemos la clave. Sin embargo, nosotros estamos criptoanalizando, que es un poquito más difícil porque somos el enemigo (o el participante del concurso) y no sabemos la clave. ¿Cómo hacemos entonces?

Vigenère presumía de que su cifrado era irrompible y, por mucho tiempo, se creyó así. Pero al final se demostró que si el texto era lo suficientemente largo, las frecuencias acababan repitiéndose, lo que hacía posible su criptonálisis. Sin embargo, éste no es el caso del cripto que nos ocupa, que solo tiene diez letras. En este caso, hay que utilizar el método de la palabra probable. Este método consiste en imaginar una posible palabra que pueda aparecer en el texto claro, colocarla bajo el cripto y, a partir de ahí sacar la clave de manera natural, restando las posiciones de desplazamiento en el alfabeto. Como se supone que clave es una palabra de diccionario, si lo que obtenemos no tiene sentido, desplazamos la palabra bajo el cripto y volvemos a hacer lo mismo, hasta que aparezca algo coherente.

¿Qué palabra probable tenemos en el cripto de ElevenPaths? Pues bien, sabemos que tiene que ver con dulces; así es que una posibilidad es ir probando con todos los que se nos ocurran (mazapanes, chocolates...). Pero además sabemos algo interesante: según la pista que nos dieron, está en plural. Así es que, probablemente, termine en "es". Pues lo que hice fue, en vez de ir probando distintas palabras, colocar ES debajo de GZ, a ver qué daba. Y entonces vi la luz.


Si lo hacéis, con el método explicado anteriormente, veréis que el resultado es CH. Y, rápidamente, recordé una palabra que tiene mucho que ver con ElevenPaths: Latch. Usando Latch como clave repetida dos veces bajo el cripto quise descifrarlo utilizando la tabla anterior. Pero me tropecé con un escollo: el Vigenère clásico no tiene números. ¿Cómo es que en el cripto aparecían? Aquí es donde me obcequé un poquillo, pensando que los números tenían que ser en realidad letras: el 6 la G y el 1 la I; y, al descifrarlo obtuve algo como "RIBOMBONES" y deduje que las dos primeras letras eran tan solo "ruido" que se habían añadido al texto para aumentar la dificultad del criptoanálisis y que había simplemente que prescindir de ellas. En vez de darme cuenta de que bastaba con ampliar el alfabeto, colocando las cifras del 0 al 9 a continuación de la Z, tal y como explicaron en la solución del blog, lo que daba como resultado "11BOMBONES" y que era precisamente el premio: una caja con 11 bombones.

De todos modos, aunque lo hubiera resuelto completamente bien, no me hubiera servido: para cuando yo mandé el correo varias personas ya se me habían adelantado con la solución correcta. Y es que, como bien sabía el equipo de criptólogos que trabajaba a contrarreloj en  Bletchley Park, no basta con resolver un enigma: hay, además, que hacerlo a tiempo.

                      

Espero que hayáis disfrutado del ejercicio tanto como yo y que os haya picado la curiosidad por este mundillo tan interesante como es el de la criptología. Solo me queda dar las gracias a ElevenPaths por este delicioso entretenimiento y a Ángel Goitia la enhorabuena por el premio.


3 comentarios:

  1. Excelente, no me meto en Criptografia pero esta lectura me pareció muy enriquecedora y el proceso de resolución es bastante ordenado y lógico. Enhorabuena. Saludos.

    ResponderEliminar
  2. Sas, estaré siguiendo tu blog, la he agregado a mi blogroll.

    ResponderEliminar

A penny for your thoughts