Bigrams, Trigrams and Naval Enigma

by Tony Sale

Part 1 of 2 parts


Tony Sale's
Codes and Ciphers



This page is in the form of Lecture Notes and has not been fully edited for Web publication.



The difficulties in breaking German Naval Enigma.


It was one of the triumphs of WW II that it was broken.

At first sight it is not obvious why Naval Enigma was so difficult, it initially used the same version of the Enigma as the German Army and Air Force and these were broken virtually throughout the War. The difficulty lay in the indicator system. This was unique to the German Navy and involved a seperate coding system, bigrams and trigrams, for concealing the message setting. As will be explained, it was this indicator system which made the breaking of Naval Enigma so difficult.

The story starts with Arther Scherbius who invented the Enigma in 1922.
He produced a relatively simple commercial machine which was a four rotor machine without plug board.

It was bought by the German Navy and used from about 1926 onwards more or less unchanged from the commercial machine.

Then the German Navy changed over to the main machine, the Heimsoeth & Rinke as used by the German Army and later the Air Force.

That was a slightly different kettle of fish because first of all the wiring inside the rotors of the machine had been changed and also the reflector and stecker or plug board at the front of the machine had been added.

You might wish to visit the Technical description of Enigma.

The German Enigma Machine in summary.

1. "Reciprocal" : If A -> J then J -> A at the same wheel position.

2. "Non-crashing" : A cannot encipher as A.

3. Turnover notches on the alphabet rings. The rings can be set to different positions relative to the core containing the cross wiring. (the Ringstellung).

4. These are the letters showing in the windows when turnover was about to occur, together with the BP rhyme.
.
.(R)oyal (F)lags (W)ave (K)ings (A)bove.
..I......II......III....IV.......V.
.

This was a mistake. All wheels should have had the same turnover points, and the later wheels 6,7 and 8 did. With the turnover points being different the wheels could be identified.
Wheels 6,7 and 8 were added by the German Navy. These wheels all had two turnover points which were the same on all of them.
This shows the wheel turnovers plotted on an alphabet.
.
5,6,7,8.. 2.........4...6,7,8.....1.........3.
|.........|.........|...|.........|.........|.
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.
.

5. For each wheel number always the same letter shows in the window at turnover.

6. The electric current flows through the wiring and lights a lamp AFTER the wheel(s) have turned.

Early Enigma - the Poles.


The first Enigma machine, used by the German Navy in the 1920s had three wheels and no Steckers.

The early Naval machine was soon worked out because the Poles had purchased a commercial version.

In 1931 the German Navy changed to the "Heimsoeth and Rinke" Enigma as used throughout the German forces for the rest of the war. This initially had three wheels and a Stecker board with only 6 letter pairs being Steckered.

The Poles had already recruited the three young mathematicians , Zygalski Rozeki and Rejewski, and they were given the task of finding how to break it.

Marian Rejewski developed mathematical theories of the Enigma and with the aid of spy material, worked out the wheel wirings. The Poles then built replica Enigmas and were able to read traffic currently for many years.

The Polish copy has a plug board at the back with ordinary telephone jacks.

When the Poles were involved only 6 letter pairs were being steckered. Later it increased to 10 which was the optimum number. But with only 6 steckers the machine behaved very nearly like an unsteckered Enigma, this made breaking much easier.

Concealing the Message Setting.


The message setting gave the starting wheel positions for encoding or decoding.

The German Navy used two different methods to conceal the message setting from an interceptor.

a) the Enigma machine itself.

A message setting, chosen by the operator, was enciphered twice on the Enigma machine starting from the Grund and the resultant letters transmitted to the intended recipient in a header to the message.

b) a completely separate coding system

On May 1st 1937 the German Navy introduced a new indicating system, the bigram substitution.

This was the main Naval system and involved selecting a trigram from a book (the Kennbuch, or K Book), enciphering this at the Grund to get the message setting, then performing a bigram substitution on the trigram and then transmitting the result as a header to the message.

The intended recipient then performed the inverse bigram substitution to recover the trigram then enciphered this at the Grund to get the message setting.

The Poles suddenly found that their systems for breaking the double message setting system, no longer worked and they did not know why.

The Grundstellung for 8th May was found as a result of a typical German error. A torpedo boat, call sign AFA, had not received its instructions on the new system and was therefore told, in a message sent in another cipher which the Poles could break, to use the old system.

Two or three messages from AFA were enough to find the Grundstellung using Forty Weepy Weepy cribs. The Grund was the same as for April 30th and the intermediate days were then got out.

But despite having solved about 15 messages for each day, the Poles could not work out the new indicator system. They suspected that it was a bigram substitution but got no further.

Forty Weepy Weepy cribs.


Continuation messages: FORT 23.30.

Top row of Keyboard used for numbers. .
Q W E R T Z U I O P.
1 2 3 4 5 6 7 8 9 0 .
Letter Y used to indicate figures.

FORTYWEEPYYWEEPY.

.

The Daily Key,(Tagschluessel)


1. The Wheel Order (WO).

The numbers of the wheels to be placed in the Enigma machine from left to right.

( 336 possible from eight wheels).

2. Ringstellung,
(Tyre or Ring setting) for each wheel, left to right.( 17,576 combinations ).

3. Stecker, or plug-board connections.

Usually ten pairs involving 20 letters.( 140 million million ).

4. The Grundstellung (Grund).

The three (or four) letters showing the position of the wheels to be used for enciphering the message setting.

single Grund on right hand side.

Breaking Naval Enigma.


In 1939 only two people thought Naval Enigma could be broken:.

Frank Birch, Head of German Naval Section, and Alan Turing.

Birch because it had to be broken.

Turing because it would be so interesting to break it!.

Turing's Work.


1) The breaking of the indicator system

He started where the Poles left off, with the 100 or so messages from May 1st-8th 1937 whose starting positions were known.

From these he had the two four letter groups, the indicators, from each message and also the message setting, ie the start position for deciphering the message which the Poles had found.

Using these and some very elegant deductions, Turing worked out the complete indicator system.

At the same time, as he later said, "I thought of the method of Banbarismus, but was not sure that it would work in practice". This was at the end of 1939.

2) In early 1940, joined by Peter Twinn, he started an attack on messages for 28th November 1938 using Forty Weepy Weepy cribs. The reason for going back so far was that only 6 steckers were being used at that time and the FortyWeepyWeepy cribs were working. These messages were broken after a fortnight's work and four other days also came out.

These breaks were helped by the first use of the EINS catalogue.

The EINS catalogue.

Once messages began to be deciphered, it was realised that the German word EINS was by far the most frequent word in Naval messages.

It was then decided to take on the prodigious task of cataloguing the encipherement of EINS at all 105,000 possible start positions. (on the three wheel Enigma). This was done BY HAND.

Later it was put onto punched cards for Freeborne's section to use.

To use the EINS catalogue consecutive groups of four letters in the message were looked up to see whether they were an encipherement of EINS.

Then with an Enigma machine set to these settings the following characters were deciphered to see if German came out.

Using the K Book and Bigram tables.


1. Select a trigram from the K Book, say YLA.

2. Look in the Zuteilungsliste to see which columns of the K Book are allocated to his particular key ( Home Waters, U Boat etc).

3. Select another trigram, (the Schluessel kenngruppe), say YVT.

Message Sheet.

4. Write in the boxes at the top of the message form:.
.
, Y V T.
Y L A .
.
Fill in the "dots" with any letters, giving say.
.
Q Y V T.
Y L A G.
.
Bigram Tables.

Now look up the vertical pairs of letters in the Bigram Tables, writing down the resultant pairs.

UB LK RS PW.

These are transmitted as two four letter groups at the start and end of the enciphered message.

Description of receiving and decoding.

It gives the position from which to find the start position by deciphering on the Enigma machine starting at the Grund.

The Interceptors Problem.


1. working out the Bigram Tables.

This had to start with a "pinch", ie a capture of a set of tables.

Once message breaking had started, it was possible, with some difficulty, to work out new bigram tables. The tables were changed roughly once a year.

2. recovering the daily keys, ie Wheel Order and Wheel Start (the Grund).
There are 336 WO's and (26)^3 or (26)^4 start positions.

ie between 6,000,000 and 150,000,000 combinations to examine to find the right one.

3. This requires a test to distinguish between a right and a wrong position,

and a very rapid means of applying this test.

Tests to find the correct machine setting.


1. "Cribs".

A Crib in BP terminology was a guess at a section of the German text that was enciphered to give the intercepted enciphered message. Such a guess required clues and the Germans provided these in abundance.

a) because of the length, time of origin, call sign etc of a message it probably began with a phrase like:. VORHERSAGEBEREICH SIEBEN. (weather forecast for Area seven).

b) routine messages were sent out day after day at about the same time, from the same place, of the same length and starting in exactly the same way.

c) Re-encodements. These were retransmission of messages already sent on some other key.

2. Banburismus.

The situation in November 1939.

No cribs.

Banburismus.


Now what Banburismus is all about is that if you have two lengths of cipher text and from the trigrams you think that they may have been enciphered from nearly the same wheel start positions, then Banburismus enable you to find the difference in start postions of the two texts. This only works because the letter distribution of language text is not flat random.

Two messages texts compared at various offsets.

I have used two English texts, my German is not up to producing German text.

1) The code breakers were looking for instances where .
2) trigrams for two or more messages differed only in .
.

..THEXCODEXBREAKERSXWEREXLOOKINGXFORXINSTANCESXWHEREX.
..TRIGRAMSXFORXTWOXORXMOREXMESSAGESXDIFFEREDXONLYXINX.
4 |.......|..........................|..............|.

..THEXCODEXBREAKERSXWEREXLOOKINGXFORXINSTANCESXWHEREX.
...TRIGRAMSXFORXTWOXORXMOREXMESSAGESXDIFFEREDXONLYXIN.
2 .................|................|.

..THEXCODEXBREAKERSXWEREXLOOKINGXFORXINSTANCESXWHEREX.
....TRIGRAMSXFORXTWOXORXMOREXMESSAGESXDIFFEREDXONLYXI.
3 ....................|.....................|.|.

..THEXCODEXBREAKERSXWEREXLOOKINGXFORXINSTANCESXWHEREX.
.....TRIGRAMSXFORXTWOXORXMOREXMESSAGESXDIFFEREDXONLYX.
3 ......................|.|.........................|

..THEXCODEXBREAKERSXWEREXLOOKINGXFORXINSTANCESXWHEREX.
......TRIGRAMSXFORXTWOXORXMOREXMESSAGESXDIFFEREDXONLY.
4 ...............|..|......|................|.

..THEXCODEXBREAKERSXWEREXLOOKINGXFORXINSTANCESXWHEREX.
.......TRIGRAMSXFORXTWOXORXMOREXMESSAGESXDIFFEREDXONL.
2 .................|...................|. ..THEXCODEXBREAKERSXWEREXLOOKINGXFORXINSTANCESXWHEREX.
........TRIGRAMSXFORXTWOXORXMOREXMESSAGESXDIFFEREDXON.
3 ..........|...........|.......|.

..THEXCODEXBREAKERSXWEREXLOOKINGXFORXINSTANCESXWHEREX.
.........TRIGRAMSXFORXTWOXORXMOREXMESSAGESXDIFFEREDXO.
3 ............|...........|......................|.

..THEXCODEXBREAKERSXWEREXLOOKINGXFORXINSTANCESXWHEREX.
..........TRIGRAMSXFORXTWOXORXMOREXMESSAGESXDIFFEREDX.
2 .........................|........................|. ..THEXCODEXBREAKERSXWEREXLOOKINGXFORXINSTANCESXWHEREX.
...........TRIGRAMSXFORXTWOXORXMOREXMESSAGESXDIFFERED.
9 ..........|.....||..|...|............|.........|||.

..THEXCODEXBREAKERSXWEREXLOOKINGXFORXINSTANCESXWHEREX.
............TRIGRAMSXFORXTWOXORXMOREXMESSAGESXDIFFERE.
4 ......................|..|........|..|.

..THEXCODEXBREAKERSXWEREXLOOKINGXFORXINSTANCESXWHEREX.
.............TRIGRAMSXFORXTWOXORXMOREXMESSAGESXDIFFER.
7 ...............|................||........|||....|.

.

This shows that the number of repeated letters is significantly greater than random, which would have been 2 on average.

Now consider these two texts as enciphered on an Enigma machine.
.
NOT KNOWN to the interceptor. * ...............WO..Ring.........Steckers.
TagSchluessel:..425..GMY...DN GR IS KC QX TM PV HY FW BJ.
Grund: MDU.
*. Message 1. KennGruppe: YLA -> NOT KNOWN start position * BUC *.
.
The code breakers were looking for instances where trigrams for two or more messages differed only in the last letter.
.
THEXCODEXBREAKERSXWEREXLOOKINGXFORXINSTANCESXWHEREX.
WEOWGZFFKDESKOAXNQXKQMCBCHOJCKTWDDGPAZISQSBLEAGQLNU.

Message 2. KennGruppe: YLO -> NOT KNOWN start position * BUL *.

TRIGRAMSXFORXTWOXORXMOREXMESSAGESXDIFFEREDXONLYXINX.
LEAEZEUNQIWQIHRCCKEKWAQZNIYJZMHTCVUNCAAIHYAXMJOKJSY.

Letter histograms.
....H.....................
....H..................H..
....H..................H..
....H..................H..
....H..................H..
....H.........H..H.....H..
....H........HH..HH....H..
H.H.H..HH.H..HH..HHH..HH..
HHHHHHHHH.HH.HH..HHH..HH..
ABCDEFGHIJKLMNOPQRSTUVWXYZ.
text 1.

..........H.....H.........
H.HHH.H...H...H.H.H...H...
HHHHHHH...H..HH.H.H...HH.H.
HHHHHHHHHHHHHHHHH.HHH.HH.H.
ABCDEFGHIJKLMNOPQRSTUVWXYZ.
cipher 1.

.......................H..
.......................H..
.......................H..
.................H.....H..
....H.........H..H.....H..
....H.........H..HH....H..
....HH..H...H.H..HH....H..
H..HHHH.H...HHH..HHH...H..
H..HHHH.H..HHHH..HHH..HHH.
ABCDEFGHIJKLMNOPQRSTUVWXYZ.
text 2.

H.........................
H.H.H...H.................
H.H.H..HHHH..H..H.......HH.
H.H.H..HHHH.HH..H...H.H.HH.
H.H.H..HHHHHHHH.HHHHHHHHHH.
ABCDEFGHIJKLMNOPQRSTUVWXYZ.
cipher 2.

.

In both of the above you can see the definitely non random spread of text letters and the much more nearly random cipher text spread.

The question now is can you manipulate these two cipher texts so that you can slide them relatively to find the point at which they are on the same start postion. The answere is yes if you punch them onto Banbury Sheets, so called because they were printed in Banbury, a town about 30 miles away from Bletchley.

These sheets had up to 200 alphabets running side by side vertically down the sheet with A at the top.

Two punched sheets as per cipoher texts 1 & 2.

Cipher text 1.
.
WEOWGZFFKDESKOAXNQXKQMCBCHOJCKTWDDGPAZISQSBLEAGQLNU.

AAAAAAAAAAAAAA.AAAAAAAAAAAAAAAAAAAAA.AAAAAAAA.AAAAA.
BBBBBBBBBBBBBBBBBBBBBBB.BBBBBBBBBBBBBBBBBB.BBBBBBBB.
CCCCCCCCCCCCCCCCCCCCCC.C.CCC.CCCCCCCCCCCCCCCCCCCCCC.
DDDDDDDDD.DDDDDDDDDDDDDDDDDDDDDD..DDDDDDDDDDDDDDDDD.
E.EEEEEEEE.EEEEEEE.EEEEEEEEEEEEEEEEEEEEEEEEE.EEEEEE.
FFFFFF..FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF.
GGGG.GGGGGGGGGGGGGGGGGGGGGGGGGGGGG.GGGGGGGGGGG.GGGG.
HHHHHHHHHHHHHHHHHHHHHHHHH.HHHHHHHHHHHHHHHHHHHHHHHHH.
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII.IIIIIIIIIIII.
JJJJJJJJJJJJJJJJJJJJJJJJJJJ.JJJJJJJJJJJJJJJJJJJJJJJ.
KKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK.
.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLL.LL.
MMMMMMMMMMMMMMMMMMMMM.MMMMMMMMMMMMMMMMMMMMMMMMMMMMM.
NNNNNNNNNNNNNNNN.NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN.N.
OO.OOOOOOOOOO.OOOOOOOOOOOO.OOOOOOOOOOOOOOOOOOOOOOOO.
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP.PPPPPPPPPPPPPPP.
QQQQQQQQQQQQQQQQQ.QQ.QQQQQQQQQQQQQQQQQQQ.QQQQQQQQQQ.
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR.
SSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSS.
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT.TTTTTTTTTTTTTTTTTTTT.
UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU..
VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV.
.WW.WWWWWWWWWWWWWWWWWWWWWWWWWWW.WWWWWWWWWWWWWWWWWWW.
XXXXXXXXXXXXXXX.XX.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.
YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY.
ZZZZZ.ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ.ZZZZZZZZZZZZZ.
.
Cipher text 2.
.
LEAEZEUNQIWQIHRCCKEKWAQZNIYJZMHTCVUNCAAIHYAXMJOKJSY.

AA.AAAAAAAAAAAAAAAAAA.AAAAAAAAAAAAAAA..AAA.AAAAAAAA.
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB.
CCCCCCCCCCCCCCC..CCCCCCCCCCCCCCC.CCC.CCCCCCCCCCCCCC.
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD.
E.E.E.EEEEEEEEEEEE.EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE.
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF.
GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG.
HHHHHHHHHHHHH.HHHHHHHHHHHHHHHH.HHHHHHHHH.HHHHHHHHHH.
IIIIIIIII.II.IIIIIIIIIIII.IIIIIIIIIIIII.IIIIIIIIIII.
JJJJJJJJJJJJJJJJJJJJJJJJJJJ.JJJJJJJJJJJJJJJJJ.JJ.JJ.
KKKKKKKKKKKKKKKKK.K.KKKKKKKKKKKKKKKKKKKKKKKKKKK.KKK.
.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL.
MMMMMMMMMMMMMMMMMMMMMMMMMMMMM.MMMMMMMMMMMMMM.MMMMMM.
NNNNNNN.NNNNNNNNNNNNNNNN.NNNNNNNNNN.NNNNNNNNNNNNNNN.
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO.OOOO.
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP.
QQQQQQQQ.QQ.QQQQQQQQQQ.QQQQQQQQQQQQQQQQQQQQQQQQQQQQ.
RRRRRRRRRRRRRR.RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR.
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.S.
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT.TTTTTTTTTTTTTTTTTTT.
UUUUUU.UUUUUUUUUUUUUUUUUUUUUUUUUUU.UUUUUUUUUUUUUUUU.
VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV.VVVVVVVVVVVVVVVVV.
WWWWWWWWWW.WWWWWWWwW.WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW.
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.XXXXXXX.
YYYYYYYYYYYYYYYYYYYYYYYYYY.YYYYYYYYYYYYYY.YYYYYYYY..
ZZZZ.ZZZZZZZZZZZZZZZZZZ.ZZZZ.ZZZZZZZZZZZZZZZZZZZZZZ.
.

Banbury Sheet Results.

.
.............offsets: 0 1 2 3 4 5 6 7 8 9 10 11.

Original text scores: 4 2 3 3 4 2 3 3 2 9 4 7.

..Cipher text scores: 3 1 1 1 0 2 2 2 2 9 2 1.

.

Its even more spectacular if you compare two enicipherements of the same letter, E as it happens, from the start positions BUC and BUL.

When these two are at the same positions then suddenly all the hole line up. This is what you would expect since exactly the same enciphered letters are being produced by each encipherment from that point.

This registration of positions was known as a "depth".



Continue to Part 2 of the Lecture



This page is created by Tony Sale
(tsale@qufaro.demon.co.uk) the original curator of the Bletchley Park Museum