# 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:

1. $f_1 = f_2$ and $K_1 = K_2$ because they obviosly would create the same keystream.
2. $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.

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?

• Re (3) really bad luck: If you have really bad luck, the attacker has guessed $K_1$ and $K_2$ right away. But cryptography is about quantifying the probability and bounding it below something widely accepted to be negligible. This is why there's no such thing as a single ‘weak key’: an adversary who knows your key is 0x0123456789abcdef has already broken your specific use, no matter what the structure of the cipher is. Aug 24, 2017 at 13:20
• Is A5/1 a good example? It only has one key rather than two /three. I'm having deja vu... Aug 24, 2017 at 21:03

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:

1. 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|}$.
2. 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.)

• Addition: to sum this up, the composition is at best slightly stronger than the strongest of the two stream ciphers; disregarding memory-related cost, at most 1 bit stronger. In some cases (including 1/2/3 in the question), it can be weaker.
– fgrieu
Aug 24, 2017 at 11:11
• The conventional wisdom is that you do this only as a hedge against cryptanalytic advances in $f_1$ or $f_2$. But from an adversary's perspective, it's not sensible to disregard memory costs. As stated, the area*time cost of this attack to find one key is $O(2^{2|K_1|} + 2^{|K_1| + |K_2|})$, which is essentially the same as the naive (sequential or parallel) brute-force attack. Aug 24, 2017 at 13:16
• How is $f_1(k_1)$ found by an attacker in the first place, in order to be able to XOR it on both sides?? Jan 21, 2020 at 13:46