0
$\begingroup$

enter image description here

In case multiple stream ciphers exist, I'm refering to this specific instance in which you generate a key that is just as long as the msg, M, as a function of a nonce and a smaller key K.

My textbook classifies this as computational secure. But why is that?

I would say that it was unconditionally secure since assuming the adversary is able to find a long key O_2 that when XOR'ed with the ciphertext produces a sensible M="sensible text", the adversary still has no clue whether that was the original message or not (it could have been the case the sender's actual msg was pure garbage).

Improve this question
$\endgroup$
6
  • $\begingroup$ Basically, the keystreams aren't purely random. They can't be, because you feed limited entropy into them. If your generator creating O takes 128 bits of key data, then at most 2^128 unique keystreams are possible. If an attacker could, for instance distinguish between a keystream created by O and genuine random data then that would reduce the searchspace a lot. $\endgroup$
    – MechMK1
    Dec 19, 2021 at 14:05
  • $\begingroup$ Also, look at real life examples of stream ciphers being broken to understand their weaknesses. $\endgroup$
    – MechMK1
    Dec 19, 2021 at 14:08
  • $\begingroup$ Could you rewrite your first sentence? It seems like you are saying that from a short key $K$, producing a stream equal to message size is unconditionally secure. $\endgroup$
    – kelalaka
    Dec 19, 2021 at 18:28
  • 2
    $\begingroup$ I believe OP has confused the keystream, which is as long as the message, with a key. There's only one key in a stream cipher, it's short and gets combined with a nonce to produce the keystream. The keystream gets XORed (or otherwise reversibly combined) with the plaintext to produce the ciphertext. Using the right words is important to avoid confusion. $\endgroup$
    – SAI Peregrinus
    Dec 20, 2021 at 3:44
  • $\begingroup$ Please note that the comments and answers here are interpreting "unconditionally secure" as information theoretically secure. If that is not your intent please clarify what you mean by "unconditionally secure". $\endgroup$
    – puzzlepalace
    Dec 21, 2021 at 0:16

1 Answer 1

Reset to default
1
$\begingroup$

If I understand the question right, it's about whether a truncated stream cipher $X(K,N)$ is unconditionally secure.

First, for a single message per key (and so, one fixed nonce $N$), the stream cipher is unconditionally secure if and only if the stream generator $X(\cdot,N)$ is a bijection, for the chosen nonce. Then, it is equivalent to using a fresh uniformly random key, which achieves perfect secrecy.

Now, if we are going to reuse the key, even with different nonces, then we have a problem: the total message length exceeds the key size and so this can not be perfectly secure. (Note that nonces are public)

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ To unconditionally secure the key must be uniformly random and have the same size as the message. A stream cipher cannot guarantee this since they are expanding a short seed into a long stream. $\endgroup$
    – kelalaka
    Dec 19, 2021 at 18:06
  • $\begingroup$ My answer covers the case when the message size is limited to the key size ("key that is just as long as the msg"). As I reread the question, I now see the "as a function of a nonce and a smaller key K"... $\endgroup$
    – Fractalice
    Dec 19, 2021 at 18:11
  • $\begingroup$ It seems your interpretation is correct. I think some parts need re-write. the size of the bijection is not totally explicit. Second, the number of bijections doesn't cover all of keyspace of uniform random key of size equal to message size ( or am I missing it). 3rd, hiding the actual reason ( 1st comment). $\endgroup$
    – kelalaka
    Dec 19, 2021 at 19:11

Your Answer

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

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