CoCalc Shared Files2 - Shuffling cards (prof) / Shuffling cards (prof).sagews
Author: Gabriel Chênevert
Views : 164

In this second lab, you'll get acquainted with AES and learn how to cryptographically shuffle a deck of cards.

Due date: Monday, October 6th, 8:25AM.

Write here the name of the collaborators (just in case):

## A) Using AES

We will use the implementation of AES provided by the PyCrypto library.

from Crypto.Cipher import AES


The message space used by this library (as is quite often the case) is the set of strings of valid 8-bit ASCII characters. In other terms, every character in such a string represents a byte. This explains the parameter lengths reported by the library:

AES.block_size, AES.key_size # in bytes

(16, (16, 24, 32))

The other widely used convention for the message space would be to write everything as hexadecimal integers; we can easily convert from one view to the other.

ord("A"), hex(ord("A"))

(65, '0x41')
chr(65), "\x41"

('A', 'A')

Just keep in mind that most 8-bit characters just won't display nicely...

"\xE9"

'\xe9'

To convert whole strings, a convenient way is the following:

import base64
base64.b16encode("hello")

'68656C6C6F'
base64.b16decode("68656C6C6F")

'hello'
Let us now initialize AES with a randomly generated 16-byte key.
k = os.urandom(16)
cipher = AES.new(k)

k.encode("hex")

'43d5cfef250cdb31ea5676fea88a7bf1'
We can now start encrypting text.
c = cipher.encrypt("Don't forget to respect the block length. A reversible padding scheme is needed in general.#####")
c.encode("hex")


Notice that the ciphertext really is just as long as the original message (96 byte-characters, which make up 6 full AES blocks).

cipher.decrypt(c)

"Don't forget to respect the block length. A reversible padding scheme is needed in general.#####"

A note on padding: the simple scheme used here (add as many # as needed) is not fully reversible (can you see why?). Some standard solutions are described here.

Notice what happens when blocks repeat:
cipher.encrypt("ECB is default. ECB is default. It's a shame!###").encode("hex")

'db69ddce909cf541fba898640fc5ef8cdb69ddce909cf541fba898640fc5ef8c33efa5346d700306c3f0e65734660933'

The first two 16-byte blocks are identical in the ciphertext (just like they are in the plaintext).

This breaks semantic security, since the attacker should not be allowed to know that the message has repeating blocks.

To do: Encrypt the same message using AES in randomized counter (CTR) mode "by hand" (i.e., don't use the PyCrypto API except to encrypt single blocks). Verify that Bob is able to decrypt the received ciphertext knowing only the shared secret key $k$.

A utility function that XORs two byte strings together.

The only difference between encryption and decryption in CTR mode is in the way the value of $\color{blue} c_0$ is obtained, so I chose to write a single function with a flag that specifies if encryption or decryption is to be performed.

def AES_CTR(k, input, decrypt=false):

import Crypto

cipher = Crypto.Cipher.AES.new(k)

blocks = [ input[i:i+16] for i in srange(0, len(input), 16) ]

if decrypt:
iv = blocks.pop(0)                                             # c0
output = ""
else:
iv = os.urandom(16)                                            # good random bytes
output = iv

ctr = ZZ(iv.encode("hex"), 16)                                     # numerical value of counter

for block in blocks:

ctr = (ctr + 1) % 2^128

hex_ctr = hex(ctr).upper()

if len(hex_ctr) < 32:                                          # zero padding to get a full block
hex_ctr = (32 - len(hex_ctr))*"0" + hex_ctr

output += xor(block, pad)

return output


m = "CTR is better.  CTR is better.  No padding needed!"
c = AES_CTR(k,m); c.encode("hex")

'1337b42b20ec47b9dd27944c8dffe556cc403fa9757f379d5fc376859edf461a76eee933986d019beba94ac4798efd482d7dc609d8fcc1aa93da7c36e44b7cb8d39a'

No recognizable pattern is present this time even though the plaintext has repeating blocks. Note the conveniently permissive attitude towards input strings whose length are not a multiple of the AES block length (we have effectively turned the block cipher into a stream cipher). We get the plaintext back by performing decryption:

AES_CTR(k, c, decrypt=true)  # ok

'CTR is better. CTR is better. No padding needed!'

A good way to verify our implementation of AES-CTR would be to test it against the PyCrypto implementation for compatibility. I personally don't like very much the flexibility it leaves to the developper of managing the counter themselves (a good opportunity to introduce a cryptographic weakness by reusing initial values), but here it is nonetheless, wrapped inside a similar-looking function.

def ref_AES_CTR(k, input, decrypt=false):

import Crypto.Cipher.AES, Crypto.Util.Counter

iv = input[:16] if decrypt else os.urandom(16)

ctr = Crypto.Util.Counter.new(128, initial_value=long(iv.encode("hex"), 16) + 1)

cipher = Crypto.Cipher.AES.new(k, Crypto.Cipher.AES.MODE_CTR, counter=ctr)

if decrypt:
return cipher.decrypt(input[16:])
else:
return iv + cipher.encrypt(input)

m = "This one was encrypted with my implementation and decrypted by PyCrypto"
c = AES_CTR(k, m)
ref_AES_CTR(k, c, decrypt=true)

'This one was encrypted with my implementation and decrypted by PyCrypto'
m = "The other way around"
c = ref_AES_CTR(k, m)
AES_CTR(k, c, decrypt=true)

'The other way around'

## B) Shuffling cards, pt. 1

Let's turn to a seemingly unrelated problem: that of a casino wanting to "impredictably" (from the point of view of the players) shuffle a deck of digital playing cards with a 128-bit shuffle key (probably generated from a master key using a CSPRNG). There are $52! \approx 2^{226}$ different ways to shuffle a deck of cards, so the whole description of a shuffle couldn't possibly fit in the shuffle key: it has to be securely derived from it.

The first, "easiest" way to do it would be to:

1. Encrypt all card values using the shuffle key.
2. Sort lexicographically the resulting ciphertexts.
3. Assign to every "plaincard" its position in the sorted "ciphercards" list.

Hence obtaining a shuffled list of the original cards.

To do: Do it! What is the first poker hand (first 5 cards) dealt from your shuffled card deck?

Here's a nice deck of 52 cards:

values = ['A'] + [ str(i) for i in [2..10] ] + ['J', 'Q', 'K']
suits  = ["hearts", "spades", "diamonds", "clubs"]
cards  = [ value + " of " + suit for value in values for suit in suits ]


We encrypt the card values (padded to a full block with spaces for easy removal) with some shuffle key:

k = os.urandom(16)
cipher = AES.new(k)
encrypted_cards = [ cipher.encrypt(card + (16 - len(card))*" ") for card in cards]


We sort these encrypted values to shuffle the deck.

encrypted_cards.sort()


Here's your hand under the given shuffle key $\color{blue} k$:

print "Shuffle no. %s" % k.encode("hex") + "\n"

[ cipher.decrypt(card).strip() for card in encrypted_cards[:5] ]

Shuffle no. a08a6824ab0177dde55d9075cdad006e ['A of hearts', 'A of spades', 'A of diamonds', 'A of clubs', '2 of hearts']

(nice one!)

## C) Shuffling cards, pt. 2

The above method works well, but rapidly becomes incovenient when the number of objects to permute gets large. Suppose for example that we want to shuffle not 52, but 52000 cards: with the above method, getting the top 5 would require 52000 single AES evaluations. A more efficient solution (look up "Format-preserving encryption" for more information) is the following:

1. Write every card value as a 2-byte word.
2. Given a card value $m$, apply to it 3 rounds of a Feistel network with inner function $f$, where $f(b) = \text{first byte of the AES encryption of byte } b \text{ padded with 15 } \#.$
3. Repeat step 2. until the resulting value falls in the $[0,51999]$ range; this is the value of the card at position $m$ after the permutation.

To do: What are the 5 first cards we get out of this 52000-card deck? How many AES evaluations did this take?

Here's a small function that gives to card value from its number:

def value(i):

return chr(i // 256) + chr(i % 256)


Shuffle key:

k = os.urandom(16)
k.encode("hex")
cipher = AES.new(k)

'0ddc4f79a0a55b246ba04a7bdb45a9e4'

Elementary byte shuffle function:

nb_calls = 0

def f(b):

global nb_calls
nb_calls += 1

return cipher.encrypt(b + 15*"#")[0]


And the main shuffling function:

def card_at_pos(m):

card = 52000

l, r = list(m)

while card > 51999:

for i in [1..3]:

l, r = r, xor(l, f(r))

card = 256*ord(l) + ord(r)

return card



Here are the top 5 cards:

[ card_at_pos(value(i)) for i in range(5) ]

[14439, 13402, 40454, 20779, 32054]
nb_calls  # number of needed AES encryptions

21

Are you able to tell where card no. 12345 lands in this shuffle? (You should! Using the fact that the Feistel network is easy to invert for somebody who knows the key...)

The inverse permutation (notice the similarity...)

def pos_of_card(c):

pos = 52000

l, r = list(c)

while pos > 51999:

for i in [1..3]:

l, r = xor(r, f(l)), l

pos = 256*ord(l) + ord(r)

return pos

p = pos_of_card(value(12345)); p

44788

Check:

card_at_pos(deck[p])  # ok

12345