https://alicegg.tech//2020/01/03/solitaire.html
Alice GG
Posted on January 3, 2020
Low Tech Crypto : Solitaire
In a previous post, I talked about the One-Time Pad, as an example of
cryptography that's achievable without a computer. It's a very
simple, yet perfectly secure cryptographic algorithm, that comes with
a lot of practical limitations, the biggest one being that it
requires a truly random key as long as the text you want to encrypt
(the plaintext). The good news is that cryptographers have been hard
at work creating algorithms that are more usable while still
providing privacy.
Solitaire, an algorithm made by Bruce Schneier in 1999 is definitely
the most famous of the low-tech cryptography algorithm since it was
featured in Neal Stephenson's book Cryptonomicon under the name
"Pontifex". As its name suggests, it uses a deck of cards to encrypt
and decrypt messages.
A regular card deck Illustraton by Aditya Chinchure
Encrypting messages
Solitaire is a stream cipher, which means it works just like the
one-time pad, except instead of using a truly random key for the
whole length of the plaintext, they generate a pseudo-random
keystream from a smaller key. In this case, our base key is a
shuffled deck of 54 cards, with two differentiable jokers (we will
call them A and B).
Let's say we have the thoroughly shuffled deck of cards below and
want to encrypt the message HAPPY NEW YEAR:
49 50 51 3 4 5 6 7 1
10 11 12 52 15 16 17 18 19
20 21 2 9 26 27 28 29 30
31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 23 A 14
22 8 24 25 B 46 47 48 13
Step 0: First we need to format the message into blocks of 5
characters (pad it with X if necessary) to avoid leaking pieces of
informations. This gives us: HAPPY NEWYE ARXXX. We will then use a
number representation of this plaintext.
H A P P Y N E W Y E A R X X X
8 1 16 16 25 14 5 23 25 5 1 18 24 24 24
Step 1: We can then start generating the keystream, by taking the
joker A and swapping it with the card beneath it. If it's the last
card put it after the first card.
49 50 51 3 4 5 6 7 1
10 11 12 52 15 16 17 18 19
20 21 2 9 26 27 28 29 30
31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 23 14 A
22 8 24 25 B 46 47 48 13
Step 2: You then find joker B and move it the same way two cards
down.
49 50 51 3 4 5 6 7 1
10 11 12 52 15 16 17 18 19
20 21 2 9 26 27 28 29 30
31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 23 14 A
22 8 24 25 46 47 B 48 13
Step 3: Swap the cards above the first joker, with the cards below
the second joker.
48 13 A 22 8 24 25 46 47
B 49 50 51 3 4 5 6 7
1 10 11 12 52 15 16 17 18
19 20 21 2 9 26 27 28 29
30 31 32 33 34 35 36 37 38
39 40 41 42 43 44 45 23 14
Step 4: Take the value of the bottom card as a number. The simplest
way to do that is to use the position of the card in the bridge suit
(clubs < diamonds < hearts < spades). For example 10 of heart is 36
and a 2 of club is just 2. Jokers are both 53.
Use this value as the index where to cut the deck for the next step.
Now swap both parts of the cut, without moving the bottom card:
4 5 6 7 1 10 11 12 52
15 16 17 18 19 20 21 2 9
26 27 28 29 30 31 32 33 34
35 36 37 38 39 40 41 42 43
44 45 23 48 13 A 22 8 24
25 46 47 B 49 50 51 3 14
Step 5: To find the output value, use the value of the top card as
the index of the output card. If the output card is not a joker,
write down its value. Start back with the deck in its current state
at step 1 until you have as many numbers in your keystream as letters
in your plaintext.
In our example, we find the following keystream:
1 34 29 35 39 46 11 12 29 50 24 26 45 6 6
Step 7: Add your keystream to your plaintext (as numbers) modulo 26
to obtain the ciphertext:
8 1 16 16 25 14 5 23 25 5 1 18 24 24 24
1 34 29 35 39 46 11 12 29 50 24 26 45 6 6
I I S Y L H P I B C Y R Q D A
You can now safely send IISYL HPIBC YRQDA to anyone who has a deck
shuffled in the same order as yours. To decrypt it, you will need to
generate the same keystream and subtract it to the ciphertext you
just produced.
A regular card deck Illustraton by Aaron Burden
Limitations
Solitaire is a great low-tech cipher since it's both practically
secure and uses items that are both easy to find and unsuspicious.
However, there are a few limitations to keep in mind while using this
cipher:
1. You should never use the same key twice, as it would allow an
attacker to gather information about your messages without even
knowing the key.
2. You should only encrypt small messages with it. A recent analysis
of Solitaire found that it leaks information at a rate of 0.0005
bits per character, while this is reasonably safe for encoding
you 140 character long tweet, it isn't safe to use for your copy
of War and Peace.
3. You still need to be careful about any extra information you
could give to an attacker, especially notes you take of the
keystream, or decks that you used / intent to use, as those can
be used to crack your messages.
If you want a more complete overview of Solitaire, I recommend the
lecture of the original Bruce Schneier's article on it. If code talks
to you more than English, I made a small Python implementation of
Solitaire that can be useful for testing purposes, you can find it on
GitHub.
Next entry FOSDEM 2020 recap
Previous entry Introducing tartiflette-plugin-scalars
Alice GG * Table of Contents
* Alice GG
* hi@alicegg.tech
* GitHub
* LinkedIn
* Mastodon
* Twitter
Alice Girard Guittard, Software Engineer and Co-Founder at
Tsukumogami Software, passionate about Software, DevOps and
Information Security.