# Security of cascaded ciphers (including question on counter-example from a paper)

A recurring theme is the security benefits of cascading two or more different ciphers. The idea is to enhance security, especially if one of the ciphers is later compromised. Intuitively (see below), cascading ciphers with independently chosen keys should result in a cipher at least as strong as the strongest one used. However, this is not always the case. A paper by Maurer and Massey (free download: https://link.springer.com/article/10.1007/BF02620231) provides a counterexample to this "folk-theorem," (their words) by claiming to demonstrate how two ciphers, C1 and C2, can become less secure when cascaded (see page 4). The paper further argues that the cascade's security is only guaranteed to be as strong as the first cipher and argues that previous proves to the contrary didn't account for attacks exploiting plaintext statistics.

Here's my counter-argument to their counter-example: Critically examining the example from the paper, neither C1 nor C2 could be considered secure ciphers. The counterexample demonstrates that C1 maps 'A' and 'B' to the same values regardless of the key, rendering it 'completely insecure' (in the paper's own words) for plaintext consisting solely of 'A's and 'B's. Similarly, C2 has the same issue for 'C' and 'D'. Given the inherent weaknesses of both ciphers, it is unsurprising that their combination is also insecure. The folk theorem (and its intuition) demands that at least one of the ciphers is secure which wasn't the case in the counter-example.

Therefore, if we impose stronger security requirements on the ciphers, the folk theorem might still hold, irrespective of the ciphers' order in the cascade.

My intuition supporting the folk theorem, regardless of which cipher is the secure is as follows - let's let C1 be the first (inner) cipher and C2 the outer cipher.

Scenario 1: C1 (inner) is Secure, C2 is insecure/less secure:

If C1 is secure and C2 is less secure, the resulting cascade should still be secure because an attacker could theoretically apply C2 themselves. If merely applying C2 (with a random key) to the ciphertext output of C1, helped break C1, it would imply that C1 was not secure to begin with.

Scenario 2: C2 is Secure, C1 is Less Secure:

If C2 is secure and C1 is less secure, the cascade should remain secure because the final encryption is done by C2. If C1 altered the plaintext in a way that it was no longer possible to encrypt it securely by C2, with a random key, then C2 was not truly secure. It seems a secure cipher should withstand any input of the user's choosing.

Applying this to the counterexample in the paper, the reason the cascade isn't secure is that neither C1 nor C2 meets the security assumptions. Thus, if at least one of the cipher individually satisfies strong security criteria, the folk theorem should hold.

• The counter-argument is missing a key point made by the paper, in particular, this: "Neither C1 nor C2 could be considered secure ciphers". The paper does not claim to the contrary. Their counter-example defines a "cipher" where the effective message space is $(A, B)$. However, the cipher is implemented by embedding the message space into a larger one. Formally speaking, this is a correct definition of a cipher in the sense of implementing a random Injection. From that standpoint, $C_1$ is insecure for that message space, while $C_2$ is not. Commented Jul 24 at 11:00
• That is, $C_2$ actually implements a random injection and can be for the key space. Now, the combination of these becomes weak, as demonstrated by the paper. Finally, as already stated in the first answer, the paper finds a counter-example that is enough to disprove the general “folk theorem.” That shouldn't be interpreted as all cascades are insecure (which is not what the paper is claiming). This is similar to Mac-then-encrypt, which is not generically secure and does not imply all such schemes are insecure. We have secure "counter-examples" used in practice. Commented Jul 24 at 11:04
• Please include an explicit question, perhaps asking if some assertion holds. Since (as noted in the question) that is likely to depend on details, state the details, or at least ask on what details the true/false status of the assertion depends.
– fgrieu
Commented Jul 24 at 16:31
• @marc: But if neither C1 or C2 could be considered secure ciphers, then it's not surprising that the result isn't secure either. This is not in any way in contradiction to the true 'folk theorem' which would never expect a secure outcome for grossly insecure ciphers. I think my point can be summarized as: The true 'folk theorem' is actually true. However, this paper introduces a strawman for the folk theorem that is easy to shoot down with examples with no applicability to the true folk theorem. Then people go invoke this paper in contexts where the talk is about the real folk theorem. Commented Jul 24 at 19:15
• fgrieu: I guess my question is - if we state the folk theorem as "Assume at least one of the ciphers C1 and C2 is a secure cipher, then the cascade is secure as well" then the folk theorem really is true - right? And it is this version that is relevant in the context of veracrypt, disk encryption with cascaded ciphers etc. Commented Jul 24 at 19:16

Your intuition is wrong, because you do not understand the limitations of a modern "secure" cipher. This is actually important and has been used to break real-world cryptosystems.

(A second, less important point, is that the paper in question is a bit old, so its exposition is tied to what people cared about back then, not what most people care about today. So it may be a bit hard to read today. The ideas are still valid, of course. The following is an informal, modern exposition of what I consider to be the main idea.)

(A third point, which is not so important for understanding, but which should not be ignored, is that cascades are mostly useless and we mostly don't do it like that anymore, but understanding the security of compositions of cryptosystems is important, mostly because of the perceived need for quantum-safe cryptography.)

#### Idea

The idea is that a secure cryptosystem hides all information about the plaintext, except the length.

We use this idea to design an insecure cascade using an insecure first cryptosystem and a secure second cryptosystem. For the first cryptosystem, you let the length of the ciphertext depend on the contents of the plaintext, not just the length of the plaintext. This signal may then leak through a secure cryptosystem.

#### Example and exercise

Example: Compress the plaintext before encrypting it. Exercise: What real-world system am I thinking about here? (Hint: The answer is not unique.)

#### The importance of being first

Note that this does not work for the second cryptosystem, hence the importance of being first. Being first allows you to do bad things to the plaintext of the second cryptosystem, which the second cryptosystem is not obligated to hide.

The second cryptosystem, however, has to work with a ciphertext, so it cannot do any harm.

#### Now what?

This result may offend you because it conflicts with your intuition. But then you should do two things: Fix your intuition. And figure out under which conditions the folk theorem is true.

For the second thing, it is fun to realise that the folk theorem is true for block ciphers. Recall that block ciphers are not cryptosystems. But the theorem might give you a hint for conditions under which the folk theorem should be true.

The mathematical statement of the folk theorem starts "for all ciphers C1 and C2", thus a counterexample is enough to disprove the folk theorem which Massey and Maurer supply.

Also your arguments seem to rely on statements such as "If C1 altered the plaintext in a way that it was no longer possible to encrypt it securely by C2" but the security of C2 cannot be determined by being weak against a specific input.

• Right, the 'folk theorem' as stated in the paper doesn't capture how people normally consider it. As for the second part, I'm trying to argue that if one of the ciphers in the cascade is secure, the cascade is secure as well. My point is that if the outer cipher really is what is normally considered a secure cipher, then it doesn't matter that the input was processed by C1. Massey/Maurer seems to argue that (versions of) the folk theorem doesn't account for plaintext stats. But I would argue opposite: A secure cipher shouldn't care if the attacker knows plaintext stats. Commented Jul 24 at 10:21

Given the inherent weaknesses of both ciphers, it is unsurprising that their combination is also insecure. [...] Therefore, if we impose stronger security requirements on the ciphers, the folk theorem might still hold, irrespective of the ciphers' order in the cascade.

I'd posit that the "folk-theorem" is impossible to prove generally true. This is due to it not being possible to naively combine secure ciphers, where the security notion used is IND-CCA2 or stronger/stricter (authentication being a prerequisite for confidentiality). So, under this conjecture, any secure cascade is either uniquely proven secure, or proven secure within a non-trivial framework of satisfiable rules (thus making it "unfolkable").

## Complications:

1. Are the keys truly independent, or only statistically independent to an outside observer (derived from the same shared secret)?
2. Are nonces / IVs / SIVs involved? How?
3. How many authentication tags are there? How do the ciphers interact with them?
4. Do the security requirements of one cipher invalidate or complicate the other?
5. What problems are caused by the other interactions between the ciphers?
6. Are the inputs canonical?
7. Are the inputs committed to?
8. Are the subroutines domain separated & committed to?

There seem to be too many considerations for any "folk-theorem" of cascades to be sufficient.

An example of a weaker-than-IND-CCA2 XEX cipher cascade being broken due to the subtle aspect of the permutation being an involution using independent keys:

Minimalism in Cryptography: The Even-Mansour Scheme Revisited