[cryptography] Improving the Solitaire Cipher by Bruce Schneier

Aaron Toponce aaron.toponce at gmail.com
Wed Aug 20 18:40:50 EDT 2014


Paul Crowley at http://www.ciphergoth.org/crypto/solitaire/ identifies two core
problems with the solitair cipher:

    * The CPRNG internal state is not reversible.
    * The CPRNG output is biased.

The solitaire cipher can be found at:

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

First, I believe the irreversibility of the algorithm is due to the shift of
jokers A & B. In Bruce's algorithm, if Joker A is on the bottom of the deck,
and because the deck is circular, then Joker A occupies the same position as
the top of the deck. As such, when step 1 is executing, Joker A will end up
beneath the top card. Per his instructions:

    1. Find the A joker. Move it one card down. (That is, swap it with the card
    beneath it.) If the joker is the bottom card of the deck, move it just
    below the top card.

    2. Find the B joker. Move it two cards down. If the joker is the bottom
    card of the deck, move it just below the second card. If the joker is one
    up from the bottom card, move it just below the top card. (Basically,
    assume the deck is a loop...you get the idea.)

I think this can be addressed with the following adjustment:

    1. Find the A joker. Move it one card down. If the joker is the bottom card
    of the deck, move it to the top card.
    
    2. Find the B joker. Move it two cards down. If the joker is the bottom
    card of the deck, move it just below the top card. If the joker is one up
    from the bottom card, move it to the top card.

However, with my testing, I still see the same ias, even though the internal
state is now reversible. I agree with Paul's hypothesis about the probability
of the top card increasing the probability of the output card.

To reduce the bias, it seems necessary to adjust the distance between the two
jokers randomly on each round. Step 4 according to Bruce's design is:

    4. Perform a count cut. Look at the bottom card. Convert it into a number
    from 1 through 53. Count down from the top card that number. Cut after the
    card that you counted down to, leaving the bottom card on the bottom.

Instead, it could be adjusted to:

    4. Perform a count cut. Look at the bottom card. Convert it into a number
    from 1 through 53. Count down from the top card that number. Perform a cut
    on the deck after the card you counted down to, placing the cut above the
    bottom joker.

In other words, by taking the "count down cut" and placing them between the
jokers, the distance between the jokers changes randomly on each round, but it
also decreases our probability that the output card will be the same as the
previous output card, if the top card is the same after two successive rounds.

Interested in feedback, as I am sure I am overlooking something here.

Thanks,

-- 
. o .   o . o   . . o   o . .   . o .
. . o   . o o   o . o   . o o   . . o
o o o   . o .   . o o   o o .   o o o
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 502 bytes
Desc: not available
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20140820/d7bc12fd/attachment.asc>


More information about the cryptography mailing list