El banburismo fue un proceso criptoanalítico desarrollado por Alan Turing en Bletchley Park en Gran Bretaña durante la Segunda Guerra Mundial . [1] Fue utilizado por la Cabaña 8 de Bletchley Park para ayudar a descifrar mensajes de la Kriegsmarine (naval) alemana cifrados en máquinas Enigma . El proceso utilizaba probabilidad condicional secuencial para inferir información sobre las configuraciones probables de la máquina Enigma. [2] Dio lugar a la invención por parte de Turing del ban como una medida del peso de la evidencia a favor de una hipótesis. [3] [4] Este concepto se aplicó más tarde en la Turingería y en todos los demás métodos utilizados para descifrar el cifrado de Lorenz . [5]
El objetivo del Banburismus era reducir el tiempo requerido por las máquinas electromecánicas Bombe mediante la identificación de las ruedas derecha e intermedia más probables de la Enigma . [6] [7] Hut 8 realizó el procedimiento de forma continua durante dos años, deteniéndose solo en 1943 cuando se dispuso de suficiente tiempo para las bombas. [8] [9] El Banburismus fue un desarrollo del " método del reloj " inventado por el criptoanalista polaco Jerzy Różycki . [10]
Hugh Alexander era considerado el mejor de los banburistas. Él y IJ Good consideraban que el proceso era más un juego intelectual que un trabajo. No era "lo suficientemente fácil como para ser trivial, pero tampoco lo suficientemente difícil como para provocar un colapso nervioso". [11]
En los primeros meses tras su llegada a Bletchley Park en septiembre de 1939, Alan Turing dedujo correctamente que los mensajes de las señales Enigma de la Kriegsmarine se cifraban según una Grundstellung común (posición inicial de los rotores) y que luego se cifraban mediante un bigrama y una tabla de búsqueda de trigramas . Estas tablas de trigramas se encontraban en un libro llamado Kenngruppenbuch (libro K) . Sin embargo, sin las tablas de bigramas, la Cabaña 8 no pudo empezar a atacar el tráfico. [12] Se logró un gran avance después del aprieto de Narvik , cuando el arrastrero armado disfrazado Polares , que se dirigía a Narvik en Noruega , fue capturado por el HMS Griffin en el Mar del Norte el 26 de abril de 1940. [13] Los alemanes no tuvieron tiempo de destruir todos sus documentos criptográficos, y el material capturado reveló la forma precisa del sistema de indicación, proporcionó las conexiones del tablero de conexiones y Grundstellung para el 23 y 24 de abril y el registro de los operadores, que proporcionó un largo tramo de texto simple emparejado y mensaje cifrado para el 25 y 26. [14]
Las tablas de bigramas en sí no formaban parte de la captura, pero Hut 8 pudo usar las listas de configuraciones para leer, retrospectivamente, todo el tráfico de la Kriegsmarine que había sido interceptado del 22 al 27 de abril. Esto les permitió hacer una reconstrucción parcial de las tablas de bigramas y comenzar el primer intento de usar Banburismus para atacar el tráfico de la Kriegsmarine, a partir del 30 de abril en adelante. Los días elegibles fueron aquellos en los que se recibieron al menos 200 mensajes y para los cuales las tablas de bigramas parciales descifraron los indicadores . El primer día en ser interceptado fue el 8 de mayo de 1940, a partir de entonces celebrado como el "Día de Foss" en honor a Hugh Foss , el criptoanalista que logró la hazaña.
Esta tarea se prolongó hasta noviembre de ese año, cuando la información ya estaba muy desactualizada, pero demostró que el Banburismus podía funcionar. También permitió reconstruir muchas más tablas de bigramas, lo que a su vez permitió descifrar las fechas del 14 de abril y del 26 de junio. Sin embargo, la Kriegsmarine había cambiado las tablas de bigramas el 1 de julio. [15] A fines de 1940, se había elaborado gran parte de la teoría del sistema de puntuación del Banburismus.
El primer piquete de Lofoten del arrastrero Krebs el 3 de marzo de 1941 proporcionó las claves completas para febrero, pero no las tablas de bigramas ni el libro K. Los descifrados subsiguientes permitieron refinar el sistema de puntuación estadística para que el Banburismus pudiera convertirse en el procedimiento estándar contra la Kriegsmarine Enigma hasta mediados de 1943. [15]
El Banburismus aprovechó una debilidad en el procedimiento de indicadores (la configuración de mensajes cifrados) del tráfico Enigma de la Kriegsmarine. A diferencia de los procedimientos Enigma del Ejército y la Fuerza Aérea alemanes , la Kriegsmarine utilizaba un Grundstellung proporcionado por listas de claves, por lo que era el mismo para todos los mensajes de un día en particular (o par de días). Esto significaba que los indicadores de tres letras estaban todos cifrados con la misma configuración de rotor para que todos estuvieran en profundidad entre sí. [16] Normalmente, los indicadores de dos mensajes nunca eran los mismos, pero podía suceder que, a mitad de un mensaje, las posiciones del rotor se volvieran iguales que la posición inicial de los rotores de otro mensaje, y las partes de los dos mensajes que se superponían de esta manera estaban en profundidad.
El principio detrás del Banburismo es relativamente simple (y parece ser bastante similar al Índice de Coincidencia ). Si se escriben dos oraciones en inglés o alemán una encima de la otra, y se hace un recuento de la frecuencia con la que una letra en un mensaje es la misma que la letra correspondiente en el otro mensaje; habrá más coincidencias de las que ocurrirían si las oraciones fueran cadenas aleatorias de letras. Para una secuencia aleatoria, se espera que la tasa de repetición para letras individuales sea de 1 en 26 (alrededor del 3,8%), y para los mensajes de la Marina alemana se demostró que era de 1 en 17 (5,9%). [17] Si los dos mensajes eran en profundidad, entonces las coincidencias ocurren tal como lo hicieron en los textos simples. Sin embargo, si los mensajes no eran en profundidad, entonces los dos textos cifrados se compararán como si fueran aleatorios, dando una tasa de repetición de aproximadamente 1 en 26. Esto permite a un atacante tomar dos mensajes cuyos indicadores difieren solo en el tercer carácter, y deslizarlos uno contra el otro buscando el patrón de repetición revelador que muestra dónde se alinean en profundidad.
La comparación de dos mensajes para buscar repeticiones se hizo más fácil perforando los mensajes en tarjetas delgadas de unos 250 milímetros (9,8 pulgadas) de alto por varios metros (yardas) de ancho, dependiendo de la longitud del mensaje. [ cita requerida ] Un agujero en la parte superior de una columna en la tarjeta representaba una 'A' en esa posición, un agujero en la parte inferior representaba una 'Z'. Las dos tarjetas de mensajes se colocaron una sobre la otra en una caja de luz y donde la luz brillaba a través de ellas, había una repetición. Esto hizo mucho más simple detectar y contar las repeticiones. Las tarjetas se imprimieron en Banbury, en Oxfordshire. Se las conoció como 'banburyes' en Bletchley Park, y de ahí el procedimiento para usarlas: Banburismus. [18]
La aplicación del procedimiento scritchmus (ver más abajo) da una pista sobre el posible rotor derecho.
Mensaje con indicador " VFG ": XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF
Mensaje con indicador " VFX ": YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ
La cabaña 8 perforaría estos en banburys y contaría las repeticiones para todos los desplazamientos válidos de −25 letras a +25 letras. Hay dos posiciones prometedoras:
XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ - -- - - - - -
Este desplazamiento de ocho letras muestra nueve repeticiones, incluidos dos bigramas, en una superposición de 56 letras (16%).
La otra posición prometedora se ve así:
XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ ---
Este desplazamiento de siete muestra sólo un trigrama en una superposición de 57 letras.
El método de Turing de acumular una puntuación de un número determinado de decibanos permite calcular cuál de estas situaciones tiene más probabilidades de representar mensajes en profundidad. Como era de esperar, la primera es la ganadora con probabilidades de 5:1 a favor, mientras que la segunda tiene solo 2:1 a favor. [19]
Turing calculó las puntuaciones para el número de repeticiones simples en superposiciones de tantas letras, y el número de bigramas y trigramas. Los tetragramas a menudo representaban palabras alemanas en el texto simple [ aclaración necesaria ] y sus puntuaciones se calcularon de acuerdo con el tipo de mensaje (a partir del análisis de tráfico), e incluso su posición dentro del mensaje. [20] Estos fueron tabulados y los valores relevantes sumados por los banburistas al evaluar pares de mensajes para ver cuáles probablemente fueran profundos.
Bletchley Park utilizó la convención de que el texto indicador de "VFX" debía estar ocho caracteres delante de "VFG", o (en términos de sólo la tercera letra diferente) que "X = G+8".
El Scritchmus era la parte del procedimiento del Banburismo que podía llevar a la identificación de la rueda de la derecha (rápida). El Banburista podía tener evidencia de varios pares de mensajes (con solo la tercera letra indicadora diferente) que mostraban que "X = Q−2", "H = X−4" y "B = G+3". Él o ella [21] buscaría en las hojas de deciban todas las distancias con probabilidades mejores que 1:1 (es decir, con puntuaciones ≥ +34). Luego se intentó construir el "alfabeto de la rueda final" formando "cadenas" de letras de la rueda final a partir de estas repeticiones. [22]
Podrían entonces construir una "cadena" como la siguiente:
G--BH---XQ
Si luego se compara esto en desplazamientos progresivos con la secuencia de letras conocida de un rotor Enigma, se descartan bastantes posibilidades debido a que se viola la propiedad "recíproca" o la propiedad de "no autocifrado" de la máquina Enigma:
G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (G cifra a B, pero B cifra a E) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (H aparentemente cifra a H) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (G cifra a D, pero B cifra a G) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (B cifra a H, pero H cifra a J) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (Q aparentemente se cifra en Q) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (G aparentemente se cifra en G) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (G cifra a H, pero H cifra a M) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (H cifra a Q, pero Q cifra a W) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (X cifra a V, pero Q cifra a X) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (B cifra a Q, pero Q cifra a Y) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (X se cifra en X)Q G--BH---X->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible-Q G--BH---X->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (Q cifra a B, pero B cifra a T)XQ G--BH--->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible-XQ G--BH-->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (X cifra a B, pero B cifra a V)--XQ G--BH->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible---XQ G--BH->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (X cifra a D, pero B cifra a X)H---XQ G--B->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (Q cifra en G, pero G cifra en V)-H---XQ G--B->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (H cifra a B, pero Q cifra a H)BH---XQ G-->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible (tenga en cuenta la propiedad G cifra a X, X cifra a G)-BH---XQ G->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (B cifra a B)--BH---XQ G->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible
El llamado "alfabeto de rueda final" ya está limitado a sólo nueve posibilidades, simplemente estableciendo una cadena de cinco letras derivadas de tan sólo cuatro pares de mensajes. Hut 8 intentaría ahora encajar otras cadenas de letras (sin letras en común con la primera cadena) en estos nueve posibles alfabetos de rueda final.
Al final esperan quedarse con un solo candidato, tal vez con un aspecto similar al siguiente:
Política nacionalM----A-D---O--XQ G--BH->ABCDEFGHIJKLMNOPQRSTUVWXYZ
No sólo esto, sino que un alfabeto de rueda final de este tipo obliga a la conclusión de que la rueda final es, de hecho, "Rotor I". Esto se debe a que "Rotor II" habría causado un cambio de rueda a mitad de camino al pasar de "E" a "F", pero eso está en el medio del tramo de la cadena de letras "F----A--D---O". Del mismo modo, todos los demás cambios de rueda posibles quedan excluidos. El Rotor I hace su cambio entre "Q" y "R", y esa es la única parte del alfabeto que no está atravesada por una cadena.
El hecho de que las distintas ruedas de la Enigma tuvieran distintos puntos de giro fue, presumiblemente, una medida de los diseñadores de la máquina para mejorar su seguridad. Sin embargo, esta misma complicación permitió a Bletchley Park deducir la identidad de la rueda final.
Una vez identificada la rueda final, estos mismos principios se pueden extender para manejar el rotor central, aunque con la complejidad adicional de que la búsqueda es para superposiciones en pares de mensajes que comparten solo la primera letra indicadora y que las superposiciones, por lo tanto, podrían ocurrir con hasta 650 caracteres de diferencia. [23]
La carga de trabajo que esto implica supera el trabajo manual, por lo que BP perforó los mensajes en tarjetas de 80 columnas y utilizó máquinas Hollerith para escanear en busca de repeticiones de tetragramas o mejores. Eso les indicó qué banburys colocar en las cajas de luz (y con qué superposición) para evaluar todo el patrón de repetición.
Armado con un conjunto de probables superposiciones de la rueda central, Hut 8 podría componer cadenas de letras para la rueda central de la misma manera que se ilustró anteriormente para la rueda final. Eso a su vez (después de Scritchmus) daría al menos un alfabeto parcial de la rueda central, y con suerte al menos algunas de las posibles opciones de rotor para la rueda central podrían eliminarse del conocimiento de rotación (como se hizo al identificar la rueda final).
En conjunto, las probables ruedas derechas y centrales darían un conjunto de carreras de bombas para el día, que se reducirían significativamente de las 336 posibles.