Suppose the key for round 0 in AES consists of 128 bits, each of which is 0.

1. Show that the key for the first round is $W(4)\text{,}W(5)\text{,}W(6)\text{,}W(7)$, where

   $$W(4)=W(5)=W(6)=W(7)=\left(\begin{array}{c}\hfill 01100010\hfill \\ \hfill 01100011\hfill \\ \hfill 01100011\hfill \\ \hfill 01100011\hfill \end{array}\right)\text{.}$$

2. Show that $W(8)=W(10)\ne W(9)=W(11)$ (Hint: This can be done without computing $W(8)$ explicitly).

Suppose the key for round 0 in AES consists of 128 bits, each of which is 1.

1. Show that the key for the first round is $W(4)\text{,}W(5)\text{,}W(6)\text{,}W(7)$, where

   $$\begin{array}{l}W(5)=W(7)=\left(\begin{array}{c}00010111\hfill \\ 00010110\hfill \\ 00010110\hfill \\ 00010110\hfill \end{array}\right)\text{,}\hfill \\ W(4)=W(6)=\left(\begin{array}{l}11101000\hfill \\ 11101001\hfill \\ 11101001\hfill \\ 11101001\hfill \end{array}\right)\text{.}\hfill \end{array}$$

   Note that $W(5)=\overline{W(4)}$ = the complement of $W(5)$ (the complement can be obtained by $XOR$ing with a string of all 1s).

2. Show that $W(10)=\overline{W(8)}$ and that $W(11)=\overline{W(9)}$ (Hints: $W(5)\oplus W(6)$ is a string of all 1s. Also, the relation $\bar{A}\oplus B=\overline{A\oplus B}$ might be useful.)

Let $f(x)$ be a function from binary strings (of a fixed length $N$) to binary strings. For the purposes of this problem, let’s say that $f(x)$ has the equal difference property if the following is satisfied: Whenever $x_1\text{,}{x}_2\text{,}{x}_3\text{,}{x}_4$ are binary strings of length $N$ that satisfy $x_1\oplus x_2=x_3\oplus x_4$, then

1. Show that if $\alpha \text{,}\beta \in GF(2^8)$ and $f(x)=\alpha x+\beta$ for all $x\in GF(2^8)$, then $f(x)$ has the equal difference property.

2. Show that the ShiftRows Transformation, the MixColumns Transformation, and the RoundKey Addition have the equal difference property.

1. Suppose we remove all SubBytes Transformation steps from the AES algorithm. Show that the resulting AES encryption would then have the equal difference property defined in Exercise 3.

2. Suppose we are in the situation of part (a), with all SubBytes Transformation steps removed. Let $x_1$ and $x_2$ be two 128-bit plaintext blocks and let $E(x_1)$ and $E(x_2)$ be their encryptions under this modified AES scheme. Show that $E(x_1)\oplus E(x_2)$ equals the result of encrypting $x_1\oplus x_2$ using only the ShiftRows and MixColumns Transformations (that is, both the RoundKey Addition and the SubBytes Transformation are missing). In particular, $E(x_1)\oplus E(x_2)$ is independent of the key.

3. Suppose we are in the situation of part (a), and Eve knows $x_1$ and $E(x_1)$ for some 128-bit string $x$. Describe how she can decrypt any message $E(x_2)$ (your solution should be much faster than using brute force or making a list of all encryptions). (Remark: This shows that the SubBytes transformation is needed to prevent the equal difference property. See also Exercise 5.)

Let $x_1=00000000$, $x_2=00000001$, $x_3=00000010$, $x_4=00000011$. Let $SB(x)$ denote the SubBytes Transformation of $x$. Show that

Conclude that the SubBytes Transformation is not an affine map (that is, a map of the form $\alpha x+\beta$) from $GF(2^8)$ to $GF(2^8)$. (Hint: See Exercise 3(a).)

Your friend builds a very powerful computer that uses brute force to find a 56-bit DES key in 1 hour, so you make an even better machine that can try $2^{56}$ AES keys in 1 second. How long will this machine take to try all $2^{128}$ AES keys?