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:
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.
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.