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

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?

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?

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.
² 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.