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

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?

-
The IV is meant to be public. –  Thomas Dec 25 '12 at 0:32
After further thought inspired by @Thomas, the IV can be "public" in the sense of not being encrypted under the first encryption, but encrypted only with key2 during the second encryption. This second encryption would mean that the pt (in the sense of the actual input to the block cipher) for encryption 1 was unknown to the attacker and the brute force attack on encryption 1 would have to encrypt under every possible key1 using a candidate IV decrypted using every possible key2.That seems to defeat the attack. –  David Stein Dec 27 '12 at 11:45

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