The statistical attack on Lorenz

The basis for breaking Lorenz statistically

This is an excerpt as a basic introduction from Tony Sale's website where much more information is given.


http://www.codesandciphers.co.uk/


The breaking of Lorenz depended on finding the wheel start positions by doing counts of various cross correlation runs down the whole length of the cipher text. The basis for this was that when patterns of bits with the correct start positions were added to the cipher bits, some of the enciphering bits generated by the Lorenz machine were stripped off revealing a non-random count due to the plain language non-uniformity.

BREAM PLAIN LANGUAGE

............................................................H
........................................................H.H.H
........................................................H.H.H
........................................................H.H.H
........................................................H.H.H
........................................................H.H.H
........H...............................................H.H.H
........H...............................................H.H.H
........H.........................H.....................H.H.H
H.......H...............H.H.......H.....................H.H.H
H.......H...............H.H.......H...H.................H.H.H
H.......H.......H.......H.H.......H.H.H.................H.H.H
H.....H.H...H.H.H.....H.H.H.H...H.H.H.H.H.H.H.....H.....H.H.H
H.H.H.H.H.H.H.H.H...H.H.H.H.H.H.H.H.H.H.H.H.H.H...H.....H.H.H
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 3 4 - + . /

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.

However, the Germans had chosen the wheel patterns on the Lorenz cipher machine so that the cipher text was nearly flat random

BREAM CIPHER

..................H.........H.........H...H...............H.H..
H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H
H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H
H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 3 4 - + . /

But the Lorenz cipher machine added two obscuring characters to the plain text to get the cipher text. These characters were generated by two sets of 5 wheels, known in Bletchley Park as the Chi(K) wheels and the Psi(S) wheels.

Of these two the Chi wheels moved regularly but the Psi wheels moved intermittently under control of the two so-called motor wheels. Thus stripping off the Chi wheel added characters was the first part of the attack on the cipher. When this had been done with the correct Chi patterns and correct Chi starts, the result was known as the De-Chi.

BREAM DECHI

............H.H.......H.............H.....H.....H.H...H........
H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H
H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H
H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 3 4 - + . /

This is also nearly flat random. However what Bill Tutte found was that if the DELTA was used things were very different. The DELTA results when one character is added to the next. If these are the same this gives / (all dots)

G++MA--.D+L---RUFSTELLUNGSSTAB.++YP.
../.../.....//......./..../...../...

So now using DELTA

DELTA BREAM PLAIN LANGUAGE

..............................................................H
..............................................................H
..............................................................H
..............................................................H
..............................................................H
..............................................................H
..............................................................H
..............................................................H
..............................................................H
..................H.....................H.................H...H
..................H.....................H.................H...H
............H.....H.....................H...........H...H.H...H
H.........H.H.....H.H.H.....H...H.H.H.H.H.......H.H.H.H.H.H...H
H...H...H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H
H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 3 4 - + . /

Again the uneven distribution of Delta plain language shows, but what also shows is the very large count of "/" resulting from the large number of repeated characters in the language and in the teleprinter editing characters.

Whilst the Delta cipher text is still nearly flat random:

DELTA BREAM CIPHER

......H.....H.....H...H.H...H...........H...........H..........
H.H.H.H.H.H.H.H.H.H.H.H.H...H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H
H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H
H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 3 4 - + . /



The Delta of the DeChi shows a residue of the excess of the "/" character

DELTA BREAM DECHI

..............................................................H
..............................................................H
....................H...H...H...H.......H...............H.H...H
H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H
H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H
H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H.H
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 3 4 - + . /

If the Chi wheel patterns are known, then the correct start positions can be found by trying every possible combination of wheel starts, adding the resultant characters to the cipher text and counting the number of resulting "/"s. This will be a maximum when the pattern starts are correct for the cipher text.

But the Chi wheels have lengths of 41, 31, 29, 26 and 23 so the total combination of possible wheel starts is about 22 Million!! so even today exhaustive search would take a long time.

However what Bill Tutte also found was that it was possible to do the search in smaller segments. If wheels K1 and K2 are taken first, this is only 1271 possible starts. If K4 and K5 are then set given K1 and K2 in the correct position, this is only 598 starts and if then K3 is set given all the others correct this is only 29 starts. So the resultant start search space is only 1,898 compared to 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.