The statistical attack on Lorenz

The basis for breaking Lorenz statistically

This page will attempt to explain the flaws in the Lorenz cipher which enabled Colossus to begin the break to find the start positions using statistical methods.

To begin, we should take a look at an example of the frequency of letters and character codes in a standard German plain text message as shown below.

Notice the usual high counts of letters A E R, in German as in English, and the very large counts of teleprinter editing characters, figure/letter shift, carriage return etc., at the right of the histogram. Note that LF, CR, Letter Shift, Figure Shift, space and null are written as 3, 4, -, +, . and / respectively.

However, the Germans chose the wheel patterns on the Lorenz cipher machine so that the resulting cipher text was nearly flat random across all characters.

This meant a simple frequency count of the letters gave no clue as to the real plain text behind the cipher so how was Bletchley Park able to break this cipher?

Learning how to add using the Vernam method

The Lorenz SZ42 cipher attachment adds two obscuring characters to the plain text to get the cipher text. These characters were generated by two sets of five wheels, known in Bletchley Park as the Chi(Χ) wheels and the Psi(Ψ) wheels. Of these two, the Chi wheels moved regularly but the Psi wheels moved intermittently under control of the two so-called motor wheels, was there anything in this movement that gave a toehold to our codebreakers?

Using the Vernam method of adding together two ITA coded letters using exclusive or (XOR) (see The Lorenz Machine), we can build the addition table below showing what each pair of letters added together results in.

Looking at the above table, we can notice a few useful pieces of information:

  1. Adding together two of the same letter will give the result of a Null character (/) which is encoded as five dots (a tape with no holes punched). See the diagonal set from top left to bottom right.
  2. Adding together a Null character with any other letter always gives back the initial letters again. (the bottom row: add /+C=C, /+J=J etc)
  3. Adding any letter a second time subtracts it's effects, it doesn't matter which order you add them.

    For example, starting with the letter A and adding the key letters C & T, we get A + C + T equals X (either A + C = F then F + T = X or C + T = V then V + A = X, it makes no difference). We can also add the same key letters back to get back to any other letter, if we add our cipher letter X to the C and T, we'll get back to our inital letter A (X + C + T = A).

Peeking through the Psi wheels

Let's firstly assume we have the wheel pin settings for the message we are trying to break. This was normally done by using a depth (where more than one message was sent with the same key) or later by a method known as rectangling.

To check every possible starting position for all twelve wheels is a phenomenally large number (1.6034 × 1019) so we need a way to cut down the number substantially. Any sort of repetition or pattern in a cipher is often a weak point that a codebreaker can use to start to find a way in, and one place we can look for a repeating pattern is in the way the Psi wheels stutter and move intermittently. When the Lorenz SZ42 was built, it was decided to make the movement more complex by adding in the two motor wheels which meant that the Psi wheels took much longer before they would start repeating the same pattern of key, but, this also added a subtle weakness which Alan Turing used when he spent a few weeks in the Research Section working on breaking Tunny keys. Bill Tutte again used this method later when working out how to break the wheels.

The equation we are using to encipher a message is as follows, where P is the plain text, Χ is the letter added by the Chi wheels, Ψ the letter added by the Psi wheels, Z the resulting cipher text and ⊕ symbolising the "exclusive or" (XOR) function.

P ⊕ Χ ⊕ Ψ = Z

Therefore, due to the reciprocal method of XOR, to decipher a message, we can simply turn that equation around the other way

Z ⊕ Χ ⊕ Ψ = P

What the codebreakers noticed was that while the Chi wheel letter changed every time, the Psi wheel would stay static 50% of the time per rotation.

CharΧΨ
1DR
2LR
3MR
4EB
53B
6PJ

Turing realised that rather than using the direct Chi and Psi, he could use the Delta (Δ) or difference between one character and the next to get a glimpse of the plain text below. If we add each line to the next along, then we can notice that for the Psi wheels, a lot of the time, we're adding together two of the same letters, which we know gives us the Null character (/). This gives this equation

(Z1⊕Z2) ⊕ (Χ1⊕X2) ⊕ (Ψ1⊕Ψ2) = (P1⊕P2)
or
ΔZ ⊕ ΔX ⊕ ΔΨ = ΔP

But, due to the repeating nature of the Psi wheels, the delta of the Psi wheels is Null half the time which means that the Psi wheels no longer change the result of the addition, cancelling out the Psi wheel key letter and effectively leaving a window through the Psi wheels 50% of the time!

Stripping the Chi wheels to create the De-Chi

We are now left with the delta of the cipher plus the delta of the Chi wheels, but as we know the pin settings of the Chi wheels, we can generate the sequence of letters created for any specific start position. What happens if we guess the wrong start positions and fill in the generated delta patterns for the Chi wheels?

The result we are left with is called the De-Chi (the result of the cipher text with the Chi wheel patterns removed). If the start positions we've chosen are (most likely) wrong, then the result of the De-Chi will be still nearly flat random as there is just as much chance of any of the 32 characters being generated as any other.

But, take a look at what happens if we're very lucky and our second guess for the start positions is correct, still knowing that we have our window through the Psi wheels 50% of the time:

ΔZ ⊕ (ΔX from key ⊕ ΔX from guess) = ΔP
cancel out the two equal ΔX
ΔZ = ΔP

We are now (around 50% of the time) generating the delta of the plaintext from the cipher tape! We still can't see the actual plaintext message to do a frequency letter count as it's the plaintext of each letter added to the next, but finally, there is a marker that Bill Tutte realised could be used to show that we have found the right start positions.

Counting the dots

If we take a look at an example piece of German plain text, we can see what happens to it when we delta the message.

G++MA--.D+L---RUFSTELLUNGSSTAB.++YP.
__/___/_____//_______/____/_____/___

Adding each letter to the next will still mostly generate random text, but whenever there is a repeated character, then we find we get our Null code (remember, the ITA2 code for Null is five dots). The reason we can see quite a number of double coded ++ (figure shift) and -- (letter shift) is that this was common practice for teleprinter traffic to encode each shift two times. This was due to the data having to be sent via radio which could corrupt letters being received. The words could be worked out by the recipient if a single letter in a word was wrong but if a single figure shift was corrupted then everything after it would be a list of letters rather than the required numbers or figures being sent.

This doubling up of character codes, plus the numerous duplicate letters in German mean that the number of Null characters in the delta plain text is very slightly higher, not by a huge amount, but over a large number of characters, it was noticable. Bill Tutte calculated the results from a known message and found that, taking into account the duplicates above and even just the likelyhood of two letters next to each other in German, meant the chance of the De-Chi being a dot rather than a cross was 55%

Therefore, it is possible that we can find our start position for the Chi wheels by simply trying each start position for each of the Chi wheels in turn, calculating the Delta De-Chi for the whole of the message down the length of the cipher tape and count the number of dots being generated. If this value is for a wrong start position, we can expect our result to be flat random garbage text with just as much chance of a dot or a cross (somewhere near 50% of the number of characters on the tape). If, however, we are on the right start positions, we should see the excess of Null characters showing up in the dot count.

Hold on though! We still have to work through all combinations of start positions for each Chi wheel, that's a total of 41 × 31 × 29 × 26 × 23 = 22,041,682 tries each one of which requires the calculation of the delta De-Chi down the whole of the tape (which could be a few thousand characters long). It's much better than before, but still a large number of calculations, can we shorten this search any more?

Bill Tutte's 1+2=. algorithm

There is another flaw in the security of the Lorenz cipher that Bill Tutte realised could be used to break this method down into smaller segments. That flaw is that the impulses of the code (the five ITA2 dots or crosses making up each letter of the code) are never mixed between each other when enciphering. The first dot or cross from the plaintext is added to the first dot or cross from the Chi wheel and the first dot/cross of the Psi wheel. The second impulse always uses the second impulse of the Chi and Psi and so on.

What this means is that the search for dots works even if we don't check all five impulses. Bill Tutte worked out that it was possible to do this (just about) even searching just the first two Chi wheels (X1 with a total of 41 start positions and X2 with 31 start positions). This gives a much smaller number of start positions to work through, 41 x 31 is just 1,271 attempts. Using that result, we should then be able to do the same for the X4 and X5 Chi wheels (only 598 starts) and finally work out the X3 (just 29 starts). This resulting search space is only 1,898 compared with 22 Million!

It was the discovery of this partitioned method of attack which allowed Colossus to find the Chi wheel starts on a cipher text in about 30 minutes. The calculation for the first break-in run became known as the 1+2=. break in - the calculation of counting the deltas of the first and second impulses of the X1 and X2 Chi wheels where the result equals a dot.