Order of cascaded ciphers

Question

Does the order of a block cipher cascade (e.g. in TrueCrypt) make a difference to the security provided, assuming independant keys?

For example:

Plaintext -> Rijndael -> Serpent -> 3DES -> Ciphertext
Plaintext -> 3DES -> Serpent -> Rijndael -> Ciphertext

The same ciphers, just ordered differently.

My intuition says no, and that the security will be at least that of the strongest cipher, but I can think of a few situations (e.g. timing attacks) where this might make a difference. I can't think of a concrete case where you could exploit this ordering, though.

Answer 1

Yes, order of ciphers would matter in some practical scenarios, in particular if an adversary can subject the implementation to a DPA attack.

Consider the scenario where the same plaintext is encrypted several times using the same key, using some chaining mode other than ECB, a random IV, and the cipher in contact with the plaintext (on either the encrypting or decrypting side) is vulnerable to DPA. The known random IV allows recovering that cipher's key using standard DPA, and then a slight variant of DPA allows recovering the plaintext in all the subsequent blocks. It does not matter how the various ciphers are keyed, the plaintext can be short, but the key (of the attacked cipher) must be reused in many sessions.

Contrast that with the case where the cipher in contact with the plaintext is DPA-protected. Perhaps the others (in particular, the one in contact with the ciphertext, which is most exposed) can be broken, but (since the keys are independent), protection of the confidentiality of the plaintext remains at least as good a that of the cipher in contact with the plaintext.

---

Conclusion: if you must cascade block ciphers using truly independent keys for some reason (I can imagine an order from high-up, e.g. regulatory), and DPA is an issue, you want to put the one you are most confident with in contact with the plaintext. However if the ciphers share their key, that's the other way around: you likely want to put the most trusted one at the most exposed place, which is in contact with the ciphertext.

Update following Hunter's question: A situation where ciphers share their key would be a cascade of 3DES-CBC with 192-bit key (168 used), followed by AES-192, using the same 192-bit key for the two ciphers (a very poor choice when DPA attacks matter). Truly independent keys are chosen independently and randomly. Derivation from a single master key using a strong KDF is also fine if performed out of the reach of an attacker, assuming in particular no side-channel attack such as DPA can be mounted on the KDF.

Note: if the first encryption scheme in a cascade leaks information about the plaintext through the length of the ciphertext (e.g. has a built-in compression scheme), then the cascade might not be secure (as pointed in this comment to a related question). That does not apply in the context of the question, though.

Answer 2

(This is not really an answer, but some formalistic remarks, which got too large for a comment.)

$\def\TDES{\operatorname{3DES}}\def\ECB{\operatorname{ECB}}\def\AES{\operatorname{AES}}\def\Serp{\operatorname{Serp}}\def\CTR{\operatorname{CTR}}$ First, to combine block ciphers (i.e. form a new block cipher from the individual ones), the components block ciphers need to have a common block size - and 3DES has a block size of 64 instead of 128 for the other ones. So we would first have to somehow build a 128-bit block cipher from the 64-bit one, for example using something like 2-block-ECB mode (I'll name this $\TDES'$ in the following).

Now of course $\AES \circ \Serp \circ \TDES'$ is a different block cipher than $\TDES' \circ \AES \circ \Serp$ etc., and the question would be if some of them are harder or easier to break (as a block cipher, used within any mode, or in the standard models.)

On the other hand, if we don't combine the block-cipher block-wise, but together with their mode of operation, it will also depend on the mode of operation.

For modes like CTR and OFB, which actually produce a key stream, which will then be XOR-ed with the data, the answer to your question is:

The order doesn't matter at all, as all variants give the same ciphertext (due to the commutativity and associativity of XOR):

$$ \begin{align*} &\quad \CTR[\AES]\circ \CTR[\TDES]\circ \CTR[\Serp] \\&= \CTR[\Serp] \circ \CTR[\AES]\circ \CTR[\TDES] \\ & = \CTR[\TDES] \circ \CTR[\Serp] \circ \CTR[\AES]\end{align*} $$ (or all other combinations, assuming you are using the same key, mode and initialization vector for the same cipher in each case.) The same is valid for OFB and even mixed uses, as well as for stream ciphers like RC4.

For ECB-mode, we have $$\begin{align*} \ECB[\AES\circ\Serp \circ \TDES'] &= \ECB[\AES]\circ\ECB[\Serp] \circ \ECB[\TDES'] \\ &= \ECB[\AES]\circ\ECB[\Serp] \circ \ECB[\TDES], \end{align*}$$ (and similar for the other combinations), but you shouldn't use ECB mode anyways.

For CBC and CFB, it gets complicated, though.

Answer 3

It matters in the case where one of the ciphers is weaker more than the other two.

Let us suppose that for some reason there was an attack on 3DES took $O(2^{40})$ but would guarantee you the plaintext value for a ciphertext. Assume further that there is an attack that reduces Rijndael/AES and Serpent's key space to $2^{56}$. Further, for simplicity, suppose that we have only two possible messages $m_1$ and $m_2$

If 3DES is the outer most encryption layer(i.e. Rijndael -> Serpent -> 3DES) then we first decrypt the final ciphertext using the attack . This leaves us with the double encryption of $C_{remaining}=Serpent(AES(M_?,k_1),k_2)$. A meet in the middle attack allows us to open that at a cost of $O(2^{57})$ using $O(2^{56})$ space. This is done by computing the AES encryptions of $m_1$ under all of it's $2^{56}$ possible keys and the serpent decryption of $c_{remaining}$ under all it's $2^{56}$ possible keys, recording the results, and then checking if there is a matching intermediate value.

On the other hand, if we were attacking Rijndael -> 3DES -> Serpent, then the meet in the middle attack does not work nearly as efficiently. The result of brute forcing from both ends won't line up even when we find the correct key because on one side we have a "plaintext" input to 3DES and on the other we have a 3DES cipher-text. To check if they match, we need to decrypt that ciphertext at cost of $O(2^{40})$. We must do this for each of the $2^{56}$ intermediate values. So instead of decrypting at a cost of $O(2^{57} + 2^{40}) = O(2^{57})$ we need $O(2^{57}*2^{40}) = O(2^{97})$

Of course, this works even if the other two ciphers are at full strength, but in that case the attack isn't practical. On the other hand, 10 years ago one could actually brute force DES's $2^{56}$ bit key space in a couple of days with custom hardware. It is also impractical if the attack against the week cipher( in this case 3DES) requires you to guess and check many possible values.