2
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

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

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