Solitaire

The Solitaire cryptographic algorithm was designed by Bruce Schneier at the request of Neal Stephenson for use in his novel Cryptonomicon, in which field agents use it to communicate securely without having to rely on electronics or having to carry incriminating tools. It was designed to be a manual cryptographic system calculated with an ordinary deck of playing cards. In Cryptonomicon, this algorithm was originally called Pontifex to hide the fact that it was about playing cards.

One of the motivations behind the creation of Solitaire is that in totalitarian environments, a deck of cards is much more affordable (and less incriminating) than a personal computer with a variety of cryptological utilities. However, as Schneier warns in the Cryptonomicon appendix, almost everyone interested in cryptanalysis will now be familiar with this algorithm, so carrying around a deck of cards can also be considered incriminating.

Since its creation, analysis has revealed flaws in encryption. It is now considered unsafe.

Encryption and decryption

This algorithm uses a standard deck of cards with 52 cards of the same suit and two jokers that are distinguished from each other, called Joker A and Joker B. For the sake of simplicity, only two suits will be used in this example, clubs and diamonds. Each card is assigned a numerical value: clubs will be numbered 1 to 13 (ace to king) and diamonds will be numbered 14 to 26 in the same way. Jokers will be assigned the values 27 and 28. Therefore, the jack of clubs would have the value 11 and the two of diamonds would have the value 15. (In a full deck of cards, the suits are ranked in order of bridge: clubs, diamonds, hearts, spades, with suited cards numbered 1 through 52, and jokers numbered 53 and 54.)

To begin encryption or decryption, place the deck of cards face up in the order agreed upon. The person who decrypts a message must have a deck arranged in the same order as the deck used by the person who encrypted the message. The way in which the order is initially decided depends on the recipients; It is preferable to shuffle the deck perfectly at random, although there are many other methods.

The algorithm generates a keystream, a sequence of values that are combined with the message to encrypt and decrypt it. Each keystream value is used to encrypt one character of the message, so the keystream must be at least as long as the message. If the keystream is longer than the message, the message may be padded with an additional repeating character, thus denying the attacker knowledge of the exact length of the message.

To encrypt a message (assumed to mean English, the original language of the novel, with a 26-letter alphabet):

1. Remove all score and spaces, leaving only 26 letters A – Z.
2. Convert each letter to its natural numerical value, A = 1, B = 2,..., Z = 26.
3. Generate a key flow value for each letter of the message using the next key flow algorithm.
4. Add each key sequence value to the corresponding formatless text number, subtracting 26 if the resulting value is greater than 26 (in mathematics, this is called modular arithmetic).
5. Turn the resulting numbers back to letters. This lyric sequence is the encrypted text.

To decrypt an encrypted text:

1. Converts each letter of the encrypted text to its natural numerical value.
2. Generate a key flow value for each letter in the encrypted text.
3. Reveal each key flow value of the corresponding encrypted text value, adding 26 if the resulting value is less than 1.
4. Turn the resulting numbers back to letters.

Keyflow Algorithm

This algorithm generates key flow values by moving cards within the deck. The key sequence algorithm is deterministic, so the key sequence values depend only on the initial platform order. The deck is supposed to be a circular array, which means that if a card ever needs to advance below the bottom card in the deck, it will simply rotate to the top (in other words, first card follows last).. Let's take for example this starter deck:

• 1 4 7 10 13 16 19 22 25 28 3 6 9 12 15 18 21 24 2 5 8 11 14 17 20 23 26

Perform these steps to generate a keystream character:

1. Locate wild A (value 27) and move it down in the deck a place. If it is the last letter, it becomes the second letter. There's no way he'll become the first letter. The deck now looks like this:
   • 1 4 7 10 13 16 19 22 25 28 3 6 9 12 15 18 21 24 2 27 5 8 11 14 17 20 23 26
2. Locate wild B (value 28) and move it down in the deck two places. Please note that if it is the penultimate letter, it becomes the second letter wrapping it. If it is the last letter, it becomes the third letter. There's no way he'll become the first letter.
   • 1 4 7 10 13 16 19 22 25 3 6 28 9 12 15 18 21 24 2 27 5 8 11 17 20 23 26
3. Make a "triple cut": divide the platform into three sections. Everything that is above the upper wild (which, after several repetitions, may not necessarily be the wildcard A) and all that is under the lower wild will be exchanged. The wilds themselves, and the cards among them, remain intact.
   • 5 8 11 14 17 20 23 26 28 9 12 15 18 21 24 2 27 1 4 7 10 13 16 19 22 25 3 6
4. Make a "conteo cut": observe the value of the card at the bottom of the deck. If the card is wild, take its value in 27. Remove that number of cards from the top of the deck and insert them right above the last card from the deck.
   • 23 26 28 9 12 15 18 21 24 2 27 1 4 7 10 16 19 22 25 3 5 8 11 14 17 20 6
5. Now, look at the value of the superior letter. Once again, any of the wilds counts as 27. Count this number of places under that letter and take the value of that letter as the next value in the key sequence. If the letter counts even as a wild card, ignore it and repeat the key flow algorithm. In this example, the top letter is 23, so we count to the 24th letter, which is 11; therefore, the value of the key sequence is 11. (Please note that no card changes place in this step, this step simply determines the value of the key sequence).

Cryptanalysis

In 1999, Paul Crowley discovered that there is a bias towards character repetition in the key sequence, which occurs approximately every 1/22.5 characters instead of the expected 1/26. As a result, Solitaire filters information at a rate of about 0.0005 bits per character. While its security may be adequate for very short messages, Solitaire is generally considered insecure.

Crowley also noticed that in some cases there are two different platform configurations that result in the same configuration after running the keyflow algorithm. For example, when joker A is on the bottom of the deck or on the top of the deck, it will become the second card after step 1. This means that the algorithm is not always reversible as Schneier had originally claimed.

In 2019 Daniel Shiu proposed modifications to the algorithm that would increase its security, at the cost of making it more difficult for the user to implement manually.