HOME

TheInfoList



OR:

Turingery in ''Testery Methods 1942–1944'' or Turing's method (playfully dubbed Turingismus by Peter Ericsson, Peter Hilton and
Donald Michie Donald Michie (; 11 November 1923 – 7 July 2007) was a British researcher in artificial intelligence. During World War II, Michie worked for the Government Code and Cypher School at Bletchley Park, contributing to the effort to solve " Tunny ...
) was a manual
codebreaking Cryptanalysis (from the Greek ''kryptós'', "hidden", and ''analýein'', "to analyze") refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic secu ...
method devised in July 1942 by the mathematician and cryptanalyst
Alan Turing Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher and theoretical biologist. He was highly influential in the development of theoretical computer ...
at the British
Government Code and Cypher School The Government Code and Cypher School (GC&CS) was a British signals intelligence agency set up in 1919. During the First World War, the British Army and Royal Navy had separate signals intelligence agencies, MI1b and NID25 (initially known as R ...
at
Bletchley Park Bletchley Park is an English country house and Bletchley Park estate, estate in Bletchley, Milton Keynes (Buckinghamshire), that became the principal centre of Allies of World War II, Allied World War II cryptography, code-breaking during the S ...
during
World War II World War II or the Second World War (1 September 1939 – 2 September 1945) was a World war, global conflict between two coalitions: the Allies of World War II, Allies and the Axis powers. World War II by country, Nearly all of the wo ...
. It was for use in
cryptanalysis of the Lorenz cipher Cryptanalysis of the Lorenz cipher was the process that enabled the British to read high-level German army messages during World War II. The British Government Code and Cypher School (GC&CS) at Bletchley Park decrypted many communications betwee ...
produced by the SZ40 and SZ42 teleprinter
rotor ROTOR was an elaborate air defence radar system built by the British Government in the early 1950s to counter possible attack by Soviet bombers. To get it operational as quickly as possible, it was initially made up primarily of WWII-era syst ...
stream cipher stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream ( keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystrea ...
machines, one of the
Germans Germans (, ) are the natives or inhabitants of Germany, or sometimes more broadly any people who are of German descent or native speakers of the German language. The Basic Law for the Federal Republic of Germany, constitution of Germany, imple ...
' ''Geheimschreiber'' (secret writer) machines. The British codenamed non- Morse traffic "Fish", and that from this machine "Tunny" (another word for the tuna fish). Reading a Tunny message required firstly that the logical structure of the system was known, secondly that the periodically changed pattern of active cams on the wheels was derived, and thirdly that the starting positions of the scrambler wheels for this message—the message key—was established. The logical structure of Tunny had been worked out by William Tutte and colleagues over several months ending in January 1942. Deriving the message key was called "setting" at Bletchley Park, but it was the derivation of the cam patterns—which was known as "wheel breaking"—that was the target of Turingery. German operator errors in transmitting more than one message with the same key, producing a "depth", allowed the derivation of that key. Turingery was applied to such a key stream to derive the cam settings.


The SZ40 and SZ42

The logical functioning of the Tunny system was worked out well before the Bletchley Park cryptanalysts saw one of the machines—which only happened in 1945, shortly before the allied victory in Europe. The SZ machines were 12-wheel
rotor ROTOR was an elaborate air defence radar system built by the British Government in the early 1950s to counter possible attack by Soviet bombers. To get it operational as quickly as possible, it was initially made up primarily of WWII-era syst ...
cipher In cryptography, a cipher (or cypher) is an algorithm for performing encryption or decryption—a series of well-defined steps that can be followed as a procedure. An alternative, less common term is ''encipherment''. To encipher or encode i ...
machines which implemented a Vernam
stream cipher stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream ( keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystrea ...
. They were attached in-line to standard Lorenz teleprinters. The message characters were encoded in the 5-bit International Telegraph Alphabet No. 2 (ITA2). The output ciphertext characters were generated by combining a
pseudorandom A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process. Pseudorandom number generators are often used in computer programming, as tradi ...
character-by-character key stream with the input characters using the "
exclusive or Exclusive or, exclusive disjunction, exclusive alternation, logical non-equivalence, or logical inequality is a logical operator whose negation is the logical biconditional. With two inputs, XOR is true if and only if the inputs differ (on ...
" (XOR) function, symbolised as in mathematical notation. The relationship between the
plaintext In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored unencrypted. Overview With the advent of comp ...
,
ciphertext In cryptography, ciphertext or cyphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext ...
and
cryptographic key A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm In mathematics and computer science, an algorithm () is a finite sequenc ...
is then: :\mathrm = \mathrm \oplus \mathrm Similarly, for deciphering, the ciphertext was combined with the same key to give the plaintext: :\mathrm = \mathrm \oplus \mathrm This produces the essential reciprocity to allow the same machine with the same settings to be used for both enciphering and deciphering. Each of the five bits of the key for each character was generated by the relevant wheels in two parts of the machine. These were termed the ''chi'' (\chi) wheels, and the ''psi'' (\psi) wheels. The ''chi'' wheels all moved on one position for each character. The ''psi'' wheels also all moved together, but not after each character. Their movement was controlled by the two ''mu'' (\mu) or "motor" wheels. in ''German Tunny'' The key stream generated by the SZ machines thus had a ''chi'' component and a ''psi'' component that were combined with the XOR function. So, the key that was combined with the plaintext for enciphering—or with the ciphertext for deciphering—can be represented as follows. :\mathrm = \textit\mathrm \oplus \textit\mathrm Symbolically: :K = \chi \oplus \psi The twelve wheels each had a series of cams (or "pins") around them. These cams could be set in a raised or lowered position. In the raised position they generated a "mark", written at Bletchley Park as "×" and equivalent to a binary digit 1, and in the lowered position they generated a "space", written as "·" and equivalent to a binary digit 0. The number of cams on each wheel equalled the number of impulses needed to cause them to complete a full rotation. These numbers are all co-prime with each other, giving the longest possible time before the pattern repeated. With a total of 501 cams this equals 2501 which is approximately 10151, an astronomically large number. However, if the five impulses are considered independently, the numbers are much more manageable. The product of the rotation period of any pair of ''chi'' wheels gives numbers between 41×31=1271 and 26×23=598.


Differencing

Cryptanalysis often involves finding patterns of some sort that provide a way into eliminating a range of key possibilities. At Bletchley Park the XOR combination of the values of two adjacent letters in the key or the ciphertext was called the difference (symbolised by the Greek letter ''delta'' \Delta) because XOR is the same as
modulo In computing and mathematics, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another, the latter being called the '' modulus'' of the operation. Given two positive numbers and , mo ...
2 subtraction (without "borrow")—and, incidentally, modulo 2 addition (without "carry"). So, for the characters in the key (K), the difference \Delta K was obtained as follows, where underline indicates the succeeding character: :\Delta K = K \oplus \underline (Similarly with the plaintext, the ciphertext, and the two components of the key). The relationship amongst them applies when they are differenced. For example, as well as: :K = \chi \oplus \psi It is the case that: :\Delta K = \Delta \chi \oplus \Delta \psi If the plaintext is represented by P and the cipertext by Z, the following also hold true: :\Delta Z = \Delta P \oplus \Delta \chi \oplus \Delta \psi And: :\Delta P = \Delta Z \oplus \Delta \chi \oplus \Delta \psi The reason that differencing provided a way into Tunny was that, although the frequency distribution of characters in the ciphertext could not be distinguished from a random stream, the same was not true for a version of the ciphertext from which the ''chi'' element of the key had been removed. This is because, where the plaintext contained a repeated character and the ''psi'' wheels did not move on, the differenced ''psi'' character (\Delta \psi) would be the null character ("·····" or 00000), or, in Bletchley Park terminology, "/". When XOR-ed with any character, this null character has no effect, so in these circumstances, \Delta \chi = \Delta K. Repeated characters in the plaintext were more frequent, both because of the characteristics of German (EE, TT, LL and SS are relatively common), and because telegraphists frequently repeated the figures-shift and letters-shift characters as their loss in an ordinary telegraph message could lead to
gibberish Gibberish, also known as jibber-jabber or gobbledygook, is speech that is (or appears to be) nonsense: ranging across speech sounds that are not actual words, pseudowords, language games and specialized jargon that seems nonsensical to outsid ...
. To quote the General Report on Tunny:
Turingery introduced the principle that the key differenced at one, now called \Delta K, could yield information unobtainable from ordinary key. This \Delta principle was to be the fundamental basis of nearly all statistical methods of wheel-breaking and setting.


Bit-level differencing

As well as applying differencing to the full 5-bit characters of the
ITA2 The Baudot code () is an early character encoding for telegraphy invented by Émile Baudot in the 1870s. It was the predecessor to the International Telegraph Alphabet No. 2 (ITA2), the most common teleprinter code in use before ASCII. Each Chara ...
code, it was also applied to the individual impulses (bits). So, for the first impulse, that was enciphered by wheels \chi_1 and \psi_1, differenced at one: :\Delta K_1 = K_1 \oplus \underline And for the second impulse: :\Delta K_2 = K_2 \oplus \underline And so on. It is also worth noting that the periodicity of the ''chi'' and ''psi'' wheels for each impulse (41 and 43 respectively for the first one) is reflected in its pattern of \Delta K. However, given that the ''psi'' wheels did not advance for every input character, as did the ''chi'' wheels, it was not simply a repetition of the pattern every 41 × 43 = 1763 characters for \Delta K_1, but a more complex sequence.


Turing's method

In July 1942 Turing spent a few weeks in the Research Section. He had become interested in the problem of breaking Tunny from the keys that had been obtained from depths. In July, he developed the method of deriving the cam settings from a length of key. It involved an iterative, almost trial-and-error, process. It relied on the fact that when the differenced ''psi'' character is the
null character The null character is a control character with the value zero. Many character sets include a code point for a null character including Unicode (Universal Coded Character Set), ASCII (ISO/IEC 646), Baudot, ITA2 codes, the C0 control code, and EB ...
("·····" or 00000), /, then XOR-ing this with any other character does not change it. Thus the delta key character is the same as that of the five ''chi'' wheels (i.e. \Delta \chi = \Delta K). Given that the delta ''psi'' character was the null character half of the time on average (because the ''psi'' wheels moved only 50% of the time) an assumption that \Delta K = \Delta \chi had a 50% chance of being correct. The process started by treating a particular \Delta K character as being the Δ\chi for that position. The resulting putative bit pattern of bits for each ''chi'' wheel was recorded on a sheet of paper that contained as many columns as there were characters in the key, and five rows representing the five bits of the \Delta \chi. Given the knowledge from Tutte's work of the periodicity of each of the wheels, this allowed the propagation of these values at the appropriate positions in the rest of the key. A set of five sheets, one for each of the ''chi'' wheels, was also prepared. These contained a set of columns corresponding in number to the cams for the appropriate ''chi'' wheel, and were referred to as a 'cage'. So the \chi_3 cage had 29 such columns. which reproduces a \chi_3 cage from the General Report on Tunny Successive 'guesses' of \Delta \chi values then produced further putative cam state values. These might either agree or disagree with previous assumptions, and a count of agreements and disagreements was made on these sheets. Where disagreements substantially outweighed agreements, the assumption was made that the \Delta \psi character was not the null character "/", so the relevant assumption was discounted. Progressively, all the cam settings of the ''chi'' wheels were deduced, and from them the ''psi'' and motor wheel cam settings. As experience of the method developed, improvements were made that allowed it to be used with much shorter lengths of key than the original 500 or so characters.


See also

*
Banburismus Banburismus was a Cryptanalysis, cryptanalytic process developed by Alan Turing at Bletchley Park in United Kingdom, Britain during the Second World War. It was used by Bletchley Park's Hut 8 to help break German ''Kriegsmarine'' (naval) message ...
*
Differential cryptanalysis Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in information input can a ...


References and notes


Bibliography

* * * * * That version is a facsimile copy, but there is a transcript of much of this document in '.pdf' format at: , and a web transcript of Part 1 at: * * * * * * {{Citation , last = Tutte , first = W. T. , author-link = W. T. Tutte , title = Fish and I , date = 19 June 1998 , url = http://frode.home.cern.ch/frode/crypto/tutte.pdf , accessdate = 7 October 2010 , url-status = dead , archiveurl = https://web.archive.org/web/20070710042331/http://frode.home.cern.ch/frode/crypto/tutte.pdf , archivedate = 10 July 2007 , df = dmy-all Transcript of a lecture given by Prof. Tutte at the
University of Waterloo The University of Waterloo (UWaterloo, UW, or Waterloo) is a Public university, public research university located in Waterloo, Ontario, Canada. The main campus is on of land adjacent to uptown Waterloo and Waterloo Park. The university also op ...
Bletchley Park Alan Turing Cryptographic attacks