Is multiple encryption using a block cipher mode of operation that use only encryption processes vulnerable to Meet-in-the-middle attacks?

Question

Some block cipher modes of operation use only encryption processes, such as CFB, OFB and CTR.

If doing multiple encryptions using them, will these encipherment schemes be vulnerable to Meet-in-the-middle attacks?

I'm asking this because there is no decryption process in these modes, so I can't imagine a Meet-in-the-middle happening because an inverse process (decryption) is needed

Answer 1

Consider double encryption with the CTR mode;

The first layer outputs a stream $o$ of the encryption of the counter block per NIST definition of the CTR document.

$$o_i = \operatorname{AES-CTR}(k_1,counter_i)$$

The second layer outputs as stream $\bar o$

$$\bar o_i = \operatorname{AES-CTR}(k_2,counter_i)$$

This means $c_i = m_i \oplus o_i \oplus \bar o_i$ and assuming that we have known-plaintext than we have

$$v_i \oplus o_i = \bar o_i$$ where $v_i = c_i \oplus m_i$

Now, the meet-in-the-middle-attack executes as;

• First, make a table of encryption of the first counter with the first key candidates
• X-or each of the results with the message block $v_1$
• Now, male a table of encryption of the first counter with the first key candidates. You can copy the first table before x-oring with $v_1$
• Sort and match and test key candidates with additional known-plaintext-ciphertext pairs.

The above is the base of the attack, however, there will be dense possible keys. Instead one can form the tables containing 2 for AES-128 and 4 for AES-256 or more blocks so that the possible candidates will be much lower. This will increase the table size by 4 or 8 times.