Combination of two stream ciphers Recently, I've been wondering what happens when I combine two stream ciphers $f_1$ and $f_2$ by xoring the keystream, so the final cipher would be:

$C = P \oplus f_1(K_1) \oplus f_2(K_2)$

$P = C \oplus f_1(K_1) \oplus f_2(K_2)$

Obviously, the keystreams shouldn't be the same because they would negotiate each other, so a few scenarios shouldn't apply:


$f_1 = f_2$ and $K_1 = K_2$ because they obviosly would create the same keystream.
$f_1 = f_2$ and $K_1 \neq K_2$ but there $f$ is insecure and $K_1$ and $K_2$ are part of a related-key attack so $f$ produces the same keystream.
Really bad luck?


Another thought was that the combination could be used to double the key length, as long as there are not related keys. Also given that $f_1 \neq f_2$ and an attacker is able to compute the keystream of only one of both,  he would be left with $C \oplus f_\mathit{other}(K)$ making the combination as secure as the most secure cipher used.

Finally, one last thought I had is that such patterns are already used in stream ciphers (e.g. A5/1) when LFSRs are combined so they might be secure?
This sort of combination is vulnerable to a meet-in-the-middle attack.  Let's start from one of your equations:

$$
C = P \oplus f_1(K_1) \oplus f_2(K_2)
$$

If we XOR $f_1(K_1)$ to both sides, we get:

$$
C \oplus f_1(K_1) = P \oplus f_2(K_2)
$$

Now if I have one known plaintext/ciphertext pair $P, C$, to attack the cipher, I can carry out the meet-in-the-middle attack:


I build a table of the values of $C \oplus f_1(K_1), K_1$ for all possible values of $K_1$.  This takes time and memory proportional to $2^{|K_1|}$.
For each possible value of $K_2$ I compute the corresponding $P \oplus f_2(K_2)$, and look it up in the table from step #1.  If I find a match I record that $K_1, K_2$ combination as a candidate key.


Now the key must be one of the candidate keys, and it only took me $2^{|K_1|} + 2^{|K_2|}$ time to find this out, not $2^{|K_1| + |K_2|}$—the combined cipher is much weaker than a cipher with the sum of the key lengths.

(Note that there can be more than one candidate key.  Any $K'_1, K'_2$ such that:

$$
f_1(K'_1) \oplus f_2(K'_2) = f_1(K_1) \oplus f_2(K_2) 
$$

...is a candidate key as well.  But you can bet the number of candidate keys will be much, much smaller than the number of keys.)