2
$\begingroup$

Does encrypting plaintext multiple times with the same stream cipher but independent keys increase security? If each key is n-bits, and the cascade uses m-streams, could this be considered mn-bit encryption? If so, when?

Versions of this question are already addressed in the following posts, but they seem to mostly discuss the result by Maurer and Massey, which states that the security is at least as strong as that of the weakest cipher in the cascade. Maybe I need to read the proof more carefully, but this doesn't seem like the tightest lower bound on security since the result seems to come from the assumption that an attacker already has access to some of each of the key-streams (although it at least says that the cascade can't hurt).

$\endgroup$
2
  • $\begingroup$ I would expect the security to be better than just doing it once. $\endgroup$ Commented Dec 30, 2022 at 11:43
  • 3
    $\begingroup$ @RohitGupta: not always; if the encryption operation is a group operation, then it's not any more secure at all (for example, OTP). You can say that it is no weaker $\endgroup$
    – poncho
    Commented Dec 30, 2022 at 15:45

1 Answer 1

2
$\begingroup$

Does encrypting plaintext multiple times with the same stream cipher but independent keys increase security? If each key is n-bits, and the cascade uses m-streams, could this be considered mn-bit encryption?

Actually, the strength of the system is between $n$ and $n\lfloor (m+1)/2 \rfloor$ bits.

The lower bound is obvious; here is an attack which breaks the system with $2^{n\lfloor (m+1)/2 \rfloor}$ work effort (assuming a known plaintext/ciphertext pair).

  • Divide the ciphers into two halves; one half containing $\lfloor m/2 \rfloor$ ciphers (and thus $n\lfloor m/2 \rfloor$ bit bits), and the other half containing $\lfloor (m+1)/2 \rfloor$ ciphers (and thus $n\lfloor (m+1)/2 \rfloor$ bit bits)

For the first half, iterate through all $2^{n\lfloor m/2 \rfloor}$ possible key values, and for each such set of keys, generate the key stream and compute $P \oplus C \oplus keystream$, and save it in a database (along with the keys that generated it).

Then, for the second half, iterate through all $2^{n\lfloor (m+1)/2 \rfloor}$ possible key values, and for each such set of keys, generate the key stream, and search for it in your database.

When you find a match (and you always will, assuming that their is a set of keys), then you also get the keys.

Both these steps take at most $2^{n\lfloor (m+1)/2 \rfloor}$ work effort, hence that is the amount of time required.

With that said, there is sometimes an easier attack against the system which reduces the required work. The obvious example is the Vingenere cipher, where encrypting the text with $m$ different keys is precisely the same as encrypting it with one key.

$\endgroup$
1
  • $\begingroup$ Thanks @poncho - that's a really cool result. Some followup questions: (1) Is there a citation for this result anywhere? (2) Any nice results like this for if the plain text isn't known? (3) This seems to look like it's true for any cascade of stream ciphers, regardless if the streams are generated with the same or different algorithms - is it? $\endgroup$
    – felix256
    Commented Jan 1, 2023 at 19:00

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.