# AES— Brute force attack versus Known plain text attack

I am taking a codes and cryptology course and the following is a questions on a past exam that I could not and still can't solve:

Suppose that E sub k denotes the function that encrypts a message M with AES,
where K is the 128-bit key. Suppose that a cryptographer discovers a function F
so that E sub k(M)=F sub k1(F sub k2(M)), where k1 and k2 are each 64-bits, and K
is easily computable from k1 and k2. Explain how one would use this to mount a known
plain text attack on AES that is faster than brute-forcing the 128-bit key.

If someone could provide a step by step explanation of how to do this, it would be greatly appreciate! Thanks in advance!

-
Please try using $\TeX$ as I have done for and shown to you (nicely writing a formula helps, at least me, in understanding what it conveys); and refrain from dumping homework (sometime basic) without a convincing indication that you tried to solve it. –  fgrieu Nov 1 '14 at 11:55

I believe this question is only answerable if $F_k$ is easily invertible. In other words, if you can compute $M=F^{-1}_k(F_k(M))$. Then a standard meet-in-the-middle attack applies.

Given message $M$, ciphertext $C = E_k(M)$ for unknown $k \in \{0,1\}^{128}$, an efficiently-computable function $X$ such that $k = X(k_1, k_2)$ for some $k_1, k_2 \in \{0,1\}^{64}$, and an invertible function $F$ such that $E_k(m) = F_{k_1}(F_{k_2}(M))$ when $k = X(k_1, k_2)$, do the following:

1. Let set $K_1 = \{F_{k_1}(M):k_1\in\{0,1\}^{64}\}$. Computing and storing this requires on the order of $2^{64}$ steps and $2^{64}$ memory.
2. Let set $K_2 = \{F^{-1}_{k_2}(C):k_2\in\{0,1\}^{64}\}$. Computing and storing this requires on the order of $2^{64}$ steps and $2^{64}$ memory.
3. Find for $k_1\in K_1$, $k_2 \in K_2$ s.t. $k_1 = k_2$. We know that some such pair must exist based on the definitions of the functions $F$ and $X$. A simple way to do this is to simply sort the sets $K_1$ and $K_2$ ($2 \times\left(2^{64} \times \log(2^{64})\right)$ operations) then you can use a linear algorithm to find a matching pair ($2 \times 2^{64}$ steps).
4. Compute $k = X(k_1, k_2)$.

If you add together the time complexities given, it is easy to see that this algorithm requires on the order of $2^{75}$ operations and on the order of $2^{65}$ memory.

-
how would I use this to mount a known plain text attack that is faster than just brute forcing the 128-bit key? –  Jok3r Oct 30 '14 at 20:20
This is a known-plaintext attack, and as demonstrated it is significantly faster than the $2^{128}$ steps (worst-case) it would take to brute force a 128-bit key. –  Stephen Touset Oct 30 '14 at 20:21
oh...guess I didn't get that from reading your answer. Thanks! –  Jok3r Oct 30 '14 at 20:23
To summaize, if you call $F$ "half-encrypt" and $F^{-1}$ "half-decrypt" and take some message for which you know the corresponding ciphertext, you half-encrypt that message with all possible $k_1$ and half-decrypt the ciphertext with all possible $k_2$. There will be some pair of outputs that are identical (e.g., you've "met in the middle"), and for that pair you know the $k_1$, $k_2$ that produced them. –  Stephen Touset Oct 30 '14 at 20:27