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?

The Playing Card Cipher

UPDATE: I have added an expanded discussion of the thought process behind this cipher and some of the underlying technologies: Linear Feedback Shift Registers and the Playing Card Cipher. Happy reading!

The following post describes a cipher, one with a few unusual properties. First off, it is not intended to be implemented with any of the usual technologies of computers, custom integrated circuits, or even electro-mechanical rotors.

It is intended to be implemented with playing cards.

It was born during an epic conference call (the total call ran to 14 hours, though my role it it lasted just around 12) when I occasionally found myself with little to do but listen and wait for an opportunity to contribute. It proceeded to evolve over several days of tweaking and (I hope) improvement until finally reaching the form I outline below.

In addition to the unusual form of implementation, this cipher was constrained by some equally unique requirements:

1) It should be possible to implement it using the technology of the 17th century.

2) It should require no tools or objects that could arouse suspicion.

3) Ideally, it should be easy to "hide" efforts at using the cipher if discovered

4) It should be possible for a person of slightly above average intelligence, if taught and given opportunity to practice, to implement the cipher from memory.

5) It should possess sufficient security for the times.

The inspiration was the cryptographic subplots of Neal Stephenson's Baroque Cycle and, in particular, the exploits of spy/courtesan Eliza. I'd also recently discovered Sony's very elegant Clefia cipher and found myself in a crypto-mood.

Not being a cryptographer, but rather a fan of cryptography, I chose to base this cipher on a fairly well know and reasonably simple href="http://en.wikipedia.org/wiki/Stream_cipher">stream cipher. For various technical reasons related to complexity of implementation, I chose a stream cipher rather than the more complex (but potentially more secure) block cipher approach.

My basis was A5/1, the cipher used to encrypt voice channels in GSM telephones. A5/1 is pretty broadly regarded as completely broken, but is well described and gloriously simple. I simplified it more. And, I'd like to mention, broken has very different meanings in 2009 and 1779. Rather than getting into a lot of design theory and the evolution (which I think is rather interesting...) let's dive in to the beast itself.

I will assume that before producing the cipher that the message to be enciphered has been translated into some sort of binary notation. There is some discussion of this later, but it could be as simple as saying that the pattern 00001 = A, 00010 = B, 00011 = C, 00100 = D, etc. at five bits per character.

But now here is now the cipher works...

Throughout the following, I use the notation that face up cards have the binary value of 1 and face down cards the binary value of 0. The entire cipher is, then, implemented using playing cards in place of binary registers.

Lay out three rows of cards.

The uppermost has (in this version of the cipher) six cards, the next seven cards, and the bottom row eleven cards. I find it easy to "right justify" these rows so that the rightmost cards are all aligned vertically. These three rows constitute the shift registers of the cipher. The leftmost card in each row constitutes the "first" position in that shift register and the rightmost the "last." Binary values will migrate from left to right across each shift register. Face up cards represent binary "1" values and face down cards represent binary "2" values. The arrangement of up and down cards constitutes the initial key of the cipher.

With this arrangement, there are 24 cards, equivalent to a keyspace of 24 bits. Paltry by modern security standards, but remember that we are doing this with playing cards! The intent here is to produce a cipher using modern design concepts but that an 18th century spy could have implemented. Note that I do not specify the method of "keying" the cipher. I have some speculations on that later, but suffice it to say that some scheme for inputting the initial pattern of cards is essential -- and that the decoder be able to produce the same initial state.

To the left of each row of cards, place a single card. This card is not actually part of the keyspace, but is used as a mnemonic to store the new first value before it is fed into the register.

It may also be helpful to place a few markers on the layout to facilitate the stepping of the cipher. The actual marker is up to the individual depending on circumstances of availability, epoch, cover story, personal preference, etc. Think poker chip, other card, pretzel, pen, Post-It note, etc (I used matches because they were handy). Each marker should be set above or below the designated card so that it does not interfere with the manipulation of the card. It will also help to have two different types of markers. Use the first kind, which we will call red, to mark the last (right-most) two cards of the upper two rows (cards 5 and 6 of the upper and cards 6 and 7 of the lower) as well as the last and next-to-las (cards 9 and 11) of the last row. Note that in the illustrations I used matches placed below the indicated cards. Then use the second kind of mark, which we will call black, to mark the 3rd, 4th, and 8th cards in the top, middle, and bottom rows respectively. Note that these cards should all lie in a vertical column if the layout was set up as I suggest. Here I simply placed a pair of matches at the top and bottom of this column.

Now begins the process of "stepping" the cipher and generating the output.

The cipher executes through a series of "rounds," each of which produces one bit of output. Each row consists of three phases (this is starting to sound like some German style board game, isn't it?).

Phase One

During the first phase we produce one bit (one binary value) of cipher output.

Look at the last (rightmost) cards. If there is an even number of 1 (face up) cards then the cipher outputs a 0. If there is an odd number of 1 cards, then the cipher outputs a 1. Note that zero is an even number. Technically this mathematical function is called an XOR and is a very big deal in modern cipher design.

This output (called the keystream) will be combined with the plaintext message bit-by-bit using the same function. If the plaintext and the keystream are both 1's or both 0's, then the ciphertext is a 0. If either the plaintext or the keystream is a 1, then the ciphertext is a 1.

Phase Two

Now we need to step the cipher forward to prepare for the next round. Look at each row's red highlighted spaces (5th and 6th, 6th and 7th, or 9th and 11th). Based on the values in these spots, we will select the new first value of that row. The extra cards laid to the left of the cipher spaces will serve as memory aids in this process.

Again, use an XOR. If the two highlighted spaces are both 1 or both 0, the extra card sets to 0. If exactly one of the highlighted spaces is 1, then the extra card sets to 1.

Phase Three

Finally we will actually step the cipher forward. This is the most time-consuming step in the process and actually involves two sub-phases.

In the first sub-phase we decide which rows will step. The result will either be two or three. Look at the black highlighted column. Based on the three cards in this column, either 1's or 0's will have a majority. If 1's have the majority, step whichever rows have 1's in this column. If 0's have the majority, step whichever rows have 0's in this column.

For example, if the top most row has a 0 in the black highlighted column, the middle row has a 1, and the bottom row has a 1, then the bottom two rows would step and the upper row would remain unchanged for this round.

Note that if all three cards are the same then all three rows step.

To actually step each row, simply start with the right most card and set it to the value of the card immediately to its left. This means that the rightmost value is lost and the "new" value is fed in from the extra cards that we set up in step two.

That's it.

That whole process produces one bit of output. It takes (about) five of those to encipher one letter.

Back then, people had a lot more time.

A few notes:

To decipher, simply start with the same initial setup and repeat this process. The beauty of the XOR is that it is self-reversing. XOR plaintext and keystream together to produce cipher text. XOR cipher text with keystream and the plain text magically reappears.

The use of the cards to represent bits by face up/down state removes any dependancy on the particular variety of card deck in use (such things have not always been as standardized as they are today). One could use Tarot cards, for example.

It may be helpful to run the cipher for some time while noting down the output on a piece of paper and then doing the xor to transform the plaintext into the cipher text. I use the extra cards of the deck to store a batch of output, stacking them face up or face down depending on each step's output.

I make no effort to define the method of key setup. Any of several strings of numbers could be used, sourced in any of several ways. Information from a newspaper, translated into binary could be used. It would, in any case, be very advisable to run the cipher a cycle or two to mix in the new key before starting to actually use the output.

I also make no guarantees of security. Let's face it, this was developed based on a flawed and broken cipher with modifications performed by a guy with little mathematical understanding of cryptology beyond the most shallow and conceptual level (that's me). The value here is purely as an exercise, a game, and a period piece.

One of the obvioius sources of tedium in this cipher is the inefficiency of binary for sending information. Versatile, yes, but it takes more than five symbols to represent the same amount of information contained in one english letter. A carefully chosen scheme for representing the text (assuming the message is in text) in binary is therefore important. Obviously ASCII with its irritatingly liesurely 8-bits per character pace is out, since there is no need to represent upper, lower, and a whole host of wacky special symbols.

Instead, since this is for secret communication, pare down to the minimums.

For starters, I suggest a five-bit code that would allow for the sending of 32 characters. Beyond the basic 26, the extras could represent common words or phrases, punctuation, or a shift character to swap to a different binary alphabet for numbers.

Six-bit characters would allow for the representation of all the numbers even more cleanly and then some (probably a short hand for common words and phrases) since it would allow for 64 possible values. Keep in mind that this binary alphabet must be memorizable.

This is a whole separate discussion, but there are countless options for optimizing the encoding process. A Huffman code is another option, of course, but I have not had the opportunity to see how effective of a Huffman code I can build and if it ends up as more effective than the shorthand I propose above.

To conclude, here is a basic example:

I wish to encode the message "GOOD NIGHT."

I encode this message using this simple binary code:

A: 00001
B: 00010
C: 00011
D: 00100
E: 00101
F: 00110
G: 00111
H: 01000
I: 01001
J: 01010
K: 01011
L: 01100
M: 01101
N: 01110
O: 01111
P: 10000
Q: 10001
R: 10010
S: 10011
T: 10100
U: 10101
V: 10110
W: 10111
X: 11000
Y: 11001
Z: 11010
Space: 11011
Period: 11100

I get:

00111 01111 01111 00100 11011 01110 01001 00111 01000 10100

I will key my cipher with the day's close of the Jow Jones Industrials which happened to be 8125.43 today (not bad, by today's standards!). Since that won't give me quite enough digits, I will concatenate it with the absolute value of the day's change, 95.81. I will ignore any 0's or 9's that come up and encode these digits in a simple three-bit binary where:

1: 000
2: 001
3: 010
4: 011
5: 100
6: 101
7: 110
8: 111

This set of digits 8125439581 sets my key as:

111 000 001 100 011 010 100 111 000

I actually have extra, so I won't end up using the last three bits. The rest I put into the cipher, starting at the upper left and loading the three rows from left to right, top to bottom. The starting position is, then:

X 111000
B RR
X 0011000
B RR
X 11010100111
BR R

Note the highlighted spots in the rows.

The first step of the cipher produces a "1" as output since the rightmost spots have two 0's and a 1.

The intermediate phase of this step sets the extra cards (initially shown as X's) to 0, 0, 0.

O 111000
B RR
O 0011000
B RR
O 11010100111
BR R

Since the upper and middle rows both have 1's in the black highlighted space, they step forward, producing this:

0 011100
B RR
0 0001100
B RR
0 11010100111
BR R

The next step produces another 1 for output (which will, either now or later, be XOR'd with the 2nd bit of the plaintext just as the first output was with the 1st bit of the plaintext).

The cipher then advances:

0 001110
B RR
0 0000110
B RR
0 11010100111
BR R

The third step produces another 1 and the cipher advances:

1 001110
B RR
1 1000011
B RR
0 01101010011
BR R

It produces a 0 and advances...

And so on and so on.

Enjoy. Use it -- with due warnings of security. If you are a 17th century secret agent, please let me know. If you find this interesting, please do so as well. I have done much thinking on this topic and hope to do more.

Oh yes, and it needs a name...I'm working on that. Perhaps at the next conference call?