5
$\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?

Improve this question
$\endgroup$
2
  • $\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
    Commented Aug 24, 2017 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
    Commented Aug 24, 2017 at 21:03

1 Answer 1

Reset to default
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.)

Improve this answer
$\endgroup$
3
  • 3
    $\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 ♦
    Commented Aug 24, 2017 at 11:11
  • 5
    $\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
    Commented Aug 24, 2017 at 13:16
  • $\begingroup$ 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?? $\endgroup$
    – SamG101
    Commented Jan 21, 2020 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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