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?