I've been obsessing over the past couple weeks trying to improve Bruce Schneier's solitaire cipher, aka "Pontifex". The more I think about it, the more I realize that there just isn't a lot that can be done about the bias of Pontifex without severely slowing down the already slow algorithm. So, instead of trying to improve on his algorithm, I came up with my own - "Talon".
This cipher discards the two jokers. You only need the standard 52-cards from a poker or bridge set (4 suits, Ace through King). As with Pontifex, this is a output feedback mode stream cipher. Also, when determining the value of the output card, the same suit order is used:
- Clubs - face value + 0
- Diamonds - face value + 13
- Hearts - face value + 26
- Spades - face value + 39
An unkeyed deck would have Ace through King of Clubs, followed by Ace through King of Diamonds, followed by Ace through King of Hearts, followed by Ace through King of Spades.
This algorithm is executed in 4 steps. You will be making four discard piles, or "talons", labeled 1, 2, 3, & 4 from left to right:
- Create four discard piles. With the deck face-up in your hand, place the top card in discard pile #1, the 2nd card in discard pile #2, the 3rd card is discard pile #3, and the 4th card in discard pile #4. For example, if the deck was unkeyed, then the Ace of Clubs would be in discard pile #1, the Two of Clubs in #2, the Three of Clubs in #3, and the Four of Clubs in #4.
- Note the face value of discard pile #1, ignoring suit, and count that many cards minus 1 from the top of the deck, and place them on top of discard pile #1. If the card was a Jack, then count 10 cards from the face up deck in your hard, and place them on top of the Jack. Do the same for the other three piles, in order (#2, then #3, then #4). In other words, the first card placed down in the discard pile, or "talon", will determine the total number of cards in that stack.
- Collect the piles by placing discard pile #1 on top of pile #2 on top of pile #3 on top of pile #4, and place the stack behind the face up deck in your hand. If all 52 cards were in discard piles (13 cards in each pile), then place the newly collected stack in your hand, face up.
- Find the output card by summing the deck value of the top card, with the deck value of the bottom card, modulo 52. Count down that many cards into the deck, and record the value of the next card. If the top card is a Queen of Hearts, then the value would be 12 + 26 = 38. And if the bottom card is the 3 of Diamonds, then the value would be 3 + 13 = 19. (38 + 19) mod 52 = 5. Count 5 cards from the top of the deck, and record the face value of the 6th card, including suit. This ensures that each card is equally likely to be the output card as the rest in the deck. To make sure you are doing the counting correctly, if the sum value mod 52 is 0, you would record the value of the top card. If the sum value mod 52 is 51, you would record the value of the bottom card.
The key lies in the initial order of the deck, as with other designs. It can be keyed with random shuffling, bridge puzzles, or passphrases. If a passphrase is used, step 4 is replaced:
- Pass cut. Get the numerical value of the first character in your passphrase. As with the original step #4, count that many cards minus 1 from the top of the deck, and cut them below the rest of the cards. A = 1, B = 2, ..., Y = 25, Z = 26. This step will break the reversibility of Talon, while keying the deck.
Example:
Suppose we start with an unkeyed deck. Our top card will be the Ace of Clubs, with the deck face up in our hands, and the bottom card will be the King of Spades.
After step 1, we would have the following 4 discard piles:
#1 #2 #3 #4 -------------- AC 1C 2C 3C
After step 2, our discard piles would look like:
#1 #2 #3 #4
--------------
AC 2C 3C 4C <-- Bottom of discard piles
5C 6C 8C
7C 9C
10C
Remaining in my hand would be:
After step 3, the order of my hand would now be:
JC,QC,KC,AD,2D,3D,4D,5D,6D,7D,8D,9D,10D,JD,QD,KD,AH,2H,3H,4H,5H,6H,7H,8H,9H,10H,JH,QH,KH,AS,2S,3S,4S,5S,6S,7S,8S,9S,10S,JS,QS,KS,AC,5C,2C,7C,6C,3C,10C,9C,8C,4C
For step 4, the Jack of Clubs is the top card. Thus, its numerical value is 11 + 0 = 11. Counting 11 cards gives me the Nine of Diamonds as my output card. I would write down 22 as my output number (9 + 13 = 22).
After another round, my deck would be ordered as:
9S,10S,JS,QS,KS,AC,5C,2C,7C,6C,3C,10C,9C,8C,4C,2D,3D,4D,5D,6D,7D,8D,9D,10D,JD,JC,QD,KD,AH,2H,3H,4H,5H,6H,7H,8H,9H,QC,10H,JH,QH,KH,AS,2S,3S,4S,5S,6S,7S,8S,KC,AD
Because my top card is the Nine of Spades, it's numerical value is 9 + 39 = 45. Counting 45 cards gives me the Four of Spades as my output card. I would write down 43 as my output number (4 + 39 = 43).
Talon is reversible, does not need an IV like Mirdek, and less error-prone than Pontifex. It greatly reduces the chance of a bias, by fast mixing the internal state through the discard piles with 4 cuts in total in 1 round. Unfortunately, according to Bruce Schneier, the chances of this cipher being secure and efficient are negligible.
I see about two new cipher designs from amateur cryptographers every week. The odds of any of these ciphers being secure are slim. The odds of any of them being both secure and efficient are negligible. The odds of any of them being worth actual money are virtually non-existent.
Currently, I do not have an implementation in Python or C. I also do not know the length of the internal PRNG. My testing shows it is sufficient for small messages, such as the length of a tweet, which is practical for field operation. My testing also shows that there is no internal bias in the system. One thing I did catch during my analysis, is that the sum of the discard piles follows the Poisson Distribution. I'm not sure how this will affect the security of Talon, if any.
Post a Comment