Project: Clojure Solitaire

For as long as I’ve been playing with computers I’ve had a mild interest in cryptography. Unfortunately that interest was so mild that I never got off my butt to actually learn anything about it. But that changed recently when I was introduced to the Solitaire encryption algorithm by Bruce Schneier.  It is an algorithm to generate a key stream using a deck of cards. This key stream is then used to encrypt a message. Only those who know the starting order of the deck (and the algorithm) can decipher the encrypted message.

If you scroll to the bottom of Schneier’s Solitaire page, you’ll see a list of programming languages that have been used to implement Solitaire. When I first visited that page there was not a version in Clojure, so I decided to write one. I had emailed Mr. Schneier about my Clojure version and he was kind enough to include a link to the code on the Solitaire page. This blog entry will describe the most important bits of that code.

The Algorithm

The result of performing an iteration of the Solitaire encryption algorithm is one key of a key stream. In this case that key stream consists of a stream of the integers from 0 to 25, inclusive. This is achieved by starting with a deck (which contains the two jokers) in an order that must be known to both the sender and receiver of the encrypted message and then performing the following operations on it:

1. Move Joker A down one spot
2. Move Joker B down two spots
3. Perform a triple cut
4. Perform a count cut

These steps will be described below. The two Jokers in a normal deck of cards are typically distinguishable. For the purposes of this description one of the Jokers will be called “A” and the other “B”; it doesn’t matter which you call “A” and which you call “B” as long as you are consistent.

Representing the Deck

The Solitaire Encryption algorithm uses a normal deck of cards, including the two Joker cards, therefore, a deck is composed of 54 cards. But, what is a card? There are many ways that one could encode a card but I decided to go with the simplest way that I could think of: encode a card as an integer – 1 through 54. The following function ensures that a given card is valid:

Note the use of the “range-checking” feature of the < function. This is nicer than the alternative:

Now that we’ve defined what a valid card is, a valid deck can be defined like so:

This function simply checks that the deck contains 54 items and that those items are all valid cards. These functions are used in the precondition check in all the other functions that take a deck and/or a card as parameters.

I also wrote a bit of helper code to give me a shuffled deck:

Moving a Card Down in the Deck

The first part of the Solitaire algorithm involves moving the two Jokers down one or two spaces in the deck, depending on the Joker. That seemed like a good place to start. I wanted to create a general function that took a deck of cards as input and returned a new deck with a given card moved down in the deck a given number of spaces.

The above is a multi-arity function. As the doc string states, if it is called with two arguments, the given card is moved down one space in the deck (it moves to below the top card if it is the bottom card) and if it is called with three arguments, the given card is moved down the given number of spaces. The three-arg version (beginning on line 12) calls the two-arg version to move card down the deck one space at a time. It does this recursively decrementing spaces each time until spaces reaches zero.

The real work is done by the two-arg version (beginning on line 6). The body of the two-arg version is a let expression with a single binding but this binding uses nested destructuring that does a lot of the hard work for us. The result of the split-with call is a two-element vector whose first element is destructured and bound to top. top will be bound to the portion of the deck that is above card and therefore does not include card. The second element of the two-element result will contain the rest of the deck and so card will be the first element of that sequence. This bottom part of the deck is further destructured into three parts. The first element is discarded by binding it to _. This is just card and we already have that so there’s no need to bind another name to it. The second element is bound to next-card; we’ll need that in a moment. The rest of the deck is bound to bottom.

The conditional on line 9 checks the value of (not next-card). If this evaluates to true, it means that card was at the bottom of the deck. Moving the bottom card down one spot in the deck is equivalent to placing it after the top card. This is achieved on line 10 by making a list of the top card, followed by card and then followed by all but the top card.

The alternative part of the conditional (line 11) is the more likely case when card is not the bottom card. In this case we concatenate the top of the deck with next-card followed by card, then the rest of the deck which is bound to bottom.

Triple Cut

After the Jokers have been moved down in the deck, a triple cut is performed. A triple cut swaps the cards above the first Joker with the cards below the second Joker; the cards in the middle – including the Jokers – don’t move. The following code defines the triple-cut function:

About half of the work needed for a triple cut is performed by the split-at-jokers function:

The result of calling split-at-jokers is almost, but not quite, what we need for a triple cut. The difference is that, after splitting, the top card of the bottom of the deck is the second Joker rather than that Joker being the last card of the middle section. For example, the result of calling split-at-jokers on the following (very small) deck:

would be:

We need to do a bit of additional manipulation inside of triple-cut to get to the point where we can simple swap the top and bottom of the deck. I opted for this pattern because I thought it was more general and consistent with they way other split functions work.

Count Cut

The count cut uses the value of the bottom card to determine where in the deck to cut. Schneier’s Solitaire algorithm describes how to assign values to the cards using the Bridge order of suits: clubs, diamonds, hearts, spades. But since this code just uses integers 1 through 52 to encode cards, there is no need for such a ranking. Note that both jokers are given the value 53 for this purpose.

Once the value of the bottom card has been determined, the deck is cut to one card past that card. But instead of a normal cut where the top and bottom are simply swapped, in this case the bottom card is left in place. Suppose we have to following (very small) deck:

a count cut would result in the following deck:

The claim is that the last card is left in place to make this step reversible, but to be honest it’s not obvious to me how that makes it reversible and I haven’t given it much thought. This page talks about how the Solitaire algorithm is not actually reversible as is claimed. Interestingly, that page also discusses how the algorithm is also biased. It goes to show that you should not roll your own security; even security professionals get it wrong!

The following is the code for count-cut:

But as before, most of the work is done by another function, cut-preserve-bottom:

Putting Them Together

The previous three sections describe the functions that are used to implement one iteration of the Solitaire algorithm which was described near the beginning of this post. I’ll repeat those steps here:

1. Move Joker A down one spot
2. Move Joker B down two spots
3. Perform a triple cut
4. Perform a count cut

And the function representing these steps is the following:

jokerA and jokerB were previously defined as:

I think you’ll agree that using Clojure’s threading macro allows this function to be a direct translation of the previously outlined algorithm.

Generating the Keystream

It was mentioned earlier that the result of performing an iteration of the Solitaire encryption algorithm is one key of a key stream. So how do we generate the key? Here’s how: after performing the previously described solitaire algorithm, look at the top card. Then, convert that card to a number. Since we’re representing cards as numbers, this step is already done with one exception: if the top card is a joker, it’s given a value of 53. This is despite the fact that this implementation gives values of 53 and 54 to the two jokers. Next, count down that many cards from the top of the deck. The card after this number is the key. The only caveat to this procedure is if the key happens to be one of the jokers. In that case you must start over by performing another iteration of the solitaire algorithm and do this as many times as required so that the next key is not a joker.

The following function is an implementation of this algorithm:

On line 7 we look at the top card. On line 8 we do the check for a joker and give it the value 53 if it is. On line 9 we split the deck at that point and destructure it only binding to the bottom portion of the deck. Then, key is given the value of the top card of the bottom portion. Line 11 does the check for the key being a joker. If it is, we recursively call generate-key passing it a new deck that has had the solitaire algorithm performed on it. Otherwise, we return a two-element vector that contains the key and the deck. Returning the deck is necessary in the case where we must call generate-key recursively in which case the deck that was used to call generate-key initially has been changed.

Now we’re ready to generate the key stream by simply wrapping a recursive call to generate-key with a call to lazy-seq as follows:

Note that this actually produces an infinite key stream!

Keying the Deck

At the beginning of this post I had mentioned that you must start with a deck “in an order that must be known to both the sender and receiver of the encrypted message”, but I did not say how that order could be arrived at. The process of putting the deck in some agreed-upon order is called “keying the deck”. In his article Mr. Schneier talks about several ways that a deck can be keyed:

1. Use identically shuffled decks.
2. Use a bridge ordering. This is a method that uses a bridge hand found in, say, a newspaper and converting that into a deck ordering.
3. Use a passphrase.

The first two methods can be done straightforwardly, but using a passphrase will require an algorithm. Mr. Schneier talks about a method that uses the solitaire algorithm itself to do this. First, start with an ordered deck: lowest card to highest card, in bridge suits (clubs, diamonds, hearts, and spades). Then, perform the solitaire algorithm on it but, instead of finding an output card, perform another count cut using the first letter (converted to a number) of the passphrase to determine where to cut. This process is repeated for each character of the passphrase. The following function takes a deck and a passphrase and returns the keyed deck:

I always love an opportunity to use a fold or reduce and the key-deck function was one of those opportunities. Of course, the important part is the function you pass to reduce which I define in the let block as key-deck-with-char on line 6. It takes a deck and a single character from the passphrase. It first converts the character to an integer on line 7 and then uses the -> macro on line 8 to thread the deck first through the solitaire function and then through cut-preserve-bottom which uses the previously defined pass-char-val as the place to cut to in the deck. The value of that operation is the new deck which is also the value returned by the function itself. We call reduce with the passed-in deck. reduce calls key-deck-with-char with the deck and the first character of the passphrase. The resulting deck is then passed to key-deck-with-char along with the second character of the passphrase. This process continues until all the characters of the passphrase have been used. The deck that results from reduce is the keyed deck.

Now, the Fun Part: Encrypting and Decrypting!

Encrypting a message with Solitaire works as follows:

1. Generate a key stream whose length is equal to the number of letters in the message to be encrypted.
2. Convert each card to a number.
3. Convert each letter in the message to a number from 1 to 26.
4. Pairwise add a number from the key stream to the corresponding number in the message, modulo 26.
5. Convert each number back to a letter.

As before we don’t need to do step 2 since we’re already representing the cards as integers. But, we do need to convert letters to numbers (step 3) and numbers back to letters (step 5). The following two functions do this for us:

I should also mention the function pad-to-mod-5-with-x. As Bruce mentions in his Solitaire page it’s tradition to break the message to be encrypted into groups of five and to use “X”‘s to pad the end of the message, if necessary. This step isn’t strictly necessary but I’ve implemented it in the code anyway. Here it is:

With those helper functions out of the way I now present the encrypt function:

This function takes the plain-text message to be encrypted and the deck to be used for the encryption. On line 7 we use the deck to create the key stream. Line 8 does any necessary padding of the message and line 9 converts the message to a sequence of integers. Line 10 creates an encoding function using a helper function which I’ll go over in a moment. The last line of the let block produces the encoded values: a sequence of integers which represent the cypher text. Finally, the body of the let produces the actual cypher text by mapping the encoded values to letters and creating a string out of them.

Now, what I call the combining function, encode-key-and-letter, is created using a helper function, create-combining-fn, which I use to remove some duplication between the encrypt and decrypt functions.

Speaking of the decrypt function:

decrypt is very similar to encrypt with a few notable differences. First, decrypt does not modify the input cipher text by calling pad-to-mod-5-with-x; it is assumed the the cipher has been encrypted using the encrypt function so the cipher text will already have a mod-5 length. Besides, it would be inappropriate to make such a modification of the cipher text in any case. Also, the creation of the combining function uses - instead of +. Finally, the message-vals and key-stream arguments to the map call on line 10 are reversed.

Removing Duplication

I just mentioned that encrypt was very similar to decrypt; in fact, it’s embarrassingly similar! If you’ve looked at the code repo, you’ll have seen that these two functions are not actually coded this way because I’ve already removed the duplication. The first thing I did was to remove the padding of the message text in encrypt. As mentioned previously it’s only for reasons of tradition that this is done and it’s not strictly necessary. After that, the only real difference between the functions is the combining function and the order of message-vals and key-stream. This is easily dealt with. I abstracted the duplication of the two functions with the following function:

This is a higher order function that both takes a function as input (combining-fn) and returns a function as output. So we’re now passing in the combining function but what about the order of message-vals and key-stream? The only reason that decrypt needed to reverse these two values was the simplicity of the combining function but this is easily remedied. With the above function we can now define encrypt and decrypt like so:

Notice how the function argument to create-combining-fn in the definition of decrypt is now #(- %2 %1) instead of simply -. This is how we remove the need to swap the values message-vals and key-stream. It’s not as elegant as simply using - but what can you do?

Let’s See It In Action

Let’s start up a repl and walk through encrypting and decrypting a message.

After loading up the solitaire code I def a var keyed-deck using the key-deck function with a password on line 4. Next, I encrypt a message using that deck on line 5 and on line 6 I display that encrypted message. Finally, I decrypt the message on line 8 and you can see that we get the original message back again. That’s it. Pretty cool, huh?