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.

-
@EthanHeilman: The question says "independant keys". –  Paŭlo Ebermann May 22 '12 at 21:04
Are you cascading the block ciphers (i.e. build a new block cipher from the combination of them), using the combination in some mode of operation, or are you cascading the ciphers together with a mode of operation for each? –  Paŭlo Ebermann May 22 '12 at 21:08
Thanks, somehow I missed that. –  Ethan Heilman May 22 '12 at 21:09
@PaŭloEbermann This is purely theoretical, so I'd be interested in the security implications of both. –  Polynomial May 23 '12 at 5:50

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.

-
Interesting. Assuming DPA is a risk, are there any analyses of common implementations of popular block ciphers in various modes? Also, is there any published analysis of DPA attacks on CPU-specific cryptographic extensions, such as Intel's AES instructions? I've only scan-read the paper you linked (I'll take a proper look later) so I my apologies if these questions are answered in it. –  Polynomial Jul 11 '12 at 20:14
DPA (and variants e.g. DEMA) is a major risk in embedded systems, Smart Cards, HSMs, FPGAs; less in standard CPUs, where software side-channel attacks are to fear (timing dependencies due to cache misses..) and the full hardware control required for DPA allows easier attacks. DPA and countermeasures (masking..) are well studied in the context of block ciphers. A typical 1 dollar Smart Card has DPA-protected DES in hardware. Operating modes do not matters much. Articles abound, see references of this one –  fgrieu Jul 11 '12 at 22:35
@fgrieu - would you mind clarifying "truly independent keys" as opposed to ciphers that "share their key"? How would you classify two "statistically independent" keys derived from a KDF with the same input? –  hunter Oct 18 '13 at 14:45

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

-
TrueCrypt uses XTS, which in this context behaves similarly to ECB. XTS is essentially a tweakable blockcipher in a ECB like mode, where the tweak contains a counter. –  CodesInChaos May 23 '12 at 18:38

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.

-
Interesting. So the optimal solution is to place the two strongest ciphers on the outside? i.e. first and last. –  Polynomial May 23 '12 at 5:49
Just for reference, if someone sees this answer in future and wonders what custom hardware could crack DES, it's COPACOBANA: copacobana.org –  Polynomial May 23 '12 at 7:41
How would you "decrypt the final ciphertext at a cost of $O(2^{40})$" in your first step? –  Paŭlo Ebermann May 23 '12 at 17:03
@PaŭloEbermann By construction I assumed that 3DES had an attack that reduced its key space to 2^40. As such one must merely try all those keys. This is, of course, a somewhat odd assumption, but the observation we get from it shows that order can matter. –  imichaelmiers May 23 '12 at 18:18
After trying all keys, how will you know which one was the right one, when your "plaintext" is actually still encrypted by AES and Serpent? –  Paŭlo Ebermann May 23 '12 at 18:21