Virtual Colossus

The statistical attack on Lorenz

The flaws in the Lorenz cipher that let Colossus find the wheel start positions.

The basis for breaking Lorenz statistically

This page explains the flaws in the Lorenz cipher that let Colossus find the start positions of the wheels using statistical methods.

To begin, let’s look at an example of the frequency of letters and character codes in a typical German plain text message.

Bar chart of character counts in German plain text, with high counts for E, A and R and very high counts for the teleprinter shift and space characters

Notice the usual high counts of the letters A, E and R, in German as in English, and the very large counts of teleprinter editing characters (figure and letter shift, carriage return and so on) at the right of the histogram.

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 and random across all characters.

Bar chart of character counts in Lorenz cipher text, with every character at roughly the same height

A simple frequency count of the letters gave no clue to the plain text behind the cipher, so how was Bletchley Park able to break it?

Learning 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 at Bletchley Park as the Chi (χ) wheels and the Psi (ψ) wheels. The Chi wheels moved regularly, but the Psi wheels moved intermittently under the control of the two so-called motor wheels. Was there anything in this movement that gave our codebreakers a toehold?

Using the Vernam method of adding two ITA2-coded letters with exclusive or (XOR) (see the Lorenz machine), we can build the addition table below, showing the result of adding each pair of letters.

The teleprinter addition square: a 32 by 32 table giving the result of adding any two characters

From this table we can see a few useful things:

  1. Adding two of the same letter always gives the null character (/), which is five dots (a tape with no holes punched). See the diagonal from top left to bottom right.
  2. Adding the null character to any letter always gives back that letter (the bottom row: / + C = C, / + J = J and so on).
  3. Adding any letter a second time removes its effect, and it doesn’t matter in which order you add them.

    For example, starting with the letter A and adding the key letters C and T, we get A + C + T = 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 again to get back to the original letter: adding C and T to our cipher letter X gives back our initial letter A (X + C + T = A).

Peeking through the Psi wheels

First, let’s assume we know the wheel pin settings for the message we are trying to break. These were normally found from a depth (where more than one message was sent with the same key), or later by a method known as rectangling.

Checking every possible start position for all twelve wheels means a phenomenally large number of tries (1.6034 × 1019), so we need a way to cut it down substantially. Any repetition or pattern in a cipher is often a weak point a codebreaker can use to find a way in, and one place to look for a repeating pattern is in the way the Psi wheels stutter and move intermittently. When the Lorenz was built, the two motor wheels were added to make the movement more complex, so the Psi wheels took much longer to 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 used this method again later when working out how to break the wheels.

The equation for enciphering 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 ⊕ the exclusive or (XOR) function:

P ⊕ χ ⊕ ψ = Z

Because XOR is reciprocal, to decipher a message we simply turn the equation around:

Z ⊕ χ ⊕ ψ = P

What the codebreakers noticed was that while the Chi letter changed every time, the Psi letter stayed the same about half the time.

Charχψ
1DR
2LR
3MR
4EB
53B
6PJ

Turing realised that rather than using the Chi and Psi letters directly, he could use the delta (Δ), the difference between one character and the next, to get a glimpse of the plain text underneath. If we add each character to the next, then for the Psi wheels we are often adding two of the same letter, which we know gives the null character (/). This gives the equation:

(Z1 ⊕ Z2) ⊕ (χ1 ⊕ χ2) ⊕ (ψ1 ⊕ ψ2) = (P1 ⊕ P2)orΔZ ⊕ Δχ ⊕ Δψ = ΔP

Because of the way the Psi wheels repeat, the delta of the Psi wheels is null about half the time. Then the Psi wheels no longer change the result, cancelling out the Psi key letter and in effect leaving a window through the Psi wheels about 50% of the time.

Stripping the Chi wheels to create the de-chi

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

The result is called the de-chi (the cipher text with the Chi wheel patterns removed). If the start positions we chose are wrong (most likely), the de-chi will still be nearly flat and random, as any of the 32 characters is just as likely as any other.

Bar chart of character counts in a de-chi from wrong start positions, nearly flat across all characters

But look what happens if we are very lucky and our next guess at the start positions is correct, still with our window through the Psi wheels about half the time:

ΔZ ⊕ (Δχ from key ⊕ Δχ from guess) = ΔPthe two equal Δχ cancel outΔZ = ΔP

We are now, around half the time, generating the delta of the plain text from the cipher tape. We still can’t see the actual plain text to do a letter frequency count, as each plain text letter has been added to the next, but at last there is a marker that Bill Tutte realised could show that we had found the right start positions.

Counting the dots

Let’s take an example piece of German plain text and see what happens to it when we take its delta.

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

Adding each letter to the next still mostly gives random text, but wherever a character is repeated we get the null code (remember, the ITA2 code for null is five dots). The reason there are so many doubled ++ (figure shift) and -- (letter shift) characters is that teleprinter operators normally keyed each shift twice. The traffic was sent by radio, which could corrupt characters. The recipient could still work out a word if a single letter was wrong, but if a single figure shift was corrupted, everything after it would come out as letters rather than the numbers or figures being sent.

This doubling of shift characters, plus the many double letters in German, means the number of nulls in the delta of the plain text is very slightly higher than chance. Not by a huge amount, but over a large number of characters it was noticeable. Bill Tutte worked it out from a known message and found that, taking into account the doubles above and even just the likelihood of two letters being next to each other in German, the chance of the de-chi being a dot rather than a cross was 55%.

Bar chart of character counts in the delta of German plain text, with a much higher count for the null character (/)

So we can find the start positions of the Chi wheels by trying each start position for each Chi wheel in turn, calculating the delta de-chi for the whole message down the length of the cipher tape, and counting the dots. For a wrong start position we can expect flat random garbage, with a dot or a cross equally likely (somewhere near 50% of the characters on the tape). But at the right start positions we should see the excess of nulls show up in the dot count.

Hold on, though. We still have to work through every combination of start positions for the Chi wheels: 41 × 31 × 29 × 26 × 23 = 22,041,682 tries, each needing the delta de-chi calculated down the whole tape (which could be a few thousand characters long). That’s much better than before, but still a huge number of calculations. Can we shorten the search any further?

Bill Tutte’s 1+2=. algorithm

There is another flaw in the Lorenz cipher that Bill Tutte realised could be used to break the search into smaller pieces. The impulses of the code (the five ITA2 dots or crosses making up each character) are never mixed with each other when enciphering. The first dot or cross of the plain text is added to the first dot or cross from the Chi wheels and the first from the Psi wheels. The second impulse always uses the second impulse of the Chi and Psi, and so on.

This means the search for dots still works even if we don’t check all five impulses. Bill Tutte worked out that it was possible (just about) to search using only the first two Chi wheels (χ1, with 41 start positions, and χ2, with 31). That gives far fewer start positions to work through: 41 × 31 is just 1,271 tries. From that result we can do the same for the χ4 and χ5 wheels (only 598 starts) and finally work out χ3 (just 29 starts). The total search is only 1,898 tries, compared with 22 million.

It was this partitioned method of attack that let Colossus find the Chi wheel starts for a cipher text in about 30 minutes. The calculation for the first run became known as the 1+2=. break-in: counting where the deltas of the first and second impulses, from the χ1 and χ2 wheels, add up to a dot.

Next: the coming of the machines, and the beginnings of Colossus.