The Double Delta Attack

The Problem

The fundamental problem of breaking Tunny (the codename at Bletchley Park for the Lorenz cipher) had to do with the number of possible combinations for the 12 wheels of the Lorenz machine. There were 41 x 31 x 29 x 26 x 23 x 43 x 47 x 51 x 53 x 59 x 37 x 61 possible orientations of the wheels. Thus, even after the exact pattern of crosses and dots on each wheel was known, there were about 10¹⁹ possible settings of the wheels that could have been used for one message. This is far too many for even modern desktop computers to evaluate, so simply checking each possible combination for the one which produced German instead of random letters was not an option. The cryptanalysts at Bletchley Park had to find another way to discover the correct wheel settings.

Statistics

The answer to the problem of breaking Tunny was to look at statistical properties of the method of encryption. The sequence of ones and zeros (referred to respectively as crosses and dots by the cryptanalysts at Bletchley) produced by each of the five pairs of χ and ψ wheels was very nearly random. This meant that, in the encrypted message, there was an equal chance of either a one or a zero appearing. However, for the clear-text written in German, the frequency of the different symbols was determined by the German language. Certain symbols, such as the whitespace character, occurred significantly more frequently in clear-text. The whitespace character, along with other more frequent letters in German, tended to have more zeros than ones, especially in the first two impulses (i.e. the first two bits). Unfortunately, it was still not reasonable to simply look at one of the five impulses individually: each impulse depended on the settings of a χ wheel, a ψ wheel and two motor wheels. For the first impulse this would be 41 x 43 x 37 x 67 = 4,370,477 possible settings to check.

Although such a brute-force statistical attack would not work, a more clever technique was devised by a cryptanalyst named William T. Tutte. Tutte came up with the concept of looking at whether or not there is a change in a given impulse from one letter to the next. He discovered that, while the encrypted message may be effectively random, the changes from one letter to the next in a pair of impulses (e.g. the first two bits) in the message would show certain deviations from pure randomness if the correct χ wheel settings were chosen. Since these deviations appear when just two χ wheels are set correctly, only about 1000 possible wheel combinations need be tested to find the correct settings for those two wheels. In this way, all the χ wheel settings could be found with a very high probability of correctness.

The Delta Notation

The notation for dealing mathematically with the Lorenz cipher is the source of the "double delta" in the name of Tutte's attack on Tunny. For the Lorenz cipher Z is the cipher text, C is the clear text, χ is the χ wheel, ψ is the ψ wheel and ψ' is the actual output of the ψ wheel (this differs from the sequence of bits on the wheel because sometimes the ψ wheels do not turn). Each of these symbols represents a stream of letters each of which is encoded by five bits/impulses. To simplify the notation the first impluse of any of the streams is written with the subscript 1, the second with 2 and so on up to the fifth with 5. So, the set of fifth impulses of the clear text stream are written C₅ and the set of first impulses of the ψ wheel output is written ψ'₁. Tutte's attack depends upon the changes in a stream which he denoted by prefixing the symbol for a certain stream with a delta. Thus, Δ χ₂ is a stream of bits, each of which is 1 if the corresponding bit in χ₂ represents a change from the last bit and zero otherwise. Thus, the delta of a stream can be calculated by simply shifting the stream one bit to the right, and adding this shifted copy to the original stream.


Since Lorenz encryption involves simply adding (mod 2) the χ and ψ wheel's current setting to the clear text message in order to get the encrypted message, the following equation describes the relationship between the cipher text and clear text:


Thus, if the delta operator is applied to both sides the equation becomes:


This equation is fundamental in the double delta attack to find the correct wheel settings.

Double Delta

The double delta attack gets its name from the fact that it relies on taking the delta of two of the five separate impulses for each letter of the encrypted message and adding them together. That is, if Z₁ is the first impulse of the cipher text and Z₂ is the second, then the sum Δ Z₁ ⊕ Δ Z₂ is the central point in the double delta attack. Using the equation for the cipher text derived above this sum is

Tutte realized that the terms Δ C₁ ⊕ Δ C₂ and Δ ψ'₁ ⊕ Δ ψ'₂ would each add up to zero more frequently than half the time. The term Δ C₁ ⊕ Δ C₂ for the clear text was usually about 60% zero and 40% one, due to the fact that text from the German language does not have a random letter distribution. In the case of Δ ψ'₁ ⊕ Δ ψ'₂ the important point is that all the ψ wheels move together or stay still together. The German designed the patterns on these wheels so that about half the time they would move and half the time they would stay still. The point of this was to add another element of randomness. However, when the ψ wheels stay still both Δ ψ'₁ and Δ ψ'₂ are zero. Since the wheel positions don't change, the delta is zero. Thus the term Δ ψ'₁ ⊕ Δ ψ'₂ is guaranteed to be zero whenever the ψ wheels don't move, which is about half the time. Further, when the ψ wheels do move, there is about a 50% chance that they will either both change or both stay the same. In each of these cases, the sum Δ ψ'₁ ⊕ Δ ψ'₂ will be zero. Thus, that sum is zero both when the ψ wheels don't move and about half the time when they do move. This means that the sum is zero about 75% of the time.

Given the above probabilities, the chance that the sum of the two terms Δ C₁ ⊕ Δ C₂ ⊕ Δ ψ'₁ ⊕ Δ ψ'₂ is zero can be calculated. It is simply the probability that they are both zero plus the probability that they are both one (in base-two modular arithmatic 1 ⊕ 1 = 0). This probability is calculated as:

So, approximately 55% of the time Δ C₁ ⊕ Δ C₂ ⊕ Δ ψ'₁ ⊕ Δ ψ'₂ is zero. Using the original double delta equation, this means that 55% of the time the equation can be simplified as follows:

This correlation between the double delta of the cipher text and of the χ wheels will only appear if the setting for the two χ wheels is correct. Otherwise the double deltas will be random and only equal half the time. Thus, by comparing Δ Z₁ ⊕ Δ Z₂ and Δ χ₁ ⊕ Δ χ₂ for all possible combinations of the χ₁ and χ₂ wheels it is possible to choose the correct setting by finding the one in which Δ Z₁ ⊕ Δ Z₂ = Δ χ₁ ⊕ Δ χ₂ most frequently. Since this process only involves trying all possible combinations for two wheels it can be done in a relatively short amount of time. In fact, this attack is exactly the algorithm used by the Colossus computer to determine the settings for the χ wheels. The Colossus compares the cipher text of a message to all the possible combinations of two χ wheels and chooses the setting where the double deltas correlate the most (i.e. match most frequently).