More Cryptanalysis of Solitaire

In 1999, I invented the Solitaire encryption algorithm, designed to manually encrypt data using a deck of cards. It was written into the plot of Neal Stephenson’s novel Cryptonomicon, and I even wrote an afterward to the book describing the cipher.

I don’t talk about it much, mostly because I made a dumb mistake that resulted in the algorithm not being reversible. Still, for the short message lengths you’re likely to use a manual cipher for, it’s still secure and will likely remain secure.

Here’s some new cryptanalysis:

Abstract: The Solitaire cipher was designed by Bruce Schneier as a plot point in the novel Cryptonomicon by Neal Stephenson. The cipher is intended to fit the archetype of a modern stream cipher whilst being implementable by hand using a standard deck of cards with two jokers. We find a model for repetitions in the keystream in the stream cipher Solitaire that accounts for the large majority of the repetition bias. Other phenomena merit further investigation. We have proposed modifications to the cipher that would reduce the repetition bias, but at the cost of increasing the complexity of the cipher (probably beyond the goal of allowing manual implementation). We have argued that the state update function is unlikely to lead to cycles significantly shorter than those of a random bijection.

Tags: academic papers, algorithms, cryptanalysis, cryptography

Posted on October 4, 2019 at 12:04 PM • 15 Comments

Comments

Patriot • October 4, 2019 12:07 PM

Looks like it happens to the best of us.

Kai • October 4, 2019 1:55 PM

Schneier’s Law strikes again. I loved Cryptonomicon, it is one of my favourite books, and the fact that the Solitaire crypto was a real thing was like the icing on the cake.
https://www.schneier.com/blog/archives/2011/04/schneiers_law.html

Michael Gaul • October 4, 2019 3:32 PM

Where I work, a click on the link to ciphergoth at “dumb mistake” is intercepted by zscalar as an attempt to visit a pornography site. I could take this in about five different directions, but I’ll just leave it at that.

Weather • October 5, 2019 12:04 AM

The mistake must have been a backdoor by spooks 😉
Would the game “eye spy” were someone says a letter and you have to guess what they saw, be used instead of a deck of cards?

Wayne • October 5, 2019 1:09 PM

I started reading Neal’s new book, Fall, and had a “I think I remember that name” moment and found it was in Cryptonomicon. So I’m re-reading Cyrptonomicon, THEN reading Fall.

And Stephenson is such light reading. Maybe I’ll be done with Fall by Festivus.

Jeff • October 5, 2019 2:08 PM

Would someone please explain what reversibility means in this context.

SpaceLifeForm • October 5, 2019 2:38 PM

Paper (cards) crypto may not be secure if there exists multiple Jokers?

How many multiple Jokers involved these days with internet infrastructure and TLS?

Jacob • October 5, 2019 7:56 PM

@Jeff: Reversible, in this context, means that given the state at time t=10, you can find the state at time t=9. Solitaire isn’t reversible because there are, in certain circumstances, two possible states, J[1-53] and [1-53]J, which will lead to the same following state. So if you end up in a state which follows one of those, you can’t reverse it to find what state preceded it.

Clive Robinson • October 6, 2019 3:28 AM

@ jeff, Jacob,

Would someone please explain what reversibility means in this context.

As @Jacob has explained you can end up in a state which you can not back out of uniquely.

You might think OK why is that important?

The point is firstly it leads to a reduced number of states in the generator, secondly it also lead to some measure of bias in the generator output because of it.

Most stream generaters have some bias, the most commonly mentioned is the Linear Feedback Shift Register (LFSR) that has one state either all zeros or all ones dependent on the feedback logic type used.

By a little thought experiment you can realise that the maximum length of all ones or all zeros the generator can produce is based on the number of it’s storage elements N that define the maximum state it can store 2^N for binary storage elements. Thus the maximum length output of zeros or ones would be with three state transitions,

{0b100..00},{0b000..00},{0b000..01}

for zeros and the inverse for ones. That it is the length of zeros/ones is 3N-2. If however the storage can not produce either the all ones or all zero’s state than it drops to 2N-2 as the maximum for one of them, which is quite a chunk of bias. Whilst not all generators can be in those three states in sequence the general principle of bias due to missing states holds.

There is also another issue that I will mention but not try to justify. Whilst some generators can generate a significant number of their states (2^N-1 for the LFSR) many can not[1]. The underlying reason often being the need to have non-linear feedback (the LFSR can be broken with just 2N output bits due to it’s linear feedback). This has concequences in that you get shorter “cycles of states” some can be very short and there can also be a multiplicity of them. Thus you can end up with quite a weak generator that cycles through as few as one state (LFSR) or just a handfull of states.

It’s why some recommend using a counter that is known to only cycle through all possible states, followed by one or more non-linear mapping functions. Block ciphers often being considered as usefull mapping functions hence you end up with what is called “Counter Mode” which for AES you might see as AES128-CTR or AES-CTR (see NIST SP800-38A).

[1] Due to mechanical deficiences in the Enigma odometer movement it did not go into all states, there are one or two books around that describe how that deficiency actually helped in breaking the German use of Enigma.

Jesse Thompson • October 6, 2019 5:30 PM

@Jeff

Reversibility described even more simply. 🙂

Reversible: left bit shift with wraparound.

1100 becomes 1001, and 1001 only could have come from 1100. The same pairing holds for every possible permutation.

(at least partly) Irreversible: left bit shift with zero fill.

1100 becomes 1000. But 0100 would have also lead to 1000, so 1000 has no unique heritage.

You cannot have a unique reverse operation to “left shift with zero fill”, because you’d have to try to recover lost bits shifted off the side. And every process where any state could have more than one parent or more than one child suffers the same fate.

When an operation is reversible, every single state has one and only one parent, and one and only one child.

When it is irreversible, at least some of the states MUST have more than one parent, some MUST have more than one child, also some MUST have zero parents and some MUST have zero children. ^[1]

Incidentally, fellow hard scifi author Greg Egan ran afoul of this in a different way when he wrote Permutation City. 😉

In any event, irreversible processes cannot maintain full entropy because at least the first step must map more possibilities into fewer possibilities with at least some duplicates. Left Shift Zero Fill cuts the possibilities in half each time, for example.

Some processes can reach an equilibrium in entropy after one or more steps though, which is like a damage control compromise. For example the process “Add two, ignoring overflow, and then set right bit to zero” loses half it’s possible states in the first operation (all the odd numbers) but then immediately reaches a stable equilibrium where the remainder of states (the even numbers) can be considered reversible among themselves. EG you lose 1 bit of entropy and then stop losing more.

^{[1] Myhill, “The converse of Moore’s Garden-of-Eden theorem”, Proc. Amer. Math. Soc. 14 (1963), 685–686}

stormwyrm • October 7, 2019 2:13 AM

Apart from Solitaire there any other pencil and paper ciphers that can be used without the aid of any automatic computing device? Apparently, RC4 can almost be done manually: the initial keying step is what makes it rather unworkable for manual use. Solitaire was clearly influenced by RC4 and tries to address this difficulty. There are cut-down variants of RC4 that are supposed to be easier to do by hand but obviously no security analysis has been done on them.

Denton Scratch • October 11, 2019 6:43 AM

@Bruce: The word you were hunting for was “afterword”, I think. “Afterward” is a sort of synonym for “after”, but not quite. Like, “After he did X, he did Y”; but “He did X; then afterward, he did Y”. I don’t know the correct grammar terminology to distinguish these two words, but I think they are two distinct parts of speech, and not really synonyms.

By contrast, “afterword” is analogous to “foreword” – it’s a page of prose that precedes or follows the main body respectively. I think a synonym is “postscript”; but that term nowadays is mostly associated with a page-description-language originally invented for laser printers.

So I claim that the meaning of “afterword” is quite distinct from either “after” or afterward”.

Hey, I don’t speak USAian very fluently; perhaps these words all mean the same thing in the USA. Dammit, I sometimes discover that I don’t even know British English; I like to be corrected when I’m wrong, so do pile in.

Lee • October 13, 2019 2:02 PM

Computers are much better at this sort of thing and can encode longer messages with better security. See my encoder/decoder which also handles Unicode: https://secure.leehaywood.org/cards/

stormwyrm • October 15, 2019 9:29 PM

@Lee: That misses the whole point of Solitaire. If you don’t have time to read Cryptonomicon and at least reach the part where Randy Waterhouse sits in a Philippine jail cell exchanging secret messages with Enoch Root using the algorithm and a deck of cards (sadly that’s near the end of the book), you can read Bruce’s own description here, including notes on the motivation for it:

https://www.schneier.com/academic/solitaire/

“…I designed it to allow field agents to communicate securely without having to rely on electronics or having to carry incriminating tools. An agent might be in a situation where he just does not have access to a computer, or may be prosecuted if he has tools for secret communication. But a deck of cards…what harm is that?”

Lee • October 16, 2019 2:59 PM

@stormwyrm: Yes, I realise that Solitaire is intended for purely manual use. But the fundamental idea of hiding a message in a pack of cards is a sound one.

So long as a password is used, an observer cannot distinguish the sequence from an ordinary and well-shuffled pack of cards – giving the same plausible deniability that Solitaire does. My method can be downloaded and used on a device not connected to a network, although of course the mere act of having/using software could possibly be detected (unless it is itself encrypted, perhaps!)

More Cryptanalysis of Solitaire

Comments

Leave a comment Cancel reply