Cryptanalysis of the Lorenz machine

Lorenz key addition SZ 40 (without cover) in the National Cryptological Museum of the USA

The cryptanalysis of the Lorenz machine, code name Tunny ( " tuna "), allowed the British in World War II , the "read along" the top-secret strategic message traffic of the German Wehrmacht . The intelligence information obtained from this, some of which was important for the war effort, was classified by the Allies as "ultra" secret .

prehistory

SZ 42 (approx. 1943, without hood) in Bletchley Park (photo from 2007), on the right a Lorenz telex T32 (approx. 1936)

From June 1941, the German Wehrmacht began to secure their telex connections between the highest command posts by means of a newly developed key machine called Key-Addition 40 (SZ 40). Above the Enigma machine , which is still used for tactical communication, it was used to encrypt strategic communications, especially between the Army High Command (OKH), based in Wünsdorf near Berlin, and the Army High Command (AOK) in cities such as Vienna, Rome and Paris , Athens, Copenhagen, Oslo, Koenigsberg, Riga, Belgrade, Bucharest and Tunis.

Burglary

Sound sample of a radio teletype transmission, called new music in BP

Sound sample of a standard Morse transmission

A typical recording strip, called undulator tape (approx. 12 mm wide and many meters long), as it was used at the time in the British interception stations to record radio telex traffic

As early as the second half of 1940, British listening stations (Y Stations) noticed German telex traffic that was clearly audible from the usual sound of Morse code , and initially nicknamed it new music ("new music") and NoMo for No Morse ("no Morse"). A little later, radio broadcasts of this kind were grouped under the code name Fish ( "fish" ). Due to a lack of capacity and resources, these messages were initially only tracked with low priority and could not be deciphered .

On August 30, 1941, however, they recorded a broadcast of about 4,000 characters in length that was sent over the radio telex from Athens to Vienna . After the recipient in Vienna could not read this correctly, he asked the remote station in Athens to repeat the transmission using a short plain text message. This happened what the British, who listened carefully, were able to follow closely. The radio operator in Athens made two mistakes.

Firstly, he used the "used" key with which he had encrypted the first message a second time, now also for the repetition. This was forbidden. For security reasons, a key could only be used once and then not be reused. This alone would not have had any fatal consequences, because the British would have been able to record the identical ciphertext at most twice without knowing more afterwards than if they had been recorded once. But the intelligence officer made a second mistake.

Presumably for the sake of convenience, the second time he did not enter the plaintext in the same way as the first time in the teletype, it was slightly abbreviated. Right at the beginning of the message he did not write SPRUCHNUMMER as he did the first time, but instead shortened the word and only wrote SPRUCHNR. As a result, the two ciphertexts differed characteristically from this point onwards, while the plaintexts continued almost identically afterwards. The Germans did not notice this, but for the British it was "a hit". Now they were in possession of a so-called depth , i.e. two different ciphertexts based on two almost identical, but slightly shifted, plaintexts, both of which had been encrypted with the same key. (In German terminology, this case is also referred to as a “clear-text-clear-text compromise” .)

This involuntary “gift” from the Germans allowed the British code breaker John Tiltman (1894–1982) in Bletchley Park (BP), England, to break into the SZ 40 for the first time . In weeks of manual work, he managed to get the two slightly “out of phase” and almost identical To determine plaintexts. To do this, he calculated the difference between the two intercepted radio messages and tried to use probable words . This enabled him to reconstruct not only the plaintext, but above all a section of the "pseudo-random" key with a length of four thousand characters. This ultimately led to the exposure of the logical structure of the key addition. The combination of the two mentioned errors turned out to be fatal for the German side, without them knowing or even suspecting it.

analysis

The British codebreaker Bill Tutte succeeded in determining the number of cams on each of the twelve wheels of the SZ 40 without seeing him.

Logical scheme of the machine key generation: The five plain text bits (left) are first linked with the first partial key generated by the "Spa wheels" ("column Caesar wheels", which continuously advance; English wheels ) and then with the by the "Spri-Wheels" ("Spring-Caesar-Wheels", which advance irregularly; Eng. wheels ) generated second partial key. The result is the five ciphertext bits (right). The irregular progression is generated by the two "command wheels " (English motor wheels or wheels in the foreground). ${\ displaystyle \ chi}$ ${\ displaystyle \ psi}$ ${\ displaystyle \ mu}$

An encrypted radio telex sent from Berlin to Army Group Courland on February 14, 1945 using the SZ 42, which was deciphered in BP

Despite the impressive feat that Tiltman had achieved by being able to reconstruct not only the two plaintexts, but above all a four thousand character long section of the pseudo-random key, the British were still a long way from regularly breaking Tunny radio messages. To do this, it was primarily necessary to first clarify the internal structure of the German machine. After the research department of BP had tried to do this in vain for some time, in October 1941 the then 24-year-old mathematician Bill Tutte (1917–2002) received the documents with the words: "See what you can make of these" (show times what you can do with it).

Tutte remembered his training course and the Kasiski test he learned there , which the Prussian infantry major Friedrich Wilhelm Kasiski (1805-1881) had published in 1863, and noted the characters in a checkered grid , with impulses (logical one) with a small cross (×) and periods of rest (logical zero) with a dot (·). As he had learned, the key length would then be "revealed" by conspicuously stacked identical strings as soon as he had chosen the correct side length of the grid. He knew that Tunny worked with twelve-digit indicator keys , where one of 25 letters appeared in eleven places (never J) and in the twelfth one of only 23 letters. So he tried it out with the product 25 × 23, i.e. with an edge length of 575.

His grid did not show any conspicuous repetitions of groups of characters that stood vertically on top of one another, but those that were slightly offset. So he shortened the side length to 574 and tried again. Now the repetitions of the characters were exactly vertically above each other. A quick prime factorization of 574 gave the factors 2 and 7 and 41. He repeated his investigation with an edge length of 41 and got a rectangle of dots and crosses that was replete with repetitions (got a rectangle with dots and crosses that was strewn with repetitions was).

German bike number	1	2	3	4th	5	6th	7th	8th	9	10	11	12
BP designation	${\ displaystyle \ psi}$ ₁	${\ displaystyle \ psi}$ ₂	${\ displaystyle \ psi}$ ₃	${\ displaystyle \ psi}$ _4th	${\ displaystyle \ psi}$ ₅	${\ displaystyle \ mu}$ ₃₇	${\ displaystyle \ mu}$ ₆₁	${\ displaystyle \ chi}$ ₁	${\ displaystyle \ chi}$ ₂	${\ displaystyle \ chi}$ ₃	${\ displaystyle \ chi}$ _4th	${\ displaystyle \ chi}$ ₅
Number of cams	43	47	51	53	59	37	61	41	31	29	26th	23

The young Bill Tutte had achieved his first important success in this way and clarified the scope (number of cams) of one of the key wheels. He called it ₁ . This was wheel 8 of the German machine, which he did not know. His further work ultimately led to the determination of the number of cams on all twelve wheels and to the complete exposure of the logical structure of the key addition without seeing a German key machine. ${\ displaystyle \ chi}$

Hand methods

Key wheels of the machine with clearly visible switch cams

machinery

Conclusion

The British code breaker Donald Michie (1923-2007), of the key additive was instrumental in the successful decipherment, drew the startling conclusion that of all the introduced by the German side as alleged strengthening of encryption and by the two command wheels ( English motor wheels ) controlled “irregular” switching of the Spri-wheels was the decisive cryptographic weakness of the machine, which made the break-in possible for the British.

"If the motor wheels had been omitted [...] Fish codes would never have been broken."

"If the command wheels had been omitted [...] the" Fish "encryption [meaning the SZ] would never have been broken."

However, James A. Reeds, Whitfield Diffie and J. V. Field resolutely contradict this view in the foreword of their edition of the General Report on Tunny (GRT) and state that a promising cryptanalytic attack on Tunny would also have been possible because of the difference method devised by BP . However, the rupture of the Lorenz machine was undoubtedly made easier by the counterproductive “stuttering” of the ψ wheels.

glossary

Reading board 40 for the telex message key sheet (message board)

In connection with the way the key addition works on the German side and its cryptanalysis on the British side , the following technical terminology was used:

Cam (German: Nocke): English word used by the British for the cam.

Crib (German: Eselsbrücke, here aptly “probable word”): English term for a text fragment which is expected to appear in plain text (German technical term also: “plain text-ciphertext compromise” ).

Depth (from English literally "depth"): Two or more ciphertexts that have been encrypted with the same key (German technical term: "Klartext-Klartext-Kompromiss" ).

Basic key: Individual setting of the cams of the twelve key wheels exchanged using secret basic key sheets. Before the summer of 1944, the cams of the Spri wheels were only changed monthly or quarterly, those of the Spa wheels were changed monthly and only the cams of the two command wheels were set differently every day.

Kiss (German literally: kiss): English expression for two different ciphertexts based on the same plain text (German technical term: "ciphertext-ciphertext compromise" ).

Command wheels ( called μ ₃₇ and μ ₆₁ by the British ): wheels 6 and 7 , which ensure that wheels 1 to 5 are shifted irregularly.

Mixed text : Machine-generated pseudo-random character sequence that was mixed with the plain text or ciphertext for encryption and decryption .

Motor wheels (German literally: "Motorräder"): English name for the two command wheels.

Spa wheels (actually Column Caesar wheels ; called χ ₁ to χ ₅ by the British ): The wheels 8 to 12 , which are switched regularly.

Spri wheels (actually Spring Caesar wheels ; called ψ ₁ to ψ ₅ by the British ): The wheels 1 to 5 , which are shifted irregularly.

Saying key: For each saying the individual starting position of the twelve key wheels , which was transmitted in encrypted form , for example HQIBPEXEZMUG for 01-13-34-06-51-01-56-21-23-07-15-11 (see picture).

Message board: Mechanical aid for easy reading of the message key (see picture).

Peg (German: pen): English word for the cams used by the British as an alternative to Cam .

literature

Friedrich L. Bauer : Deciphered Secrets. Methods and maxims of cryptology. 3rd, revised and expanded edition. Springer, Berlin a. a. 2000, ISBN 3-540-67931-6 .
I. J. Good : Enigma and Fish. In: Francis Harry Hinsley , Alan Stripp: Codebreakers - The inside story of Bletchley Park. Oxford University Press, Reading, Berkshire 1993, pp. 161 ff. ISBN 0-19-280132-5 .
Marek Grajek : Nie tylko Enigma - Ryba, która przemówiła, ( German "Not only Enigma - The fish that spoke" ), 2013 (Polish), ISBN 8-3011-7373-4
James A. Reeds, Whitfield Diffie , JV Field: Breaking Teleprinter Ciphers at Bletchley Park: An edition of I. J. Good, D. Michie and G. Timms: General Report on Tunny with Emphasis on Statistical Methods (1945). Wiley - IEEE Press, 2015. ISBN 978-0-470-46589-9 .
Bill Tutte : Fish and I. 1998. PDF; 62 kB. Retrieved January 4, 2017.

Web links

Commons : Lorenz machine - album with pictures, videos and audio files

Jack Copeland : Colossus: Breaking the German 'Tunny' Code at Bletchley Park. The Rutherford Journal. Retrieved January 9, 2017.
Lorenz SZ-40/42. In: CryptoMuseum.com. (English). Retrieved January 9, 2017.
General Report on Tunny. (GRT). In: AlanTuring.net. (English). Retrieved January 9, 2017.
Part of the General Report on Tunny, the Newmanry History, formatted by Tony Sale. 2001. (PDF; 430 kB; English). Retrieved January 9, 2017.

Individual evidence

↑ Donald Michie : Colossus and the Breaking of the Wartime "Fish" Codes. Cryptologia , 26: 1, pp. 17-58, 2002. doi: 10.1080 / 0161-110291890740 . DOC; 220 kB.

↑ Undulator ( Memento of the original from January 25, 2017 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. Brief explanation (English) and sketch. Retrieved January 25, 2017. @1@ 2

^ Gordon Welchman: The Hut Six Story - Breaking the Enigma Codes. Allen Lane, London 1982; Cleobury Mortimer M&M, Baldwin Shropshire 2000, p. 11. ISBN 0-947712-34-8 .

↑ Friedrich L. Bauer: Deciphered secrets. Methods and maxims of cryptology. 3rd, revised and expanded edition. Springer, Berlin a. a. 2000, p. 388.

^ Bill Tutte : Fish and I. S. 5, 1998. PDF; 62 kB. Retrieved January 4, 2017.

^ Bill Tutte: Fish and I. 1998. PDF; 62 kB. Retrieved January 4, 2017.

↑ Donald Michie: Colossus and the Breaking of the Wartime "Fish" Codes. Cryptologia, 26: 1, p. 33, 2002. doi: 10.1080 / 0161-110291890740 . DOC; 220 kB.

↑ James A. Reeds, Whitfield Diffie , JV Field: Breaking Teleprinter Ciphers at Bletchley Park: An edition of I. J. Good , D. Michie and G. Timms: General Report on Tunny with Emphasis on Statistical Methods (1945). Wiley - IEEE Press, 2015, S. XCII (English). ISBN 978-0-470-46589-9 .

↑ ^a ^b James A. Reeds, Whitfield Diffie, JV Field: Breaking Teleprinter Ciphers at Bletchley Park: An edition of I. J. Good, D. Michie and G. Timms: General Report on Tunny with Emphasis on Statistical Methods (1945). Wiley-IEEE Press, 2015, p. 410 (English). ISBN 978-0-470-46589-9 .

↑ James A. Reeds, Whitfield Diffie, JV Field: Breaking Teleprinter Ciphers at Bletchley Park: An edition of I. J. Good, D. Michie and G. Timms: General Report on Tunny with Emphasis on Statistical Methods (1945). Wiley-IEEE Press, 2015, p. 396 (English). ISBN 978-0-470-46589-9 .

↑ James A. Reeds, Whitfield Diffie, JV Field: Breaking Teleprinter Ciphers at Bletchley Park: An edition of I. J. Good, D. Michie and G. Timms: General Report on Tunny with Emphasis on Statistical Methods (1945). Wiley-IEEE Press, 2015, p. 19 (English). ISBN 978-0-470-46589-9 .

↑ David Kahn: Seizing the Enigma - The Race to Break the German U-Boat codes 1939 -1943. Naval Institute Press, Annapolis, MD, USA, 2012, p. 139. ISBN 978-1-59114-807-4 .

[1] Donald Michie : Colossus and the Breaking of the Wartime "Fish" Codes. Cryptologia , 26: 1, pp. 17-58, 2002. doi: 10.1080 / 0161-110291890740 . DOC; 220 kB.