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!

  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Nov 1, 2014 at 11:55

1 Answer 1


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.