Saturday, July 5, 2008

Werftschlüssel and Rasterschlüssel '44

180px-Enigma.jpgIt is now time for the second and third of my promised favorite ciphers. And, just to let you know, I am now planning on creating an entry for Vic cipher and some of the other very elaborate spy ciphers of the cold war. Operationally Vic and its cousins were not effective for the field -- requiring too much precision, time, and care and training for a field radio operator or cipher clerk who may well be working under fire. The importance of ensuring that ciphers can realistically be used in field conditions sometimes escapes the notice of the experts charged with developing cipher systems. As we will see, this weakness played an important role in undermining one of the ciphers planned for study today. ADFGVX, on the other hand, certainly can be implemented under field conditions.

I feel I proved this when I wrote my last crypo blog entry -- the examples were all typed while riding the bus!

The Werftschlüssel is more generally known by its anglicized name "Dockyard Cipher" or just "Dockyard." It was the standard mid-grade code used by the German navy during WW2, a companion to the famous Enigma machine that was better suited to auxiliary vessels, small units, and others situations where the expensive and valuable Enigmas could not reasonably be issued. Dockyard is best known for the role it played in routine breaking of Enigma ciphers. Always ready to help out their foes with some bad practice, the German navy would often send identical (or at the very largely similar) messages in the two systems. The easier-to-break Dockyard would yield the known-plaintext crib that was necessary for the folks at Bletchley Park to break that day's Enigma settings.

Dockyard was simple to implement -- the plaintext was written out in five columns (apparently there were specially printed tables to help with this process).

Using the plaintext "It was the best of times, it was the worst of times" would set up columns like this:


Each vertical pair of letters (or digraph) would be encrypted together according to one of a set of tables published on a monthly or bimonthly basis. IT would be looked up and replaced with its cipher pair, TH with its pair, WE with its, and so on. Each column would be enciphered with using the keypairs from a separate table. These columns were selected from the book of 20 or 30 columns mentioned earlier -- I don't know if the procedure was to use a daily set of columns or for the operator to select five for each message and somehow communicate that in an indicator group.

The idea of using 20 or 30 different digraph substitutions was an interesting one -- presumably intending to reduce the amount of traffic that was generated for each. The seriation step also helped break up common digraphs (e.g. the "ch" that is as common in German as the "th" is in English). Digraphic substitution is a nice way of diffusing the statistical predictability of language -- no single digraph has the same obvious statistical dominance as "e" for example. There still are trends, and with a large enough sample, they are noticeable.

The seriation of Dockyard works to further diffuse the common elements of language, but the resulting digraphs still do not have a random distribution, much as we might think that they would. The statistical frequency of individual letters and certain patterns of letter use still result in digraphs appearing more often than others. The EE pairing is more common than any other, for example, because there are simply more e's going around to possibly end up stacked on top of each other.

As a result, the Naval Section at Bletchley could slowly compile up a key for each of the tables in a set. Using the statistical procedures discussed together with some guesses about message content (all the tools of classical cryptanalysis), the tables would be recovered. Once the tables were recovered, identifying which five were in use on a given message was a relatively simple matter of frequency counts. From all of this, the Dockyard cipher was probably the greatest source of intercept information to the Allies about German naval movements -- particularly considering its role as a source of Enigma plaintext cribs. From 1941 to 1945, about 33,000 dockyard messages were intercepted. 90% of them were read the same day they were intercepted...

The second cipher of the day, Rasterschlüssel '44, was not quite as thoroughly broken by the Allies, but more because of its late arrival than because of its security. An unfortunate example of the distance between field operators and back-room-thinkers, RS44 was issued with ambiguous instructions and a complicated operational procedure that resulted in frequent resending of messages, slow operation, and frustrated cipher clerks. And since frustrated cipher clerks have been known to violate procedure and just send the damn thing in the clear once in a while, RS44 ended up as its own worst enemy.

Picture 1.jpgThough I titled this thread of blogging "My Favorite Cipher," and I am a big fan of ADFGVX and find something nifty about the simple tables of Dockyard, I don't particularly like the Rasterschlüssel. It is a transposition cipher alone -- something which a certain truthiest superstition tells me can't possibly be as secure as a mix of transposition and substitution (remember -- diffusion and confusion) as used by ADFGVX. How can it be, I just feel, that a cipher that preserves all the right letters can have the security of one that changes them? Just move then around -- like a big word scramble!

I know, it is wrong, but I can't help but feel that way...

RS 44 was a fairly complex table based transposition. The grid above was specially issued -- one per day -- to all units using the cipher. The clerk would randomly select a square to start in and begin filling in the message in the open spaces, working from left to right, wrapping down columns and back up to the beginning if the message ran off the bottom of the printed grid. The grid was printed on cardboard and was placed behind a thin "flimsy" printed with a grid that let the light and dark squares show through. That way the clerk knew what spaces could be filled in and what couldn't. Once the message was filled in, taking off began.

Using a complex and troublesome formula, the cipher clerk would then determine the column to begin taking the message text off. This process would proceed from top to bottom, moving from left to right as each column was completed. Once the leftmost column was transcribed off, the process would start at the rightmost and work through until the message was done. Indicator groups would indicate both the starting position of the message and the column from which the taking off to the final cipher text began.

That's it. This has been described as the ultimate hand field cipher -- but I can't help but feel a certain "that's it?" at the end of the procedure. But yeah, that's it. I suspect that we see another case of the "possibly combinations" fallacy. Based on the formula that created the daily grid tables, there was an absurdly large number of possible combinations. More, in fact, than rotor settings on the Enigma machine.

And again, German cipher designers let themselves be overwhelmed by the mathematical possibilities of a system and ignore implementation details.

I look back on these two, on Dockyard and RS'44, and can't help that they lack the certain elegance of ADFGVX. RS'44 in particular relies on the tired old misconception that a larger number of possibilities equates with increased security. Dockyard has the cleverness to use multiple keys within each message -- effectively decreasing the traffic in each substitution key. Unfortunately, it still generates a significant amount of traffic in each table. The designers of Dockyard probably thought that each combination of tables would effectively constitute an entirely new key (and picking 5 of 20 tables yields 1,860,480 possibly combinations, 5 of 30 yields 17,100,720).

Each table in dockyard was composed along the lines of some fairly strict rules. Any given letter pair and its cipher were reciprocal -- if EH enciphered as DG then DG enciphered as EH. No letter from the plaintext pair could appear in the ciphertexext pair. For the plaintext digraph ML the cipher digraph could contain neither the letter M nor the letter L in either position. This dramatically limited the possibilities that needed to be tried and gave the cryptanalyst a few extra clues. It simplified the job of creating the tables and sped things up for the cipher clerk and helped to introduce some self-checking features into the cipher. Nice idea -- but at a cost in security. A cost that was probably accepted in light of the massive number of tables available (or rather, of the massive number of combinations of tables that might be used in any given day's key).

Since the cryptanalysts at Bletchley learned to look at each column as essentially a separate entity, they were able to aggregate samples large enough to bring statistical tools to bear. With the result, as mentioned, that Dockyard was despite good intentions one of the most well read of German wartime ciphers.


Anonymous said...

I am afraid your description of of the decryption method for RS44 is not correct!

You wrote:" Using a complex and troublesome formula, the cipher clerk would then determine the column to begin taking the message text off. This process would proceed from top to bottom, moving from left to right as each column was completed. Once the leftmost column was transcribed off, the process would start at the rightmost and work through until the message was done."

Actually the deciphering clerk took off the columns in the order they were numbered on the stencil -- not from leftmost to rightmost as you describe. Without knowledge of this numbering, which changed every day and was unknown to the Allies, RS44 proved so difficult to solve that Bletchley Park and Arlington Hall gave up trying unless they had captured the stencils.

The difficulty came from two features: the unknown transposition over 25 columns and the unknown position of blank cells -- of which there were 15 in every row of 25.

Although this cipher was complicated and difficult for the clerks, as you rightly point out, it was nevertheless even more difficult to solve and thus was a highly successful cipher because so little was broken.

Just Nick said...

Thanks for the info -- I'll have to go back and reread the doc's I have on RS'44. I recall some extra steps in the decryption process but it has been a while since I've looked at it.

I'd argue, though, that a cipher's success is not just a product of security. An excessively complex cipher that leads to shortcuts, messages sent in the clear, messages repeated in different ciphers, etc. is only as effective as the effective security it provides - after the consequences of any shortcuts or errors are taken into account.

German cipher clerks were notoriously (and to my mind surprisingly) lazy and sloppy - perhaps a product of arrogance - leading to some of the breaks that the folks at Bletchley exploited. An example of this was a tendency to encrypt identical messages in multiple ciphers. If one of these ciphers (e.g. Dockyard) was broken, the decrypt could help provide a crib to break current keys/settings for the other, more difficult cipher (e.g. Naval Enigma).

Tough procedures, rigorously followed, and systems that helped ensure the following of those procedures, are as important to cryptographic success as the underlying algorithm.