Encryption mode with chained algorithms Suppose that I want to encrypt some data using two different algorithm chained (e.g. AES and Serpent) and harnessing the benefits of CBC.

I can do:

SERPENT_CBC( AES_CBC(plaintext) )


or

SERPENT_ECB( AES_CBC(plaintext) )


Of course the second solution is computationally slighter than the first one.
But can it be considered as safe as the first one?

Links to papers or books that discuss this topic are welcome.
Note: This is not (yet) a full answer, but I'm posting this anyway in the hope that I or someone else might be able to complete it later.  Please don't upvote this yet.  If you can fill in the gaps in the vague proof sketch below, please do so; if you post it as a separate answer, you'll have my vote.



It's pretty trivial to show that, if AES-CBC is secure and the keys are independent, then both of your schemes will also be secure.  Of course, that's not a very interesting result, so, to get something more interesting, we'll need to assume that AES-CBC is somehow not secure enough by itself.

Of course, we could hypothesize all kinds of attacks on AES or on your use of the CBC mode, but, to keep things simple, let's just assume that the security of the AES layer is completely lost because the attacker knows your AES key.  (This assumption also has the advantage that, besides being just about the worst-case scenario imaginable, it also seems a lot more plausible in practice than any hypothetical cryptanalytic attack on AES.)

CBC encryption using a secure block cipher normally provides IND-CPA security, assuming that the attacker cannot predict the IV and that the message length is fixed (i.e. not useful to the attacker).  It's easy enough to show that, assuming that Serpent is a secure block cipher, and that you implement CBC correctly, your first scheme is also at least as secure as Serpent-CBC alone, and thus also IND-CPA secure.

The remaining question then is:


  Assuming that the attacker knows the AES key (but not the Serpent key), and that both AES and Serpent are secure block ciphers, does the construction Serpent-ECB( AES-CBC( $m$ ) ) provide IND-CPA security?


Intuitively, provided that the CBC IV is chosen randomly, it seems that the answer might, in fact, be yes, although I have no proof of this yet.



In particular, we have the following lemma:


  Lemma: If no plaintext block is ever encrypted twice, ECB mode instantiated with a secure block cipher is IND-CPA secure.


(Proof omitted, but it's kind of intuitive: a secure block cipher looks like a random permutation, and two outputs of a random permutation are indistinguishable if you've never seen either of them before.)

So the question becomes whether an adversary who:


a) knows the key,
b) can choose the messages, but
c) does not know the IVs in advance


would be able to force the output of CBC encryption to contain the same block more than once with a non-negligible probability.

Of course, this might happen by chance, if the number of encrypted blocks gets close to the birthday bound, although it's not quite clear whether such random collisions actually provide any advantage to the attacker.  Still, even if they do, we may avoid this issue by assuming that the total number of blocks the adversary can ask to be encrypted is much less than $2^{64}$.

We can also show that, even if the attacker knows the CBC mode encryption key and can choose the plaintext to be encrypted, as long as the IV is uniformly randomly chosen and unknown to the attacker when they choose the message, each of the ciphertext blocks, considered individually, will also be uniformly random.

However, that's not quite enough to show that the attacker would not be able to introduce correlations between the ciphertext blocks, possibly causing them to repeat more often than expected.  Intuitively, that should not be possible, if the block cipher used is, in effect, randomly drawn from a secure pseudorandom permutation family, but I'm getting too tired to be able to show this right now.