Cryptology Historical Data on Cryptanalysis of Rotor Machines

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Events

• FRIEDMAN in 1925 successfully cryptanalyzed the HEBERN machine (HCM with 5 rotors). As a consequence the US Army didn't adopt this machine. Later a significantly enhanced device by FRIEDMAN and ROWLETT, the ECM (»Electric Cipher Machine«) was introduced.
  Wikipedia: Friedman, Rowlett.
  
  
• BEURLING in 1931 solved HAGELIN's B21.
  Wikipedia: Beurling.
  
  
• HAGELIN's C line, used in World War II by the US Army as M-209, was cracked by German cryptologists at OKW/Chi led by Erich HÜTTENHAIN. The Americans in 1942 learned this fact from a deciphered Italian Army message. They immediately enhanced the machine. A German 2004 publication [Article in Telepolis] reports that the Germans also cracked the new encryption method. To this end Reinold WEBER developed an electromechanical device—similar to the Polish »bomba« (see below)—that was destroyed at the end of the war. The Norwegian mathematician Ernst SELMER also solved the HAGELIN device during the World War single-handedly.
  Wikipedia: Hüttenhain, Selmer.
  
  
• In the 1930's the Japanese rotor machines of the pre-war era were cracked by the Americans (KULLBACK, ROWLETT), Germans (Werner KUNZE), and British. The Americans also continually cracked the enhanced versions during World War II.
  Wikipedia: Kullback, Rowlett.
  
  
• The Polish cryptologists Marian REJEWSKI, Henryk ZYGALSKI, and Jerzy RÓZICKI successfully cryptanalyzed the commercial Enigma, and from 1934 on also the pre-war version of the Wehrmachts-Enigma. In particular they found the secret inner wiring of all the rotors, without having a real Enigma at their disposition. They found methods for reducing the key space to a manageable size using known or probable plaintext (stereotypical phrases). They constructed the »bomba«, an electromechanical simulation of an essential part of the Enigma mechanism, and used it for exhaustion of the reduced keyspace by parallel processing. At the begin of WWII they handed their knowledge over to the British who were baffled because they themselves (Dillwyn KNOX) had struggled for breaking the Enigma without avail.
  Wikipedia: Rejewski, Zygalski, Rozycki, Knox.
  
  
• During the war the British continually solved the Enigma-encrypted messages, sometimes a bit delayed after the machines had an upgrade. The mathematical masterminds of this enterprise were Gordon WELCHMAN (1906–1985) and Alan TURING (1912–1954). They found several approaches to reduce the size of the keyspace, and constructed devices, the »Turing bombes«, that could exhaustively search the remaining keyspace. All this became publicly known not before 1974. Until then the public and the military believed in the security of Enigma. The German cryptologists knew about the weakness of the machine but didn't know of the British successes. They simply didn't imagine someone could afford and organize such a huge amount of man and machine power as was necessary to take advantage of Enigma's shortcomings.
  Wikipedia: Welchman, Turing.
  
  
• When the German Navy inserted a fourth rotor into their Enigma the capabilities of the British »bombes« were swamped. The US cryptologists took over. NCR (the National Cash Register Company) constructed high-performance devices (»US Navy bombe«) that, after a delay of almost one year, could again break the German Navy messages routinely from the middle of 1944 on. The head of this project was Joseph DESCH.
  Wikipedia: Desch.
  
  
• Based on the British know-how—and thereby indirectly on that of the long ago ousted Polish—the Americans could break several versions of the Enigma in cooperation with the British. This division of work mainly pertained to the construction and configuration of the »bombes« for the different Enigmas.
  
  
• The British (William TUTTE, Maxwell NEWMAN, Tom FLOWERS) in 1943 also constructed »COLOSSUS«, the first working electronic computer, that enabled them to successfully cryptanalyze the »Schlüsselzusatz«, the cryptographic teleprinter by Lorenz (SZ machines, »Tunny«). Other famous mathematicians who worked in this project were P. J. HILTON and I. J. GOOD. After the end of the war the British completely destroyed COLOSSUS, and leaved the fame of inventing the electronic computer to the Amerikans ECKERT and MAUCHLY who built the ENIAC. In November 2007 a reconstructed Colossus was used for solving SZ42 encrypted messages (Cipher Event) in race with customary PCs. The latter were faster, as expected, but the advance was surprisingly small.
  Wikipedia: Tutte, Newman, Hilton, Good, Colossus.
  
  
• The different versions of the Siemens Geheimschreiber (T52, »Sturgeon«) also were at least partially broken by the cryptanalysts of Bletchley Park with the help of specially constructed machines about the end of the war.
  
  
• In Sweden Arne BEURLING already in 1940 cracked the T52. The Swedes had lots of ciphertext because the German teleprinter cables to the occupied Norway run through the neutral Sweden. BEURLING worked only with these ciphertexts. He didn't have a clue about the corresponding cipher machine. This is perhaps the most astonishing individual accomplishment in the history of cryptanalysis. As a consequence the Swedes could read large parts of the strategic messages of the Germans during WWII, and warned the Soviets about Hitler's invasion. The Soviets didn't believe them. This became publicly known not before the 1990's.
  Wikipedia: Beurling.

A comprehensive source for the last item:

• Bengt Beckman: Codebreakers: Arne Beurling and the Swedish Crypto Program During World War II. AMS 2002, ISBN 0-8218-2889-4.

For Tutte's work on the SZ machines see

• Jerry Roberts: Lorenz: Breaking Hitler's Top Secret Code at Bletchley Park. The History Press, Sroud Gloucestershire UK 2017, ISBN 9-780-7509-7885-9.
• Chris Christensen: Review of Lorenz and comments on the work of William Tutte. Cryptologia 42 (2018), 445—466.

A typical phenomenon of WWII is that many countries occupied lots of leading mathematicians as cryptanalysts. Nevertheless in the postwar period up to 1975 cryptology was not an active mathematical research domain. The main reason probably was the fact that the war activities were classified for a long time after the end of the war.

A survey of German mathematicians involved in cryptology during WWII is:

• Frode Weierud, Sandy Zabell: German mathematicians and cryptology in WWII. Cryptologia 44 (2020), 97—171.

A modern efficient approach to analyzing the pre-war version of Enigma (broken by the Polish cryptologists) is in

• George Lasry, Nils Kopal, Arno Wacker: Cryptanalysis of Enigma double indicators with hill climbing. Cryptologia 43 (2019), 267—292.

Effects to the Course of the War

Experts guess that the cryptanalytic successes of the Allies shortened the second World War by one or two years. In particular the allied troups had dared the invasion of Normandy (»D-Day«) only much later.

Also the German cryptanalysts had considerable successes [*]. Nevertheless the Allies were significantly superior in this respect. The reasons can mainly be located in the German organizational disorder:

• The British treated cryptanalysis with top priority (enforced by CHURCHILL), centralized it at Bletchley Park, organized and coordinated it in a professional way, and endowed it with substantial resources, for example up to 10000 persons. The entire project had the codename »ULTRA«, and its very existence was revealed only in 1976.
• In contrast German cryptanalysis suffered from fragmentation, rivalry, and mutual distrust.
  • Navy, Army, and Air Force maintained several independent units for intelligence that along the way also dealt with cryptanalysis.
  • The »Heereswaffenamt« was responsible for the supply of cryptographic equipment. Its cryptologic expertise was minimal.
  • The leading cryptanalysts were employees of the cipher bureau of the High Command (»Oberkommando der Wehrmacht«, OKW/Chi), a staff unit that the officers of the combat troups—in particular in the Prussian tradition—looked at with arrogance. Another unit with substantial skills was the cryptanalytic section of the Ministry for Foreign Affairs, »PersZ«. Its members were civil servants the military had absolutely no respect for.
  • During the war people more and more hesitated admitting errors, especially for fear of the SS whose power increased from day to day. It was more advisible to explain the enemy's knowledge by treason than to admit that the own cipher systems were weak, or even that earlier decisions were erroneous.
  • The German cryptologists knew how the break the Enigmas, and the Siemens and Lorenz encrypting teleprinters. However there are only very few documents or testimonies left. For example Frowein in 1944 showed that the Navy Enigma with 4 rotors might be broken with 25 letters of known plaintext, and that about 80 letters even allowed to derive the rotor wirings. They didn't sense that the allies had the same knowledge and moreover were able to exploit it efficiently.

On the other hand some machines remained unbroken (according to the present state of knowledge).

• The Germans couldn't break the American SIGABA, as well as the British TYPEX that was an improved version of the Enigma.
• On the other hand the Wanderer (»Menzer«) devices that the Germans constructed in the last period of the war and only scarcely brought into use put unsolvable problems to the Allies.

———
[*] Friedrich L. Bauer, Erich Hüttenhain; Entzifferung 1939–1945. Informatik-Spektrum 31/3 (2008), Springer-Verlag

Consequences for the Security of Ciphers

• KERCKHOFFS' principle (1883) is of eminent importance: A cipher must be secure even if the enemy knows its details. Or in other words: The security of a cipher must be granted as long as the key is secret.
  »Il faut qu'il puisse sans inconvéniant tomber entre les mains de l'ennemi.«
  Wikipedia: Auguste KERCKHOFFS VAN NIEUWENHOFF, 1835–1903.
• Another way to state KERCKHOFFS' principle is:

  Parameters that qualify as key must be changeable easily and instantly.

  
  
• Furthermore a cipher must stand cryptanalysis also taking account of operating errors—laxness, neglecting strong instructions, laziness, thoughtlessness.
• The security of rotor machines crucially depends on the complexity of their control logic.

Rotor machines can produce strong ciphers. A modern algorithmic approach (realized as computer simulation) could work as follows (project idea):

• Use 256-letter rotors (for the alphabet of octets).
• Drive them by a decent pseudorandom generator.

Research problem: Find quantitative criteria for the security of such a rotor machine:

1. How does the security depend on the number of rotors?
   These criteria could resemble the criteria for the number of rounds of a bitblock cipher, see Part 2 of these lectures.
2. How does the security depend on the quality of the pseudorandom generator?
   These criteria could resemble the criteria for the quality of bitstream ciphers, see Part 4 of these lectures.