Solitaire (cipher)

Last updated

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.

Contents

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. Furthermore, analysis has revealed flaws in the cipher such that 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 two 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). For example, take this starting deck:

Perform these steps to generate one character of the keystream.

  1. Locate the A joker 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 B 3 6 9 12 15 18 21 24 2 A 5 8 11 14 17 20 23 26
  2. Locate the B joker 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 B 9 12 15 18 21 24 2 A 5 8 11 14 17 20 23 26
  3. Perform a "triple cut": split the deck into three sections delimited by the jokers, and exchange the top and bottom section. The jokers themselves, and the cards between them, are left untouched.
    • 5 8 11 14 17 20 23 26 B 9 12 15 18 21 24 2 A 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 (53 when using a full deck). Remove that number of cards from the top of the deck and insert them just above the last card in the deck.
    • 23 26 B 9 12 15 18 21 24 2 A 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 (53 when using a full deck). 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 the 24th card, which is 11, determines the keystream value. (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]

Related Research Articles

Blowfish is a symmetric-key block cipher, designed in 1993 by Bruce Schneier and included in many cipher suites and encryption products. Blowfish provides a good encryption rate in software, and no effective cryptanalysis of it has been found to date. However, the Advanced Encryption Standard (AES) now receives more attention, and Schneier recommends Twofish for modern applications.

<span class="mw-page-title-main">Shuffling</span> Procedure used to randomize a deck of playing cards

Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. Shuffling is often followed by a cut, to help ensure that the shuffler has not manipulated the outcome.

In cryptography, RC4 is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, rendering it insecure. It is especially vulnerable when the beginning of the output keystream is not discarded, or when nonrandom or related keys are used. Particularly problematic uses of RC4 have led to very insecure protocols such as WEP.

<span class="mw-page-title-main">Stream cipher</span> Type of symmetric key cipher

A stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known as state cipher. In practice, a digit is typically a bit and the combining operation is an exclusive-or (XOR).

<span class="mw-page-title-main">Autokey cipher</span> Classic polyaphabet encryption system

An autokey cipher is a cipher that incorporates the message into the key. The key is generated from the message in some automated fashion, sometimes by selecting certain letters from the text or, more commonly, by adding a short primer key to the front of the message.

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

<span class="mw-page-title-main">Concentration (card game)</span> A memory based card game

Concentration is a round game in which all of the cards are laid face down on a surface and two cards are flipped face up over each turn. The object of the game is to turn over pairs of matching cards.

<span class="mw-page-title-main">Joker (playing card)</span> Playing card

The Joker is a playing card found in most modern French-suited card decks, as an addition to the standard four suits. From the second half of the 20th century, they have also been found in Spanish- and Italian-suited decks, excluding stripped decks.

The affine cipher is a type of monoalphabetic substitution cipher, where each letter in an alphabet is mapped to its numeric equivalent, encrypted using a simple mathematical function, and converted back to a letter. The formula used means that each letter encrypts to one other letter, and back again, meaning the cipher is essentially a standard substitution cipher with a rule governing which letter goes to which. As such, it has the weaknesses of all substitution ciphers. Each letter is enciphered with the function (ax + b) mod 26, where b is the magnitude of the shift.

In cryptography, the Cellular Message Encryption Algorithm (CMEA) is a block cipher which was used for securing mobile phones in the United States. CMEA is one of four cryptographic primitives specified in a Telecommunications Industry Association (TIA) standard, and is designed to encrypt the control channel, rather than the voice data. In 1997, a group of cryptographers published attacks on the cipher showing it had several weaknesses which give it a trivial effective strength of a 24-bit to 32-bit cipher. Some accusations were made that the NSA had pressured the original designers into crippling CMEA, but the NSA has denied any role in the design or selection of the algorithm. The ECMEA and SCEMA ciphers are derived from CMEA.

Multiple encryption is the process of encrypting an already encrypted message one or more times, either using the same or a different algorithm. It is also known as cascade encryption, cascade ciphering, multiple encryption, and superencipherment. Superencryption refers to the outer-level encryption of a multiple encryption.

<span class="mw-page-title-main">Glossary of cryptographic keys</span>

This glossary lists types of keys as the term is used in cryptography, as opposed to door locks. Terms that are primarily used by the U.S. National Security Agency are marked (NSA). For classification of keys according to their usage see cryptographic key types.

In cryptography, ciphertext stealing (CTS) is a general method of using a block cipher mode of operation that allows for processing of messages that are not evenly divisible into blocks without resulting in any expansion of the ciphertext, at the cost of slightly increased complexity.

The Two-square cipher, also called double Playfair, is a manual symmetric encryption technique. It was developed to ease the cumbersome nature of the large encryption/decryption matrix used in the four-square cipher while still being slightly stronger than the single-square Playfair cipher.

Mental poker is the common name for a set of cryptographic problems that concerns playing a fair game over distance without the need for a trusted third party. The term is also applied to the theories surrounding these problems and their possible solutions. The name comes from the card game poker which is one of the games to which this kind of problem applies. Similar problems described as two party games are Blum's flipping a coin over a distance, Yao's Millionaires' Problem, and Rabin's oblivious transfer.

The Goldwasser–Micali (GM) cryptosystem is an asymmetric key encryption algorithm developed by Shafi Goldwasser and Silvio Micali in 1982. GM has the distinction of being the first probabilistic public-key encryption scheme which is provably secure under standard cryptographic assumptions. However, it is not an efficient cryptosystem, as ciphertexts may be several hundred times larger than the initial plaintext. To prove the security properties of the cryptosystem, Goldwasser and Micali proposed the widely used definition of semantic security.

In cryptanalysis, attack models or attack types are a classification of cryptographic attacks specifying the kind of access a cryptanalyst has to a system under attack when attempting to "break" an encrypted message generated by the system. The greater the access the cryptanalyst has to the system, the more useful information they can get to utilize for breaking the cypher.

In cryptography, a keystream is a stream of random or pseudorandom characters that are combined with a plaintext message to produce an encrypted message.

<span class="mw-page-title-main">Cryptography</span> Practice and study of secure communication techniques

Cryptography, or cryptology, is the practice and study of techniques for secure communication in the presence of adversarial behavior. More generally, cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, information security, electrical engineering, digital signal processing, physics, and others. Core concepts related to information security are also central to cryptography. Practical applications of cryptography include electronic commerce, chip-based payment cards, digital currencies, computer passwords, and military communications.

Identity-based conditional proxy re-encryption (IBCPRE) is a type of proxy re-encryption (PRE) scheme in the identity-based public key cryptographic setting. An IBCPRE scheme is a natural extension of proxy re-encryption on two aspects. The first aspect is to extend the proxy re-encryption notion to the identity-based public key cryptographic setting. The second aspect is to extend the feature set of proxy re-encryption to support conditional proxy re-encryption. By conditional proxy re-encryption, a proxy can use an IBCPRE scheme to re-encrypt a ciphertext but the ciphertext would only be well-formed for decryption if a condition applied onto the ciphertext together with the re-encryption key is satisfied. This allows fine-grained proxy re-encryption and can be useful for applications such as secure sharing over encrypted cloud data storage.

References

  1. ↑ Schneier, Bruce (May 1999). "Solitaire" . Retrieved 2 July 2006.
  2. 1 2 Crowley, Paul. "Problems with Bruce Schneier's "Solitaire"" . Retrieved 26 March 2018.
  3. 1 2 Shiu, Daniel (13 Sep 2019). "Analysis of Solitaire". arXiv: 1909.06300 [cs.CR].
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.