Combining several symmetric ciphers using XOR

Question

I have seen a talk by Rüdiger Weis, where he says that you can combine two symmetric ciphers using XOR. According to him, that has the effect that its sufficient if only one of the ciphers is secure.

How does he do that? I have thought of

ciphertext = twofish(message) XOR aes(message)

but I can't see how the receiver would decrypt that, as he does not know either twofish(message) or aes(message).

I also thought of

ciphertext = twofish(aes(message))

But there is no XOR involved. So whats the problem with the above approach?

I have seen this answer but I don't think its relevant anymore. Using multiple ciphers may be needed to defend against NSA mass surveillance.

EDIT: The two formulas is what I came up with. Rüdiger Weis only said, "you can combine ciphers and XOR is involved".

Answer 1

The usual method to do this is to turn the block cipher into a stream cipher. In that way the ciphertext is generated by XOR'ing the plaintext with a generated key stream. This key stream in turn is generated by the mode of operation that turns the block cipher into a key stream. There are several of these modes, but CTR mode of operation is most often used (in new protocols anyway). You don't need to do this for stream ciphers of course.

Now you can just use $C = P \oplus K^1 \oplus K^2$ where $C$ is the ciphertext, $P$ is the plaintext and $K^1$ is the key stream of one cipher and $K^2$ is the key stream of the other cipher. As XOR is associative and commutative you can see this as first applying key stream 1 or key stream 2, and then the other. The key streams will have the same size as the plaintext.

This is similar to applying two one-time-pads to the plaintext. Given a secure block cipher, a key stream generated using CTR is secure but not perfectly secure. So it's not identical to using two one-time-pads. One difference with a one time pad is that CTR mode requires a nonce; the same nonce can be used for both stream ciphers though.

In contrast to one time pads it is possible to cryptoanalyze a stream cipher. This means that the key streams should be sufficiently independent of one another. So the stream ciphers should be created using separate keys and ciphers. If you would use the same key, IV and cipher then key streams would cancel each other out, leaving you with the plaintext after encryption.

---

Small stream cipher introduction

With a stream cipher a key and a nonce are used with the cipher to generate a key stream of any size. Usually the plaintext is not needed as input at this stage. The key stream is then XOR'ed with the plaintext. As the key stream should be indistinguishable from random to an attacker, it should be impossible to invert this operation without the key and nonce. Decryption is identical to encryption and if a block cipher is used then you may only need to use the block cipher in one direction (encryption or decryption). You can encrypt and decrypt by applying the key streams in any order as the XOR operation is associative and commutative.

Answer 2

There is a very simple, completely generic solution, that unlike the other solution doesn't assume anything about how the two encryption schemes work internally (e.g., that they are built from block ciphers or have pseudorandom ciphertexts): given a message $m$, choose a uniformly random $m_1$ of the same length and let $m_2 = m \oplus m_1$. Then encrypt $m_1$ under the first scheme and $m_2$ under the second (using independent keys), sending both ciphertexts. To decrypt, recover $m_1$ and $m_2$ and output the message $m=m_1 \oplus m_2$. (This is all just a simple secret-sharing of the message.)

This works because even if the attacker can break, say, the first scheme and recover $m_1$, the security of the second scheme hides $m_2$ and thereby $m$.

Answer 3

If you have a uniformly random string $s$ as long as your message $m$, then $s \oplus m$ is a one-time pad (using $\oplus$ for XOR).

If a cipher is secure, then its ciphertext should look like uniform randomness to anyone who does not have the key (even if they know the message). The XOR combination is then effectively a one-time pad.

At least, that's the intuition. The formal study of these things goes by the name of robust combiners

There's no security problem with doing the two in sequence as in your example. But the XOR combination allows you to do the two encryptions in parallel, which may be more efficient in some cases.

EDIT: I see what you mean now. Are you sure that's exactly what he said? It looks to me like that construction is not going to be decryptable, like you suspected. Are you sure it's not something along the lines of Maarten's answer (which does decrypt), or a RNG (which doesn't need to)?