Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
Is it actually quicker? I would have thought this almost entirely depends on your implementation, since in each case the final block cannot be calculated until the AES layer is finished. If you have an efficient implementation then I suspect they should be almost exactly the same speed. –  figlesquidge Mar 23 at 15:43
    
Also, what is your overall goal here? Whilst hopefully someone can provide a direct answer, I would have thought there was probably a better direct solution to your problem –  figlesquidge Mar 23 at 15:44
    
possible duplicate of Combining multiple symmetric encryption algorithms - implications? –  rath Mar 23 at 16:06
    
@figlesquidge CBC is a bit more complex than ECB. Using it twice will require to read and save in memory more past blocks, it will also implies some XORs more. In some circumstances this may be a problem. However I simply want to know if the CBC security can be considered "associative" (this is not the correct word), in the sense that you don't have to apply it to every cipher to achieve the same security level. –  Faust Mar 23 at 16:24
1  
True, but a few xors isn't a significant cost if you can interleave the two algorithms - certainly nothing compared to running AES/SERPENT on each block. –  figlesquidge Mar 23 at 16:27

1 Answer 1

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.

share|improve this answer
    
Nice, you cannot go much deeper without getting your feet really wet :P –  Maarten Bodewes - owlstead Apr 23 at 0:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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