Linear Feedback Shift Registers and The Playing Card Cipher

So I was looking for a name for my playing card cipher that I described a few days ago. I'd go with that, call it PCC for short, but that is the name of a local market chain and therefore has already been taken.

I'd thought of a few more. Realize, please, that ciphers often have acronym names and, particularly for not-so-serious ones like this, the name involves a degree of punning. Hence the following candidates:

CARD: Cipher Algorithm with Randomized Deck
DECK: Deniable Encryption with Card-based Keystream

Personally, I like DECK. And so DECK it shall be known as. At least for the length of this post.

Now, after writing up the initial description, I thought it might be a good idea to expand on the underlying design and design rational. And, by way of that, to talk a little about stream cipher design.

First off, I know that this is by no means the first attempt to produce a cipher based around playing cards. At the very least "Solitaire," developed by Real Cryptologist and crypto-guru Bruce Schneier got there first.

But I think that my Clever Idea is the use of playing cards as indicators of binary state, therefore enabling the translation of any cipher into playing card form -- it is just a matter of producing one that blends simplicity and security in a way as to produce a reasonable amount of security for a reasonable amount of effort.

For various reasons, when I was putting together DECK this "reasonableness requirement" drove me to focus on stream ciphers. In a nutshell, a stream cipher is one where the cipher mechanism operates independently of the plaintext. The output of this independently running stream then modifies the cipher text one bit (in the case of a binary cipher like mine) at a time. Most older stream ciphers are bit-oriented because they were intended to be implemented in dedicated hardware (military radios, bulk encryption hardware, cell phones). Many newer ones are designed to produce 8-bit bytes, 32-bit words, or other chunks of keystream all at once, as ciphers are increasingly expected to run on general purpose computing systems.

But we're dealing with playing cards and need to keep it simple -- so a bitwise stream cipher it was to be.

The most well understood mechanism of stream cipher design is something called a Linear Feedback Shift Register or LSFR. If you look at DECK, you will see that it has three of them -- each of the three rows of six, seven, and eleven cards constitutes an LSFR.

An LSFR consists of a certain number of registers (each card is a register). An LSFR steps, as described in CARD, by pushing the contents of the register one to the right (from the input side to the output), discarding the rightmost bit, and using a combination of bits in the register's previous state to produce a new input bit going in to the new state.

The input bit is produced by XOR of the contents of several specified bits in the register. If the specified bits are chosen correctly (technically they must be primitive polynomials, which is something I don't really understand, but is something I can look up here or here or here) then your LSFR will produce a sequence of output bits (based, say, on the rightmost bit of the register, the one we "discard" with each shift) that does not repeat for 2^n-1 steps (where, predictably, n is the length of the register).

In other words, a properly designed 6-bit LSFR will produce a unique sequence of bits for 63 steps. A properly designed 7-bit LSFR will produce a unique sequence of bits for 127 steps. And a properly designed 11-bit LSFR will produce a unique combination of bits for 2,047 steps. It also means that there are 2n unique patters that each LSFR can produce.

Now I could simply use an LSFR to produce a sequence of bits -- and indeed this approach can be used when a non-secure cipher is needed (e.g. when randomizing an electrical signal to reduce RFI or for some spread-spectrum transmission techniques). But I want to produce a secure cipher and for that a simple LSFR is not going to work.

Here's why:

A Linear Feedback Shift Register has, unsurprisingly given its name, a linear output. That means that the output of the LSFR depends in a simple and obvious way on the contents of the LSFR. If I had a simple LSFR and I recorded the output for a period of time equal to its length, then I would know what the register contents were at the point I started.

Since an LSFR is also deterministic, that is to say that given the state of the register at any given time it is possible to determine the state of the register at any other time, once you know the register at one point in time any future or past output can be determined.

A simple known-plaintext attack then makes breaking a simple LSFR child's play.

Some complications are needed. One option is to combine a single LFSR with some sort of nonlinear stage to generate the output.

This would mean instead of taking the keystream off the right-hand-edge of the cipher I'd do something more complex. Typically this would involve grabbing not just the end value but several values from within the register and combining them together in a more complex way.

At first this was the approach I pursued.

The original draft of DECK (which may yet see some life in a mildly altered form) was a 24-bit (24-card) LFSR. The reason for 24, by the way, was the purely arbitrary decision that the 16-million possible keys to a 24-bit keyspace would produce enough security for my application.

I then developed a simple non-linear function (by flipping a coin during that epic conference call) that took four input bits from the LFSR and used them to determine a single output bit. I had the idea that which four bits in the LFSR were tapped to feed the non-linear function could be part of the keyspace and therefore increase the complexity of the cipher.

This is inspired by a late-cold-war cipher called KEA that was used in some exportable radio equipment that was sold under various Foreign Military Sales efforts. Exact details of KEA (which I believe stands for "Kinetic Encryption Algorithm) are not known, but the variable-taps-to-non-linear-combiner idea comes from there.

Anyhow, it turned out to be rather more difficult to keep track of those 24 cards, stepping all of them every round, then I expected. And, while I'm sure I'd eventually have memorized it, I kept having to consult a table written on a sticky note ("Stick Together!") to produce the output bit.

This lead to a phase of introspection and review. There is, fortunately, another way to generate a less-guessable output from a LFSR. This involves combining the output of several registers together. Several registers with regular stepping can be mixed by a non-linear function, as is done in the E0 cipher used in Bluetooth devices.

While this might break up the stepping from one titanic effort of 24 cards at a time, I'd still be dealing with some sort of memorized nonlinear function (and the one in E0 is a bear, so I'd have to simplify it a lot for my purposes).

Another approach for adding nonlinearity to cipher consisting of several LFSR's is to step them irregularly but combine them simply. This is done in a lot of simple (and theoretical) bitstream ciphers. Read Applied Cryptography to read about them. This is also the approach taken by A5/1, the much mocked GSM cipher.

A5/1 isn't really mocked so much as it is broken. Which, in cryptanalytic circles, is the same thing. It has several known flaws and a sufficiently small keyspace as to make them practical for exploitation. But before we get all cranky about it, let's remember that A5/1 was developed in 1987 -- 22 years ago, an eternity in cipher years and was, if you buy the conspiracy theories, deliberately kept somewhat weak at the request of European police and security agencies. Though much of that intentional weakening is in the key setup, which is out of scope for this discussion.

Despite this, I've always found A5/1 to be a very pleasing cipher. Let's take a look at it:

Note that Wikipedia has very much more attractive illustration of A5/1 here but the diagram runs from RIGHT-to-LEFT, the reverse of all of my other descriptions. My brain must work from left-to-right, the opposite of French cryptologists (A5/1 is French). So I found this image, which I pwned, but since I got it from a ppt about breaking A5/1, I don't feel too naughty.

If you think back to the description of DECK, you may already see similarities. Note the three LFSR's: upper, middle, and lower. The plus-in-a-circle stands for XOR, so you may be able to figure out the three feedback lines, one for each register. The upper and bottom are tapped in four places, the central one in two places. The output is generated by simply XOR'ing the rightmost bits of each of the three registers.

None of this is fancy -- and in fact none of it is particularly secure. Where A5/1 gets interesting is how it clocks the three registers. Look at the three center(ish) bits, C1, C2, and C3. Just like DECK, A5/1 clocks whichever registers have the same value as the majority of the center bits. Two or three registers clock.

What drew me to this construction is that 3/4 of the time, only two registers have to clock. So, when it comes time to flip the playing cards, instead of having to deal with 24 of them every round, there is a chance that our DECK-using agent will only have to flip 13, 17 or 18 cards. On average, that means flipping 18 cards. Labor saving!

To get the numbers down, for DECK, I reduced the contents of all three registers. I also changed the feedback polynomials and tapped all three registers at only two places each. Both have a negative security impact, I'm sure, but also simplify the user's job. The fact that the taps for the shorter two registers work out to the last two positions helps. So the only extra number that needs to be memorized is that the long register taps at the 9th and final spots.

So that is, roughly put, the evolution of DECK. All of the other discussion points of developing a good binary language that were mentioned in the original posting apply.

Now I'm still playing with this playing-card-cipher idea. I still hold out some potential for the single-register version. I also have some thoughts about a "short but wide" cipher that uses five bit values for each stage of the shift register, thereby producing enough output to encipher one "letter" worth of information at a time.

I also wonder if there would be a way to mix a couple of techniques to produce "reasonable" security with greater convenience. Perhaps a fixed permutation (shuffling but not flipping) of a set number of bits at a time (probably five) combined with a more simply generated keystream. This might vaguely resemble Phillip Rogaway's OCB block cipher construction which I'm rather partial to (and not just because he's a prof at Davis, my home town). The permutation could be keyed but constant across a given message. Not sure about the security implications of that, or how much additional convenience it would give.

More musings...likely...

It would get away from the genesis of DECK, which was to use playing cards to implement well understood modern cipher techniques. But hey, its all in fun anyway, isn't it?

On the security of passed notes in a 8th grade classroom...

This entry into my blog is a letter of advice to all of you school children who are out there passing notes, hoping to keep your messages secret from other students, teachers, and administrators. To tell you the truth, I have no idea of you kids these days are still passing notes, but I choose to believe that you do, that it isn't all SMS traffic these days. Much like I choose to assume that all kids today aren't taking MDMA like it was M&M's and/or packing a 9... But, given that I've recently learned that all kids do apparently go through a dinosaur phase, I feel that there is hope for the world.

But this isn't about parenting and the resulting paranoias and self deceptions, it is about maintaining traffic security.

Kids, your channels are wide open to interception. You've all seen the teacher intercept the passed note, read the contents aloud, and shame those involved into humiliation. That's just not cool. No one knows that you saw Joey around behind the library kissing Jenny or whatever is in those notes (that do actually seem to be a predominantly female concern). Least of all Joey or Jenny or the members of your intelligence network. So start to put some kind of protective encipherment across these things.

You might be using a simple monoalphabetic substitution -- and that will prevent the causal reader from understanding the message at a glance. Shifting all the letters one, two, or thirteen to the right might buy you what the intelligence guys call operational security -- that is enough time to complete your mission (let us say sneaking around behind the library to kiss that good-for-nothing but hunky Joey), but it won't save the message from eventual decryption and your actions from exposure (possibly at the worst possible moment -- mid smooch!). So if you're going to use a monoalphabetic, at least use yourself a random alphabet, even if it does increase the workload at encryption and decryption time. Security is not for the lazy or hurried!

Far better would be to pull out a polyalphabetic -- a code that uses several different alphabets to arrange the substitution between the plain text and the cipher text. These can actually be pretty easy to set up based around an easy-to-remember code word, and therefore simpler to implement operationally in that no-evidence world of the deep cover agent or middle school student. Pick a keyword that everyone knows and agrees to. Ideally it is random and meaningless, but let's make it easy and fun and choose the school mascot's name. My high-school was the Blue Devils. That'll do nicely. It provides us with a sequence of ten different (well, actually eight different) alphabets that we use. For the first one, the letter A in the plaintext would be enciphered as a B and any other letters would use the same shift of 1. For the next letter in your plaintext, the letter A would encipher as an L, a B as an M, a C as an N and so on -- based around the original shift. For the third letter, A would encipher as U...and if you are referring back to they codeword, you probably have the method figured out.

This vastly increases complexity, because if the message is sufficiently short and the key period (the time until you wrap around and start reusing the same sequence of alphabets -- ten characters in this case) is unknown, the cryptologist has a much more challenging job of applying the sort of statistical analysis that can blow a straight monoalphabetic wide open. But here we run into one of the unfortunate errors made by amateur and hobbyist cryptographers -- that of assuming that each message will face an enemy's scrutiny in isolation. The reality is that a cipher system is rarely, if ever, practically used on a single message. Instead it is used for days, weeks, or even years to protect a whole series of messages. The longer the system and the key is in force, the greater the volume of traffic likely to be intercepted and the greater the quantity of raw material the analyst can work with. And, remember, that once a key is blown based on bad practice with a single message or amassed traffic, all the traffic protected by that key is compromised. No good.

So change your keys often -- perhaps every week. Or every day. And use keys that are hard for the analyst to guess. No boy bands, teen idols, or school mascots.

Here is another good tip -- use a superenciphered code rather than a straight cipher. Cryptanalysis depends very strongly on probability and good guesswork -- guessing the nature of the message you are trying to break. If you know that the message contains a certain word in a certain location, you can figure out what the alphabetic substitution was at that point and possibly get a break that will spread further or to other messages. So let's suppose you have a science teacher named Mr. Polymer who is sadly encumbered with extremely protuberant eyes. If you send a message in his class, there is a fair chance it would contain the word POLYMER, thereby giving your foe a clue. Instead, make up some codeword that stands in for his true name. Don't make it MR BUGEYES or anything else that is obvious. Make it BLUE SHARK or even better yet something completely random like GRLXX or LYUOG. Do this for all frequently used or distinctive names and locations. For very frequently used ones, have several code names that you switch between at random, so that hunk Joey might be known as LNEMQ, POVON, and WEUBC depending.

Much improved -- but with a warning. If you are in a hurry -- never partially protect a message. If you have to pass a note and don't have time during the geometry quiz to fully encipher it, don't use the codewords at all. This merely risks their compromise if the message is intercepted. TELL WEUBC TO MEET ME BEHIND THE YRPED DURING NRFFO TO QAGOT is really just asking to have the codes for Joey, library, lunch, and presumably "make out" compromised -- not just for this message but for all messages. Thing strategically and don't put the network at risk out of a desire to protect one message.

In general, don't put any easily guessed information into your message. It might seem surprising, but the headers that contain message address information should never be enciphered. They should be sent either in clear text or using another cipher or code of some sort. It might seem like a huge risk to your security, but predictable information like names and addresses should never be put in the body of an encrypted message. Again, don't risk the entire message or channel out of a desire to protect one part of it. Most military ciphers of the golden age used separate codewords or encipherment tables to secure the beginning and end of the message.

While you're at it -- see if there is something you can do to vary the cipher key used slightly. This is another component of most military grade ciphers. There is a weekly or daily key that is common for all folks on a channel. But there is another part of the coding system that is varied from message to message -- a indicator as it is usually known. We might choose to slightly vary the shift in our polyalphabetic or add a transposition (think word scramble) component to our cipher that is controlled by this indicator group. The indicator group is sent in the clear somewhere in the message or its header information. We might apply some transformation to the indicator before using it in our keying process, but we always send it in the clear.

I know -- its starting to get kind of hectic by now. But remember that the risk of compromising your intelligence and actions never allows for shortcuts. For the moment, I leave you with a relatively effective polyalphabetic and some good instructions about how to ensure that it is implemented in an effective system. Be careful, keep the notes short, and don't get caught with Joey! More sophistication, and more protection, are coming...

An interesting discovery

Every so often an old interest gets dragged up out of the background and brought into the light again. And in that background-to-light-dragging process, I always find that I learn something new about that area of interest or am able to attack it with some new perspective.

Well over the past few weeks, I've rediscovered the world of "crypto" with a certain enthusiasm. And as I've come back to visit those old friends, ADFVGX, NEMA, Dockyard, and the SX-52, I've looked at some of them with a new light. And I've discovered new companions (even if I don't like them very much) like the Rasterschlüssel'44.

And here is another new one -- one that has been known about since the mid-1990's but that I never paid attention to: the Reihenschieber. It translates as "series slide" and both the word and the device bear a noticeable (and noteworthy) relationship with slide rules (Rechenscieber). This interesting device was developed during the 1950's, put into use in the German armed forces in 1957, and used for a decade or so to encrypt information described as "up to top-secret." Since cipher technology of the cold war tends to be much harder to learn about than that of the second, this device holds a lot of potential to see how cryptographic thinking advanced in a decade or two.

Note that the Reihenschieber was developed before the revelations about British cryptanalytic success during the war were made public in 1977 -- and therefore may not embody the full state of the art that the agencies privy to that information had at hand. It was also an artifact of the early Bundeswehr, and so developed under some significant restrictions as imposed by the allied powers.

Note that in this article I'm choosing, unusually, to analyze the cipher and perform my back-of-the-envelope cryptanalysis first, rather than opening with a description of the device and its operation. I'm working primarily from John Savard's excellent description which, never the less, contains some areas of ambiguity on the actual use of the cipher. I haven't yet decided to spring the $35 for a reprint of the 1996 Cryptologia article that is the definitive source of Reihenschieber information and until then, my knowledge of its implementation may remain a little sketchy.

The result of these advances and constraints is an interesting device -- half mechanical crypto and half classical. It is a mechanical series of rods that generate a (hopefully) pseudorandom number sequence. This pseudorandom sequence is in turn used to select which column (from one of ten) and which table (one of two) is to be used to perform a simple substitution of each letter in the plaintext.

Does this sound familiar? A polyalphabetic substitution where the cryptographic strength lies in the fact that the alphabets change frequently? Think about how an Enigma machine works -- or any other machine of the period for that matter. At any given point, it consists of a single arrangement of input letters to output letters. Press a key, your input letter gets enciphered according to that arrangement, and then a new arrangement is selected for the next letter using a very complex mechanical (or electro-mechanical) scheme.

Effectively, this is the exact same method used by the Reihenschieber. Instead of a series of wheels, pins, cams, and wires that generates an ever-changing series of substitution alphabets from a vast menu (in the case of some of the machines the number of possible alphabets could be 26! or more -- 4.032914611266057x10^26 if you like), the Reihenschieber select one of twenty pre-generated alphabets according to a complex (but nothing like Enigma or its friends) series of sliding rods.

This is also similar the Dockyard cipher as described in an earlier post. Dockyard also used twenty (or in later versions thirty) substitution tables, but only five of them at any time and they were combined with an interesting fractionation step. Note that fractionation is very out of favor by this point -- apparently the statistical camouflage it offers was finally found to be more illusory than effective once a sufficiently large amount of traffic was generated (though some fractionation is used in the great Soviet spy ciphers).

It might seem that this new cipher would be more like Dockyard than the machines by virtue of its more limited pool of alphabets. This may not be true, however. First off, the 20 alphabets are all in play at any given point, not just five per day. And since the selection of alphabet does vary in a pseudorandom fashion (rather than repeating cyclically through out the message) it will be much more difficult to amass the required traffic in each alphabet that is necessary for a break. Given that a new substitution table is issued monthly, given good precautions the tables may not themselves be broken in time.

The real security in any such cipher, however, depends not on the simple substitution that takes place for each letter, but on the process by which the alphabet varies from letter to letter. And here is where another offsetting advantage might play into the hands of the Reihenschieber. Machine based systems generate both their alphabets and their alphabetic sequences on the fly, in the field, according to a pre-determined algorithm. Even the most secure such systems have historically possessed flaws, unknown or accepted by the designers, that result in patters, repeats, or other notable variations from the truly random.

The American SIGABA was probably the high point of this era, largely because it separated the process of varying the alphabet from the process of creating that alphabet. But I get ahead of myself. Musings on the amazing SIGABA and the equally amazing William Friedman will have to wait for a different day, one probably embodying bourbon and not coffee.

My thought, returning to our cipher-du-jour, is that the alphabets used by the Reihenscieber have the potential to be much more carefully selected and vetted than those created internally by the rotor machines. Similarly, the combinations of numbers on the rods that arrange to select the alphabet tables are selected in an office back home -- and therefore have the potential for considerably more algorithmic complexity and analysis to eliminate weak combinations. Heck, in 1957, they might have even used one of those new computers to do some of the work!

Quality over quantity, in other words.

That said, the Reihenschieber did not have a flawless mechanism for generating the pseudorandom sequence that governed substitution table selection. And now, at last, we must with our imperfect understanding, attempt to actually analyze the device.

As you can see, we have a series of ten imprinted rods (I can't help but picture them as chopsticks!). These rods are arranged according to a procedure (and here we hit the point where my information sources break down) that involves a daily key assigned by HQ (or whomever the responsible cryptographic agency would be) and an area key that is either similarly assigned by HQ or else is selected by the cipher clerk much in the manner of a message indicator. Given the name "area key" I also wonder if it might not be a centrally assigned key, but one that is assigned based on regional sectors, communications nets, or levels of security. In other words the daily key remains constant for the entire Bundeswehr for a given 24 hour period but quartermasters operating near Bonn would have a different area key than artillerymen operating in the Rhineland.

In any case, the daily key consisted of ten letters A-Z that governed the selection of ten sticks out of 26 and the order in which they were placed in the frame (the ten chopsticks were labeled, as you can probably guess, A-Z). The area key, combined with a second numeric portion of the daily key, to specify which of the four sides of each stick was placed to the front as well as the lateral position of each stick relative to its peers.

The exact method remains obscure, but involves the group of lower case letters towards the left side of each stick. They were aligned to a sequence generated, somehow, by a combination of the puzzling area key and the ten digit numeric daily key. This sounds complicated, but I can picture the process taking but a few seconds for an experienced operator. Its the kind of simple operation that can be performed in the field, by flashlight, in the middle of the rain. Notice that this system has no electrical requirements and no "moving parts" in a mechanical sense?

After these alignments, the small grid section would be slid along the large table of numbers that was produced by the arrangement of the sticks. At each stopping place, the digits visible in the windows would be used, in pairs, to select the encipherment table. One digit would be used to select one of the ten columns in a given table, the second digit would select between one of two tables (0-4 = table one, 5-9 = table two). Note that (other than the first and last digit of the sequence) each digit was used twice: once to select a table and then for the next letter to select the table.

Unfortunately, I don't yet have access to the full details of this system that are often as revealing as are the details of the algorithm. How were indicators created and transmitted? How were numbers handled? Were there provisions for using separate codewords for common names (much like RS'44?). I'm particularly interested in the question of message indicators and the actual role of the area key. Since the analysis of this sort of cipher tends to depend on getting a "depth" of multiple messages enciphered with identical alphabets, were there provisions to prevent this from happening? There are a staggering number of ways to arrange the sticks (I haven't done the math on that yet) so there should be an ability to support some sort of message variable key.

In any case, this cipher is an interesting hybrid. It really is a "paper Enigma" -- a non-mechanical attempt to mirror the sort of cipher scheme that was used by rotor machines. I suspect that, despite the vulnerabilities of rotor machines, they were well understood and that the national security agencies of the infant West Germany liked the well understood security that they offered. It is almost a paper-and-pencil cipher, but has the potential to offer much more security than anything else of that era. We shall see.

Werftschlüssel and Rasterschlüssel '44

It 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:

I T W A S
T H E B E
S T O F T
I M E S I
T W A S T
H E W O R
S T O F T
I M E S X

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.

Though 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.

My favorite cipher

There is something gloriously manual about a hand cipher, a cipher using pencil, paper, and possibly a small collection of keytables or such. There is intimate connection with the message, and a comprehensible dynamic that is impossible for the oily "kerchunk" of a rotor machine or the silent algorithmic intensity of yet more modern techniques.

So, in my not-remotely-technical way, I propose a quick review of three interesting wartime hand ciphers. One from the First World War, two from the Second, all three German. I'll take a look at these three from the standpoint of a cipher clerk enciphering a message in the field and then, with a perspective as artistic as it is mathematical, at the inner workings that render reversible incomprehensibility. It'll take time, so bear with me. First one, then the rest later on. If I get into it, there might even be more than these three..

ADFGVX -- and the heroic efforts that lead to its breaking -- is at least conceptually familiar to students of 1918. In the final year of that static conflict, the French cryptographic victory helped the allies withstand the final German push to Paris (it should be noted that there are those who question this widely held view of the history).

The German designers of ADFGVX knew well that a successful cipher needed to be simple to use. This lesson, and the corollary that a complex cipher may, through laziness or simple haste, may prove self-compromising in the field, was one that would be lost between the wars, much to the relief of allied cryptanalysts who knew they could always count on sloppy German practice.

But ADFGVX itself embodied some very interesting ideas. For starters, it enciphered messages into six easily transmitted letters: A, D, F, G, V, and X. In Morse, these letters are simple to send and difficult to confuse on reception. Clear transmission (and therefore minimum repetition) improves security.

Let us suppose you have the message "It was the best of times" to encrypt. The first ingredient is a 6x6 substitution square (note that original versions of this used the letters ADFGX in a 5x5 grid and therefore could not directly encipher numbers). In the field, this would have been provided by headquarters and, probably, changed on a daily basis.

  A D F G V X
A Q 1 W E R 2
D 3 T Y U 4 I
F O P A 5 S 6
G D F 7 G 8 H
V J 9 K 0 L Z
X X C V B N M

(Note that I generated this square by typing on that irritating anachronism, the QWERTY keyboard. I don't pretend to cryptographic validity here.)

We look up each letter in the plain text in the grid and then write down the two ciphertext letters that define its coordinates (row first, column second, so "R" would be represented as AV).

Our message encrypts as:

I T W A S T H E B E S T O F T I M E S
DXDDAFFFFVDDGXAGXGAGFVDDFADDDXXXAGFV

Note that the length is now doubled -- but these are the six easiest letters to transmit (radio was effectively all Morse back then!).

We're not done, because this is just a simple monophonic substitution. That is, every letter in the plaintext corresponds to a single symbol in the ciphertext (even if that symbol consists of two letters). And a monophonic substitution is about as easy to solve as it gets.

Now we write our columns out according to a code word that we have been given. This might also change from day to day, or depending on recipient, in an effort to reduce the amount of traffic a given key setup would produce. Our code word is EDMONDS -- but we omit the second instance of any repeated letter for EDMONS. Write the intermediate encipherment out underneath this word, lining each letter up underneath the ones above it.

EDMONS
DXDDAF
FFFVDD
GXAGXG
AGFVDD
FADDDX
XXAGFV

I got lucky and my message lined up directly underneath the key word, making things look tidy and in fact more cryptographically secure.  The Germans left any blank columns unfilled but, as the tale will show, would have been better off adding random nulls at the end to fill all columns fully and equally.

Now take the letters off vertically by columns, in order of the alphabetical position of the letters in the key word. In this case, take of the D column first, then the E column, the M column, the N, the O, and finally the S. Per traditionally proper technique, we will do so in five letter groups.

XFXGA XDFGA FXDFA FDAAD XDDFD VGVDG FDGDX V

This message would then be transmitted.

Analytically, ADFGVX embodies degrees of both transposition (portions of the message are moved around -- think word scramble) and substitution (think, well, substitution). Interestingly, however, it relies on a third component for its security kicker: fractionation. This results from the step where each plaintext letter's two-part symbol is written down horizontally and then taken off vertically. Each plain text symbol is, therefor, divided (or fractionated) into two parts which are located in different portions of the ciphertext. Modern cryptography places quite a bit of emphasis on this idea -- confusion and diffusion being two sought after goals.

At first blush ADFGVX might seem extremely secure. But the reality is that there are cracks a cryptanalyst can pursue. Realize that after our first step -- the plaintext's initial transformation by substitution into the double-lenth intermediate message of digraphic symbols -- all we had was a simple monophonic substitution. Funny looking, yes, but ultimately almost entirely devoid of security. Given any message with a normal distribution of characters and statistics will quickly yield the digraph pairs that correspond to each plaintext letter. Our sample message is statistically skewed, but AG's representation of E would quickly stand out in any normal frequency count. From there, the rest follows and the message is wide open.

A cagy cryptanalyst can, then try to break back from the fractionation component of the second step. Trialing different lengths and sequences of the columnar transposition guided by the keyword in the cipher's second step is a brute force possibility. This would involve taking an intercepted message "backward" to the intermediate stage by various different keywords, then analyzing the resultant intermediate text for normal statistical distributions of digraph pairs.

Hold on, in case I lost you, think of it this way...and remember that once we reach the intermediate stage of the in-order double-lenght message, the break is effectively trivial.

Our wily cryptanalyst starts by assuming the message's keyword was four letters long. It really doesn't matter what those letters were because a four letter word can only yield 24 possible ways of taking off the columns to produce the final cipher:

1234, 1243, 1324, 1243, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321.

The cryptanalyst now tests the intercept by transcribing the message backwards into each of these columnar orders. This, incidentally is exactly what the friendly cipherclerk on the receiving end would do, but he would know they keyword and therefore the order in which to fill in the received code. Each of these 24 possibilities is then take off (going sideways this time) to produce a candidate intermediate text. Do a statistical count on this intermediate text and see if it looks valid. If close, try to decrypt. If gibberish, try again.

Sounds easy but time consuming -- but when nations are on the line resources are usually available, and nothing so far can't be taught to any moderately apt college student. But now let's say your foe used a five letter keyword for the 2nd step. That would have 120 combinations you' have to examine. Six letters? 720. Eight letters? 5,760. Nine? 51,840. You get the idea, right? And we forgot to account for the paltry six possibilities offered by a three character keyword. The Germans, at least in the first intercepts to be broken, used 20 columns...

In the end, the French depended upon some even more clever analysis. Cryptographic genius George Painvin spent months (and lost 20 pounds) breaking this cipher just ahead of the threat of a German offensive aimed at Paris. He guessed the structure of the cipher and saw that the essential security lay in the columnar transposition. To avoid brute force, he used two messages with the identical beginnings so helpfully common to military communication to determine the number of transposition columns used (20). The identical openings resulted in the first twenty characters of the intercept being identical. After that first column, the diffusion element of the cipher intermingled the traces of the identical openings with the divergent bodies.

Knowing that there were 20 columns, he could reconstruct them. Some were longer and some shorter by one letter. Logically, the longer columns would be to the left because of the order in which they were filled in. This sorted the columns into two groups -- the long left and the short right, thinning the field a little but still leaving far too many options to try. Assuming that messages with identical beginnings might have identical endings, Painvin was able to apply his opening logic in reverse and create a few groups of pairs that he knew must be next to each other, but not which was to the left and which was to the right. But with two columns, he could afford to roll the dice and try to find statistical distributions that matched written German.

That worked, and allowed him to find the digraph pairs for a few common letters. Using this break, the rest of the columnar arrangement and the substitution square filled themselves in by turns. Statistical guesses at the substitution arrangement could guide the arrangement of the columns (arrangements that produced greater frequencies of digraphs corresponding to common letters were more likely to be correct). As more columns were arranged, more digraphs emerged, and so on, until the columnar arrangement and the substitution table were both fully filled out and all that day's traffic could be read.

It was laborious and depended on a sufficient volume of traffic. The French never read ADVGVX reliably -- only on days with sufficient traffic to generate the sort of kick start needed. The initial breaks took weeks to analyze -- rendering the effort useless from a tactical standpoint. But as experience (and traffic and poor communications practice) grew, solutions were achieved sometimes the same day the messages were sent.

All this said, I like the beauty of this cipher. It embodies both substitution and transposition, and yet is relatively wieldy. If you thought that trial example was tough, just wait until parts two and three...

There are also a few steps that could be taken to improve security. A classic step is to substitute codewords for frequently named people and places. Certain suspected patterns can help speed up the breaking of the final stage, and if an army is fighting in Verdun, for example, a cryptanalyst looking at a signal to or from that army might look for that word. Substitute FIBLA for that word (and then encrypt it) and you have an improvement. Even better, have FIBLA, GIZWA, NILMO, and QAGTL all as options for the cipher clerk to pick at random.

The second stage keyword should be long, to maximize the number of choices facing the cryptanalyst. Chose a phrase like "YOURE MY WONDER WALL" (I've had that song stuck in my head today) instead of just a few words. Take columns headed by duplicate letters off in order instead of ignoring repeats and you have a 17 letter keyword: 355,687,428,096,000 possible combinations, more than enough to prevent trial-and-error cryptanalysis as I suggested. Better yet, don't use a keyword at all (and I believe this might be how the Germans actually implemented the cipher) but a numeric sequence (11 4 7 8 3 8 6 10 1 5 2 9 12) that couldn't correspond to some word or phrase a codebreaker might recognize.

An implementation that somehow changed a portion of the key (say the keyphrase) at every message would increase security. A little recognized fact is that message length can have a lot to do with the ability of a foe to compromise a cipher system. ADFGVX is vulnerable, but only with a sufficient amount of identically keyed traffic. So embedding an encrypted version of an ever changing key phrase or selecting one from a daily sequence rather than using the same one all day long would help. One could easily see a book that contained the substitution square on the left side and a table of 50 different transposition keys on the right, each identified by an in indicator to be sent along with the message or else some sort of scheme for sequencing to govern their selection. This was a common feature of some of the better ciphers of the 2nd world war and shortly thereafter -- the amazing American SIGABA machine for one, the postwar Swiss NEMA for another -- an indicator group that specified an easily changed portion of the machine's settings was transmitted (enciphered in some manner) as part of the message header and footer. The great Soviet spy ciphers (Vic and its kin) used similarly variable portions for every message.

I think that the idea of saying "I transmit part of my cipher key IN my message?" is shocking to most. Understandably! But the countermeasure is that done properly, the indicator group is not easy to read, and the effect of reducing message traffic for any given setup more than outweighs the risks.

Naturally, all the standard weaknesses of classical error cryptography (and their potential countermeasures) are present as well. Sloppy work resulting in identical messages being sent with different keys. Sending the same message on a secure and a non-secure channel resulting in the compromise of all the message on the secure channel for that keying period. Stereotyped beginnings or entire messages -- this was the bane of actual German cryptography, with a national penchant for patriotic phrasing or "nothing to report" reports...

Interestingly, while it would considerably weaken the security of the thing, it is possible to do a ADFGVX variation with no prepared materials, using a keyphrase of sufficient length to form up the initial substitution table. Take the letters of "The sky above the port was the color of television, tuned to a dead channel" and use them to form the initial grid, alphabetically filling in the rest of the spaces.

  A D F G V X
A T H E S K Y
D A B O V P R
F W C L F I N
G D B G J M Q
V X Z 0 1 2 3
X 4 5 6 7 8 9

Of course, we'd need to come up with some scheme for the numbers -- or else use the 5x5 version. Its weaker, since an analyst could guess the arrangement once they started to get a break. But for a spy or someone forced to work with no materials and sending a very small amount of traffic, it has possibilities.

I find this cipher charming for some reason. Its balance of complexity and comprehensibility works for me. It has its vulnerabilities, but then again so does anything of this period or level of sophistication.

The accessibility of it means I can play with it in my mind, try to understand it the way I picture George Painvin did.