# Advanced Block Cipher Attacks

How do I make a block cipher??
One very common way is to alternate Substitution, Permutation, and key mixing.
Recall that ALL the security of the cipher should be in the key; we should assume the attacker has full documentation and details of our cipher and the code we're using to run it.

Shannon defines 2 important properties to make this possible; *Confusion* and *Diffusion*.
Confusion; It's really hard to understand what the cipher is doing; if I write it out as a mathematical equation, it's far too complicated to actually solve.
Diffusion; If I change one bit in the key or the plaintext, *about half* of the bits in the ciphertext should change. This means that similar inputs create VERY different outputs.

## Substitution (S-Boxes)
A S-box performs substitution on the bytes of the input. This is intended to create *nonlinearity* in the encryption process. This helps us get confusion (and a little diffusion).

### Linearity

Linearity is complicated. We will simply define it as "predictability"; if I know a fact about $x_0$ and I can predict features of $f(x_0)$ then $f(x)$ is linear.

An S-box is very simple; just substitute the bytes in a plaintext.
Example;

Sbox = [36, 156, 149, 124, 58, 24, 203, 253, 167, 221, 113, 5, 208, 123, 162, 13, 189, 200, 121, 44, 77, 230, 91, 159, 133, 75, 154, 234, 225, 125, 179, 244, 45, 184, 93, 102, 186, 21, 8, 241, 85, 81, 129, 235, 147, 161, 28, 60, 119, 210, 104, 233, 251, 131, 216, 70, 15, 136, 196, 197, 83, 198, 157, 50, 219, 153, 169, 101, 41, 61, 245, 205, 242, 175, 59, 46, 137, 42, 140, 160, 97, 32, 240, 65, 174, 164, 132, 73, 11, 106, 120, 34, 12, 72, 178, 195, 181, 163, 229, 214, 108, 246, 139, 30, 18, 192, 92, 76, 126, 94, 238, 152, 155, 110, 202, 20, 47, 31, 19, 254, 26, 99, 117, 231, 248, 27, 80, 38, 187, 69, 103, 14, 199, 88, 0, 224, 191, 138, 43, 190, 130, 23, 33, 226, 183, 25, 51, 109, 239, 115, 188, 177, 105, 48, 16, 173, 17, 56, 148, 218, 10, 165, 222, 29, 194, 79, 63, 7, 3, 220, 82, 249, 87, 116, 170, 247, 144, 74, 90, 182, 71, 118, 237, 98, 54, 227, 68, 213, 176, 135, 86, 62, 143, 252, 185, 22, 243, 4, 255, 52, 35, 201, 95, 142, 217, 112, 151, 171, 67, 53, 122, 127, 96, 150, 64, 40, 215, 49, 180, 166, 114, 107, 6, 134, 1, 9, 39, 172, 2, 37, 57, 158, 209, 84, 232, 223, 236, 128, 89, 193, 204, 211, 66, 111, 250, 206, 141, 146, 168, 207, 212, 145, 78, 100, 228, 55]

def S(x):
    out = []
    for byte in x:
        out.append(Sbox[byte])
    return bytearray(out)

In this case we go byte by byte... (we don't have to).

## Permutation (P-Boxes)

Shuffle the input bits around. Thats it. Literally.
P-boxes introduce diffusion, because a change in one bit gets moved allllll around.

One simple example;

def P(x):
    # Shift x 7 bits to the right, then
    # take the top 7 bits and make them the bottom 7
    shifted = (x << 7) | (x >> (64 - 7))
    
    # Return the "rotated" version of x
    return shifted & ((1 << 64) - 1)

## Key Mixing

XOR the key into the plaintext.

x = x ^ key

## Rounds
Okay now lets define a Round function as

def r(x, k):
    # S box
    word = S(x)
    # P box
    word = P(word)
    # mix in the key
    return word ^ k

Okay.
Take a second to prove that this cipher,

ciphertext = r(plaintext, key)

is trivially breakable with *one* plaintext-ciphertext pair (hint;........... focus on recovering the key, and assume you know everything else except that).

This isn't so great, so cipher designers just *do it a lot*.

def encrypt(plaintext, key):
    for i in range(num_rounds):
        plaintext = r(plaintext, key)
    return plaintext

It's not *ideal* for the key to always be the same, so lets define a function called the key_schedule

def key_schedule(key, round_num)

that scrambles the master key into a key that will only be used for the current round, a "round key". Theres a lot of strong ways to do this so I'll just always assume the round keys are pretty much random.

Bringing this back in...

def encrypt(plaintext, key):
    for i in range(num_rounds):
        plaintext = r(plaintext, key_schedule(key, i))
    return plaintext

Decryption works almost the exact opposite. Take a moment to check your understanding by constructing a function that DECRYPTS a round; that reverses the action of the round function.

Okay. So now this seems really hard to break.
Take a moment to try...

Heres some really clever attacks that sometimes work reallllly well......

## Slider Attack
Let's attack this function first

def encrypt(plaintext, key):
    for i in range(num_rounds):
        plaintext = r(plaintext, key)
    return plaintext

This is (usually) fine.
In fact, repeating the round function even 2 or 3 times makes it a lot harder to get the key back. If `num_rounds = 100,000` or something, it's almost impossible.
But recall; in some cases, if `r(x, key)` is simple enough, we can just recover the key from an input-output pair.
So if we can find $(x, y)$ where $y = r(x,key)$, we can find the key.

...
okay...
but how do we do that?
We can just... guess......

If `plaintext` is `n` bits long, then there are $2^n$ possible plaintexts...

### The Birthday Paradox
The [Birthday Paradox](https://betterexplained.com/articles/understanding-the-birthday-paradox/) states that if I need some shared value to occur between 2 random values between 0 and $N$, then I need to generate $sqrt(N)$ values.

So back to the cipher
If I get you to encrypt $sqrt(2^n)$ random plaintexts to get plaintext-ciphertext pairs $p_i, c_i$, just by dumb chance, there will (likely) exist plaintext $p_s = r(p_t, k)$
where $p_s$ and $p_t$ are just two different plaintexts (we don't know which ones though!!!).
This is called a *slid pair*, because;

                p_s --> r() --> i_1 --> r() --> ... --> r() --> i_n --> r() --> c_s
p_t --> r() --> p_s --> r() --> ... --> r() --> i_n --> r() --> c_t

(I'm omitting the key for clarity because it's always the same).
See how the two different paths look "Slid" by 1 over?

Heres the trick;
We KNOW the round function is weak. So now if we look over all the pairs of plaintexts, we can assume each is a slid pair, find the key, then test it. If it's wrong, whatevs. If it isn't, we broke it!! We've found your key in $O(2^n)$ work and $O(sqrt(2^n))$ plaintext-ciphertext pairs.
Note;
For some pair of plaintexts, $p_2 = r(r(p_1,k), k)$ But recall that REPEATEDLY applying the round function makes key recovery HARD.

## Differential Cryptanalysis
The last example was a little contrived. Theres is usually a key schedule, and num_rounds is usually small (~<16).

The idea is that almost EVERYTHING about the cipher is LINEAR.
$r(x,k) \oplus 1 \approx r(x \oplus 1, k)$
$\oplus$ means xor; its just `^`
Take a moment to convince yourself that
$r(x,k) \oplus 1 = r(x \oplus 1, k)$ if we DON'T use an S box
Now the key idea is very powerful. By simple chance, if it's randomly generated, the S box often has biases.

Compute
$Sbox[x] \oplus Sbox[x \oplus \Delta_i] = \Delta_{out}$
for all $x$ and all $\Delta_i$ (so from 0 to 256 for the given S box). Put this into a table.

Lets say $Sbox[x] \oplus Sbox[x \oplus \Delta_i] = \Delta_{out}$ for a certain $\Delta_i$ and
$\Delta_{out}$ with a probability $P = 1/2$. That means that $r(x,k) \oplus \Delta_o = r(x \oplus \Delta_i, k)$ or equivalently

IMPORTANTLY;

$\Delta_o = r(x \oplus \Delta_i, k) \oplus r(x,k)$
B/c the Pbox, $\Delta_o$ might not be exactly $\Delta_{out}$, but it'll be a jumbled version of it.

This is called a differential characteristic.

Now we know that half of the time, $\Delta_o = r(x \oplus \Delta_i, k) \oplus r(x,k)$. But because we build that table all that time ago, we calculated $Sbox[x] \oplus Sbox[x \oplus \Delta_i] = \Delta_{out}$ for all possible inputs. So we know what $x$ could possibly be for an input of $\Delta_i$ to create a difference of $\Delta_{out}$. Knowing what the input and output to the round function are, we can repeat this many times, and eventually converge on only one possible key.
Little vague? Maybe... Let's see it a little bit more concretely;
Lets ASSUME that

def r(x, k):
    # S box
    word = S(x)
    # No P box to make this clear :D
    # 
    # mix in the key
    return word ^ k

def encrypt(plaintext, key):
    for i in range(2):
        plaintext = r(plaintext, key_schedule(i, key))
    return plaintext

Let's also assume that $Sbox[x] \oplus Sbox[x \oplus 1] = 1$ 1/2 of the time, when $0<=x<=128$

So lets say I'm only encrypting 1 byte at a time.
The encryption function is $k_2 \oplus S[k_1 \oplus S[x]]$ where $k_2, k_1$ are round keys.
For now, they're one byte.
So we put in a 0 and (lets say) it encrypts to 127. Then we put in 1 and it encrypts to 126. Assuming that the differential characteristic held true, we know that $0 <= S[0] \oplus k_1 <= 128$. Given we know $S[0]$, we have a constraint on $k_1$.
By inserting another guess, we could further constrain the $k_1$ value...
Once we have enough constraints, BRUTEFORCE!!!

Final details;
Sometimes, the differentials aren't so easy. You might need to chain different differential characteristics together to get a solve; i.e.
We put in $\Delta_1$, then after round one, we have $\Delta_5$, etc etc... and the ciphertext differential is $\Delta_{40}$
$\Delta_1 => \Delta_5 => \Delta_{99} => \Delta_{40}$