Solitaire (cipher)

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.[1] It was designed to be a manual cryptosystem calculated with an ordinary deck of playing cards. In Cryptonomicon, this algorithm was originally called Pontifex to hide the fact that it involved playing cards.

One of the motivations behind Solitaire's creation is that in totalitarian environments, a deck of cards is far more affordable (and less incriminating) than a personal computer with an array of cryptological utilities. However, as Schneier warns in the appendix of Cryptonomicon, just about everyone with an interest in cryptanalysis will now know about this algorithm, so carrying a deck of cards may also be considered incriminating.

Since its creation, analysis has revealed flaws in the cipher. It is now considered insecure.

Encryption and decryption

This algorithm uses a standard deck of cards with 52 suited cards and two jokers which are distinguishable from each other, called the A joker and the B joker. For simplicity's sake, only two suits will be used in this example, clubs and diamonds. Each card is assigned a numerical value: the clubs will be numbered from 1 to 13 (Ace through King) and the diamonds will be numbered 14 through 26 in the same manner. The jokers will be assigned the values of 27 and 28. Thus, the jack of clubs would have the value 11, and the deuce of diamonds would have the value 15. (In a full deck of cards, the suits are valued in bridge order: clubs, diamonds, hearts, spades, with the suited cards numbered 1 through 52, and the jokers numbered 53 and 54.)

To begin encryption or decryption, arrange the deck of cards face-up in an order previously agreed upon. The person decrypting a message must have a deck arranged in the same order as the deck used by the person who encrypted the message. How the order is initially decided upon is up to the recipients; shuffling the deck perfectly randomly is preferable, although there are many other methods.

The algorithm generates a keystream, a sequence of values which are combined with the message to encrypt and decrypt it. Each value of the keystream 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 repeated character, thus denying the attacker knowledge of the exact length of the message.

To encrypt a message:

  1. Remove all punctuation and spaces, leaving only the 26 letters A–Z.
  2. Convert each letter to its natural numerical value, A = 1, B = 2, ..., Z = 26.
  3. Generate one keystream value for each letter in the message using the keystream algorithm below.
  4. Add each keystream value to the corresponding plaintext number, subtracting 26 if the resulting value is greater than 26. (In mathematics this is called modular arithmetic.)
  5. Convert the resulting numbers back to letters. This sequence of letters is the ciphertext.

To decrypt a ciphertext:

  1. Convert each letter in the ciphertext to its natural numerical value.
  2. Generate one keystream value for each letter in the ciphertext.
  3. Subtract each keystream value from the corresponding ciphertext value, adding 26 if the resulting value is less than 1.
  4. Convert the resulting numbers back to letters.

Keystream algorithm

This algorithm generates keystream values by moving cards within the deck. The keystream algorithm is deterministic, so the keystream values depend only on the initial order of the deck. The deck is assumed to be a circular array, meaning that should a card ever need to advance below the bottom card in the deck, it will simply rotate back to the top (in other words, the first card follows the last card). We will take for example this starting deck:

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

Perform these steps to generate one character of the keystream.

  1. Locate the A joker (value 27) and move it down the deck by one place. If it is the last card, it becomes the second card. There is no way for it to become the first card. 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 the B joker (value 28) and move it down the deck by two places. Notice that if it is the second to last card, it becomes the second card by wrapping around. If it is the last card, it becomes the third card. There is no way for it to become the first card.
    • 1 4 7 10 13 16 19 22 25 3 6 28 9 12 15 18 21 24 2 27 5 8 11 14 17 20 23 26
  3. Perform a "triple cut": split the deck into three sections. Everything above the top joker (which, after several repetitions, may not necessarily be the A joker) and everything below the bottom joker will be exchanged. The jokers themselves, and the cards between them, are left untouched.
    • 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. Perform a "count cut": observe the value of the card at the bottom of the deck. If the card is either joker take its value to be 27. Remove that number of cards from the top of the deck and insert them just above the last card in the deck.
    • 23 26 28 9 12 15 18 21 24 2 27 1 4 7 10 13 16 19 22 25 3 5 8 11 14 17 20 6
  5. Now, look at the value of the top card. Again, either joker counts as 27. Count this many places below that card and take the value of that card as the next value in the keystream. If the card counted to is either joker, ignore it and repeat the keystream algorithm. In this example the top card is 23, so we count to the 24th card, which is 11; thus the keystream value is 11. (Note that no cards change places in this step, this step simply determines the keystream value).

Cryptanalysis

In 1999 Paul Crowley discovered that there is a bias towards repeating characters in the keystream, which occur about every 1/22.5 characters rather than the expected 1/26.[2] As a result, Solitaire leaks information at a rate of about 0.0005 bits per character.[3] While its security may perhaps be adequate for very short messages, in general Solitaire is considered insecure.

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

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

References
  1. Schneier, Bruce (May 1999). "Solitaire". Retrieved 2 July 2006.
  2. Crowley, Paul. "Problems with Bruce Schneier's "Solitaire"". Retrieved 26 March 2018.
  3. Shiu, Daniel (13 Sep 2019). "Analysis of Solitaire". arXiv:1909.06300 [cs.CR].
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.