4
$\begingroup$

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.
  3. 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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Squeamish Ossifrage Aug 24 '17 at 13:20
  • $\begingroup$ Is A5/1 a good example? It only has one key rather than two /three. I'm having deja vu... $\endgroup$ – Paul Uszak Aug 24 '17 at 21:03
5
$\begingroup$

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.)

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – fgrieu Aug 24 '17 at 11:11
  • 4
    $\begingroup$ 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. $\endgroup$ – Squeamish Ossifrage Aug 24 '17 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.