Can combining two secure block ciphers be insecure?

Question

Let's say we have two secure block ciphers FOO and BAR. Will a new block cipher built by combining them into a single new block cipher result in any insecurity?

$$\begin{align} \operatorname{BAZ}_K(x)&=\operatorname{FOO}_K(\operatorname{BAR}_K(x))\\ \operatorname{BAZ}^{-1}_K(x)&=\operatorname{BAR}^{-1}_K(\operatorname{FOO}^{-1}_K(x)) \end{align} $$

Answer 1

It depends on what you mean by "a secure block cipher", but under a strong enough definition (which is thought to hold in practice), the answer is "no" for boring reasons. If we had some block cipher $F_k$ such that $F_{k}^{-1}$ was also a secure block cipher, then the composition:

$$(F_k\circ F_k^{-1})(x) = x$$ Would trivially not be a secure block cipher.

Therefore, if we want to justify this (contrived) counterexample, we would need $F_k$ being a secure block cipher to imply that $F_k^{-1}$ is as well. This does not hold for the "standard" notion of security of block ciphers (distinguishing the PRP from random), but does hold if you also allow the adversary to query the "inverse" function.

Most block ciphers in practice are thought to satisfy this stronger definition, but this kind of insecure construction (composing a block cipher with its inverse) is a "dumb" attack on your idea, and relies on the two block ciphers ($F_k$ and $F_k^{-1}$) sharing a great deal of structure mathematically.

Answer 2

The answer is: in theory, maybe... but in practice, never in a million years (literally).

If the ciphers are too similar (BAR is almost identical to the decryption function of FOO) they could cancel each other out, assuming you use the exact same key in both. But in practice, you'd probably still get a more secure cipher as long as each individual cipher is secure - and probably even if they aren't.

Why?

Let's take a look at SP-Networks (the basis for most modern ciphers)... You take a round function, some nonlinear invertible function to obscure the meaning of each (usually byte). Then, you mix the bits with bits from some completely different byte within the message. Doing this, a difference of an individual bit is meant to change the entire message. Therefore, even an almost perfect decryption function would simply add more nonlinearity. If there's a single difference in either algorithm the worst you can do is make it no more secure than it was.

However, if you use 2 different encryption algorithms you can consider them 1 "product cipher" of the 2 algorithms. Let's say you use AES-256 and Serpent-256... You could use the same key for both and effectively get a single 46-round cipher, from Serpent(AES(message)). The first 14 rounds are AES rounds, the last 32 are Serpent rounds, and the result is a cipher with the cryptographic strength of combined AES and Serpent.

This wouldn't be the case if you could break each cipher individually, but since you never use AES(message) anywhere except as Serpent's message, the AES ciphertext becomes an internal state in your supercipher. Hence, breaking either algorithm individually does nothing, and even breaking both wouldn't necessarily allow you to do anything useful. You'd need to not only break both ciphers, but also break them as they relate to each other.

That being said, you should use different keys for each algorithm as a matter of standard practice. That's not really required by the math but you'll get made fun of if you don't... As well as exposing yourself to an unrealistically small risk that in any rational mind doesn't matter, but could ruin you if you're really unlucky.

Update: If you're concerned about one of the algorithms having a side-channel attack, you should use the one without the possible side-channel first. That way, any side channel simply recovers ciphertext. This tactic only works if the keys are both mutually independent (aka knowing one key tells nothing about the other).

Update 2:

What would be a real-world case where you end up with less security?

Let's say we use out 2 algorithms: AES and the hypothetical SEA... SEA is the same as AES, except an SEA decryption round is an AES encryption round.

Let's say the last 5 round keys of SEA are the same as the first 5 AES round keys, but the other round keys are different. Let's also assume SEA uses 7 rounds in total. We get:

// [algo]_ENC = a single encryption round
// [algo]_DEC = a single decryption round
msg = AES_ENC(msg)
msg = AES_ENC(msg)
msg = AES_ENC(msg)
msg = AES_ENC(msg)
msg = AES_ENC(msg)
msg = AES_ENC(msg)
msg = AES_ENC(msg)
msg = AES_ENC(msg)
msg = AES_ENC(msg)
msg = AES_ENC(msg)
msg = AES_ENC(msg)
msg = AES_ENC(msg)
msg = AES_ENC(msg)
msg = AES_ENC(msg)

msg = AES_DEC(msg)
msg = AES_DEC(msg)
msg = AES_DEC(msg)
msg = AES_DEC(msg)
msg = AES_DEC(msg)
msg = SEA_ENC(msg)
msg = SEA_ENC(msg)

Notice how some of the AES_ENCs are cancelled out by AES_DEC? Since AES_DEC is SEA_ENC for those rounds we have effectively reduced our cipher to a modified 9-round AES. Since our hypothetical SEA only has 7 rounds, we end up with 3 less rounds than normal AES.

*Unless your algorithm BAR is specifically designed to undo FOO, you're probably fine.

In real life, no 2 algorithms used will ever produce that result (unless you're specifically trying to make it less secure). I just included that example to explain how it could possibly happen.

There are other ways you could end with less security but they all require BAR to be an inverse of FOO. You could, in theory, find a BAR that's not an inverse of foo but manages to reduce the security, but that's a purely-theoretical attack. The difficulty of finding such a BAR would be mostly the same as breaking your original algorithm.