ciphergoth.org > Cryptology > Solitaire bias

Problems with Bruce Schneier's "Solitaire"

Readers of Neal Stephenson's "Cryptonomicon" will be familiar with the cipher "Solitaire" (called "Pontifex" in the book), which was designed by cryptologist Bruce Schneier specifically for the purposes of the book. It is intended to be the first truly secure hand cipher, and requires only a pack of cards for encryption and decryption.

As yet, the technical information about the design of the cipher has not been made available, but I decided to go investigating, and I've now written a fast "C" implementation of the cipher suitable for collecting statistics about the CPRNG at its heart. I have found two interesting facts:

The CPRNG state machine is not reversible, contrary to what the operational notes claim: the initial step in which a joker is moved to the top if it is on the bottom cannot be reversed. This is surprising since non-reversible CPRNGs tend to have shorter periods and can more easily exhibit bias.
And indeed, the output of the CPRNG is very biased. The output of each step of the CPRNG is a number from 0 to 25; you would expect successive outputs to be the same around one time in 26, but my experiments show that the frequency is closer to 1/22.5.

I'm making the source code for the tests I ran available to the public domain. Note that the problems reported in earlier versions are not present in this version; it turns out that it was only my development version that had the problems anyway and the one available for download was fine.

C implementation of Solitaire, optimised to perform both cuts in a single copying step; on my machine I can generate 10^7 samples in 20 seconds.
Perl implementation of Solitaire modified to do coincidence counting and take the same user interface as the C version, though of course the C version is about 250 times faster. This is useful for debugging and verifying the C version.
Normal distribution probability calculator, for when your statistical significance gets so high you fall off the end of your normal tables. Unfortunately, the significance of the bias I've detected in Solitaire (passphrase CRYPTONOMICON, 9999999 samples, 444745 coincidences) falls off the end of what this program can calculate, at 98.87 standard deviations from the mean...

I believe I now know the main reasons why this bias arises: when the value of the top card is the same in two successive rounds, an event you would expect to occur with probability just under 2%, the probability that the output letter is also the same is very high, around 34%. This is I assume because when this happens it's likely that many other cards are also in the same positions across the rounds. This isn't the sole source of the bias but it's by far the largest component. Below is the output from my latest version of c-sol, instrumented to measure the correlations between "coincidences" (two successive outputs being the same) and "top matches" (the value of the top card being the same on two successive rounds); everything it measures shows some bias, so there's more to be found than what I've discovered so far.

$./c-sol BIASED 26000001
  24509422     334473
    983536     172569
Top matches overall:
Sample: 507042 / 26000000
Measured p = 0.0192044 +0.000297226 = 0.0195016 (+1.5477 %)
+11.0429 SDs from mean
Coincidences overall:
Sample: 1156105 / 26000000
Measured p = 0.0384615 +0.00600404 = 0.0444656 (+15.6105 %)
+159.196 SDs from mean
Coincidences where top matches:
Sample: 172569 / 507042
Measured p = 0.0384615 +0.301883 = 0.340345 (+784.896 %)
+1117.8 SDs from mean
Coincidences where top doesn't match:
Sample: 983536 / 25492958
Measured p = 0.0384615 +0.000119155 = 0.0385807 (+0.309803 %)
+3.12843 SDs from mean

Update 2001 August 13: Frans Lategan made an interesting observation on the movement of the jokers in Solitaire, which I hadn't spotted until now.

I'm interested in designing a secure hand cipher; my first attempt, Mirdek turns out to be very insecure, but I return to the problem from time to time.

ciphergoth.org > Cryptology > Solitaire bias