Banburismus 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 Bletchley Park's Hut 8 para ayudar a descifrar los mensajes de la Kriegsmarine alemana (naval) cifrados en las máquinas Enigma . El proceso utilizó probabilidad condicional secuencial para inferir información sobre los ajustes probables de la máquina Enigma. [2] Dio lugar a la invención de Turing de la prohibición como una medida del peso de la evidencia a favor de una hipótesis. [3][4] Este concepto se aplicó más tarde en Turingery y todos los demás métodos utilizados para descifrar el cifrado de Lorenz . [5]
Descripción general
El objetivo de Banburismus era reducir el tiempo requerido de las máquinas Bombe electromecánicas identificando las ruedas centrales y derechas más probables del Enigma . [6] [7] Hut 8 realizó el procedimiento continuamente durante dos años, deteniéndose solo en 1943 cuando se dispuso de suficiente tiempo de bombeo. [8] [9] Banburismus fue un desarrollo del " método del reloj " inventado por el criptoanalista polaco Jerzy Różycki . [10]
Hugh Alexander fue considerado el mejor de los banburistas. Él e IJ Good consideraron el proceso más un juego intelectual que un trabajo. "No fue lo suficientemente fácil para ser trivial, pero no lo suficientemente difícil como para causar un ataque de nervios". [11]
Historia
En los primeros meses después de llegar a Bletchley Park en septiembre de 1939, Alan Turing dedujo correctamente que los ajustes de mensaje de las señales Enigma de la Kriegsmarine estaban cifrados en un Grundstellung común (posición inicial de los rotores), y luego 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 tablas de bigramas, Hut 8 no pudo comenzar a atacar el tráfico. [12] Se logró un gran avance después del pellizco 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 lo hicieron. tuvieron tiempo para destruir todos sus documentos criptográficos, y el material capturado reveló la forma precisa del sistema de indicación, suministró las conexiones del tablero de conexiones y Grundstellung para el 23 y 24 de abril y el registro de los operadores, que dio un largo tramo de texto plano emparejado y mensaje cifrado para los días 25 y 26. [14]
Las tablas de bigramas en sí no formaron parte de la captura, pero Hut 8 pudo usar 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 bigrama 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 de bigrama parciales descifraron los indicadores . El primer día que se rompió fue el 8 de mayo de 1940, que a partir de entonces se celebró como "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 bigrama, lo que a su vez permitió romper el 14 de abril y el 26 de junio. Sin embargo, la Kriegsmarine había cambiado las tablas de bigramas el 1 de julio. [15] A finales de 1940, se había elaborado gran parte de la teoría del sistema de puntuación Banburismus.
El pellizco Primera Lofoten del barco rastreador de Krebs el 3 de marzo 1941 proporcionado las claves completas para febrero - pero no hay mesas bigrama o libro de K . Los descifrados consiguientes permitieron refinar el sistema de puntuación estadística para que Banburismus pudiera convertirse en el procedimiento estándar contra Kriegsmarine Enigma hasta mediados de 1943. [15]
Principios
Banburismus utilizó 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 clave, por lo que era el mismo para todos los mensajes en un día en particular (o par de días). Esto significaba que todos los indicadores de tres letras estaban cifrados con la misma configuración del rotor para que estuvieran todos en profundidad entre sí. [16] Normalmente, los indicadores para dos mensajes nunca eran los mismos, pero podría suceder que, a mitad de camino a través de un mensaje, las posiciones del rotor fueran 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 de Banburismus 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 de letras aleatorias. Para una secuencia aleatoria, se espera que la tasa de repetición para letras individuales sea 1 en 26 (alrededor del 3.8%), y para los mensajes de la Armada alemana se demostró que es 1 en 17 (5.9%). [17] Si los dos mensajes fueran en profundidad, entonces las coincidencias ocurren tal como ocurrieron en los textos sin formato. Sin embargo, si los mensajes no fueran 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 deslícelos uno contra el otro buscando el patrón de repetición del sorteo 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 mm de alto (10 ") por varios metros de ancho (tenían diferentes tarjetas para diferentes longitudes de mensaje). Un agujero en la parte superior de un La columna de la tarjeta representaba una 'A' en esa posición, un agujero en la parte inferior representaba una 'Z'. Las dos tarjetas de mensaje se colocaron una encima de la otra en una caja de luz y donde la luz brillaba, había una repetición. Esto hizo que fuera mucho más sencillo detectar y contar las repeticiones. Las tarjetas se imprimieron en Banbury en Oxfordshire. Se conocieron como 'banburies' en Bletchley Park, y de ahí el procedimiento que las usa: Banburismus. [18]
La aplicación del procedimiento scritchmus (ver más abajo) da una pista sobre el posible rotor de la derecha.
Ejemplo
Mensaje con indicador " VFG ": XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF
Mensaje con indicador " VFX ": YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ
El Hut 8 los perforaría en banburies y contaba las repeticiones de todas las compensaciones válidas 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 solo un trigrama en una superposición de 57 letras.
El método de Turing de acumular una puntuación de varios decibenes permite calcular cuál de estas situaciones es más probable que represente mensajes en profundidad. Como era de esperar, el primero es el ganador con probabilidades de 5: 1 en adelante, el último es de solo 2: 1 en adelante. [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 en alemán en texto plano 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 estar en profundidad.
Bletchley Park usó la convención de que el indicador de texto plano de "VFX" está ocho caracteres por delante de "VFG", o (en términos de la tercera letra diferente) que "X = G + 8".
Scritchmus
Scritchmus era la parte del procedimiento de Banburismus que podía conducir a la identificación de la rueda derecha (rápida). El Banburist podría tener evidencia de varios pares de mensajes (con solo la tercera letra indicadora diferente) mostrando que "X = Q − 2", "H = X − 4" y "B = G + 3". Él [21] buscaría en las hojas de deciban todas las distancias con probabilidades superiores a 1: 1 (es decir, con puntuaciones ≥ +34). A continuación, se intentó construir el "alfabeto de la rueda final" formando "cadenas" de letras de la rueda final a partir de estas repeticiones. [22] Entonces podrían construir una "cadena" de la siguiente manera:
G - BH --- XQ
Si luego se compara 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 en B, pero B cifra en E) G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (H aparentemente se cifra en H) G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (G cifra en D, pero B cifra en G) G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (B cifra en H, pero H cifra en 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 encripta a Q, pero Q encripta a W) G - BH --- XQABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (X cifra en V, pero Q cifra en 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 codifica a B, pero B codifica a T)XQ G - BH --->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible-XQ G - BH ->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (X cifra en B, pero B cifra en V)--XQ G - BH->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible--- XQ G - BH->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (X cifra en D, pero B cifra en X)H --- XQ G - B->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (Q codifica a G, pero G codifica a V)-H --- XQ G - B->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (H cifra en B, pero Q cifra en H)BH --- XQ G ->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible (tenga en cuenta que G codifica a X, X codifica a la propiedad G)-BH --- XQ G->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es imposible (B cifra en B)--BH --- XQ G->ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... es posible
El llamado "alfabeto de rueda final" ya está limitado a solo nueve posibilidades, simplemente estableciendo una cadena de letras de cinco letras derivadas de tan solo cuatro pares de mensajes. Hut 8 ahora intentaría encajar otras cadenas de letras, unas sin letras en común con la primera cadena, en estos nueve alfabetos candidatos de rueda final.
Eventualmente, esperarán quedarse con un solo candidato, tal vez luciendo así:
NUPF ---- A - D --- O--XQ G - BH->ABCDEFGHIJKLMNOPQRSTU VWXYZ
No sólo esto, sino que tal alfabeto de rueda final fuerza a la conclusión de que la rueda final es de hecho "Rotor I". Esto se debe a que "Rotor II" habría provocado una rotación en el medio de la rueda 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, se excluyen todas las demás pérdidas de balón posibles en la mitad de la rueda. 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 distintas ruedas Enigma tuvieran distintos 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 del extremo.
Rueda intermedia
Una vez que se identifica la rueda del extremo, estos mismos principios pueden extenderse para manejar el rotor del medio, aunque con la complejidad adicional de que la búsqueda es de superposiciones en pares de mensajes que comparten solo la primera letra del indicador, y que las superposiciones podrían por lo tanto ocurrir en con 650 caracteres de diferencia. [23]
La carga de trabajo de hacer esto va más allá del trabajo manual, por lo que BP marcó los mensajes en tarjetas de 80 columnas y usó máquinas Hollerith para buscar repeticiones de tetragramas o mejores. Eso les dijo qué banburies instalar en las cajas de luz (y con qué superposición) para evaluar todo el patrón de repetición.
Armado con un conjunto de superposiciones probables 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, la probable rueda derecha y la rueda central darían un conjunto de carreras de bombe para el día, que se reducirían significativamente de las 336 posibles.
Ver también
- Análisis secuencial
Referencias
- ^ Simpson, Edward , Capítulo 13, Introducción a Banburismus y Capítulo 38, Banburismus revisitado: profundidades y Bayes . En Copeland, B. Jack ; Bowen, Jonathan P .; Wilson, Robin ; Sprevak, Mark (2017). La guía de Turing . Prensa de la Universidad de Oxford . ISBN 978-0198747826.
- ↑ Aunque se afirma con frecuencia que este método es un ejemplo de inferencia bayesiana , Donald Gilles ha argumentado ( Gilles, Donald (1990), "La función de ponderación de la evidencia de Turing-Good y la medida de Popper de la severidad de una prueba", Br. J. Phil. Sci. , 41 , págs. 143-146), que el proceso no es realmente bayesiano, sino popperiano .
- ^ Hodges, Andrew (1992), Alan Turing: The Enigma , Londres: Vintage, pág. 197, ISBN 978-0-09-911641-7
- ^ Bueno, IJ (1979). "Estudios de Historia de la Probabilidad y Estadística. Trabajo estadístico de XXXVII AM Turing en la Segunda Guerra Mundial". Biometrika . 66 (2): 393–396. doi : 10.1093 / biomet / 66.2.393 . Señor 0548210 .
- ^ Copeland, Jack (2006), "Turingery", en Copeland, B. Jack (ed.), Colossus: The Secrets of Bletchley Park's Codebreaking Computers , Oxford: Oxford University Press, págs. 378–385, ISBN 978-0-19-284055-4
- ^ Copeland, Jack (2004), "Enigma", en Copeland, B. Jack (ed.), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma , Oxford: Oxford University Press, pág. 261, ISBN 0-19-825080-0
- ^ Mahón (1945) p. 17
- ^ Murray, Joan (1992), "Choza 8 y Enigma naval, Parte I", en Hinsley, FH ; Stripp, Alan (eds.), Codebreakers: The inside story of Bletchley Park , Oxford: Oxford University Press (publicado en 1993), p. 118, ISBN 978-0-19-280132-6
- ^ Mahón (1945) p. 95
- ^ Bueno (1993) p. 155
- ^ Bueno (1993) p. 157
- ↑ Alexander ( c. 1945) p. 94
- ^ Mason, Geoffrey B (c. 2004). "Historias de servicio de los buques de guerra de la Marina Real en la Segunda Guerra Mundial" . HMS Griffin - Destructor de clase G . Consultado el 28 de octubre de 2009 .
- ^ Mahón (1945) p. 22
- ↑ a b Mahon (1945) p. 26
- ^ Churchhouse, RF (2002). Códigos y cifrados: Julio César, el Enigma e Internet . Cambridge: Editorial Cambridge University Press. pag. 34 . ISBN 0-521-00890-5.
- ↑ Alexander ( c. 1945) p. 96
- ^ Venta, Tony . "Banburismus" . Diccionario criptográfico de Bletchley Park de 1944 . La Administración Nacional de Archivos y Registros (NARA) 8601 Adelphi Road, College Park, Maryland . Consultado el 15 de noviembre de 2009 .
- ^ Hosgood (2008) 2.3 Búsqueda de "evidencia"
- ^ Hosgood (2008) 4.2.2 Categorías de mensajes
- ^ Joan Clarke trabajó como Banburist. Señor, Lynsey Ann (2008). "Joan Elisabeth Lowther Clarke Murray" . proyecto de honores . Universidad de St Andrews. Archivado desde el original el 7 de junio de 2011 . Consultado el 16 de noviembre de 2009 .
- ^ Hosgood (2008) 7.0 Scritchmus
- ^ Hosgood (2008) 6.0 El alfabeto de la rueda central
Bibliografía
- Alexander, C. Hugh O'D. (c. 1945), Historia criptográfica del trabajo sobre el enigma naval alemán , Archivos Nacionales, Kew, Referencia HW 25/1
- Good, Jack (1993), "Enigma and Fish", en Hinsley, FH ; Stripp, Alan (eds.), Codebreakers: The inside story of Bletchley Park , Oxford: Oxford University Press, ISBN 978-0-19-280132-6
- Hosgood, Steven (2008). "Todo lo que siempre quiso saber sobre el banburismo pero tenía miedo de preguntar" . Archivado desde el original el 9 de marzo de 2016 . Consultado el 9 de marzo de 2016 .
- MacKay, David JC Teoría de la información, inferencia y algoritmos de aprendizaje Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1 . Este libro de texto en línea incluye un capítulo que discute los aspectos de la teoría de la información del Banburismus.
- Mahón, AP (1945). "La historia de Hut Eight 1939 - 1945" . Consultado el 21 de octubre de 2009 .
Otras lecturas
- Sebag-Montefiore, Hugh . Enigma: la batalla por el código . Cassell Military Paperbacks, Londres, 2004. ISBN 978-1-4072-2129-8
enlaces externos
- El diccionario criptográfico de Bletchley Park de 1944
- "Todo lo que siempre quiso saber sobre el banburismo pero tenía miedo de preguntar" : todo el procedimiento investigado en detalle, con un ejemplo trabajado.