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 Hut 8 de Bletchley Park para ayudar a descifrar mensajes de la Kriegsmarine (naval) alemana cifrados en máquinas Enigma . El proceso utilizó probabilidad condicional secuencial para inferir información sobre las configuraciones probables de la máquina Enigma. [2] Dio lugar a la invención de Turing de la prohibición como medida del peso de la evidencia a favor de una hipótesis. [3] [4] Este concepto se aplicó más tarde en Turingery y en todos los demás métodos utilizados para descifrar el cifrado de Lorenz . [5]
El objetivo de Banburismus era reducir el tiempo requerido por las máquinas electromecánicas Bombe identificando las ruedas derecha e intermedia más probables del Enigma . [6] [7] La cabaña 8 realizó el procedimiento continuamente durante dos años, deteniéndose sólo en 1943, cuando se dispuso de suficiente tiempo de bombardeo. [8] [9] El banburismo 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 consideraron el proceso más como un juego intelectual que como un trabajo. "No era lo suficientemente fácil como para ser trivial, pero tampoco lo suficientemente difícil como para causar un ataque de nervios". [11]
En los primeros meses después de su llegada a Bletchley Park en septiembre de 1939, Alan Turing dedujo correctamente que los ajustes de los mensajes de las señales Enigma de la Kriegsmarine estaban cifrados en un Grundstellung (posición inicial de los rotores) común, y luego eran supercifrados con un bigrama. y una tabla de búsqueda de trigramas . Estas tablas de trigramas estaban en un libro llamado Kenngruppenbuch (libro K) . Sin embargo, sin las mesas bigram, Hut 8 no pudo empezar a atacar el tráfico. [12] Se logró un gran avance después del apuro de Narvik en el que 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 indicador, suministró las conexiones del tablero y Grundstellung para el 23 y 24 de abril y el registro de los operadores, que proporcionó una larga extensión de texto plano emparejado y mensaje cifrado Para los días 25 y 26. [14]
Las tablas de bigram en sí no formaron parte de la captura, pero Hut 8 pudo utilizar las listas de configuración 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 bigram y comenzar el primer intento de utilizar Banburismus para atacar el tráfico de la Kriegsmarine, a partir del 30 de abril. Los días elegibles fueron aquellos en los que se recibieron al menos 200 mensajes y para los cuales las tablas parciales de bigram descifraron los indicadores . El primer día en romperse fue el 8 de mayo de 1940, posteriormente celebrado como el "Día de Foss" en honor a Hugh Foss , el criptoanalista que logró la hazaña.
Esta tarea duró hasta noviembre de ese año, momento en el que la inteligencia estaba muy desactualizada, pero demostró que Banburismus podía funcionar. También permitió reconstruir muchas más tablas de bigram, lo que a su vez permitió romper el 14 de abril y el 26 de junio. Sin embargo, la Kriegsmarine modificó las tablas de bigramas el 1 de julio. [15] A finales de 1940, gran parte de la teoría del sistema de puntuación del Banburismus se había elaborado.
El primer golpe de Lofoten del arrastrero Krebs el 3 de marzo de 1941 proporcionó las claves completas de febrero, pero no tablas de bigramas ni libros K. Los consiguientes descifrados permitieron perfeccionar el sistema de puntuación estadística para que Banburismus pudiera convertirse en el procedimiento estándar contra la Kriegsmarine Enigma hasta mediados de 1943. [15]
Banburismus aprovechó una debilidad en el procedimiento del indicador (la configuración de mensajes cifrados) del tráfico de Kriegsmarine Enigma. A diferencia de los procedimientos Enigma del ejército y la fuerza aérea alemanes , la Kriegsmarine utilizó un Grundstellung proporcionado por listas de claves, por lo que era el mismo para todos los mensajes en un día (o par de días) en particular. Esto significó que todos los indicadores de tres letras estaban cifrados con la misma configuración del rotor para que todos estuvieran en profundidad entre sí. [16] Normalmente, los indicadores para dos mensajes nunca eran los mismos, pero podía suceder que, a mitad de un mensaje, las posiciones de los rotores se volvieran las mismas que la posición inicial de los rotores para otro mensaje, las partes de los dos Los mensajes que se superponían de esta manera eran profundos.
El principio detrás del Banburismus es relativamente simple (y parece bastante similar al Índice de Coincidencia ). Si se escriben dos frases en inglés o alemán, una encima de la otra, y se cuenta la frecuencia con la que una letra de un mensaje coincide con la letra correspondiente del 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 de letras individuales sea de 1 entre 26 (alrededor del 3,8%), y para los mensajes de la Marina alemana fue de 1 entre 17 (5,9%). [17] Si los dos mensajes fueron en profundidad, entonces las coincidencias ocurren tal como lo hicieron en los textos sin formato. Sin embargo, si los mensajes no eran profundos, 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 sólo en el tercer carácter, y deslícelos uno contra el otro buscando el patrón de repetición 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 aproximadamente 250 milímetros (9,8 pulgadas) de alto por varios metros (yardas) de ancho, dependiendo de la longitud del mensaje. [ cita necesaria ] Un agujero en la parte superior de una columna de la tarjeta representaba una 'A' en esa posición, un agujero en la parte inferior representaba una 'Z'. Las dos tarjetas con mensajes se colocaron una encima de la otra sobre una caja de luz y donde la luz brillaba, se repetía. Esto hizo que fuera mucho más sencillo detectar y contar las repeticiones. Las tarjetas se imprimieron en Banbury , Oxfordshire. Se les conoció como 'banburys' en Bletchley Park, y de ahí el procedimiento para utilizarlos: 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 los perforaría en banburys y contaría las repeticiones para todas las compensaciones válidas: −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 solo un trigrama en una superposición de 57 letras.
El método de Turing de acumular una puntuación de un número de decibanes permite calcular cuál de estas situaciones tiene más probabilidades de representar mensajes en profundidad. Como era de esperar, el primero es el ganador con una cuota de 5:1, el segundo solo con una cuota de 2:1. [19]
Turing calculó las puntuaciones para el número de repeticiones individuales en superposiciones de tantas letras y el número de bigramas y trigramas. Los tetragramas a menudo representaban palabras alemanas en texto plano [ se necesita aclaración ] y sus puntuaciones se calculaban según 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 resumidos por los banburistas al evaluar pares de mensajes para ver cuáles tenían probabilidades de ser más profundos.
Bletchley Park utilizó la convención de que el texto plano indicador de "VFX", estaba ocho caracteres por delante de "VFG", o (en términos de sólo la tercera letra diferente) que "X = G+8".
Scritchmus era la parte del procedimiento Banburismus que podía conducir a la identificación de la rueda derecha (rápida). El banburista podría tener evidencia de varios pares de mensajes (donde solo difiere la tercera letra indicadora) que muestran que "X = Q-2", "H = X-4" y "B = G+3". Él o ella [21] buscaría en las hojas 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 las ruedas finales a partir de estas repeticiones. [22] Luego podrían construir una "cadena" de la siguiente manera:
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 la violación de 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 B, pero B cifra E) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (H aparentemente cifra H) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (G cifra D, pero B cifra G) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (B cifra H, pero H cifra J) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (Q aparentemente cifra Q) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (G aparentemente cifra G) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (G cifra H, pero H cifra M) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (H cifra Q, pero Q cifra W) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (X cifra a V, pero Q cifra a X) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (B cifra Q, pero Q cifra Y) G--BH---XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (X cifra a X)Q G--BH---X->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible-Q G--BH---X->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (Q cifra B, pero B cifra T)XQ G--BH--->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible-XQ G--BH-->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (X cifra B, pero B cifra V)--XQ G--BH->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible---XQ G--BH->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (X cifra D, pero B cifra X)H---XQ G--B->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (Q cifra a G, pero G cifra a V)-H---XQ G--B->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (H cifra B, pero Q cifra H)BH---XQG-->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible (tenga en cuenta los cifrados G para X, los cifrados X para la propiedad G)-BH---XQG->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (B cifra B)--BH---XQG->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 sólo cuatro pares de mensajes. La cabaña 8 ahora intentaría encajar otras cadenas de letras (aquellas que no tienen letras en común con la primera cadena) en estos nueve alfabetos candidatos de rueda final.
Con el tiempo, esperarán quedarse con un solo candidato, tal vez con este aspecto:
NUPF----A--D---O--XQ G--BH->ABCDEFGHIJKLMNOPQRSTU VWXYZ
No sólo esto, sino que un alfabeto de rueda de extremo así obliga a concluir que la rueda de extremo es en realidad "Rotor I". Esto se debe a que "Rotor II" habría causado un giro en la mitad de la rueda al pasar de "E" a "F", pero eso está en el medio del lapso de la cadena de letras "F----A--D ---Oh". Asimismo, quedan excluidos todos los demás posibles vuelcos en el centro de las ruedas. El rotor I realiza su rotación entre "Q" y "R", y esa es la única parte del alfabeto que no está atravesada por una cadena.
Que las diferentes ruedas Enigma tuvieran diferentes puntos de rotación 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 que se identifica la rueda del extremo, estos mismos principios pueden extenderse para manejar el rotor central, aunque con la complejidad añadida de que la búsqueda es para superposiciones en pares de mensajes que comparten sólo la primera letra indicadora, y que las superposiciones, por lo tanto, podrían ocurrir en hasta a 650 caracteres de diferencia. [23]
La carga de trabajo que supone hacer esto va más allá del trabajo manual, por lo que BP marcó los mensajes en tarjetas de 80 columnas y utilizó máquinas Hollerith para buscar repeticiones de tetragramas o mejores. Eso les indicó qué banburys colocar en las cajas de luz (y con qué superposiciones) para evaluar todo el patrón de repetición.
Armado con un conjunto de probables superposiciones en la rueda central, Hut 8 podría componer cadenas de letras para la rueda central de la misma manera que se ilustra arriba para la rueda del extremo. Esto, a su vez (después de Scritchmus) daría al menos un alfabeto parcial de la rueda intermedia y, con suerte, al menos algunas de las posibles opciones de rotor para la rueda intermedia podrían eliminarse del conocimiento de rotación (como se hizo al identificar la rueda final).
En conjunto, las probables ruedas derecha e intermedia darían un conjunto de carreras explosivas para el día, que se reducirían significativamente de las 336 posibles.