Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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!

share|improve this question
    
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 at 11:55

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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 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. –  Stephen Touset Oct 30 at 20:21
    
oh...guess I didn't get that from reading your answer. Thanks! –  Jok3r Oct 30 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 at 20:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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