What is the best attack here?
$E_k(m)=DES_{k1}(DES_{k2}(m)) \oplus k3$
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this communityWhat is the best attack here?
$E_k(m)=DES_{k1}(DES_{k2}(m)) \oplus k3$
I cannot think of how to attack this using exactly the same resources as the classic meet-in-the-middle attack against double-DES, but there is a way to solve it with similar computational and memory resources (i.e. with about $2^{57}$ time and memory), but using $2^{56}$ chosen plaintexts and $2^{56}$ (adaptive) chosen ciphertexts.
First, notice that if we ask for the encryption of $m$, xor the ciphertext with a known constant $T$, and then ask for the decryption of $E_k(m) \oplus T$, the following equality holds: $$E_k^{-1}(E_k(m) \oplus T) = DES_{k2}^{-1}(DES_{k1}^{-1}(DES_{k1}(DES_{k2}(m)) \oplus k3 \oplus T \oplus k3))$$ $$= DES_{k2}^{-1}(DES_{k1}^{-1}(DES_{k1}(DES_{k2}(m)) \oplus T))$$ So we don't have to worry about the third key, and now we only need to figure out how to conduct a MitM attack against that construction using four applications of DES and two keys. We are going to do this in an inside-out fashion.
Step one: pick any 64-bit value, $A$, and for all $2^{56}$ possible candidate values of $k2$ (which I will denote $k2^*$), do the following:
Store all $2^{56}$ values of $F$ in a hash table, along with the $k2^*$ candidate values associated with each.
Step two: For all $2^{56}$ possible candidate values of $k1$ (denoted $k1^*$), do the following:
Any such collision will 'suggest' that $k1 = k1^*$ and $k2 = k2^*$ (the stored $k2^*$ candidate value for $F$), a suggestion that can be easily tested in the following manner:
If you know $m$, $m'$, and $E_k(m)$ and $E_k(m')$, then compute $DES_{k1^*}(DES_{k2^*}(m)) \oplus DES_{k1^*}(DES_{k2^*}(m'))$ and check if that equals $E_k(m) \oplus E_k(m')$. If so, then you almost certainly have the right keys. From there, $k3$ is trivially deducible.