Can a nested block cipher avoid the meet in the middle attack by using a secret initialization vector for the inner encryption?

Question

It seems to be believed that encrypting twice with a block cipher using an independent key each time is not as secure as you might expect because of the "meet in the middle" attack.

This is an attack with known plaintext. The theory is that the attacker encrypts the plaintext with every possible key, and decrypts the known cipher text with every possible key and then looks for a match between decrypted cipher text and encrypted plaintext. So brute force attacks takes only twice as long as for single encryption instead of $2^{\text{number of key bits}}$ times as long as you might expect.

However, as far as I can see, if the first encryption using $k_1$ used CBC with a truly random and secret IV, then no meet in the middle is possible because the attacker would have to encrypt for every key for every IV to find a match which for example in DES is harder than encrypting for every possible pair of keys. In my hypothetical system, the IV can be simply double encrypted and prepended to the start of the ciphertext for the benefit of the intended recipient. It must not be used for anything else and if the second encryption wants to use CBC then it should use a separate random IV.

This seems so obvious that it must have been thought before, so what understanding am I missing?

Answer 1

Eli Biham examined this, along with a long series of other "internal chaining" modes in the paper "Cryptanalysis of Multiple Modes of Operation" in AsiaCrypt 1994.

His conclusion was that there were ways of attacking such modes that were strictly easier than the standard "external chaining" mode that is now commonly used; his paper is the chief reason that we stick to what we do use.

For example, in the case that you have CBC mode (with secret IV, as you suggested), followed by an independently keyed ECB mode, one way to attack this is to do a chosen ciphertext attack; ask for the decryption of the message (A B B) (where A and B are distinct blocks); if the plaintext message is (P1 P2 P3), then it turns out that $D_{k2}(A) \oplus D_{k2}(B) = P2 \oplus P3$; this makes brute forcing $k2$ straightforward (and once that is recovered, $k1$ can then be brute forced).

Other modes (I believe CBC mode followed by CBC mode would be one example) don't have such easy tricks; for them, you need to find an internal collision and exploit it. One possible way to do it (for CBC mode followed by CBC mode) is as for the repeated decryptions of plaintexts of the form (A A A) (for various block-sizes values of A); if two different values A, B satisfy $A \oplus D_{k2}(A) = B \oplus D_{k2}(B)$, then the third word of the corresponding plaintexts will be the same. Hence, if we ask for $2^{32}$ (assuming DES) such plaintexts, we can scan the plaintexts for collisions in the third word; once we find such collisions, we can do a brute force search to verify that the collision was caused at the $k2$ level, and if so, recover $k2$.

Now, it may be that these attacks are of mostly theoretical interest; they are often chosen ciphertext attacks, and chosen ciphertext attacks can be thwarted by a simple Message Authentication Code. However, given that the standard modes don't have these theoretical weaknesses, people have found it safer just to stick with the now standard modes.