Decía en el post en el que formulé el enunciado del reto que el método de criptoanálisis al que me refiero en este desafío es el que se explica en el artículo 'Ciphertext-only cryptanalysis of Enigma' de James Gillogly publicado en la revista 'Cryptologia' (Octubre 1995).
El enunciado del reto es el siguiente: Otto, operador alemán de la máquina enigma en la Wehrmacht, es un tanto vago e indisciplinado, y nunca ha entendido eso de limitar la longitud de los mensajes a enviar a 300 caracteres como máximo, y tener que dividir aquellos que sean más largos en varias partes y cifrar estas últimas con claves diferentes. Piensa: "¡Menudo trabajo, lo meto todo en uno y listo!". ¿Puedes descifrar el mensaje que se proporciona como recurso asociado al reto y que Otto envió allá por 1936?
Texto cifrado:
FHJIA GXUMG LESXR QPULE ZWQYN EQXJZ OWHMO AWJRR LMKDW RKHUT OBGNG KSXXL PZQXO XBYJO QROJD TUCTJ UHMCR RBSWT QTMJM CLOCI WDMSM XKRZG VYOBL QVTRC MKCFD SOIAD LTQKM POEUF TASLK KMKAQ HHSVR RBUOR ZETBT PABYD HMFLB ECVJY BAKXV MXNWN GZDRF CCVCK PUCTZ JTLNB BYJQX CSDYY SLSMV JSUOU NYWVU XNJQP UIDBC IWYEE IZMHC RCETL HQJDQ ERURL LXPCB KWKAB UBPZY VAULX SXTFM SWICC EGPYK YXMLT VGTJT IXBIZ ATYHD XEBCK UHMOH CQSMY WZPWB XIIRX XFQSN JACRD HFSUA CULFX HMGCU KISAE ULIRP AXMYL SPWDL CSYHJ RPYZT EOEPV WJBZG YHOEF ANCBA BDBYS ZIMGF YSLIP SAHRS ONJBH VWGOE DXCOM DJATM OUTKC JCYVR CDKRG ZINVE JHBMU AKGCG XOYRB UGOCD AEXIY FIPGO IIQNW FKASI PHHBF UFSGV AYDGI TJZJW WXZLC TFHKB VSVBI FRVMY WAFMO NIQNS NSIOC TCGQI RCQXU RHNAT HCOGU IHLHR KRCGY BLOMA QWTAO XRLXC MXMLS KYPLK NXJBG CMNVT CAQFS CAINE ZMERE PZQWI DYPBO JGRMT LVJLG MJAUF XSHSA UKJKA IJDTV DLZXX QEEUB ITLUY ZRBKG ELHPE ULPUR GHXCC KGPHK SROIN GBVOR FBKDB VLGGL JWDRJ FWYNZ XKUIQ AMQSI VNOSK QIELK MUOLM QHWQT QFXFJ VKSPX HGHEV AIYBG JRYTO ACQVE SZXPL QOBUO QXKKT RWZLB MCHXJ VMHKU KOBUN AYIFD LTHYY SQNWV COMCR BDLNB OECZV XHBEQ IDDWH VUVXT BRLCS MTGYH ULUNX CIBMU LXBPJ UHSMB PAPSL ISNZD MBGGD FVJGR XUPGF HTVKV WHRLY VQGEK IUIEK FDPHY DUJBF CBKYH RGJOX TDBHO VNXNO FJAUC PPXKF DDEPO ZIJUV SNQPQ XAJXK TOPZA UACPP KPJMV OLRCI UOEAB XBPMO EWHOW MDLON IOYYA FKVTU STAOB YVOQJ JIUIX YIGFQ KPANQ ZHRDD OIUAY BQPTF VBXLE XKZXL XCUWB RACZU PKFDM IKOFZ KXZMP KHAJI
El IC se define como la probabilidad de que dos letras tomadas al azar de un texto sean iguales.
Todo idioma tiene un IC estándar propio (por ejemplo: el español de aproximadamente 0,0775, el alemán de 0,0762, etc.), mientras que en un texto "aleatorio", como el obtenido al cifrar un texto en claro con una máquina Enigma, el IC es de aproximadamente 0,0385
Es decir, es como si el IC fuera una "huella" mediante la cual podemos saber si un texto, lo suficientemente largo para que su cálculo sea significativo, está escrito en un idioma (e incluso, en qué idioma) o, por el contrario, se trata de un texto "aleatorio", y, por tanto, la idea en este método de criptoanálisis se basa en ir obteniendo paulatinamente textos parcialmente descifrados con el IC más alto, considerando por separado los parámetros de la clave de una máquina Enigma, de tal forma que éste se vaya aproximando a lo esperado para un texto en claro escrito en alemán.
El primer paso del método de James Gillogly consiste en obtener el IC mayor del descifrado del criptograma para todos los posibles órdenes de los rotores y, dentro de cada uno de ellos, todas las posiciones iniciales de cada rotor, fijando el ajuste de los anillos en 1 - 1 - 1 (A - A - A) y con el tablero de conexiones sin ningún conector puesto. El orden de los rotores con el IC más alto así obtenido sería aquél con el que se obtuvo el texto cifrado que se está criptoanalizando.
Recuerdo que el IC se calcula de la siguiente manera:
Donde: fi es la frecuencia o número de ocurrencias del carácter i en el texto, en este caso el texto cifrado a criptoanalizar, y N es el tamaño del texto cifrado (en este caso, 1.175 caracteres).
En 1936, fecha en la que según el enunciado se envía el mensaje a criptoanalizar, la máquina enigma tenía sólo tres rotores (I, II y III), cada uno de los cuales podía situarse en cualquiera de las tres ranuras dispuestas para alojarlos, y tenía sólo 6 cables para conectar pares de letras en el tablero de conexiones.
Para implementar los diferentes pasos del método de James Gillogly utilizo el simulador en python del excelente sitio web "Jean-François BOUCHAUDY's Crypto page". Para el primer paso lo modifico para que descifre el criptograma para cada uno de los 6 posibles órdenes de los rotores (I - II - III, I - III - II, ..., III - II - I) y, dentro de cada uno de ellos, con cada una de las 17.576 posiciones iniciales de los rotores (A - A - A, A - A - B, ..., Z - Z - Z), fijando el ajuste de los anillos en A - A - A y sin ningún conector en el tablero de conexiones, y para que vaya calculando el IC de todos los textos así descifrados. Lo ejecuto y veo que el IC más alto es 0,042973648918047, que se corresponde con el descifrado para el orden de los rotores III - I - II y posición inicial de los mismos D - X - X. Por tanto, conforme a lo comentado anteriormente, podría haber recuperado uno de los parámetros de configuración de la máquina; el orden de los rotores con los que se habría obtenido el texto cifrado objeto del reto sería: III - I - II.
Ahora, tomando como base el mismo simulador, implemento el segundo paso del método de James Gillogly, que consiste en:
a) Paso 2.1: Para el orden de los rotores y a partir de la posición inicial de cada uno de ellos obtenidos en el primer paso (III - I - II y D - X - X, respectivamente), obtengo el IC mayor del descifrado del criptograma para cada ajuste del anillo posible del rotor derecho o rápido (de 'A' a 'Z'), fijando el ajuste de los anillos izquierdo y central (velocidad de giro lenta y media, respectivamente) en 1 - 1 (A - A) y con el tablero de conexiones sin ningún conector puesto. De esta forma recupero la mejor configuración para el rotor derecho o rápido (ajuste del anillo y posición inicial).
Es decir, descifro el criptograma con las siguientes configuraciones:
Rotores: III - I - II; Ajuste de los anillos: A - A - A; Posición inicial: D - X - X.
Rotores: III - I - II; Ajuste de los anillos: A - A - B; Posición inicial: D - X - Y.
Rotores: III - I - II; Ajuste de los anillos: A - A - C; Posición inicial: D - X - Z.
...
Rotores: III - I - II; Ajuste de los anillos: A - A - Z; Posición inicial: D - X - W.
Este Paso 2.1 se ejecuta muy rápido, ya que sólo hay que testear 26 configuraciones de ajuste de los anillos / posición inicial de los rotores, y veo que el IC mayor es 0,046377904237196, que se corresponde con el descifrado para el orden de los rotores III - I - II, ajuste de los anillos A - A - F y posición inicial de los rotores D - X - C.
b) Paso 2.2: Con la mejor configuración del rotor derecho o rápido hallada en el punto anterior, repito lo mismo para el rotor central o medio, es decir, para el orden de los rotores y a partir de la posición inicial del rotor izquierdo o lento obtenidos en el Paso 1 (III - I - II y D, respectivamente), y con el ajuste del anillo y posición inicial del rotor derecho o rápido hallados en el Paso 2.1, obtengo el IC mayor del descifrado del criptograma para cada ajuste del anillo posible del rotor central o medio (de 'A' a 'Z'), fijando el ajuste del anillo izquierdo o lento en 1 (A) y con el tablero de conexiones sin ningún conector puesto. De esta forma recupero la mejor configuración para el rotor central o medio (ajuste del anillo y posición inicial).
Es decir, descifro el criptograma con las siguientes configuraciones:
Rotores: III - I - II; Ajuste de los anillos: A - A - F; Posición inicial: D - X - C.
Rotores: III - I - II; Ajuste de los anillos: A - B - F; Posición inicial: D - Y - C.
Rotores: III - I - II; Ajuste de los anillos: A - C - F; Posición inicial: D - Z - C.
...
Rotores: III - I - II; Ajuste de los anillos: A - Z - F; Posición inicial: D - W - C.
Este Paso 2.2 también se ejecuta muy rápido, ya que al igual que en el anterior sólo hay que testear 26 configuraciones de ajuste de los anillos / posición inicial de los rotores, y veo que el IC mayor es 0,0494907390626699, que se corresponde con el descifrado para el orden de los rotores III - I - II, ajuste de los anillos A - E - F y posición inicial de los rotores D - B - C.
Por tanto, conforme a lo comentado anteriormente, ya habría recuperado la mejor configuración, ajuste del anillo y posición inicial, tanto para el rotor derecho o rápido, Paso 2.1, como para el rotor central o medio, Paso 2.2.
Ahora, tomando como base el mismo simulador, implemento el tercer y último paso del método de James Gillogly, que consiste en, asumiendo que son correctos los parámetros de configuración de la máquina hallados hasta el momento, obtener los mejores resultados para el descifrado del criptograma objeto de análisis, de forma separada, con cada uno de los pares de letras posibles que pueden ser conectadas entre sí en el tablero de conexiones. Es decir, primero con: A -B, después con A - C, ..., y finalmente con Y - Z.
En este Paso 3, como indicador de mejor resultado y para mensajes cortos, se suele utilizar una tabla de trígrafos en lugar del IC. No obstante, como el mensaje del reto es suficientemente largo, en este caso utilizo también el IC, ya que éste también discriminará efectivamente los pares de letras conectadas entre sí en el tablero de conexiones.
Para el orden de los rotores: III - I - II; Ajuste de los anillos: A - E - F; Posición inicial: D - B - C, los IC's mayores se producen para los siguientes pares de letras interconectadas en el panel de conexiones:
G - I: 0,0540418282648882
C - D: 0,053646018340643
F - H: 0,0535677262677154
A - M: 0,0525905252093226
J - K: 0,0518568994889267
I - J: 0,0510029359527348
E - N: 0,0505201348363478
Con lo que probablemente las conexiones establecidas en el tablero conectarían entre sí las letras de los pares resaltados en negrita (en 1936 sólo había 6 cables para realizar estas conexiones). Se descarta el par I - J porque la letra 'I' figura en el par con el IC más alto y una letra no puede estar conectada con más de otra letra. Además, la letra 'J' aparece también en el par anterior y éste también presenta un IC más alto.
Y, finalmente, trato de llegar al texto en claro ejecutando el mismo simulador con la siguiente configuración:
Orden de los rotores: III - I - II; Ajuste de los anillos: A - E - F;
Posición inicial: D - B - C;
Conectores en el tablero de conexiones: G - I; C - D; F - H; A - M; J - K; E - N
En el texto que se muestra en la figura anterior:
1.- Hay que sustituir 'ZZ' por ',' y 'X' por '.', ya que en la Wehrmacht se hacia la sustitución inversa en el texto en claro antes de cifrar éste.
2.- Asimismo, hay que sustituir los números escritos en letra ('ZWO' y 'SEQS') por sus guarismos correspondientes (2 y 6, respectivamente).
3.- Además, hay que realizar cuando procede, la sustitución de 'UE' por 'Ü', etc.
4.- Y para terminar de dar forma al mensaje original, hay que ir poniendo los espacios que correspondan entre las palabras.
Y, una vez hecho esto, se verá que el mensaje original está formado por dos párrafos de la entrada correspondiente a la máquina enigma en la wikipedia en alemán, que son aquellos que cifré para obtener el criptograma de este reto.
Evidentemente, lo ideal hubiera sido poner en este reto un mensaje cifrado auténtico de los enviados por los alemanes en la WWII y que éste fuera lo suficientemente largo y se hubiera obtenido con no demasiados conectores enchufados, pero, a falta de uno de estas características y para asegurarme de que el método de James Gillogly tuviera éxito, opté finalmente por cifrar los dos párrafos mencionados anteriormente para conseguir un criptograma que cumpliera con los dos factores críticos de éxito que he mencionado: que su tamaño fuera suficiente (el del reto tiene una longitud de 1.175 caracteres, algo totalmente inusual entre los enviados en la WWII, aunque había algún listo indisciplinado, como nuestro operador de ficción de la Wehrmacht preferido, Otto, que mandaba mensajes bastantes más largos de lo que la norma imponía) y que los pares de letras conectados en el tablero de conexiones no fueran demasiados.
Por tanto, la verdad es que no creo que el método de James Gillogly, de haberse podido aplicar por existir la potencia de cálculo necesaria para ello, hubiera tenido mucho éxito en aquella época, ya que los alemanes, además de obligar a los operadores a transmitir mensajes cortos, justo antes de la guerra aumentaron el número de cables de 6 a 10, con lo que en ese momento se podían conectar entre sí 20 letras del tablero de conexiones; demasiados conectores para que este método hubiera podido tener éxito en un número relevante de mensajes cifrados.
De hecho, tras las pruebas que el propio James Gillogly realizó para medir la efectividad de este ataque, en las que empleó mensajes cifrados por él mismo, no auténticos de los enviados por los alemanes en la WWII, y considerando que tenía éxito cuando el texto en plano obtenido presentaba una precisión del 80% o más respecto del original, llegó a la conclusión de que con su método sólo se hubieran podido descifrar con éxito, aproximadamente:
- Criptogramas de unos 1.500 caracteres (algo muy inusual): El 75% de los criptogramas si hubiera 6 cables interconectando pares de letras en el tablero de conexiones (hasta 1938 sólo había 6 cables para ello) y el 5% si hubiera 10 cables interconectando pares de letras en el tablero de conexiones (justo antes de la guerra el número aumentó de 6 a 10).
- Criptogramas de unos 300 caracteres (el máximo permitido por la norma): El 15% de los criptogramas si hubiera 6 cables interconectando pares de letras en el tablero de conexiones (hasta 1938 sólo había 6 cables para ello) y el 0% si hubiera 10 cables interconectando pares de letras en el tablero de conexiones (justo antes de la guerra el número aumentó de 6 a 10).
- Criptogramas de unos 175 caracteres (algo ya muy usual): El 2% de los criptogramas si hubiera 6 cables interconectando pares de letras en el tablero de conexiones (hasta 1938 sólo había 6 cables para ello) y el 0% si hubiera 10 cables interconectando pares de letras en el tablero de conexiones (justo antes de la guerra el número aumentó de 6 a 10).
Significa esto que: ¿James Gillogly perdió el tiempo con su método porque éste no vale para nada? Pues en mi opinión no, aunque sólo sea desde un punto de vista teórico y no muy práctico. Me explico:
- Aunque la potencia de cálculo, que no el desconocimiento de estas técnicas, hacia que este método quedara fuera del alcance de los criptoanalistas durante la Segunda Guerra Mundial, la tecnología necesaria para realizar este tipo de ataques estuvo disponible poco después y las máquinas Enigma estuvieron en uso mucho después de la WWII. Por tanto, si después de la guerra los operadores no guardaron las precauciones necesarias con respecto a la longitud del mensaje y el número de conectores empleados, las transmisiones que realizaron pudieron haber sido vulneradas mediante ataques de sólo texto cifrado ('Ciphertext-only attack'), mucho más económicos y fáciles de automatizar que otros tipos de ataque.
- Aunque, evidentemente, con el desuso de la máquina Enigma los mensajes cifrados con ella perdieron mucho interés, todavía quedaban (e incluso quedan) mensajes no descifrados con una longitud menor de 300 caracteres que aunque sólo sea por su valor histórico merecería la pena descifrar. Pues bien, aquí es donde se puede decir que el método de James Gillogly ha aportado un mayor valor añadido, aunque no sea directamente aplicable por falta de eficacia a mensajes tan cortos y con muchos conectores enchufados en el tablero de conexiones, ya que éste ha sido examinado y refinado por otros criptoanalistas para hacerlo más eficaz en las citadas condiciones. Es el caso, por ejemplo, de Geoff Sullivan y Frode Weierud, que en su artículo titulado 'Breaking German Army
Ciphers' (publicado en la revista 'Cryptologia' en Junio de 2005) mejoran notablemente el método de James Gillogly, dando lugar al método de escalada de la colina ('hill climbing'). Lo interesante de este algoritmo es que se ha aplicado con éxito para descifrar mensajes originales del ejército alemán en la Segunda Guerra Mundial en los que, por su tamaño y número de conectores enchufados, el método de James Gillogly era inefizaz. ¿En qué consiste el método de escalada de la colina ('hill climbing')? Bueno, si es el caso, esto será objeto de nuevas entradas en este blog.
******** PRÓXIMO RETO
Reto 44: "Cinta móvil".
Comentarios
Publicar un comentario