The Secret History of Typex QQQQQ…

A few years ago, while giving a talk at Westminster Under School on the WW2 pigeon cipher, I mentioned that (a) Typex messages were sent in groups of five letters; and (b) when some German codebreakers looked at intercepted Typex messages early on in the war, they noticed that the last letter of each cryptogram was almost never X.

I then asked the Westminster boys what the Germans inferred from this (which was actually an incredibly subtle and difficult question). I was thoroughly delighted when a quiet high voice at the back suggested that the Germans could have concluded that they were looking at an Enigma-class machine encryption, where the last letter group was padded out with Xs.

Indeed, our young future head of GCHQ was right: the space bar on the Typex keyboard was attached to the X key, and operators typically used spaces (i.e. Xs) to pad out the final message group to a multiple of five letters.

Separately, German codebreaker Otto Buggisch also noticed early on in the war that the first three letters of RAF Typex messages were almost never A, I, and R respectively: though Buggisch deemed his obervation to have “no practical significance”.

All the same, this is a good example of bad enciphering practice (because stereotyped contents such as HEILHITLER or KEINEBESONDERENEREIGNISSE leave all cipher systems exposed), and goes to show that Britain started the war with cipher practices that were essentially no better or worse than Germany’s.

Yet if we have a look at the secret history of the QQQQQ group as used in Typex messages, we find something that might help us to (eventually) reveal the contents of a well-known cipher mystery…

The British Navy and Typex

ADM 1-27186 tells us in good detail how Typex cipher practice changed in the British Navy through the war years.

The Navy started with the same set of five black rotors used by the Army: the machine setting keys specified which drums to use, and were initially constant for a week, but on 2nd September 1940 were changed every day. A further two red rotors were added on 1st June 1941, giving a choice of seven rotors.

At first, the per-message drum settings were chosen at random by the operator and “the actual initial setting of the drums was transmitted as the first and last groups of the message or message section”. “Message sections were limited, for security reasons, to 60-70 groups, after which a new message section was chosen. Sections were separated by groups of five Q’s.”

Hence the first appearance of QQQQQ in Naval Typex messages was as a plaintext separator between message sections. That is, a typical long message would look as follows, where ABCDE was the (raw) indicator of the first message section and LMNOP was the (raw) indicator of the second message section:

ABCDE ….. [60+ groups] ….. ABCDE QQQQQ LMNOP ….. [more groups] ….. LMNOP

Buggisch also recalled that some Typex-related documents found at Dunkirk (along with a rotor-less Typex machine, and perhaps a reflector) mentioned “an English cipher security officer point[ing] out that he has noticed frequent breaches of the strict regulation that wheels should be turned on at random after a message has been enciphered”.

On 1st November 1941, however, Navy operators’ freedom to choose their own settings was curtailed, and books of disguised message settings were introduced in the Navy: at the same time, the practice of using QQQQQ as a section separator ceased.

After 1st March 1942, the optional use of Typex plugboards was indicated by FIELD at the start of messages.

1st February 1943 saw the introduction of two sets of seven new rotors wired specifically for the Navy, called “Code X” (for normal secure traffic) and “Cypher X” (for more secure traffic with plugboards), and where the original seven drums were still used for Inter-service traffic. Then:

On the 29th December, 1943, following a further review of Typex security, which amongst other things showed this system was particularly vulnerable to cryptographic attack from stereotyped beginnings, a revised procedure for concealing the start of the text was brought into force. From this date, the first ten to fifteen words of the subject matter were buried in the text, in addition to the address.

A new (and somewhat cumbersome) doubly-enciphered message setting procedure was introduced on 1st February 1944: but this was broadly balanced out by extra latitude when dealing with multiple message sections. Now “message sections were once again distinguished by the self-evidence group of five Q’s with the added proviso, however, that after each such group the right hand drum must be rotated one place before encyphering was continued.”

Finally:

In April 1944, the cyclic procedure was introduced as a security measure in the cyphering of short messages which, by reason of their brevity, were unsuited to the “buried address” procedure.

I don’t know what “the cyclic procedure” was, all suggestions gratefully received. 🙂

The British Army and Typex

Christos has a good page on the Typex, with scans of HW 40/89: ‘Typex questionnaire’:

From this, we know that at the very start of the war, each Typex rotor contained 14 “large” letters (of 26), where operator-set random settings could only use these large letters: but this restriction disappeared in mid-1940.

Codress burying (i.e. concealed coded addresses) was introduced on 1st January 1941, while disguised message settings were introduced on 19th May 1941, some six months before the Navy did the same.

A letter-shift procedure was introduced on 1st Feb 1944, and a figure/letter shift procedure on 1st September 1944: these were introduced in the Navy on the same dates.

The Royal Air Force and Typex

It was the RAF who invented Typex: but the amount of RAF-related Typex information I have found is quite small.

However, Stuart Rutter once posted some scans (now only in the Wayback Machine) from the February 1943 user manual for the (mostly) portable Typex Mk VI (which is what I suspect was used in the field for the Pigeon Cipher):

Preparation of message for transmission – Withdraw and detach the tape from the message printer and insert in manuscript, as the first group, the disguised message setting used at the commencement of the message. If the message is complete in one section write this disguised message setting and groups of five Q’s must be inserted appropriately in the spaces left for that purpose. Each section must begin and end with the disguised message setting, in manuscript, appropriate to it. The tape should then be gummed to a message form so that there are ten groups in each line. This is done in order to facilitate the counting of the total number of groups.

It’s not as clear as in the other cases how the QQQQQ section should be used, but it’s there nonetheless.

Can Love Conquer All?

Dufty recounts (chapter 43) a charming “cryptological love story” about two lovelorn Typex operators separated by General McArthur’s push North, who would occasionally hide messages to each other at the start of Typex messages.

The way they had been trained to use Typex was to write some filler nonsense text at the start (presumably the “ten to fifteen words” mentioned in the Navy account), followed by an (enciphered) QQQQQ separator, followed by the address and finally the actual message contents. Because the filler text was stripped out of the message at the far end before being passed onwards, the operators had just enough latitude to insert their own messages.

Incidentally, it’s not clear to me whether this QQQQQ was always added at a five-letter boundary or whether it could appear at any position: I strongly suspect the former, so it could prove valuable to find out from any still-living Typex operators if this is correct. (Perhaps I’ll ask David Dufty if he would be so kind as to ask one of the Australian Typex operators he interviewed.)

The reason this might be interesting to us is that if (as has seemed reasonably likely to me for some time) the Pigeon Cipher was sent on D-Day (6th June 1944), their Australian love messages in the margins were being sent at about the same time.

And so it may well be that the Pigeon Cipher’s internal structure includes a short filler section and a (plaintext) QQQQQ block, followed by a single extra step on the rightmost rotor: and only then the actual message.

Cryptanalyzing QQQQQ?

The introduction of a filler header plus a QQQQQ separator to Typex messages certainly had the effect of hiding stereotyped beginnings, which was a positive lesson learned from attacking Enigma.

Yet had German cryptanalysts had a reflector and a set of Typex rotors to work with (which they very nearly did on a number of occasions, most notably in Dunkirk and in Tobruk, and there was even a “North African Story” that claimed that they did), could they have exploited (later in the war) the presence of plaintext QQQQQ to crack messages, perhaps with some Bombe-like machine assistance?

Kelly Chang’s (2012) dissertation on the cryptanalysis of Typex is silent on this: Chang treats Typex messages as if they were flat, uniform text messages (i.e. ‘pure’ Typex), which – as we can see from all the above – they were often not.

So, if a Typex message contains plaintext QQQQQ, where would it be? A first trick is to note that because we also know that Q cannot encipher to itself on both Enigma and Typex machines, we need not search for QQQQQ anywhere in a Typex message where Q appears: that is, we can sometimes see where QQQQQ isn’t. And if it turns out that the practice was to only place QQQQQ on five-letter boundaries in the plaintext, we need not check any ciphertext block containing a Q.

Furthermore, given a day’s collection of intercepted Typex messages (which would all have the same rotors selected), a German codebreaker could select the message with the most (random) instances of Q in the top part of the message, so as to sharply reduce the number of places to brute-force search for QQQQQ (because each Q instance in the ciphertext would ‘knock out’ itself and four preceding positions to check).

Curiously, in the case of the Pigeon Cipher, if we colour blue the five-letter indicator groups at the start and end, and colour red all the instances of the letter Q…

…you immediately notice that the third line (“PABUZ WYYNP …..”) contains no letter Q instances at all. This may just be a coincidence, of course: but I personally would be unsurprised if that line turned out to contain QQQQQ in the plaintext somewhere.

If this is right, do we now have enough to break the Pigeon Cipher? I’m not yet sure: but I suspect we’re starting to move closer to a position where we can reduce the search space by millions (if not billions) of times. And at some point, perhaps we’ll have reduced it enough to be able to sensibly set a search in motion… we shall see, fingers crossed!