Cryptography
aes meet-in-the-middle-attack
Updated Thu, 14 Jul 2022 15:19:18 GMT

AES-- Brute force attack versus Known plain text attack


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

Suppose that $E_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_k(M) = F_{k_1}(F_{k_2}(M))$, where $k_1$ and $k_2$ are each 64-bits, and $K$ is easily computable from $k_1$ and $k_2$.

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!



Solution

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.

Comments (4)

  • +0 – how would I use this to mount a known plain text attack that is faster than just brute forcing the 128-bit key? — Oct 30, 2014 at 20:20  
  • +2 – 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. — Oct 30, 2014 at 20:21  
  • +0 – oh...guess I didn't get that from reading your answer. Thanks! — Oct 30, 2014 at 20:23  
  • +0 – 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. — Oct 30, 2014 at 20:27  

References