Cryptonomicon (129 page)

This is the heart of Solitaire. The above descriptions of encryption and decryption work for any output-feedback mode stream cipher. This section explains how Solitaire works.

Solitaire generates a keystream using a deck of cards. You
can think of a 54-card deck (remember the jokers) as a 54-element permutation. There are 54!, or about 2.31 3 10
⁷¹
, possible different orderings of a deck. Even better, there are 52 cards in a deck (without the jokers), and 26 letters in the alphabet. That kind of coincidence is just too good to pass up.

To be used for Solitaire, a deck needs a full set of 52 cards and two jokers. The jokers must be different in some way. (This is common. The deck I’m looking at as I write this has stars on its jokers: one has a little star and the other has a big star.) Call one joker A and the other B. Generally, there is a graphical element on the jokers that is the same, but different size. Make the “B” joker the one that is “bigger.” If it’s easier, you can write a big “A” and “B” on the two jokers, but remember that you will have to explain that to the secret police if you ever get caught.

To initialize the deck, take the deck in your hand, face up. Then arrange the cards in the initial configuration that is the key. (I’ll talk about the key later, but it’s different than the keystream.) Now you’re ready to produce a string of keystream letters.

This is Solitaire:

1. Find the A joker. Move it one card down. (That is, swap it with the card beneath it.) If the joker is the bottom card of the deck, move it just below the top card.

2. Find the B joker. Move it two cards down. If the joker is the bottom card of the deck, move it just below the second card. If the joker is one up from the bottom card, move it just below the top card. (Basically, assume the deck is a loop… you get the idea.)

It’s important to do these two steps in order. It’s tempting to get lazy and just move the jokers as you find them. This is okay, unless they are very close to each other.

So if the deck looks like this before step 1:

3 A B 8 9

at the end of step 2 it should look like:

3 A 8 B 9

If you have any doubt, remember to move the A joker before the B joker. And be careful when the jokers are at the bottom of the deck.

3. Perform a triple cut. That is, swap the cards above the first joker with the cards below the second joker. If the deck used to look like:

2 4 6 B 4 8 7 1 A 3 9

then after the triple cut operation it will look like:

3 9 B 4 8 7 1 A 2 4 6

“First” and “second” jokers refer to whatever joker is nearest to, and furthest from, the top of the deck. Ignore the “A” and “B” designations for this step.

Remember that the jokers and the cards between them don’t move; the other cards move around them. This is easy to do in your hands. If there are no cards in one of the three sections (either the jokers are adjacent, or one is on top or the bottom), just treat that section as empty and move it anyway.

4. Perform a count cut. Look at the bottom card. Convert it into a number from 1 through 53. (Use the bridge order of suits: clubs, diamonds, hearts, and spades. If the card is a ♣, it is the value shown. If the card is a ♦, it is the value plus 13. If it is a ♥, it is the value plus 26. If it is a ♠, it is the value plus 39. Either joker is a 53.) Count down from the top card that number. (I generally count 1 through 13 again and again if I have to; it’s easier than counting to high numbers sequentially.) Cut after the card that you counted down to, leaving the bottom card on the bottom. If the deck used to look like:

7…
cards
. . . 4 5…
cards
. . . 8 9

and the ninth card was the 4, the cut would result in:

5…
cards
.  . . 8 7…
cards
. . . 4 9

The reason the last card is left in place is to make the step reversible. This is important for mathematical analysis of its security.

5. Find the output card. Look at the top card. Convert it into a number from 1 through 53, in the same manner as above. Count down that many cards. (Count the top card as number one.) Write the card after the one you counted to on a piece of paper. (If you hit a joker, don’t write anything down and start over again with step 1.) This is the first
output card. Note that this step does not modify the state of the deck.

6. Convert the card to a number. As before, use the bridge suits to order them. From lowest to highest, we have clubs, diamonds, hearts, and spades. Hence,
A
♣ through
K
♣ is 1 through 13,
A
♦ through
K
♦ is 14 through 26,
A
♥ through
K
♥ is 1 through 13, and
A
♠ through
K
♠ is 14 through 26.

That’s Solitaire. You can use it create as many keystream numbers as you need.

I know that there are regional differences in decks of cards, depending on the country. In general, it does not matter what suit ordering you use, or how you convert cards to numbers. What matters is that the sender and the receiver agree on the rules. If you’re not consistent you won’t be able to communicate.

Solitaire is only as secure as the key. That is, the easiest way to break Solitaire is to figure out what key the communicants are using. If you don’t have a good key, none of the rest matters. Here are some suggestions for exchanging a key.

1. Shuffle the deck. A random key is the best. One of the communicants can shuffle up a random deck and then create another, identical deck. One goes to the sender and the other to the receiver. Most people are not good shufflers, so shuffle the deck at least ten times, and try to use a deck that has been played with instead of a fresh deck out of the box. Remember to keep a spare deck in the keyed order, otherwise if you make a mistake you’ll never be able to decrypt the message. Also remember that the key is at risk as long as it exists; the secret police could find the deck and copy down its order.

2. Use a bridge ordering. A description of a set of bridge hands that you might see in a newspaper or a bridge book is about a 95-bit key. If the communicants can agree on a way to convert that to a deck ordering and a way to set the jokers (perhaps after the first two cards that are mentioned in the discussion of the game), this can work. Be warned:
the secret police can find your bridge column and copy down the order. You can try setting up some repeatable convention for which bridge column to use; for example, “use the bridge column in your hometown newspaper for the day on which you encrypt the message,” or something like that. Or use a list of keywords to search the
New York Times
website, and use the bridge column for the day of the article that comes up when you search on those words. If the keywords are found or intercepted, they look like a passphrase. And pick your own convention; remember that the secret police read Neal Stephenson’s books, too.

3. Use a passphrase to order the deck. This method uses the Solitaire algorithm to create an initial deck ordering. Both the sender and receiver share a passphrase. (For example, “SECRET KEY.”) Start with the deck in a fixed order; lowest card to highest card, in bridge suits. Perform the Solitaire operation, but instead of Step 5, do another count cut based on the first character of the passphrase (19, in this example). (Remember to put the top cards just above the bottom card in the deck, as before.) Do this once for each character. Use another two characters to set the positions of the jokers. Remember, though, that there are only about 1.4 bits of randomness per character in standard English. You’re going to want at least an 80-character passphrase to make this secure; I recommend at least 120 characters. (Sorry, but you just can’t get good security with a shorter key.)

Here’s some sample data to practice your Solitaire skills with:

Sample 1: Start with an unkeyed deck:
A
♣ through
K
♣,
A
♥ through
K
♥,
A
♦ through
K
♦,
A
♠ through
K
♠,
A
joker,
B
joker (you can think of this as 1-52,
A
,
B
). The first ten outputs are:

4 49 10 (53) 24 8 51 44 6 33

The 53 is skipped, of course. I just put it there for demonstration. If the plain text is:

A A A A A
A A A A A

then the cipher text is:

E X K Y I
Z S G E H

Sample 2: Using keying method 3 and the key “FOO,” the first fifteen outputs are:

8 19 7 25 20 (53) 9 8 22 32 43 5 26 17 (53) 38 48

If the plain text is all As, the cipher text is:

I T H Z U
J I W G R
F A R M W

Sample 3: Using keying method 3 and the key “CRYPTONOMICON,” the message “SOLITAIRE” encrypts to:

K I R A K
S F J A N

Of course, you should use a longer key. These samples are for test purposes only. There are more samples on the website, and you can use the book’s PERL script to create your own.

Solitaire is designed to be secure even if the enemy knows how the algorithm works. I have assumed that
Cryptonomicon
will be a best seller, and that copies will be available everywhere. I assume that the NSA and everyone else will study the algorithm and will watch for it. I assume that the only secret is the key.

That’s why keeping the key secret is so important. If you have a deck of cards in a safe place, you should assume the enemy will at least entertain the thought that you are using Solitaire. If you have a bridge column in your safe deposit box, you should expect to raise a few eyebrows. If any group is known to be using the algorithm, expect the secret police to maintain a database of bridge columns to use in cracking attempts. Solitaire is strong even if the enemy knows you are using it, and a simple deck of playing cards is still much less incriminating than a software encryption program running on your laptop, but the algorithm is no substitute for street smarts.

The first rule of an output-feedback mode stream cipher, any of them, is that you should never use the same key to
encrypt two different messages. Repeat after me: NEVER USE THE SAME KEY TO ENCRYPT TWO DIFFERENT MESSAGES. If you do, you completely break the security of the system. Here’s why: if you have two ciphertext streams,
A
+
K
and
B
+
K,
and you subtract one from the other, you get (
A
+
K
) – (
B
+
K
) =
A
+
K
–
B
–
K
=
A
–
B.
That’s two plaintext streams combined with each other, and is very easy to break. Trust me on this one: you might not be able to recover
A
and
B
from
A
–
B,
but a professional cryptanalyst can. This is vitally important: never use the same key to encrypt two different messages.

Keep your messages short. This algorithm is designed to be used with small messages: a couple of thousand characters. If you have to encrypt a 100,000-word novel, use a computer algorithm. Use shorthand, abbreviations, and slang in your messages. Don’t be chatty.

For maximum security, try to do everything in your head. If the secret police starts breaking down your door, just calmly shuffle the deck. (Don’t throw it up in the air; you’d be surprised how much of the deck ordering is maintained during the game of 52-Pickup.) Remember to shuffle the backup deck, if you have one.

There’s quite a lot of it, but it’s far too complicated to reproduce here. See http://www.counterpane.com, or write to Counterpane Systems, 1711 North Ave #16, Oak Park, IL 60302.

I recommend my own book,
Applied Cryptography
(John Wiley & Sons, 1996), as a good place to start. Then read
The Codebreakers
, by David Kahn (Scribner, 1996). After that, there are several books on computer cryptography, and a few others on manual cryptography. You can subscribe to my free e-mail newsletter at
http://www.counterpane.com/
crypto-gram.html
or by sending a blank e-mail message to
[email protected].
It’s a fun field; good luck.