Design and implementation by Matthew McKague. Original document at https://uwspace.uwaterloo.ca/bitstream/handle/10012/1141/memckagu2005.pdf

Card-Chameleon was written as part of a Masters of Mathematics Thesis at the University of Waterloo by Matthew McKague, and under the direction of Alfred Menezes. In his paper, Matthew examines the security of design aspects of RC4, then presents a new cipher called “Chameleon”. Learning from both Chameleon and RC4, another new cipher is introduced called RC4B, with the goal of greater security than RC4. After defining Chameleon and RC4B, both ciphers are implemented as playing card ciphers. Chameleon is discussed here under the name Card-Chameleon.

On a personal note, this cipher is one of my favorite playing card ciphers, for a few reasons. First is the fact that you do not need a table to execute the cipher. Just like Solitaire, the cipher can be executed entirely in hand. Unlike Solitaire, however, no modulus mathematics is needed to derive the ciphertext when encrypting, or deriving the plaintext when decrypting. The algorithm decides exactly what the ciphertext and plaintext characters will be without any math. This greatly minimizes the need to keep notes, which could fall into the wrong hands, while executing the cipher. Second, the design is clean and elegant. It is not as error-prone as some of the other playing card ciphers, and it can be executed quite quickly. On average, I can sustain about 4 plaintext characters per minute, and after getting the look-up table memorized, 5 plaintext characters per minute is doable. At that pace, a message the length of a tweet would only take about 30 minutes.

In this cipher, the jokers are optional. If you wish to encrypt the spaces in the plaintext, then the jokers will be defined as the space in this procedure. However, you will need to identify one joker as red and the other as black. Some decks come with one colored joker and one black-and-white joker. In other decks, you will need to define which is which. Also, should the Secret Police suspect that you are using playing cards to encrypt and decrypt secret messages, you will need a good story why you are carrying a deck with jokers. Be familiar with games, such as Euchre, that take advantage of the jokers.

This algorithm requires an initialization vector (IV) to be prepended to the plaintext before the encryption process begins. This will extend the length of the plaintext by 26 or 27 characters, depending fully on whether or not you decide to include the jokers in the algorithm. On this page, we will not use the jokers.

As mentioned, the Card-Chameleon cipher requires an IV as part of encrypting the plaintext. This needs to be accomplished before setting up the deck. Using the table assignment below, and a random shuffling of the deck for each round, I came up with the following IV as an example:

XMCARIUQXCFPJZOVJWIYZJHCJV

This IV is prepended to the plaintext before beginning the encryption algorithm.

Card-Chameleon uses the following assignments, which assigns an English character to exactly two cards in the deck, one black and one red:

As such, both the Seven of Hearts and the Seven of Spades are assigned the English character “G”, and the English character “X” is assigned both to the Jack of Diamonds and the Jack of Clubs.

Part of field agent paraphernalia are “code books”. These books typically assign numbers to letters, as well as phrases to numerical strings. As such, the Card-Chameleon table can have the table assignments shuffled, and then printed into a code book version that the field agent can use as a look-up table. For teaching this cipher, our table will remain as printed.

Please see Card-Chameleon Deck Keying which outlines a Chard-Chameleon specific algorithm for keying the deck.

To setup the deck, the sender and recipient must agree on a deck order. Once the deck order is determined, we need to permute the deck slightly, so that it strictly alternates between red and black suits. The algorithm for setting up the deck is as follows:

• Deal two face up piles- Take the deck face up in your hand, and deal out two piles, placing each red card on one pile and each black card on the other. Be sure to preserve the order card-for-card exactly, and do not place down groups of colors together.
• Combine the two piles- After the two face up piles have been built, create a single combined interleaved pile, by taking the black card off the top black pile, then the red top card off the top red pile. Continue strictly alternating black and red cards until the two piles are exhausted and you have a single pile of strictly alternating red and black cards, with a red card on top, and a black card on bottom.

Card-Chameleon uses two different algorithms for encryption and decryption. Although the algorithms are very similar, they differ subtly enough, that they need to be described separately.

Further, the algorithm for keying the deck with the IV behaves slightly differently than encrypting the plaintext, or decrypting the ciphertext. Because the IV is exactly 26 characters (or 27 the jokers are used), you can easily mark on your sheet when you need to change the algorithm. The steps below assumed that you have already created the IV.

In the IV and encryption algorithms, you will be identifying the black cards, and working from that as a pivot point. For decryption, you will be identifying the red cards, and working from that as your pivot point. I have emphasized this in the steps for clarity.

Here as a YouTube video demonstrating the Card-Chameleon algorithm.

For each letter of the IV, execute the following steps shuffling the deck deterministically. You will not be writing down any values while working the IV.

• Using the table assignment above, locate the black card in the key deck corresponding to the IV letter.
• Identify the red card immediately above this black card. Interpret this card as letter 't'.
• Using the table assignment above, locate the black card for letter 't'.
• Exchange the red card immediately above this black card with the top card (also red).
• Move the black card for letter 't' and the next red card immediately above this black card (red) to the bottom of the deck.
• Move the top two cards on the deck (one red and one black) to the bottom of the deck.

The deck is now prepared for encrypting the plaintext, or decrypting the ciphertext.

Before proceeding with encrypting the plaintext, make sure that you have generated a 26 character (or 27 if using the jokers) IV, and have keyed the deck based on this IV.

For each letter of the plaintext, execute the following steps to determine the ciphertext character:

• Using the table assignment above, locate the black card in the key deck corresponding to the plaintext letter.
• Identify the red card immediately above this black card. Interpret this as letter 't'.
• Using the table assignment above, locate the black card for letter 't'.
• Identify the red card immediately above this black card. Interpret this an your ciphertext letter, and write it down.
• Exchange this ciphertext red card with the top card (also red).
• Move the top two cards of the deck (one red and one black) to the bottom of the deck.

Send the IV and the ciphertext together as the completed message to the recipient, with the IV as the first 26 characters (or 27 if using the jokers) of the completed message.

Before proceeding with encrypting the plaintext, make sure that you have generated a 26 character (or 27 if using the jokers) IV, and have keyed the deck based on this IV.

For each letter of the ciphertext, execute the following steps to determine the plaintext character:

• Using the table assignment above, locate the red card in the key deck corresponding to the plaintext letter.
• Identify the black card immediately beneath this red card. Interpret this as letter 't'.
• Using the table assignment above, locate the red card for letter 't'.
• Identify the black card immediately beneath this red card. Interpret this an your plaintext letter, and write it down.
• Exchange the red card corresponding to the ciphertext character with the top card (also red).
• Move the top two cards of the deck (one red and one black) to the bottom of the deck.

Discard the IV as the first 26 characters (or 27 if using the jokers). The rest of the message is the intended plaintext.

Although the algorithm seems a bit picky, it is actually pretty straight forward once you practice, and can be executed quickly with little concern of making a mistake. Further, no math is needed to determine the plaintext or ciphertext characters.

However, you do need to take care that you are executing all the steps. It can be easy to look for the first character, without needing to find the second, and permute the deck. I have done this a couple times in practice, and as a result, my decrypted ciphertext was unreadable.

As with most card ciphers listed here, this algorithm is new and untested. So, you should use it at your own risk. However, because Card-Chameleon is loosely based on RC4, some assumptions can be made about its security currently, even if new attacks have not yet been discovered.

Card-Chameleon uses a pair of 26 (or 27) cards in hand. Thus, the possible keys with Card-Chameleon is (26!)^2 or about 176-bits of entropy. This brings the key space well out of reach for brute force attacks with modern hardware. Further, the use of an initialization vector limits the effectiveness of attacks on Card-Chameleon. Using the English alphabetic characters only, there are a total of 26^26 possible initialization vectors, or about 155-bits of entropy. In order to launch an attack on the initial state, 25 collisions on one IV are required.

Further, the IV does not induce a publicly known permutation on the state in Card-Chameleon. The IV does induce a permutation, however, but this permutation is dependent on the ordering of the black cards. Since this ordering is private, the induced cycle cannot be determined without guessing the ordering. As such, the best known attack is the “branch and bound attack” on Card-Chameleon. This has an order of O(n!). For Card-Chameleon, this is 2^155, which is more than enough to be considered secure.

Knudsen's attack against RC4 applies to Card-Chameleon, although the complexity of the attack scales to O(n!) with RC4, that this card cipher was loosely designed against, rather than O(sqrt(n!)). This means it is possible to use Card-Chameleon securely for smaller 'n' than is possible for RC4. Card-Chameleon achieves this with n=26 (or n-27 if the jokers are used).

Kevin Spinar, as “<Alipha>” in ##crypto on Freenode, noticed that you can recover the deck order with a complexity of 96-bits. This is a serious reduction from the claimed protection of 176-bits. This is done via a chosen plaintext attack of 26 “A”s. He describes it below:

So, what I'm doing is running the 26-letter passphrase (I'm not doing padding
to the next 5 letters, nor using IVs) through the Card Chameleon algorithm with
a random deck for each encryption (so 48 random decks for the 48 trials below).
 
Because of how Card Chameleon works--the ciphertext letter corresponds to the
red card which gets swapped with the top card of the deck--I know what red card
is on the top of the deck. (Which then gets moved to the bottom.) So for each
subsequent ciphertext, I can slowly build an ordering of the red cards as they
get moved to the top of the deck. 
 
So then after 26 letters, ideally, every red card has been moved to the top of
the deck. Except that not every card gets moved to the top and sometimes a card
gets swapped out from the position that was already recorded. And so, after 26
letters, you can recover only a "mostly" accurate ordering of the red cards.
 
I did some trials with some different plaintexts and recorded what card
positions I was able to correctly guess after the 26-letter plaintext was
encrypted. A dot means the guess is correct and an X means it's incorrect.
The cards are ordered top-to-bottom. So the leftmost . or X is the top red card.
 
You'll notice that the bottommost cards are more-likely to be correct than the
topmost cards. This is because the cards near the bottom of the deck were most-
recently at the top of the deck and so there is less chance that the card was
swapped out of the order we determined. We will always know the bottommost red
card.

AAAAAAAAAAAAAAAAAAAAAAAAAA .............X............ 25/26 red cards correct
ThisissometestIdonotknowit X.....XXXXX..X...XX....... 17/26 red cards correct
Applesbananascarrotsdonuts .X..X.....XX.XXX....X..... 18/26 red cards correct
AnotherphraseIhavenoideahm XXXX.XX.X....X.....X....X. 16/26 red cards correct
abcdefghijklmnopqrstuvwxyz XXXXXX.X.......X.....X.... 17/26 red cards correct
thequickbrownfoxjumpsoverz .X...X.XXX.XX.XXX......... 16/26 red cards correct
zyxwvutsrqponmlkjihgfedcba XXXX..XX.XX..X............ 17/26 red cards correct
attackatdawnattackatdawnaa ....X...X.X.X...X....X.... 20/26 red cards correct
 
AAAAAAAAAAAAAAAAAAAAAAAAAA .............X...X........ 24/26 red cards correct
ThisissometestIdonotknowit X..XXX.X.X.X.XX........... 17/26 red cards correct
Applesbananascarrotsdonuts XX.X.XX.XX...X..X......... 17/26 red cards correct
AnotherphraseIhavenoideahm XXXXXXXXX......X.X........ 15/26 red cards correct
abcdefghijklmnopqrstuvwxyz XX.XXX..X.XXX..X.....X.... 15/26 red cards correct
thequickbrownfoxjumpsoverz ...XXXX...XX.XXX.....X.... 16/26 red cards correct
zyxwvutsrqponmlkjihgfedcba .XXX.X.X.XXXX...X......... 16/26 red cards correct
attackatdawnattackatdawnaa X....XXXXX.XX.X........... 17/26 red cards correct
 
AAAAAAAAAAAAAAAAAAAAAAAAAA ..................X....... 25/26 red cards correct
ThisissometestIdonotknowit ...X..X....XX..........X.. 21/26 red cards correct
Applesbananascarrotsdonuts .X......XXX.X......XX..... 19/26 red cards correct
AnotherphraseIhavenoideahm XXX..XX.X..X.XX.....X..... 16/26 red cards correct
abcdefghijklmnopqrstuvwxyz XX.X.XXX.X....XX.X..X..... 15/26 red cards correct
thequickbrownfoxjumpsoverz XXX.XX..XX.....X.X...X.... 16/26 red cards correct
zyxwvutsrqponmlkjihgfedcba .XXX.XXX.XXX....X..X...... 15/26 red cards correct
attackatdawnattackatdawnaa XX..XXX...X...X.X......... 18/26 red cards correct
 
AAAAAAAAAAAAAAAAAAAAAAAAAA ...........X........X..... 24/26 red cards correct
ThisissometestIdonotknowit X..XXX....X.....X.......X. 19/26 red cards correct
Applesbananascarrotsdonuts XXX..XXX...X...XX.XXX..... 14/26 red cards correct
AnotherphraseIhavenoideahm ..XX.XXXX..X.....XX....... 17/26 red cards correct
abcdefghijklmnopqrstuvwxyz ..XXX.X.XXX..X.X.......... 17/26 red cards correct
thequickbrownfoxjumpsoverz XXX.XX.X..X.XX............ 17/26 red cards correct
zyxwvutsrqponmlkjihgfedcba .X.XXX..X.XX....X..X...... 17/26 red cards correct
attackatdawnattackatdawnaa ..X.X......X.X.X....X..... 20/26 red cards correct
 
AAAAAAAAAAAAAAAAAAAAAAAAAA ..X..................X.... 24/26 red cards correct
ThisissometestIdonotknowit .X...XX.XXXX....X.X....... 17/26 red cards correct
Applesbananascarrotsdonuts ...X..XXX..XXX............ 19/26 red cards correct
AnotherphraseIhavenoideahm XXX.XX..X....X............ 19/26 red cards correct
abcdefghijklmnopqrstuvwxyz XXXX..X.X.X.X.XX.......X.. 15/26 red cards correct
thequickbrownfoxjumpsoverz X.X.XXXXXXX.X............. 16/26 red cards correct
zyxwvutsrqponmlkjihgfedcba .XXXXXX.X...XX.X...X...... 15/26 red cards correct
attackatdawnattackatdawnaa .XX.XX.....XXX.X.......... 18/26 red cards correct
 
AAAAAAAAAAAAAAAAAAAAAAAAAA ...................X..X... 24/26 red cards correct
ThisissometestIdonotknowit .X.XX....XXX...X....XX.... 17/26 red cards correct
Applesbananascarrotsdonuts .XX.X..X....X..X..X.X...X. 17/26 red cards correct
AnotherphraseIhavenoideahm XXXXX.....XX..X...X...X... 16/26 red cards correct
abcdefghijklmnopqrstuvwxyz XX.XXXXX.XX...X.X..X...... 14/26 red cards correct
thequickbrownfoxjumpsoverz XX.XXX.XXX..X...X...XX.... 14/26 red cards correct
zyxwvutsrqponmlkjihgfedcba XX..X.X..XXX.XXX.X........ 15/26 red cards correct
attackatdawnattackatdawnaa X..X.XXX.X........X.X..... 18/26 red cards correct

The code for the above tests can be found at https://github.com/alipha/CardCrypto/blob/master/CardCrypto/Test.cs

His suggestion to improve the security of the cipher would be to swap the red card above the plaintext black card with the top red card, rather than swapping the second red card.

Ciphertexts are published here at Card-Chameleon Ciphertexts. Analysis to follow.

Because no mathematics are involved with the operation of encrypting and decrypting text, this makes Card-Chameleon a pleasurable cipher to operate. The only operations required are merely finding and moving cards, which make the algorithm less error-prone than other card ciphers, and quick to operate. This is what makes it my favorite card cipher to operate, among my list.