Criptoanálisis del cifrado de Lorenz - Cryptanalysis of the Lorenz cipher

El criptoanálisis del cifrado de Lorenz fue el proceso que permitió a los británicos leer mensajes del ejército alemán de alto nivel durante la Segunda Guerra Mundial . El Código del Gobierno Británico y la Escuela de Cifrado (GC&CS) en Bletchley Park descifraron muchas comunicaciones entre el Oberkommando der Wehrmacht (OKW, Alto Mando Alemán) en Berlín y sus comandos del ejército en toda la Europa ocupada, algunas de las cuales estaban firmadas como "Adolf Hitler, Führer". Se trataba de transmisiones de radio que no eran de Morse interceptadas y que habían sido cifradas por los adjuntos de cifrado del flujo del rotor de la teleimpresora Lorenz SZ . Los descifrados de este tráfico se convirtieron en una fuente importante de inteligencia " Ultra ", que contribuyó significativamente a la victoria de los Aliados.

Para sus mensajes secretos de alto nivel, las fuerzas armadas alemanas cifraron cada carácter utilizando varias máquinas de cifrado de flujo Geheimschreiber (escritor secreto) en línea en ambos extremos de un enlace de telégrafo utilizando el Alfabeto de Telegrafía Internacional No. 2 de 5 bits (ITA2). Posteriormente se descubrió que estas máquinas eran la Lorenz SZ (SZ para Schlüssel-Zusatz , que significa "accesorio de cifrado") para el ejército, la Siemens y Halske T52 para la fuerza aérea y la Siemens T43, que fue poco utilizada y nunca fue rota por la Aliados.

Bletchley Park descifra los mensajes cifrados con las máquinas Enigma y reveló que los alemanes llamaron "Sägefisch" (pez sierra) a uno de sus sistemas de transmisión de teleimpresores inalámbricos , lo que llevó a los criptógrafos británicos a referirse al tráfico radiotelegráfico alemán cifrado como " Pez ". " Tunny " (pez atún) fue el nombre que se le dio al primer enlace no Morse, y posteriormente se utilizó para las máquinas de cifrado y su tráfico.

Al igual que con el criptoanálisis completamente separado del Enigma , fueron las deficiencias operativas alemanas las que permitieron el diagnóstico inicial del sistema y una forma de descifrarlo. A diferencia de Enigma, ninguna máquina física llegó a manos aliadas hasta el final de la guerra en Europa, mucho después de que se estableciera el descifrado total. Los problemas para descifrar los mensajes de Tunny llevaron al desarrollo de " Colossus ", la primera computadora digital programable y electrónica del mundo, diez de las cuales estaban en uso al final de la guerra, momento en el que alrededor del 90% de los mensajes seleccionados de Tunny estaban siendo descifrados. en Bletchley Park.

Albert W. Small, un criptoanalista del Cuerpo de Señales del Ejército de EE. UU. Que fue adscrito a Bletchley Park y trabajó en Tunny, dijo en su informe de diciembre de 1944 a Arlington Hall que:

Las soluciones diarias de los mensajes de Fish en GC&CS reflejan un trasfondo del genio matemático británico, una excelente capacidad de ingeniería y un sólido sentido común. Cada uno de estos ha sido un factor necesario. Cada uno podría haber sido sobreenfatizado o subestimado en detrimento de las soluciones; un hecho notable es que la fusión de los elementos aparentemente ha estado en perfecta proporción. El resultado es una contribución sobresaliente a la ciencia criptoanalítica.

Las máquinas alemanas de Tunny

Las máquinas Lorenz SZ tenían 12 ruedas cada una con un número diferente de levas (o "pasadores").

OKW / nombre de la rueda Chi	A	B	C	D	mi	F	GRAMO	H	I	J	K	L
Nombre de la rueda BP	${\ Displaystyle \ psi}$1	${\ Displaystyle \ psi}$2	${\ Displaystyle \ psi}$3	${\ Displaystyle \ psi}$4	${\ Displaystyle \ psi}$5	${\ Displaystyle \ mu}$37	${\ Displaystyle \ mu}$61	${\ Displaystyle \ chi}$1	${\ Displaystyle \ chi}$2	${\ Displaystyle \ chi}$3	${\ Displaystyle \ chi}$4	${\ Displaystyle \ chi}$5
Número de levas (pines)	43	47	51	53	59	37	61	41	31	29	26	23

Los adjuntos de cifrado Lorenz SZ implementaron un cifrado de flujo Vernam , utilizando una compleja matriz de doce ruedas que entregaron lo que debería haber sido un número pseudoaleatorio criptográficamente seguro como un flujo de claves . El flujo de claves se combinó con el texto plano para producir el texto cifrado en el extremo de transmisión utilizando la función exclusiva o (XOR) . En el extremo receptor, una máquina configurada de forma idéntica produjo el mismo flujo de claves que se combinó con el texto cifrado para producir el texto sin formato, es decir, el sistema implementó un algoritmo de clave simétrica .

El flujo de claves fue generado por diez de las doce ruedas. Esto fue un producto de XOR-ing el carácter de 5 bits generado por las cinco ruedas de la derecha, las ruedas chi ( ) y las cinco de la izquierda, las ruedas psi ( ). Las ruedas chi siempre se movían en una posición por cada carácter de texto cifrado entrante, pero las ruedas psi no. ${\ Displaystyle \ chi}$${\ Displaystyle \ psi}$

Levas en las ruedas 9 y 10 que muestran sus posiciones elevadas (activas) y bajas (inactivas). Una leva activa invirtió el valor de un bit ( • → x y x → • ).

Las dos ruedas centrales mu ( ) o "motor" determinaban si las ruedas psi giraban o no con un nuevo carácter. Después de cifrar cada letra, las cinco ruedas psi se movieron o se quedaron quietas y se volvió a utilizar la misma letra de la psi-key. Al igual que las ruedas chi , la rueda _{61 se} movía después de cada personaje. Cuando ₆₁ tenía la leva en la posición activa y así generó x (antes de moverse) _{37 se} movió una vez: cuando la leva estaba en la posición inactiva (antes de moverse) ₃₇ y las ruedas psi se quedaron quietas. En todas las máquinas, excepto en las primeras, hubo un factor adicional que influyó en el movimiento o no de las ruedas psi . Estos eran de cuatro tipos diferentes y se llamaron "Limitaciones" en Bletchley Park. Todos involucraban algún aspecto de las posiciones anteriores de las ruedas de la máquina. ${\ Displaystyle \ mu}$${\ Displaystyle \ mu}$${\ Displaystyle \ mu}$${\ Displaystyle \ mu}$${\ Displaystyle \ mu}$

El número de levas en el conjunto de doce ruedas de los SZ42 máquinas totalizaron 501 y fueron co-prime entre sí, dando un tiempo extremadamente largo período antes de la secuencia de teclas repetido. Cada leva podría estar en una posición elevada, en cuyo caso contribuía x a la lógica del sistema, invirtiendo el valor de un bit, o en la posición bajada, en cuyo caso generaba • . El número total posible de patrones de levas elevadas fue de 2 ^501, que es un número astronómicamente grande. En la práctica, sin embargo, aproximadamente la mitad de las levas de cada rueda estaban en posición elevada. Más tarde, los alemanes se dieron cuenta de que si el número de levas elevadas no se acercaba mucho al 50%, habría corridas de x sy • s, una debilidad criptográfica.

El proceso de determinar cuáles de las 501 levas estaban en posición elevada se denominó "rotura de ruedas" en Bletchley Park. Derivar las posiciones de inicio de las ruedas para una transmisión en particular se denominó "ajuste de la rueda" o simplemente "ajuste". El hecho de que las ruedas psi se movieran todas juntas, pero no con cada carácter de entrada, fue una de las principales debilidades de las máquinas que contribuyeron al éxito criptoanalítico británico.

Una máquina de cifrado Lorenz SZ42 con sus cubiertas retiradas en el Museo Nacional de Computación en Bletchley Park

Telegrafía segura

La telegrafía electromecánica se desarrolló en las décadas de 1830 y 1840, mucho antes de la telefonía , y operaba en todo el mundo en la época de la Segunda Guerra Mundial . Un extenso sistema de cables vinculados a sitios dentro y entre países, con un voltaje estándar de -80 V que indica una "marca" y +80 V que indica un "espacio". Cuando la transmisión por cable se volvió impracticable o inconveniente, como para las unidades móviles del ejército alemán, se utilizó la transmisión por radio.

Las teleimpresoras en cada extremo del circuito consistían en un teclado y un mecanismo de impresión, y muy a menudo un mecanismo de lectura y perforación de cinta de papel perforada de cinco orificios . Cuando se usa en línea , al presionar una tecla alfabética en el extremo de transmisión, el carácter relevante se imprime en el extremo de recepción. Sin embargo, habitualmente el sistema de comunicación implicaba que el operador de transmisión preparaba un conjunto de mensajes fuera de línea pinchándolos en una cinta de papel y luego se conectaba en línea solo para la transmisión de los mensajes grabados en la cinta. Por lo general, el sistema enviaría unos diez caracteres por segundo y, por lo tanto, ocuparía la línea o el canal de radio durante un período de tiempo más corto que para la escritura en línea.

Los caracteres del mensaje fueron representados por los códigos del Alfabeto de Telegrafía Internacional No. 2 ( ITA2 ). El medio de transmisión, ya sea por cable o por radio, utilizó comunicación serial asíncrona con cada carácter señalado por un impulso de inicio (espacio), 5 impulsos de datos y 1½ impulsos de parada (marca). En Bletchley Park, los impulsos marcados se representaban con x("cruz") y los impulsos espaciales con •("punto"). Por ejemplo, la letra "H" se codificaría como ••x•x.

Los caracteres de cambio de figura (FIGS) y cambio de letra (LETRS) determinaron cómo el extremo receptor interpretó la cadena de caracteres hasta el siguiente carácter de cambio. Debido al peligro de que se corrompa un carácter de cambio, algunos operadores escribirían un par de caracteres de cambio al cambiar de letras a números o viceversa . Entonces, escribirían 55M88 para representar un punto. Esta duplicación de caracteres fue muy útil para el criptoanálisis estadístico utilizado en Bletchley Park. Después del cifrado, los caracteres de turno no tenían un significado especial.

La velocidad de transmisión de un mensaje radiotelegráfico era tres o cuatro veces mayor que la del código Morse y un oyente humano no podía interpretarlo. Sin embargo, una teleimpresora estándar produciría el texto del mensaje. El archivo adjunto de cifrado de Lorenz cambió el texto sin formato del mensaje en texto cifrado que no era interpretable para quienes no tenían una máquina idéntica configurada de forma idéntica. Este fue el desafío al que se enfrentaron los descifradores de códigos de Bletchley Park.

Interceptación

La interceptación de las transmisiones Tunny presentó problemas sustanciales. Como los transmisores eran direccionales, la mayoría de las señales eran bastante débiles en los receptores de Gran Bretaña. Además, se utilizaron unas 25 frecuencias diferentes para estas transmisiones, y la frecuencia a veces se cambiaba a la mitad. Después del descubrimiento inicial de las señales que no son Morse en 1940, se instaló una estación de interceptación de radio llamada Foreign Office Research and Development Establishment en una colina en Ivy Farm en Knockholt en Kent, específicamente para interceptar este tráfico. El centro estaba dirigido por Harold Kenworthy, tenía 30 receptores y empleaba a unos 600 empleados. Entró en pleno funcionamiento a principios de 1943.

Una cinta de 12 milímetros (0,47 pulgadas) de ancho, producida por un ondulador similar a los utilizados durante la Segunda Guerra Mundial para el tráfico telegráfico inalámbrico 'Tunny' interceptado en Knockholt, para su traducción a caracteres ITA2 que se enviarán a Bletchley Park.

Debido a que un solo carácter perdido o dañado podía hacer imposible el descifrado, se requería la mayor precisión. La tecnología onduladora utilizada para registrar los impulsos se había desarrollado originalmente para Morse de alta velocidad. Produjo un registro visible de los impulsos en una cinta de papel estrecha. Esto fue leído luego por personas empleadas como "lectores de resbalones" que interpretaron los picos y valles como las marcas y espacios de los caracteres ITA2. Luego se produjo una cinta de papel perforada para su transmisión telegráfica a Bletchley Park, donde fue perforada.

El cifrado de Vernam

El cifrado Vernam implementado por las máquinas Lorenz SZ utiliza la función booleana "exclusiva o" (XOR) , simbolizada por ⊕ y verbalizada como "A o B pero no ambas". Esto está representado por la siguiente tabla de verdad , donde x representa "verdadero" y • representa "falso".

Otros nombres para esta función son: disyunción exclusiva, no igual (NEQ) y suma de módulo 2 (sin "llevar") y resta (sin "pedir prestado"). La suma y la resta del módulo 2 son idénticas. Algunas descripciones del descifrado de Tunny se refieren a la suma y otras a la diferenciación, es decir, a la resta, pero significan lo mismo. El operador XOR es asociativo y conmutativo .

La reciprocidad es una característica deseable de un cifrado de máquina, de modo que la misma máquina con la misma configuración se puede utilizar para cifrar o para descifrar. El cifrado Vernam logra esto, ya que la combinación de la secuencia de caracteres de texto sin formato con la secuencia de claves produce el texto cifrado, y la combinación de la misma clave con el texto cifrado regenera el texto sin formato.

Simbólicamente:

Texto sin formato ⊕ Clave = Texto cifrado

y

Texto cifrado ⊕ Clave = Texto sin formato

La idea original de Vernam era utilizar la práctica de la telegrafía convencional, con una cinta de papel del texto plano combinada con una cinta de papel de la clave en el extremo de transmisión y una cinta de clave idéntica combinada con la señal de texto cifrado en el extremo de recepción. Cada par de cintas clave habría sido único (una cinta de una sola vez ), pero generar y distribuir tales cintas presentaba considerables dificultades prácticas. En la década de 1920, cuatro hombres de diferentes países inventaron las máquinas de cifrado Vernam de rotor para producir un flujo de claves para actuar en lugar de una cinta de claves. El Lorenz SZ40 / 42 fue uno de ellos.

Características de seguridad

Una distribución típica de letras en un texto en inglés . El cifrado inadecuado puede no enmascarar suficientemente la naturaleza no uniforme de la distribución. Esta propiedad se aprovechó en el criptoanálisis del cifrado de Lorenz debilitando parte de la clave.

Un cifrado de sustitución monoalfabético como el cifrado Caesar puede romperse fácilmente, dada una cantidad razonable de texto cifrado. Esto se logra mediante el análisis de frecuencia de las diferentes letras del texto cifrado y comparando el resultado con la distribución de frecuencia de letras conocida del texto sin formato.

Con un cifrado polialfabético , hay un alfabeto de sustitución diferente para cada carácter sucesivo. Entonces, un análisis de frecuencia muestra una distribución aproximadamente uniforme , como la obtenida de un generador de números (pseudo) aleatorios . Sin embargo, debido a que un juego de ruedas de Lorenz giraba con cada carácter mientras que el otro no, la máquina no disfrazó el patrón en el uso de caracteres adyacentes en el texto llano alemán. Alan Turing descubrió esta debilidad e inventó la técnica de diferenciación que se describe a continuación para aprovecharla.

El patrón de cuáles de las levas estaban en la posición elevada y cuál en la posición baja se cambiaba diariamente en las ruedas del motor ( 37 y 61). Los patrones de las levas de la rueda chi se cambiaron inicialmente mensualmente. Los patrones de la rueda psi se cambiaron trimestralmente hasta octubre de 1942 cuando la frecuencia se incrementó a mensual, y luego a diaria el 1 de agosto de 1944, cuando la frecuencia de cambio de los patrones de la rueda chi también se cambió a diaria. ${\ Displaystyle \ mu}$${\ Displaystyle \ mu}$

El número de posiciones iniciales de las ruedas fue 43 × 47 × 51 × 53 × 59 × 37 × 61 × 41 × 31 × 29 × 26 × 23, que es aproximadamente 1.6 × 10 ¹⁹ (16 mil millones de billones), un número demasiado grande para que los criptoanalistas intenten un " ataque de fuerza bruta " exhaustivo . A veces, los operadores de Lorenz desobedecían las instrucciones y se transmitían dos mensajes con las mismas posiciones de inicio, fenómeno denominado "profundidad" . El método por el cual el operador de transmisión le dijo al operador de recepción los ajustes de la rueda que había elegido para el mensaje que estaba a punto de transmitir se denominó "indicador" en Bletchley Park.

En agosto de 1942, los inicios de fórmulas de los mensajes, que eran útiles para los criptoanalistas, fueron reemplazados por algún texto irrelevante, lo que dificultó un poco la identificación del verdadero mensaje. Este nuevo material se denominó quatsch (en alemán, "tonterías") en Bletchley Park.

Durante la fase de las transmisiones experimentales, el indicador constaba de doce apellidos alemanes, cuyas letras iniciales indicaban la posición a la que los operadores giraban las doce ruedas. Además de mostrar cuándo dos transmisiones estaban completamente en profundidad, también permitió la identificación de profundidades parciales donde dos indicadores diferían solo en una o dos posiciones de las ruedas. A partir de octubre de 1942, el sistema indicador cambió al operador de envío que transmite las letras no cifradas QEP seguidas de un número de dos dígitos. Este número se tomó en serie de un libro de códigos que se había enviado a ambos operadores y proporcionaba, para cada número QEP, los ajustes de las doce ruedas. Los libros fueron reemplazados cuando se habían agotado, pero entre reemplazos, las profundidades completas podían identificarse mediante la reutilización de un número QEP en un enlace Tunny en particular.

Diagnóstico

El primer paso para descifrar un nuevo cifrado es diagnosticar la lógica de los procesos de cifrado y descifrado. En el caso de una máquina de cifrado como Tunny, esto implicó establecer la estructura lógica y, por lo tanto, el funcionamiento de la máquina. Esto se logró sin el beneficio de ver una máquina, lo que solo sucedió en 1945, poco antes de la victoria aliada en Europa. El sistema de cifrado fue muy bueno para garantizar que el texto cifrado Z no contuviera características estadísticas, periódicas o lingüísticas para distinguirlo del azar. Sin embargo, esto no se aplicó a K , χ , ψ ' y D , que era la debilidad que significaba que las teclas Tunny podían resolverse.

Durante el período experimental de las transmisiones de Tunny cuando el sistema indicador de doce letras estaba en uso, John Tiltman , el criptoanalista veterano y notablemente dotado de Bletchley Park, estudió los textos cifrados de Tunny e identificó que usaban un cifrado Vernam.

Cuando dos transmisiones ( a y b ) utilizan la misma clave, es decir, son en profundidad, la combinación de ellos elimina el efecto de la llave. Llamemos a los dos textos cifrados Za y Zb , la clave K y los dos textos planos Pa y Pb . Entonces tenemos:

Za ⊕ Zb = Pa ⊕ Pb

Si se pueden resolver los dos textos sin formato, la clave se puede recuperar de cualquier par de texto cifrado-texto sin formato, por ejemplo:

Za ⊕ Pa = K o
Zb ⊕ Pb = K

El 31 de agosto de 1941 se recibieron dos mensajes largos que tenían el mismo indicador HQIBPEXEZMUG. Los primeros siete caracteres de estos dos textos cifrados eran iguales, pero el segundo mensaje era más corto. Los primeros 15 caracteres de los dos mensajes fueron los siguientes (en la interpretación de Bletchley Park):

John Tiltman probó varias piezas probables de texto sin formato, es decir, un "pesebre" , contra la cadena Za ⊕ Zb y descubrió que el primer mensaje de texto sin formato comenzaba con la palabra alemana SPRUCHNUMMER (número de mensaje). En el segundo texto plano, el operador había utilizado la abreviatura común NR para NUMMER . Había más abreviaturas en el segundo mensaje y la puntuación a veces difería. Esto permitió a Tiltman resolver, durante diez días, el texto sin formato de ambos mensajes, ya que una secuencia de caracteres de texto sin formato descubiertos en Pa , podría luego ser juzgada contra Pb y viceversa . A su vez, esto produjo casi 4000 caracteres de clave.

Los miembros de la Sección de Investigación trabajaron en esta clave para tratar de derivar una descripción matemática del proceso de generación de claves, pero sin éxito. Bill Tutte se unió a la sección en octubre de 1941 y se le asignó la tarea. Había leído química y matemáticas en el Trinity College de Cambridge antes de ser reclutado para Bletchley Park. En su curso de formación, le habían enseñado la técnica de examen Kasiski de escribir una clave en un papel cuadriculado con una nueva fila después de un número definido de caracteres que se sospechaba que era la frecuencia de repetición de la clave. Si este número fuera correcto, las columnas de la matriz mostrarían más repeticiones de secuencias de caracteres que el azar por sí solo.

Tutte pensó que era posible que, en lugar de utilizar esta técnica en todas las letras de la clave, que probablemente tuvieran una frecuencia de repetición prolongada, valdría la pena intentarlo en la secuencia formada tomando solo un impulso (bit) de cada letra, con el argumento de que " la parte podría ser criptográficamente más simple que el todo ". Dado que los indicadores de Tunny usaban 25 letras (excluyendo la J) para 11 de las posiciones, pero solo 23 letras para la duodécima, probó la técnica de Kasiski en el primer impulso de los caracteres clave usando una repetición de 25 × 23 = 575. Esto hizo No produjo una gran cantidad de repeticiones en las columnas, pero Tutte sí observó el fenómeno en diagonal. Por lo tanto, volvió a intentarlo con 574, que se repite en las columnas. Reconociendo que los factores primos de este número son 2, 7 y 41, lo intentó nuevamente con un punto de 41 y " obtuvo un rectángulo de puntos y cruces que estaba repleto de repeticiones ".

Sin embargo, estaba claro que la secuencia de primeros impulsos era más complicada que la producida por una sola rueda de 41 posiciones. Tutte llamó a este componente de la clave χ ₁ ( chi ). Pensó que había otro componente, que era XOR-ed con esto, que no siempre cambiaba con cada nuevo carácter, y que este era el producto de una rueda que llamó ψ ₁ ( psi ). Lo mismo se aplica a cada uno de los cinco impulsos, indicados aquí mediante subíndices. Entonces, para un solo carácter, la clave K constaba de dos componentes:

K = χ ⊕ ψ .

La secuencia real de caracteres añadidos por las ruedas psi , incluidos los que no avanzan, se denominó psi extendido y se simbolizó con ψ ′.

K = χ ⊕ ψ ′ .

La derivación de Tutte del componente ψ fue posible por el hecho de que era más probable que los puntos fueran seguidos por puntos y que los cruces fueran seguidos por cruces. Esto fue producto de una debilidad en la configuración clave alemana, que luego detuvieron. Una vez que Tutte hizo este avance, el resto de la Sección de Investigación se unió para estudiar los otros impulsos, y se estableció que las cinco ruedas ψ se movían juntas bajo el control de dos ruedas μ ( mu o "motor").

Diagnosticar el funcionamiento de la máquina Tunny de esta manera fue un logro criptoanalítico verdaderamente notable, y se describió cuando Tutte fue admitido como Oficial de la Orden de Canadá en octubre de 2001, como " una de las mayores hazañas intelectuales de la Segunda Guerra Mundial ".

Turingery

En julio de 1942, Alan Turing pasó algunas semanas en la Sección de Investigación. Se había interesado en el problema de separar a Tunny de las llaves que se habían obtenido de las profundidades. En julio, desarrolló un método para derivar los ajustes de la leva ("rotura de rueda") a partir de una longitud de llave. Se hizo conocido como "Turingery" (llamado en broma "Turingismus" por Peter Ericsson, Peter Hilton y Donald Michie ) e introdujo el importante método de "diferenciación" en el que se basaba gran parte del resto de la resolución de claves Tunny en ausencia de profundidades. .

Diferenciando

Se estaba buscando un proceso que manipulara el texto cifrado o la clave para producir una distribución de frecuencia de caracteres que se apartara de la uniformidad que el proceso de cifrado pretendía lograr. Turing descubrió que la combinación XOR de los valores de caracteres sucesivos (adyacentes) en un flujo de texto cifrado o clave, enfatiza cualquier desviación de una distribución uniforme. La corriente resultante se denominó diferencia (simbolizada por la letra griega "delta" Δ ) porque XOR es lo mismo que la resta de módulo 2. Entonces, para un flujo de caracteres S , la diferencia ΔS se obtuvo de la siguiente manera, donde el subrayado indica el carácter siguiente:

ΔS = S ⊕ S

El flujo S puede ser texto cifrado Z , texto plano P , clave K o cualquiera de sus dos componentes χ y ψ . La relación entre estos elementos todavía se aplica cuando se diferencian. Por ejemplo, además de:

K = χ ⊕ ψ

Es el caso que:

ΔK = Δ χ ⊕ Δ ψ

De manera similar para el texto cifrado, el texto sin formato y los componentes clave:

ΔZ = ΔP ⊕ Δ χ ⊕ Δ ψ

Entonces:

ΔP = ΔZ ⊕ Δ χ ⊕ Δ ψ

La razón por la que la diferenciación proporcionó una forma de entrar en Tunny fue que, aunque la distribución de frecuencia de los caracteres en el texto cifrado no se podía distinguir de un flujo aleatorio, lo mismo no era cierto para una versión del texto cifrado a partir del cual el elemento chi de la clave había ha sido eliminado. Esto se debe a que, donde el texto plano contiene un carácter repetido y las ruedas psi no se mueven, el carácter psi diferenciado ( Δ ψ ) sería el carácter nulo (' / ' en Bletchley Park). Cuando XOR-ed con cualquier carácter, este carácter no tiene ningún efecto, por lo que en estas circunstancias, ΔK = Δ χ . El texto cifrado modificado por la eliminación del componente chi de la clave se denominó deci D en Bletchley Park, y el proceso de eliminación como "des- chi -ing". De manera similar, para la eliminación del componente psi que se conocía como " depsi -ing" (o "suspiro profundo" cuando era particularmente difícil).

Entonces, el delta de chi ΔD fue:

ΔD = ΔZ ⊕ Δ χ

Los caracteres repetidos en el texto plano fueron más frecuentes debido a las características del alemán (EE, TT, LL y SS son relativamente comunes) y porque los telegrafistas repetían con frecuencia los caracteres de cambio de cifras y de letras como su pérdida en una transmisión telegráfica ordinaria. podría dar lugar a un galimatías.

Para citar el Informe general sobre Tunny:

Turingery introdujo el principio de que la clave diferenciada en uno, ahora llamada ΔΚ , podría proporcionar información que no se puede obtener de la clave ordinaria. Este principio Δ iba a ser la base fundamental de casi todos los métodos estadísticos de frenado y ajuste de ruedas.

Se aplicó diferenciación a cada uno de los impulsos de los caracteres codificados ITA2. Entonces, para el primer impulso, que fue cifrado por las ruedas χ ₁ y ψ ₁ , diferenciadas en uno:

ΔK ₁ = K ₁ ⊕ K ₁

Y para el segundo impulso:

ΔK ₂ = K ₂ ⊕ K ₂

Etcétera.

La periodicidad de las ruedas chi y psi para cada impulso (41 y 43 respectivamente para el primer impulso) también se refleja en el patrón de ΔK . Sin embargo, dado que las ruedas psi no avanzaron para cada carácter de entrada, como lo hicieron las ruedas chi , no fue simplemente una repetición del patrón cada 41 × 43 = 1763 caracteres para ΔK ₁ , sino una secuencia más compleja.

El método de Turing

El método de Turing de derivar los ajustes de las levas de las ruedas a partir de una longitud de llave obtenida de una profundidad, implicaba un proceso iterativo . Dado que el carácter delta psi era el carácter nulo ' / ' la mitad del tiempo en promedio, una suposición de que ΔK  =  Δ χ tenía una probabilidad del 50% de ser correcta. El proceso comenzó tratando un carácter ΔK particular como el Δ χ para esa posición. El patrón resultante putativo poco de x y • para cada chi rueda, se registró en una hoja de papel que contenía tantas columnas como había personajes de la clave, y cinco filas que representan los cinco impulsos de la Delta chi . Dado el conocimiento del trabajo de Tutte, de la periodicidad de cada una de las ruedas, esto permitió la propagación de estos valores en las posiciones adecuadas en el resto de la clave.

También se preparó un juego de cinco hojas, una para cada una de las ruedas chi . Estos contenían un conjunto de columnas que correspondían en número a las levas de la rueda chi apropiada , y se denominaban "jaula". Entonces, la jaula χ ₃ tenía 29 columnas de este tipo. Las sucesivas "suposiciones" de los valores de Δ χ produjeron entonces más valores putativos del estado de la leva. Estos pueden estar de acuerdo o en desacuerdo con los supuestos anteriores, y en estas hojas se hizo un recuento de los acuerdos y desacuerdos. Cuando los desacuerdos superaban sustancialmente a los acuerdos, se asumió que el carácter Δ ψ no era el carácter nulo ' / ', por lo que se descartó el supuesto relevante. Progresivamente, se dedujeron todos los ajustes de las levas de las ruedas chi y, a partir de ellos, los ajustes de las levas de la rueda del motor y psi .

A medida que se desarrolló la experiencia del método, se realizaron mejoras que permitieron que se utilizara con longitudes de clave mucho más cortas que los 500 caracteres originales ".

Testery

The Testery fue la sección en Bletchley Park que realizó la mayor parte del trabajo involucrado en descifrar los mensajes de Tunny. En julio de 1942, el volumen de tráfico se estaba acumulando considerablemente. Por lo tanto, se creó una nueva sección, dirigida por Ralph Tester, de ahí el nombre. El personal estaba formado principalmente por ex miembros de la Sección de Investigación, e incluía a Peter Ericsson, Peter Hilton , Denis Oswald y Jerry Roberts . Los métodos de Testery eran casi completamente manuales, tanto antes como después de la introducción de métodos automatizados en Newmanry para complementar y acelerar su trabajo.

La primera fase del trabajo del Testery se desarrolló de julio a octubre, con el método predominante de descifrado basado en profundidades y profundidades parciales. Sin embargo, después de diez días, el inicio de fórmula de los mensajes fue reemplazado por un quatsch sin sentido , lo que dificultaba el descifrado. No obstante, este período fue productivo, a pesar de que cada descifrado tomó un tiempo considerable. Finalmente, en septiembre, se recibió una profundidad que permitió utilizar el método de rotura de ruedas de Turing, " Turingery ", lo que permitió comenzar a leer el tráfico actual. Se recopilaron amplios datos sobre las características estadísticas del idioma de los mensajes y se amplió la colección de pesebres.

A finales de octubre de 1942, se cerró el enlace Tunny experimental original y se abrieron dos nuevos enlaces (Bacalao y Pulpo). Con estos enlaces y los siguientes, el sistema de indicadores de 12 letras para especificar la clave del mensaje fue reemplazado por el sistema QEP. Esto significaba que solo se podían reconocer las profundidades completas, a partir de números QEP idénticos, lo que condujo a una reducción considerable del tráfico descifrado.

Una vez que el Newmanry entró en funcionamiento en junio de 1943, la naturaleza del trabajo realizado en el Testery cambió, con los descifrados y la rotura de ruedas que ya no dependía de las profundidades.

Atún británico

Un atún británico reconstruido en el Museo Nacional de Computación , Bletchley Park . Emuló las funciones del Lorenz SZ40 / 42, produciendo texto claro impreso a partir de la entrada de texto cifrado.

La llamada "British Tunny Machine" era un dispositivo que reproducía exactamente las funciones de las máquinas SZ40 / 42. Se utilizó para producir el texto sin cifrar alemán a partir de una cinta de texto cifrado, una vez que se determinaron los ajustes de la cámara. El diseño funcional se produjo en Bletchley Park, donde diez Testery Tunnies estaban en uso al final de la guerra. Fue diseñado y construido en el laboratorio de Tommy Flowers en la Estación de Investigación de la Oficina General de Correos en Dollis Hill por Gil Hayward , "Doc" Coombs , Bill Chandler y Sid Broadhurst. Se construyó principalmente a partir de equipos electromecánicos estándar de central telefónica británica , como relés y uniselectores . La entrada y salida se realizó mediante una teleimpresora con cinta de papel de lectura y perforación. Estas máquinas se utilizaron tanto en Testery como más tarde en Newmanry . Dorothy Du Boisson, que era operadora de máquinas y miembro del Servicio Naval Real de Mujeres (Wren), describió que enchufar la configuración era como operar una central telefónica antigua y que recibió descargas eléctricas en el proceso.

Cuando Hayward invitó a Flowers a probar la primera máquina de tunny británica en Dollis Hill escribiendo la frase de prueba estándar: "Ahora es el momento de que todos los buenos hombres acudan en ayuda del grupo", agradeció mucho que el rotor funcionara. se ha configurado para proporcionar la siguiente salida de Wordsworthian :

Se agregaron características adicionales a los British Tunnies para simplificar su operación. Se hicieron más refinamientos para las versiones utilizadas en Newmanry, el tercer Tunny se equipó para producir cintas de chi .

Newmanry

El Newmanry fue una sección creada por Max Newman en diciembre de 1942 para estudiar la posibilidad de ayudar en el trabajo del Testery automatizando partes de los procesos de descifrado de mensajes Tunny. Newman había estado trabajando con Gerry Morgan, jefe de la Sección de Investigación sobre formas de romper a Tunny cuando Bill Tutte se acercó a ellos en noviembre de 1942 con la idea de lo que se conoció como la "ruptura 1 + 2". Se reconoció que esto era factible, pero solo si estaba automatizado.

Newman produjo una especificación funcional de lo que se convertiría en la máquina " Heath Robinson ". Reclutó a la Estación de Investigación de la Oficina de Correos en Dollis Hill y al Dr. CE Wynn-Williams en el Establecimiento de Investigación de Telecomunicaciones (TRE) en Malvern para implementar su idea. El trabajo en el diseño de ingeniería comenzó en enero de 1943 y la primera máquina se entregó en junio. El personal en ese momento estaba formado por Newman, Donald Michie , Jack Good , dos ingenieros y 16 Wrens. Al final de la guerra, el Newmanry contenía tres máquinas Robinson, diez Computadoras Colossus y varios Tunnies británicos. El personal estaba formado por 26 criptógrafos, 28 ingenieros y 275 Wrens.

La automatización de estos procesos requirió el procesamiento de grandes cantidades de cinta de papel perforada, como aquellas en las que se recibieron los mensajes cifrados. La precisión absoluta de estas cintas y su transcripción era esencial, ya que un solo carácter en error podía invalidar o corromper una gran cantidad de trabajo. Jack Good introdujo la máxima "Si no se marca, está mal".

El "asalto 1 + 2"

WT Tutte desarrolló una forma de explotar la falta de uniformidad de los bigramas (letras adyacentes) en el texto llano alemán utilizando el texto cifrado diferenciado y los componentes clave. Su método se denominó "intrusión 1 + 2" o "ataque doble delta". La esencia de este método era encontrar la configuración inicial del componente chi de la clave probando exhaustivamente todas las posiciones de su combinación con el texto cifrado y buscando evidencia de la falta de uniformidad que reflejaba las características del texto plano original. El proceso de rotura de la rueda tenía que haber producido con éxito la configuración actual de la leva para permitir que se generara la secuencia relevante de caracteres de las ruedas chi . Era totalmente impracticable generar los 22 millones de caracteres de las cinco ruedas de chi , por lo que inicialmente se limitó a 41 × 31 = 1271 de las dos primeras.

Dado que para cada uno de los cinco impulsos i :

Z _yo = χ _yo ⊕ ψ _yo ⊕ P _yo

y por lo tanto

P _yo = Z _yo ⊕ χ _yo ⊕ ψ _yo

para los dos primeros impulsos:

(P ₁ ⊕ P ₂ ) = (Z ₁ ⊕ Z ₂ ) ⊕ ( χ ₁ ⊕ χ ₂ ) ⊕ ( ψ ₁ ⊕ ψ ₂ )

Calcular un supuesto P ₁ ⊕ P ₂ de esta manera para cada punto de inicio de la secuencia χ ₁ ⊕ χ ₂ produciría x sy • s con, a largo plazo, una mayor proporción de • s cuando el punto de inicio correcto hubiera sido usado. Sin embargo, Tutte sabía que usar los valores diferenciados (∆) amplificaba este efecto porque cualquier carácter repetido en el texto plano siempre generaría • , y de manera similar ∆ ψ ₁ ⊕ ∆ ψ ₂ generaría • siempre que las ruedas psi no se movieran, y aproximadamente la mitad de las veces que lo hicieron, un 70% en general.

Tutte analizó un texto cifrado descifrado con la versión diferenciada de la función anterior:

(∆Z ₁ ⊕ ∆Z ₂ ) ⊕ (∆ χ ₁ ⊕ ∆ χ ₂ ) ⊕ (∆ ψ ₁ ⊕ ∆ ψ ₂ )

y comprobó que genera • alrededor del 55% de las veces. Dada la naturaleza de la contribución de las ruedas psi , la alineación de la corriente chi con el texto cifrado que dio el conteo más alto de • s de (∆Z ₁ ⊕ ∆Z ₂ ⊕ ∆ χ ₁ ⊕ ∆ χ ₂ ) fue la que era más probable que estuviera en lo cierto. Esta técnica se podría aplicar a cualquier par de impulsos y así proporcionan la base de un enfoque automatizado para la obtención de la de- chi (D) de un texto cifrado, desde el que el psi componente podría ser eliminado por métodos manuales.

Robinsons

Heath Robinson fue la primera máquina producida para automatizar el método 1 + 2 de Tutte. Se le dio el nombre por los Wrens que lo operaron, en honor al dibujante William Heath Robinson , quien dibujó dispositivos mecánicos inmensamente complicados para tareas simples, similar al dibujante estadounidense Rube Goldberg .

La especificación funcional de la máquina fue realizada por Max Newman. El diseño de ingeniería principal fue obra de Frank Morrell en la estación de investigación de la oficina de correos en Dollis Hill en el norte de Londres, con su colega Tommy Flowers diseñando la "Unidad de combinación". El Dr. CE Wynn-Williams, del Centro de Investigación de Telecomunicaciones de Malvern, produjo los contadores de relés y válvulas electrónicas de alta velocidad. La construcción comenzó en enero de 1943, la máquina prototipo se usó en Bletchley Park en junio.

Las partes principales de la máquina fueron:

• un mecanismo de lectura y transporte de cinta (apodado el "armazón de la cama" debido a su parecido con un armazón de cama de metal volcado) que ejecutaba la clave en bucle y las cintas de mensajes a una velocidad de entre 1000 y 2000 caracteres por segundo;
• una unidad de combinación que implementó la lógica del método de Tutte;
• una unidad de conteo que contaba el número de • s, y si excedía un total preestablecido, lo mostraba o imprimía.

El prototipo de máquina fue eficaz a pesar de varias deficiencias graves. La mayoría de estos fueron superados progresivamente en el desarrollo de lo que se conoció como "Old Robinson".

Coloso

Una computadora Mark 2 Colossus. Los operadores de Wren son (de izquierda a derecha) Dorothy Du Boisson y Elsie Booker. El panel de control inclinado de la izquierda se usó para configurar los patrones de los pines en el Lorenz. El transporte de cinta de papel "armazón de cama" está a la derecha.

En 1994, un equipo dirigido por Tony Sale (derecha) comenzó la reconstrucción de un Mark 2 Colossus en Bletchley Park. Aquí, en 2006, Sale y Phil Hayes supervisan la resolución de un mensaje cifrado con la máquina completa.

La experiencia de Tommy Flowers con Heath Robinson, y su experiencia previa y única con las válvulas termoiónicas (tubos de vacío) lo llevaron a darse cuenta de que se podía producir una mejor máquina utilizando la electrónica. En lugar de que el flujo de claves se lea desde una cinta de papel perforada, un flujo de claves generado electrónicamente podría permitir un procesamiento mucho más rápido y flexible. La sugerencia de Flowers de que esto podría lograrse con una máquina que fuera completamente electrónica y contendría entre mil y dos mil válvulas, fue tratada con incredulidad tanto en el Establecimiento de Investigación de Telecomunicaciones como en Bletchley Park, ya que se pensó que sería "demasiado poco confiable para hacer un trabajo útil ". Sin embargo, contó con el apoyo del controlador de investigación de Dollis Hill, W Gordon Radley, e implementó estas ideas para producir Colossus , la primera máquina de computación digital y electrónica del mundo que era totalmente programable, en el notablemente corto tiempo de Diez meses. En esto contó con la asistencia de sus colegas de la estación de investigación de la oficina de correos Dollis Hill : Sidney Broadhurst, William Chandler, Allen Coombs y Harry Fensom .

El prototipo Mark 1 Colossus (Colossus I), con sus 1500 válvulas, entró en funcionamiento en Dollis Hill en diciembre de 1943 y estaba en uso en Bletchley Park en febrero de 1944. Esto procesaba el mensaje a 5000 caracteres por segundo utilizando el impulso de leer la cinta. orificios de la rueda dentada para actuar como la señal del reloj . Rápidamente se hizo evidente que se trataba de un gran avance en el criptoanálisis de Tunny. Se encargaron más máquinas Colossus y se cancelaron los pedidos de más Robinson. Un Mark 2 Colossus mejorado (Colossus II) contenía 2400 válvulas y funcionó por primera vez en Bletchley Park el 1 de junio de 1944, justo a tiempo para los desembarcos del día D en Normandía .

Las partes principales de esta máquina fueron:

• un mecanismo de lectura y transporte de cinta (el "armazón de cama") que ejecuta la cinta de mensajes en un bucle a 5000 caracteres por segundo;
• una unidad que generó el flujo de claves electrónicamente;
• cinco unidades de procesamiento en paralelo que podrían programarse para realizar una amplia gama de operaciones booleanas;
• cinco unidades de conteo, cada una de las cuales contaba el número de • so x s, y si excedía un total preestablecido, lo imprimía.

Las cinco unidades de procesamiento en paralelo permitieron que la "interrupción 1 + 2" de Tutte y otras funciones se ejecutaran a una velocidad efectiva de 25.000 caracteres por segundo mediante el uso de circuitos inventados por Flowers que ahora se llamarían registro de desplazamiento . Donald Michie elaboró ​​un método para usar Colossus para ayudar en la rotura de la rueda, así como para el ajuste de la rueda. Esto luego se implementó en hardware especial en Colossi posteriores.

Un total de diez computadoras Colossus estaban en uso y una undécima estaba en servicio al final de la guerra en Europa ( Día VE ).

Maquinas especiales

Además de las teleimpresoras y perforadoras producidas comercialmente, se construyeron otras máquinas para ayudar en la preparación y verificación de cintas en Newmanry y Testery. El complemento aproximado a mayo de 1945 fue el siguiente.

Pasos en el ajuste de la rueda

Determinar la posición inicial de las ruedas chi ( χ ) requería primero que la configuración de la leva hubiera sido determinada por "rotura de la rueda". Inicialmente, esto se logró mediante el envío de dos mensajes en profundidad .

El número de posiciones de inicio para las dos primeras ruedas, χ ₁ y χ ₂ fue 41 × 31 = 1271. El primer paso fue probar todas estas posiciones de inicio contra la cinta de mensajes. Esta fue la "ruptura 1 + 2" de Tutte que implicó calcular (∆Z ₁ ⊕ ∆Z ₂ ⊕ ∆ χ ₁ ⊕ ∆ χ ₂ ), lo que da un supuesto ( ∆D ₁ ⊕ ∆D ₂ ) - y contar el número de veces esto dio • . Las posiciones iniciales incorrectas darían, en promedio, un recuento de puntos del 50% de la longitud del mensaje. En promedio, el recuento de puntos para un punto de partida correcto sería del 54%, pero inevitablemente hubo una considerable dispersión de valores alrededor de estos promedios.

Tanto Heath Robinson, que se convirtió en lo que se conoció como "Old Robinson", y Colossus fueron diseñados para automatizar este proceso. La teoría estadística permitió la derivación de medidas de qué tan lejos estaba cualquier conteo del 50% esperado con un punto de partida incorrecto para las ruedas chi . Esta medida de desviación de la aleatoriedad se denominó sigma. Los puntos de partida que dieron un recuento de menos de 2,5 × sigma, denominados "total establecido", no se imprimieron. Lo ideal para que una carrera estableciera χ ₁ y χ ₂ era que un solo par de valores de prueba produjera un valor sobresaliente para sigma, identificando así las posiciones de inicio de las dos primeras ruedas chi . A continuación se muestra un ejemplo de la salida de dicha ejecución en un Mark 2 Colossus con sus cinco contadores: a, b, c, dye.

Con un mensaje de tamaño medio, esto tardaría unos ocho minutos. Sin embargo, al utilizar el paralelismo del Mark 2 Colossus, el número de veces que se tuvo que leer el mensaje podría reducirse en un factor de cinco, de 1271 a 255. Habiendo identificado las posibles posiciones de inicio de χ ₁ , χ ₂ , el siguiente paso era tratar de encontrar las posiciones iniciales para las otras ruedas chi . En el ejemplo anterior, hay un solo ajuste de χ ₁ = 36 y χ ₂ = 21 cuyo valor sigma lo hace destacar del resto. Este no fue siempre el caso, y Small enumera 36 ejecuciones adicionales diferentes que podrían probarse de acuerdo con el resultado de la ejecución χ ₁ , χ ₂ . Al principio, las elecciones en este proceso iterativo las tomaba el criptoanalista sentado a la salida de la máquina de escribir y dando instrucciones a los operadores de Wren. Max Newman ideó un árbol de decisiones y luego asignó a Jack Good y Donald Michie la tarea de idear otros. Estos fueron utilizados por los Wrens sin recurrir a los criptoanalistas si se cumplían ciertos criterios.

En el ejemplo anterior de Small, la siguiente carrera fue con las dos primeras ruedas chi colocadas en las posiciones iniciales encontradas y tres exploraciones paralelas separadas de las tres ruedas chi restantes . Tal carrera se denominó "carrera corta" y tomó alrededor de dos minutos.

Entonces, las posiciones de inicio probables para las ruedas chi son: χ ₁ = 36, χ ₂ = 21, χ ₃ = 01, χ ₄ = 19, χ ₅ = 04. Estas tenían que ser verificadas antes del mensaje de chi ( D ) fue pasado al Testery. Esto implicó que Colossus realizara un recuento de la frecuencia de los 32 caracteres en ΔD . Small describe la verificación del recuento de frecuencias de los caracteres ΔD como la "prueba de fuego ", y que prácticamente todos los criptoanalistas y Wren en Newmanry and Testery sabían de memoria el contenido de la siguiente tabla.

Si los puntos de inicio derivados de las ruedas chi pasaron esta prueba, el mensaje de chi -ed se pasó al Testery donde se usaron métodos manuales para derivar los ajustes de psi y motor. Como señaló Small, el trabajo en Newmanry requirió una gran cantidad de ciencia estadística, mientras que en el Testery requirió mucho conocimiento del lenguaje y fue de gran interés como arte. El criptoanalista Jerry Roberts señaló que este trabajo de Testery representaba una carga mayor para el personal que los procesos automatizados en Newmanry.

Ver también

• El Museo Nacional de Computación

notas y referencias

Bibliografía