CoCalc Shared Files2 - Shuffling cards / Shuffling cards.sagews
Author: Gabriel Chênevert
%html
<p>In this second lab, you'll get acquainted with AES <i>and</i> learn how to cryptographically shuffle a deck of cards.</p>
<p>Due date: Monday, October 3rd, 8:25AM.</p>
<p><span style="color:red;">Write here the name of the collaborators</span> (just in case):</p>
<br><br>
<h2>A) Using AES</h2>
<p>We will use the implementation of AES provided by the <a href="https://www.dlitz.net/software/pycrypto/api/current/">PyCrypto</a> library.</p>


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

Due date: Monday, October 3rd, 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"))

chr(65), "\x41"


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

"\xE9"


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

import base64
base64.b16encode("hello")

base64.b16decode("68656C6C6F")

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

k.encode("hex")

'5402cc8d556bcdcd3d236f2aaf9aa4bd'
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")

cipher.decrypt(c)

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

%html
<p>This breaks semantic security, since the attacker should not be allowed to know that the message has repeating blocks.</p>
<p><b>To do</b>: Encrypt the same message using AES in randomized counter (CTR) mode "by hand" (<i>i.e.</i>, 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$.</p>


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$.



%html
<h2>B) Shuffling cards, pt. 1</h2>

<p>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.</p>

<p>The first, "easiest" way to do it would be to:</p>

<ol>
<li>Encrypt all card values using the shuffle key.</li>
<li>Sort lexicographically the resulting ciphertexts.</li>
<li>Assign to every "plaincard" its position in the sorted "ciphercards" list.</li>
</ol>
<p>Hence obtaining a shuffled list of the original cards.</p>

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


## 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?



%html
<h2>C) Shuffling cards, pt. 2</h2>

<p>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:</p>

<ol>
<li>Write every card value as a 2-byte word.</li>
<li>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 } \#.$$</li>
<li>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.
</ol>

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



## 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?




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...)