Thursday, February 10, 2011

[ovpmzdqh] Storing a key in a deck of cards

As observed in Schneier's cipher Solitaire, a deck of cards can steganographically carry quite a bit of information (log2(52!) = 225.6 bits), and shuffling can generate that much entropy manually.

However, unlike the flawed RC4 inspired implementation of Solitaire, let's just use AES, encoding a key in the permutation of the cards.  We assume all parties have access to the necessary equipment and software; we just need a method of storing a key.  This may be a solution in search of a problem.

An arbitrary number within range may be converted to and from a permutation by writing the number in mixed radix notation.  (Are there better ways?)

35 cards are sufficient for 128 bits of entropy, leaving 17 which can be used for error detection, perhaps one suit plus 10 Jack Queen King of another suit.  The 17 cards can be interleaved with the other 35 making it less obvious that the deck is not an ordinary shuffled deck.  These parity "bits" are a nice feature because a human will probably have to manually enter the cards into a computer.

A simple way to compute parity is to convert (SHA1(key) mod (17!)) into a permutation.  Substitute a stronger hash function as necessary.  There are almost certainly better ways (coding theory, etc.)

When generating entropy, shuffle the 35 cards, and have a computer calculate the order of the parity cards, and interleave them with the main deck so that the last suit isn't obviously segregated.  Because the 17 designated parity cards are known, they can be separated out later; their order just needs to be preserved.

One can make a backup deck storing the same key by using a different structure of parity cards and mixed radix ordering.  Perhaps the inverse permutation. Then there will not be the suspiciousness of carrying two decks seemingly identically shuffled.  The parity cards should be sufficient to distinguish which structure a deck has, unless one is fantastically unlucky.

No comments :