Criptoanálisis de un Cifrador de Sustitución Monoalfabética utilizando Colonias de Hormigas

”Criptoan´alisis de un Cifrador de Sustituci´on Monoalfab´etica utilizando Colonias de Hormigas” Pablo Itaim Ananias Valpara´ıso, 19 de Diciembre del 2005 Resumen El presente trabajo describe una implementaci´ on de un algoritmo de Colonias de Hormigas para el Ataque a un Cifrador de Sustituci´ on Monoalfab´etica.

1.

Introducci´ on

El ser humano siempre ha tenido secretos de muy diversa ´ındole, y ha buscado mecanismos para mantenerlos fuera del alcance de miradas indiscretas. Julio C´esar empleaba un sencillo algoritmo para evitar que sus comunicaciones militares fueran interceptadas. Leonardo Da Vinci escrib´ıa las anotaciones sobre sus trabajos de derecha a izquierda y con la mano zurda. Otros personajes, como Sir Francis Bacon o Edgar Allan Poe eran conocidos por su afici´ on a los c´odigos criptogr´aficos, que en muchas ocasiones constitu´ıan un apasionante reto para el ingenio. Por su parte, se conocen como ”cl´ asicos” a todos los sistemas de cifrado anteriores a la II Guerra Mundial, o lo que es lo mismo, al nacimiento de las computadoras. Estas t´ecnicas tienen en com´ un que trabajan con las letras del alfabeto y pueden ser empleadas usando simplemente l´apiz y papel, y que pueden ser criptoanalizadas casi de la misma forma. De hecho, con la ayuda de las computadoras, los mensajes cifrados empleando estos c´ odigos son f´ acilmente descifrables, por lo que cayeron r´apidamente en desuso. La transici´on desde la Criptograf´ıa cl´ asica a la moderna se da precisamente durante la II Guerra Mundial, cuando el Servicio de Inteligencia aliado rompe la m´ aquina de cifrado del ej´ercito alem´an, llamada ENIGMA. Sin embargo, lo anterior no significa que estos algoritmos no sean de importancia para la Criptolog´ıa. Al contrario, su importancia radica en el hecho que la mayor´ıa de los algoritmos de cifrado de uso com´ un hoy en d´ıa utilizan operaciones de cifradores cl´asicos para la construcci´on de sus bloques. Por ejemplo, el Data Encryption Standard (DES)[1], utiliza tres operadores simples llamados sustituci´on, permutaci´on (transposici´on) y XOR. Dada su simplicidad y del hecho de que son utilizados para la construcci´on de cifradores m´as modernos, los cifradores cl´ asicos son los primeros en ser considerados a la hora de estudiar nuevas t´ecnicas de ataque como la que se va a discutir en el presente trabajo. Existen varios tipos de cifradores cl´ asicos, sin embargo, la mayor´ıa cae en alguna de las siguientes categor´ıas: cifradores o algoritmos de sustituci´ on o de transposici´on. En este trabajo se desarrolla una implementaci´on de un algoritmo de colonias de hormigas [2] que permite efectuar un ataque autom´ atico del algoritmo cl´asico de sustituci´on Monoalfab´etica que se describe en la secci´on 2.3. En la literatura existen pocos trabajos que traten el uso de algoritmos de optimizaci´on y metaheur´ıstica para el ataque autom´ atico de sistemas cl´asicos. En [3], Clark y Dawson implementaron tres algoritmos, basados en Simulated Annealing, Algoritmos Gen´eticos y Tabu Search respectivamente, para efectuar un ataque autom´ atico sobre un algoritmo cl´ asico de sustituci´on. El el trabajo, efectuaron una comparaci´on entre los tres algoritmos, resultando el Tabu Search el m´as eficiente, al considerar una menor cantidad de claves para encontrar la clave correcta y as´ı poder descifrar el mensaje. Por otro lado, Russell, Clark y Stepney [4, 5], utilizan una mezcla de Colonias de Hormigas con Multiple anagramming para atacar un algoritmo cl´asico de transposici´on. El resultado fue exitoso, destac´andose el hecho de ser la primera aproximaci´ on de Colonias de Hormigas en el Criptoan´alisis [5]. Si consideramos que ese desarrollo fue sobre cifradores cl´ asicos de transposici´on, podr´ıamos decir que el presente trabajo es la primera aproximaci´ on de colonias de hormigas para el ataque autom´atico de cifradores cl´asicos de sustituci´on. Para una mejor lectura, el presente trabajo se ha organizado de la siguiente manera: en la secci´on 2, se define el problema a resolver y el algoritmo a utilizar. En la secci´on 3, se describen los sistemas de Colonia

de Hormigas. La descripci´ on de la implementaci´on realizada se presenta en el punto 5 y sus resultados se analizan en el punto 5. Finalmente, en el punto 6 se indican las conclusiones m´as importantes.

2.

Definici´ on del Problema

Para entender bien el problema que se pretende resolver, comenzaremos describiendo el sistema de cifrado que se pretende atacar y la forma convencional de ataque.

2.1.

Cifrados Monoalfab´ eticos

Pertenecen a este tipo de sistemas todos los algoritmos criptogr´aficos que, sin desordenar los s´ımbolos dentro del mensaje, establecen una correspondencia u ´nica para todos ellos en todo el texto. Es decir, si al s´ımbolo A le corresponde el s´ımbolo D, esta correspondencia se mantiene a lo largo de todo el mensaje. Por ejemplo, el algoritmo de C´esar, llamado as´ı porque es el que empleaba Julio C´esar para enviar mensajes secretos, es uno de los algoritmos criptogr´aficos m´as simples. Consiste en sumar 3 al n´ umero de orden de cada letra. De esta forma a la A le corresponde la D, a la B la E, y as´ı sucesivamente. Si asignamos a cada letra un n´ umero (A = 0, B = 1, . . .), y consideramos un alfabeto de 26 letras, la transformaci´on criptogr´afica ser´ıa: C = (M + 3) mod 26. Obs´ervese que este algoritmo ni siquiera posee clave, puesto que la transformaci´on siempre es la misma. Obviamente, para descifrar basta con restar 3 al n´ umero de orden de las letras del criptograma. Sin embargo, en el caso m´ as general de cifrado monoalfab´etico, la sustituci´on es arbitraria, siendo la clave k precisamente la tabla de sustituci´ on de un s´ımbolo por otro. En este caso tenemos N ! posibles claves.

2.2.

Criptoan´ alisis

El cifrado monoalfab´etico constituye la familia de m´etodos m´as simple de criptoanalizar, puesto que las propiedades estad´ısticas del texto claro se conservan en el criptograma. Supongamos que, por ejemplo, la letra que m´as aparece en Castellano es la A. Parece l´ogico que la letra m´as frecuente en el texto cifrado sea aquella que corresponde con la A. Relacionando las frecuencias relativas de aparici´on de cada s´ımbolo en el mensaje cifrado con el histograma de frecuencias del idioma en el que se supone est´a el texto claro, podremos averiguar la clave. Adem´as de relacionar las frecuencias de los s´ımbolos, se relacionan las frecuencias de aparici´on de los bigramas y trigramas. Con ello se puede ir afinando la equivalencia de letras, sobre todo en aquellas que tienen baja frecuencia de aparici´ on.

2.3.

Algoritmo de Cifrado utilizado

Como ya se ha mencionado, para el presente trabajo se utiliz´o un algoritmo cl´asico de sustituci´on monoalfab´etica. La relaci´ on entre las letras del alfabeto claro con las del cifrado se gener´o en forma aleatoria por medio de una permutaci´ on del alfabeto con 27 caracteres (considerando el espacio). Con esto se busc´o darle un poco m´as de complejidad al cifrado, ya que en el peor de los casos habr´ıa que revisar las 27! claves posibles. As´ı, el algoritmo de cifrado genera una permutaci´on del alfabeto al azar y luego reemplaza los caracteres claros por los correspondientes cifrados.

3.

Los Sistemas de Colonias de Hormigas (ACS)

Los algoritmos ACS (Ant Colony System) son modelos inspirados en el comportamiento de colonias de hormigas reales. Estudios realizados explican c´omo animales casi ciegos, como son las hormigas, son capaces de seguir la ruta m´ as corta en su camino de ida y vuelta entre la colonia y una fuente de abastecimiento. Esto es debido a que las hormigas pueden ”transmitirse informaci´on” entre ellas gracias a que cada una de ellas, al desplazarse, va dejando un rastro de una sustancia llamada feromona a lo largo del camino seguido. As´ı, mientras una hormiga aislada se mueve de forma esencialmente aleatoria, los ”agentes” de una colonia de ´ hormigas detectan el rastro de feromona dejado por otras hormigas y tienden a seguir dicho rastro. Estas a su vez van dejando su propia feromona a lo largo del camino recorrido y por tanto lo hacen m´as atractivo, puesto que se ha reforzado el rastro de feromona. Sin embargo, la feromona tambi´en se va evaporando con el paso 2

del tiempo provocando que el rastro de feromona sufra, por otro lado, cierto debilitamiento. En definitiva, puede decirse que el proceso se caracteriza por una retroalimentaci´on positiva, en la que la probabilidad con la que una hormiga escoge un camino aumenta con el n´ umero de hormigas que previamente hayan elegido el mismo camino. El primer algoritmo basado en la optimizaci´on mediante colonias de hormigas fue aplicado al Problema del Vendedor Viajero (o TSP) [2], obteni´endose unos resultados bastante alentadores. A partir de dicho algoritmo se han desarrollado diversas heur´ısticas que incluyen varias mejoras, y han sido aplicados no solo al TSP sino tambi´en a problemas como el Problema de enrutamiento de Veh´ıculos (o VRP), entre otros. Los algoritmos ACS son procesos iterativos. En cada iteraci´on se ”lanza” una colonia de m hormigas y cada una de las hormigas de la colonia construye una soluci´on al problema. Las hormigas construyen las soluciones de manera probabil´ıstica, gui´ andose por un rastro de feromona artificial y por una informaci´on calculada a priori de manera heur´ıstica. La regla probabil´ıstica para el caso del TSP es: [τij (t)]α [ηij ]β α β h∈J k [τih (t)] [ηih ]

Pijk (t) = P

j ∈ Nik

(1)

i

donde Pijk (t) es la probabilidad con la que, en una iteraci´on t del algoritmo, la hormiga k, situada actualmente en la ciudad i, elige a la ciudad j como pr´oxima parada. Nik es el conjunto de ciudades no visitadas todav´ıa por la hormiga k. τij (t) es la cantidad de feromona acumulada sobre el arco (i, j) en la iteraci´on t. ηij es la informaci´ on heur´ıstica para la que, en el caso del TSP, se utiliza la inversa de la distancia existente entre las ciudades i y j. α y β son dos par´ametros del algoritmo, los cuales hay que ajustar. Cuando todas las hormigas han construido una soluci´on debe actualizarse la feromona en cada arco. La f´ormula a seguir es: τij (t) = (1 − ρ)τij (t) + ρ∆τij (t) (2) donde ∆τij (t) = L1+ . ρ es el coeficiente de evaporaci´ on de la feromona. L+ es el largo de la mejor soluci´on encontrada. Tras la actualizaci´on de la feromona puede comenzarse una nueva iteraci´on. El resultado final es la mejor soluci´on encontrada a lo largo de todas las iteraciones realizadas.

4.

Descripci´ on del Ataque

La t´ecnica natural para comparar claves candidatas de los cifradores de sustituci´on monoalfab´etica es ir comparando las estad´ısticas de los n−gramas de los mensajes descifrados con aquellas del lenguaje claro. La ecuaci´on (3), es una f´ ormula general utilizada para determinar la calidad de una clave propuesta (k) para un cifrador de sustituci´ on. En ella, A corresponde al alfabeto del lenguaje {A, B, . . ., Z, }, donde representa el s´ımbolo espacio. K y D corresponden las estad´ısticas del lenguaje claro (conocido) y mensaje cifrado respectivamente. Los ´ındices u, b y t corresponden a la estad´ıstica de los unigramas, bigramas y trigramas respectivamente. Los valores de α, β y γ permiten asignarle distintos pesos a cada uno de los tipos de n−gramas. X X X u u b b t t Ck = α ∗ − D(i) − D(ij) − D(ijk) (3) K(i) +β∗ K(ij) +γ∗ K(ijk) i∈A

i,j∈A

i,j,k∈A

Del trabajo de Clark y Dawson [3] se desprende que si se consideran las estad´ısticas de los unigramas y de los bigramas, la de los trigramas no producen un aumento significativo en la eficiencia del algoritmo. Dado lo anterior, para el desarrollo del presente trabajo se utilizaron los siguientes valores para las variables de peso: α = 1, β = 1 y γ = 0. El algoritmo se inicia determinando la estad´ıstica del lenguaje desde un archivo patr´on. El archivo debe ser un texto lo suficientemente largo como para determinar de buena forma la estad´ıstica y estar escrito en el mismo idioma del texto cifrado. Si se cuenta con la informaci´on, el texto patr´on debe tratar del mismo tema que el texto cifrado. Con esto se aumenta la probabilidad de encontrar la clave en menos tiempo. En este punto se tiene la frecuencia de aparici´on de unigramas y bigramas en el texto claro. A continuaci´on, se determina la estad´ıstica del lenguaje en el mensaje cifrado. Con esos datos se inicia el algoritmo de hormigas cuyo pseudoc´odigo se muestra a continuaci´on: procedimiento hormigas Inicializar 3

Para cada asociaci´ on (i, j) hacer τij (0) = τ0 fin para Para k = 1 hasta m hacer Ubicar la hormiga k en una letra del alfabeto cifrado elegida aleatoriamente fin para Sea mejor clave[] la clave candidata con la mejor calidad y lmin su calidad Para t = 1 hasta el numero de ciclos haga Inicio Para k = 1 hasta m haga Inicio Repetir seleccionar la mejor relaci´ on letra clara-letra cifrada hasta hormiga k complete su tour (hasta que la hormiga genere la clave candidata) calcular la calidad de la clave candidata generada por la hormiga k Fin Para Guardar la mejor clave candidata encontrada hasta el momento y su calidad actualizar los niveles de feromona τij Fin Para formar la clave candidata, cada hormiga comienza de una letra del alfabeto cifrado tomada al azar y busca la letra del texto claro que m´ as cercana este en frecuencia de aparici´on. A continuaci´on, se verifican las frecuencias de bigramas que comiencen o terminen con la letra en cuesti´on buscando la misma relaci´on. Una vez determinada la letra con la cual tiene mayor afinidad, esta asociaci´on se registra como parte de la clave candidata. Una vez que todas las hormigas completaron su tour, se calcula la calidad de las distintas claves candidatas utilizando la ecuaci´ on (3). Con esto, se determina la mejor clave candidata de la ronda y se compara con la mejor clave candidata almacenada. Si existe una clave candidata con mejor calidad que la almacenada, se actualiza y se modifican los niveles de feromona, los cuales asocian una letra cifrada con una determinada posici´on dentro del vector de clave candidata lo que se corresponde con una determinada letra clara.

5.

Resultados experimentales

El algoritmo descrito en el punto anterior fue implementado en lenguaje C y ejecutado en un computador con procesador AMD Mobile Sempron 3000, con 512 MB en RAM con lo cual se lograron tiempos de ejecuci´on menores a los 15 segundos para el peor de los casos. Respecto a los par´ ametros del Algoritmo, el factor de evaporaci´on de feromona se fij´o en 0.5, el cual es el valor m´as usado en las implementaciones de este tipo de algoritmos. Asimismo, se utilizaron 27 hormigas (una por cada s´ımbolo del alfabeto) y 70 iteraciones del algoritmo. Cabe se˜ nalar que se utilizaron textos de distinto largo y cifrados con claves generadas al azar, adem´as de dos textos utilizados como patr´on, los que ten´ıan un largo de 500,000 caracteres cada uno y de los cuales uno coincid´ıa en el tema de los textos cifrados y el otro no. Para cada texto cifrado se efectuaron 20 ejecuciones del algoritmo quedando registrada la cual con la que se obtuvo el mejor resultado. Esto se muestra en la Tabla 1 y en el Gr´afico 1. Se puede observar que en aquellas ejecuciones en las cuales el Tema del Texto patr´on coincid´ıa con el tema del texto cifrado, la calidad de la soluci´ on fue notablemente superior, logrando generar la clave utilizada con textos cifrados m´as peque˜ nos.

Tema textos Temas Coinciden Temas no Coinciden

500 11 2

700 13 2

900 15 2

Largo del Texto Cifrado 1000 1500 2000 5000 17 21 25 27 2 4 17 19

10000 27 23

20000 27 25

50000 27 27

Cuadro 1: Calidad de la soluci´ on dependiendo del Largo del Texto cifrado y de la relaci´on existente entre los textos

4

Figura 1: Comparaci´on de la calidad de las soluciones De los resultados expuestos anteriormente se comprueba que se puede implementar un ataque autom´atico exitoso sobre cifradores cl´ asicos de sustituci´on monoalfab´etica utilizando colonias de hormigas. Los resultados se mejoran si se conoce el tema de que trata el texto que esta cifrado y ´este tiene una longitud adecuada. Por otra parte, dado que no se cuenta con los benchmarks utilizados por [3, 4, 5], los resultados de este trabajo no son comparables a los presentados por los mencionados autores.

6.

Conclusiones y posibles mejoras

En el presente trabajo se logr´ o implementar un ataque autom´atico exitoso sobre cifradores cl´asicos de sustituci´on monoalfab´etica utilizando colonias de hormigas. Inicialmente se discuti´o respecto a las propiedades que hacen que dichos algoritmos sean vulnerables siendo la principal el hecho de que ning´ un algoritmo de este tipo es lo suficientemente sofisticado como para esconder la estad´ıstica del lenguaje claro. Una posible mejora del algoritmo presentado seria estudiar la factibilidad de automatizar el control de par´ametros del algoritmo con el objeto que, a medida que va iterando y obteniendo resultados, el algoritmo se ajuste de mejor manera para obtener mejore resultados y en menos tiempo.

Referencias [1] U.S. Department of Commerce/National Bureau of Standards. Data encryption standard. Federal Information Processing Standards, 46(1), Enero 1988. [2] Marco Dorigo and Luca Maria Gambardella. Ant colony system: A cooperative learning approach to the traveling salesman problem. 1(1):53–66, April 1997. [3] Andrew Clark and Ed Dawson. Optimisation heuristics for the automated cryptanalysis of classical ciphers. J. Combin. Math. Combin. Comput., 28:63–86, 1998. Papers in honour of Anne Penfold Street.

5

[4] Matthew Russell, John A. Clark, and Susan Stepney. Using ants to attack a classical cipher. In E. Cant´ uPaz, J. A. Foster, K. Deb, L. D. Davis, R. Roy, U.-M. O’Reilly, H.-G. Beyer, R. Standish, G. Kendall, S. Wilson, M. Harman, J. Wegener, D. Dasgupta, M. A. Potter, A. C. Schultz, K. A. Dowsland, N. Jonoska, and J. Miller, editors, Genetic and Evolutionary Computation Conference: GECCO 2003, Chicago, USA, July 2003, number 2723 in LNCS, pages 146–147. Springer, 2003. poster paper. [5] Matthew D. Russell, John A. Clark, and Susan Stepney. Making the most of two heuristics: Breaking transposition ciphers with ants. In CEC 2003: International Conference on Evolutionary Computation, Canberra, Australia, December 2003, pages 2653–2658. IEEE, 2003.

6