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

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

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:

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

(65, '0x41')

('A', 'A')

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:

'68656C6C6F'

'hello'

Let us now initialize AES with a randomly generated 16-byte key.

'43d5cfef250cdb31ea5676fea88a7bf1'

We can now start encrypting text.

'c48cf35883beee2e019235131dcc8e786e58270ab68247e3caab0ce001ac170f7ab550a059d21bdfedbdec2a5396ad561d31277b8db7af0ac652712b075eae64e5592016ef0ec7474fbc1d21a811df877c6fa435f9be036c324b2165465c026e'

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

"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:

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

'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:

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

'This one was encrypted with my implementation and decrypted by PyCrypto'

'The other way around'

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:

- Encrypt all card values using the shuffle key.
- Sort lexicographically the resulting ciphertexts.
- 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:

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

We sort these encrypted values to shuffle the deck.

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

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

(nice one!)

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:

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

Shuffle key:

'0ddc4f79a0a55b246ba04a7bdb45a9e4'

Elementary byte shuffle function:

And the main shuffling function:

Here are the top 5 cards:

[14439, 13402, 40454, 20779, 32054]

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

44788

Check:

12345