Criptografía (CXCIX): Reto 43

Pongo otra entrada sobre la máquina Enigma, de la que, evidentemente, soy un auténtico fan; muy torpe, pero fan al fin y al cabo. La máquina de cifrado más famosa de la historia; la utilizada por el ejército alemán durante la Segunda Guerra Mundial.

En este caso se trata de un desafío que se refiere a un enfoque más "moderno" sobre su criptoanálisis, el contenido en el artículo 'Ciphertext-only cryptanalysis of Enigma' de James Gillogly publicado en la revista 'Cryptologia' (Octubre 1995). Y digo "moderno" no sólo porque fue publicado hace ya unos 25 años, sino porque el ataque se basa en la estadística del lenguaje, técnicas que ya se conocían de hace mucho tiempo.

Tal y como diré en el post de solución a este reto, no es que se trate de un método precisamente muy eficaz, ni siquiera creo que se hubiera podido utilizar en su época por falta de la potencia de cálculo necesaria, aunque ahora queda perfectamente al alcance de cualquier PC sin demasiadas prestaciones, pero me ha parecido muy interesante por dos circunstancias: en primer lugar, porque viene a demostrar que, en ocasiones, es posible el criptoanálisis de los mensajes de la máquina Enigma sin más que tener el texto cifrado de los mismos ('Ciphertext-only cryptanalysis'), sin necesidad de probar todas las configuraciones posibles de la máquina (una absoluta locura) o de conocer parte del texto en claro correspondiente al texto cifrado del que se dispone ('Known-plaintext attack'), y aplicar a éste técnicas de estadística del lenguaje (algo que incluso se suponía que no era posible, aunque es verdad que falla con bastante o mucha frecuencia, ya que presenta dos factores críticos de éxito: la longitud del criptograma, que debe ser suficientemente largo, y el número de conectores en el tablero de conexiones, más probabilidad de éxito cuantas menos sean), y, en segundo lugar, porque ha servido de base para desarrollar métodos mucho más eficaces utilizando dichas técnicas.

Dicho todo lo anterior, en este post pongo otro reto de criptografía en el que se ve involucrada la máquina enigma.

Como siempre, se admiten soluciones en forma de comentarios a esta entrada. Pasado un tiempo iré proporcionando pistas para su resolución, un máximo de tres, y posteriormente actualizaré este post con la solución.

Reto 43: "¿Coincidencia?".

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?

Dificultad:

Tipo:       Criptografía.

Recursos:

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

******** 10/10/2021
Pista 1:    El indicador en el que se basa el método de James Gillogly para el criptoanálisis de los mensajes de la máquina Enigma, considerando única y exclusivamente el texto cifrado del que se dispone ('Ciphertext-only cryptanalysis'), es el índice de coincidencia (IC).

Ya expliqué en una entrada de este blog qué es el índice de coincidencia (IC), pero lo vuelvo a hacer muy brevemente: es 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).

******** 11/10/2021
Pista 2:    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.

Utiliza un simulador de la máquina enigma y configúralo 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, calcula el IC de todos los textos así descifrados y quédate con el mayor IC obtenido.

Verás 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, ya habrías recuperado uno de los parámetros de configuración de la máquina; el orden de los rotores con el que se habría obtenido el texto cifrado objeto del reto sería: III - I - II.

Ahora, deberás realizar el segundo paso del método de James Gillogly, que consiste en:

a) 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), obtener 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 recuperarás la mejor configuración para el rotor derecho o rápido (ajuste del anillo y posición inicial).

Es decir, en nuestro reto, descifrado del 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.

b) Con la mejor configuración del rotor derecho o rápido hallada en el punto anterior, repetir 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 primer paso (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 punto anterior, obtener 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 recuperarás la mejor configuración para el rotor central o medio (ajuste del anillo y posición inicial).

******** 12/10/2021
Pista 3:    Si has ejecutado el Paso 2 mediante un simulador, de forma mucho más rápida que en el Paso 1, ya que sólo hay que testear 26 configuraciones de ajuste de los anillos / posición inicial de los rotores para el punto a) y otros tantos para el b), ya habrás visto que el IC más alto para el punto a) 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, y que para el punto b) 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 en la pista anterior, ya habrías recuperado la mejor configuración, ajuste del anillo y posición inicial, tanto para el rotor derecho o rápido, punto a), como para el rotor central o medio, punto b).

Ahora, únicamente queda realizar 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 el IC también discriminará efectivamente los pares de letras conectadas entre sí en el tablero de conexiones.

******** 12/10/2021

Solución.

******** PRÓXIMO RETO

Reto 44:   "Cinta móvil".