Thursday, April 16, 2009

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.

Picture 1.jpgThe 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?

No comments: