21 oct 2017

Desmitificando Enigma


Hace dos semanas, escribí sobre cómo funcionaba la archiconocida Enigma I e hice una breve reseña de su historia. No entré a narrar la hazaña de descifrarla llevada a cabo por polacos e ingleses, pero una serie de comentarios en la página de mi entrada en Menéame me hicieron plantearme escribir sobre el impacto de Marian Rejewski y factores ajenos al criptoanálisis en el éxito de Turing; el grave error de pensar en la Enigma como una única máquina; su inmerecida fama de mejor máquina de cifrado de la 2ª Guerra Mundial y otros aspectos frecuentemente olvidados que pueden ayudar a desmitificarla y entenderla mejor.


La Enigma es una y trina

A pesar de que se suela hablar de la Enigma, hubo casi tantas versiones como letras del abecedario: Enigma A, B, C, D, H, I, K, M4,...

Árbol genealógico de las Enigma, hecho por Paul Reuvers y Frode Weierud y sacado del gran Cryptomuseum.com


Si mencionan la Enigma sin apellidos, probablemente se refieran a la Enigma I, la más famosa de todas por ser muy utilizada por el ejército de tierra y las fuerzas aéreas nazis. Tampoco podemos olvidarnos de la Enigma M4, adoptada en plena guerra únicamente por los submarinos nazis (U-Boots). Contaba con un rotor adicional y fue un hueso durísimo de roer para los criptoanalistas, que la llamaban Shark y no lograron ningún avance hasta que se hicieron con un libro de códigos rescatado de un U-Boot enemigo.

U-Boot usado en la 2ª Guerra Mundial, cortesía del Bundesarchiv alemán



Enigma, ¿conocida o extraña?

Muchos piensan que la máquina Enigma era una total desconocida para los criptoanalistas aliados. Ésto es parcialmente falso, ya que la Enigma llevaba rondando desde los años veinte y había sido exhibida y publicitada por su creador, por lo que su manera de funcionar era conocida por la mayoria de servicios secretos. Sin embargo, es fundamental recordar que cada Enigma es un mundo, y las particularidades de los rotores de la empleada por los nazis (desde mucho antes de la guerra) eran totalmente desconocidas, hasta que los matemáticos polacos Marian Rejewski, Jerzy Różycki y Henryk Zygalski caracterizaron el cableado interno de cada rotor en 1932, tras siete años de investigación e innovación (se considera que Rejewski fue pionero en aplicar métodos de matemática pura, principalmente teoría de grupos, para resolver un cifrado).


Apología de un polaco

Los polacos recuerdan a los soviéticos en esta historia: mientras el fundamental esfuerzo de guerra de los últimos suele ser minimizado por la historiografía mainstream, lo mismo ocurre con el mérito criptográfico de los primeros. Tanto en Descifrando Enigma como en Bletchley Park (la mansión donde trabajaban los criptoanalistas británicos, reconvertida a museo) vemos escasísimas referencias a Marian Rejewski y su equipo, que les allanaron enormemente el camino proporcionándoles una descripción exacta de la Enigma I, el método combinatorio básico para descifrarla e incluso prototipos de los famosos dispositivos que tanto ayudaron en Bletchley Park, conocidos como bombes (el propio nombre es de origen polaco, bomba kryptologiczna).

Alan Turing con la bombe y un eslogan que le muestra como amo absoluto del descifrado de Enigma. Su papel en la construcción de la bombe fue tan importante como el del ingeniero Harold Keen y el matemático Marian Rejewski.


Aunque voy a dejarlo aquí, estos no son todos los clichés falsos que tenemos sobre la Enigma. Nos quedaría mencionar que los estadounidenses no se quedaron de brazos cruzados y construyeron una bombe más rápida que la británica, que una Enigma sin reflector hubiera sido prácticamente indescifrable (el hecho de que una letra nunca se encripte como sí misma es la base de todos los métodos que se emplearon), que la Enigma no era la mejor cifradora de la Segunda Guerra Mundial (la máquina Lorenz era más compleja y la historia de su descifrado, mucho más mítica) y que los alemanes se equivocaron al hacer 10 cambios en el plugboard (si no sabes qué es, léete esto) y no 11, lo cual habría maximizado la potencia de la máquina.

Bombe estadounidense

Todo lo mencionado no quiere decir que Enigma no merezca su fama, es una máquina apasionante histórica y criptográficamente. Tanto que aún en este siglo seguimos descifrándola, con proyectos colaborativos como este, en el que numerosos voluntarios internacionales pusieron sus ordenadores a crackear algunos códigos pendientes de la potente Enigma M4.

Máquina Lorenz, expuesta en el National Museum of Computing en Bletchley Park. Algún día tengo ganas de hablar sobre ella.




Fuentes y lectura recomendada

The Code Book, Simon Singh

http://www.telegraph.co.uk/history/world-war-two/11231608/Breaking-the-Enigma-code-was-the-easiest-part-of-the-Nazi-puzzle.html

http://www.microsiervos.com/archivo/seguridad/m4-project.html

https://www.meneame.net/m/cultura/haz-tu-propia-maquina-enigma 

https://commons.wikimedia.org/wiki/File:Bundesarchiv_DVM_10_Bild-23-63-65,_U-Boot_U_36.jpg

https://es.wikipedia.org/wiki/Teor%C3%ADa_de_grupos

https://en.wikipedia.org/wiki/Marian_Rejewski#Solving_the_wiring

www.cryptomuseum.com/crypto/enigma/tree.htm

http://www.cryptomuseum.com/crypto/enigma/index.htm

http://www.cryptomuseum.com/crypto/enigma/i/index.htm

8 oct 2017

Haz tu propia máquina Enigma

La máquina Enigma es un hito criptográfico. Su llamativo diseño y la inevitable asociación con la Alemania nazi la dota de un halo legendario, que podría hacernos creer que su funcionamiento es hermético e incomprensible. Nada más lejos de la realidad: está basada en tres simples dispositivos (rotor, plugboard y reflector). Conociéndolos bien, podremos entenderla perfectamente e incluso construir nuestra propia Enigma.


La máquina Enigma, como Hitler, empezó a popularizarse dos décadas antes de su apoteosis en la 2ª Guerra Mundial. En 1918, el ingeniero eléctrico alemán Arthur Scherbius patentaba su invento para cifrar texto por medio de rotores al que decidió llamar αἴνιγμα (Enigma en griego). El mismo año, un soldado volvía a Munich tras firmarse el armisticio que sellaba la derrota de su país en la Gran Guerra. Sólo un lustro más tarde, nuestros dos protagonistas cobraban fama: la Enigma era presentada al público y la prensa en congresos internacionales, y el soldado se ganaba la simpatía de parte del pueblo alemán tras ser juzgado y encarcelado por liderar un intento de golpe de estado. La continuación de esta historia es bien conocida, así que nos centraremos en la del invento de Scherbius.

1937: la Enigma ya cifra las comunicaciones de otros ejércitos además del alemán, como el italiano y el bando franquista en la Guerra Civil española. Los británicos, aún sin Turing en plantilla, logran descifrar las comunicaciones de los dos últimos porque sus Enigmas no incorporan plugboard (la mayor fuente de complejidad de la máquina, que describiremos más tarde), pero no tienen la cortesía de compartir sus hallazgos con el bando republicano, que perdió sin conseguir resolver el enigma.


Pero ya vale de historia, es hora de explicar en qué consistía el artilugio. Tenía pinta de máquina de escribir moderna a la que se le ha intercambiado el soporte para papel por un conjunto de letras que parece un segundo teclado, sólo que no se pueden pulsar y se iluminan (mostrando la letra cifrada) cuando escribimos en el teclado verdadero. También se le han añadido un montón de agujeros en la parte delantera (éste es el famoso plugboard) y detrás del falso teclado, tres grandes ruedas dentadas con letras o números escritos en el borde (conocidas como rotores). Oculto, está el tercer elemento necesario para comprenderla: el reflector. No formaba parte del diseño original de Enigma, y fue incorporado posteriormente para simplificar enormemente su uso, ya que permitía cifrar y descifrar textos con la misma máquina, sin realizar ningún ajuste. Su función, como sugiere el nombre, era "reflejar" la corriente procedente del rotor izquierdo y hacerla retroceder como vemos en este fabuloso esquema hecho por MesserWoland:

La Enigma funciona por medio de simples circuitos eléctricos, así que sólo tienes que seguirle la corriente. Pulsas la A y la señal pasa por el rotor derecho, cuyo cableado interno la hace cambiar de dirección. En el ejemplo de arriba, vemos cómo el rotor derecho la desvía de la posición 1 (asociada a la letra A) a la 2 (asociada a la B). La corriente sufre otros dos desvíos en el rotor central y el izquierdo, y llega al reflector, que no es más que un "cuarto rotor" con dos peculiaridades: no rota (ahora explicaremos cómo lo hacen los otros) y su entrada y salida de corriente están conectados al mismo rotor, actuando como un espejo. La señal recorre el circuito de vuelta y se ilumina la G. Ésta es la letra A cifrada, y al introducir G en una Enigma con las claves adecuadas, la volveremos a descrifrar obteniendo la A original. A cambio de aportar versatilidad a la Enigma, el reflector es el culpable del gran talón de Aquiles de la máquina: es imposible que una letra se cifre como sí misma. Esta característica fue fundamental para que Turing y su equipo "descifraran" Enigma.

Esta disposición puede parecer suficientemente compleja, pero no lo es. Si la mantenemos constante, nuestro código será fácilmente descifrado mediante análisis de frecuencias. Pero afortunadamente, un vaso es un vaso y los rotores rotan. A un ritmo bastante regular, además: el derecho gira cada vez que pulsamos una tecla; el de enmedio cada 26 vueltas del derecho; y el izquierdo, cada 26 del de enmedio (26 no es un número mágico, es la cantidad de letras del alfabeto internacional y no, no puedes cifrar la ñ con una Enigma). La rotación hace que cambie el recorrido de cada letra que ciframos, como puedes observar en la parte inferior del esquema que acabamos de comentar.
Ya sólo nos queda hablar del plugboard. Se trata sencillamente de un conjunto de agujeros asociados a cada letra que se encuentran al final del circuito. Si conectas mediante un cable los agujeros A y B, cuando el resultado del cifrado sea una A, se iluminará la B y viceversa.

Observa cómo giran los rotores y se iluminan las letras delanteras en este gif de origen desconocido. Fíjate en que, a pesar de pulsar siempre la misma tecla, se van iluminando distintas letras.

A estas alturas de la entrada puedo confesar que el título era un pelín clickbait, pero no del todo. He "construido" (programado en Python) un modelo históricamente preciso de la más mítica de las Enigmas, la Enigma I, arquetipo de la máquina por ser la más utilizada por los nazis en la guerra y el objetivo principal del equipo de Alan Turing. La inmensa mayoría de simulaciones de la máquina que encontrarás por internet son de la Enigma I. Tenía la peculiaridad de poderse elegir tres de entre cinco rotores disponibles, multiplicando la potencia de la máquina (número de estados posibles) por diez. Este número sale de calcular las posibles combinaciones de sólo tres rotores (3!=6) y compararlas con las posibles combinaciones de tres rotores escogidos entre cinco (5!/2=60). El plugboard permitía hacer diez cambios, lo que multiplicada la complejidad de la máquina (debido a un cálculo combinatorio en el que no voy a entrar) por 26!/((26-20)!·2¹⁰·10!)=150 738 274 937 250
P

Por último, los estados posibles de los tres rotores son 26³=17 576. Multiplicando estos tres números, obtenemos la cantidad de estados posibles de la Enigma I.

Genial modelo gráfico para entender el funcionamiento interno de Enigma. Me ayudó mucho a entenderla. Pruébalo online aquí.

Antes de abandonaros a vuestra suerte con mi código (aunque no es justo decir esto, porque lo he llenado de comentarios para que sea más legible), quiero animaros a proseguir en el impulso que os trajo aquí: construir una Enigma vosotros mismos. Aunque puede ser frustrante a ratos, acaba siendo súper satisfactorio y, lo más importante, permite comprenderla muchísimo mejor que cualquier descripción que leáis, por muy divulgativa que sea. Si queréis orientaros, hay documentación de Enigmas programadas en Ruby, Java, Matlab,... e incluso tutoriales para reconstruir una Enigma física, de las de verdad.

Aquí tenéis mi modelo, que se basa en convertir los rotores, el plugboard y el reflector en listas, y las letras en números que tendrán un doble papel según la fase del cifrado: antes de pasar por el reflector, la letra n será cifrada por cada rotor como el n-ésimo elemento de la lista asociada a dicho rotor. Tras pasar por el reflector, operaremos al revés, cifrando la letra n como la posición del elemento con valor n en esa lista. Todo este trabalenguas se entiende mucho mejor en el propio código.
El giro de los rotores está implementado como sumar uno a la letra y hacer módulo 26 (tras un giro completo, hemos de volver al mismo sitio). La función toma como variables lo mismo que necesitaríamos para operar con una Enigma: las claves (rotores utilizados y posición inicial de los mismos, junto con los cambios del plugboard) y el texto a cifrar. La función devuelve el texto cifrado. He añadido como ejemplo un fragmento de una canción de Labordeta encriptado con otro modelo de la Enigma I. Se llama Banderas rotas y trata sobre derrotas. Evoca sentimientos agridulces: el descifrado de Enigma fue clave para romper banderas con esvásticas y habría sido de gran ayuda para derrotar a sus aliados españoles.

Nunca sabremos si, de habernos dado los británicos la clave de la Enigma franquista, estaríamos hoy cifrando esta canción.


Si no tienes Python, puedes ejecutar y jugar con esta función online en repl.it, eliminando la primera línea de código (sí, la codificación de caracteres sigue dándonos la lata en pleno 2017).