Number of cryptographic operations required to perform a MitM for 4DES

Question

Suppose DES is applied 4 times with 4 different 56-bit keys ($k_1$ to $k_4$). By using meet-in-the-middle attack, what is the number of cryptographic operations required for known-plaintext attack?

The given answer:

For each pair of $k_1$ and $k_2$, we need 2 encryptions and 2 decryptions. There is a total of $2^{112}$ pairs. So the total required is $2^{114}$ cryptographic operations.

I don't understand why there are 4 operations for each pair of keys. I thought each half of the attack requires ($2^{56*2} = 2^{112}$) operations so the total number should be only ($2^{112} * 2 = 2^{113}$) operations. What am I getting wrong here?

Answer 1

In MitM for 2DES, in a tabulation phase we compute and keep $2^{56}$ 64-bit values and their associated key, then in a search phase we compute up to $2^{56}$ 64-bit values and search these in the table. There's a hit about once in $2^{64-56}=2^8=256$ searches, that is about $2^{56-8}=2^{48}$ hits, and all except one are false hits. We need to eliminate false hits with a few extra DES operations: typically two, testing an extra plaintext/ciphertext pair². Further, a fraction of the 64-bit values have been obtained $k>1$ times in the first phase, and when we hit one of these in the search¹, the number of DES operations required to eliminate the false hit is $1+k$. All these details increase the number of DES operations by less than 1% from the base $2^{57}$ (for full search, or $3\times2^{55}$ on average), and some expositions neglect that detail³.

But if we implemented MitM for 4DES by precomputing $2^{112}$ 64-bit values, each 64-bit value would be obtained an average of $2^{112-64}=2^{48}$ times, thus in the search phase we'd be swamped in false hits: rather than rare (once in 256 searches) that would be the norm, and eliminating a false hit would need an average of $1+2^{48}$ extra DES. This is an unreasonable amount of extra work.

A simple line of though to attack 4DES is to attack using normal MitM the block cipher 2BIG, where BIG is a block cipher with double the key size and block size of normal DES (that is 112-bit key and 128-bit block size) obtained by applying 2DES with the 112-bit key on each 64-bit half of a 128-bit block, requiring two DES operations. MitM will theoretically³ break 2BIG in about $2^{113}$ evaluations of BIG (for full search), thus about $2^{114}$ evaluations of DES.

---

¹ Assuming we kept all the corresponding keys in the tabulation phase, which is required if we want to be sure the find a solution.

² When we get a confirmation with that second plaintext/ciphertext pair, most often we have hit the right pair of 56-bit key halves. But probability of the contrary remains about $2^{-16}$, so we want an extra check using a third plaintext/ciphertext pair, at a cost 2 DES operations.

³ There's an elephant in the room: even against 2DES, much more against 4DES, basic MiTM requires so much RAM and RAM accesses that the cost of DES operations is comparably negligible.