Score:0

Crypto

Why are stream ciphers computationally secure?

Sebastian Nielsen

4/19/23, 12:29 PM

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

164

0 + 0

stream-cipher

security-definition

perfect-secrecy

MechMK1

4/19/23, 2:05 PM

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.

MechMK1

4/19/23, 2:08 PM

Also, look at [real life examples](https://en.wikipedia.org/wiki/Wired_Equivalent_Privacy) of stream ciphers being broken to understand their weaknesses.

kelalaka

4/19/23, 6:28 PM

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.

SAI Peregrinus

4/20/23, 3:44 AM

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.

puzzlepalace

4/21/23, 12:16 AM

Please note that the comments and answers here are interpreting "unconditionally secure" as [information theoretically secure](https://en.wikipedia.org/wiki/Information-theoretic_security). If that is not your intent please clarify what you mean by "unconditionally secure".

Maarten Bodewes

9/18/23, 11:05 AM

@SAIPeregrinus Indeed, and this is where the confusion lies, as there are usually many fewer keys than messages; the idea then that a cipher using a smaller key is information theoretically secure fails.

Score:0

Crypto

Fractalice

4/19/23, 6:02 PM

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)

0 + 0

kelalaka

4/19/23, 6:06 PM

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.

Fractalice

4/19/23, 6:11 PM

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

kelalaka

4/19/23, 7:11 PM

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

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Why are stream ciphers computationally secure?

TH: เหตุใดการเข้ารหัสสตรีมจึงมีความปลอดภัยในการคำนวณ

RO: De ce sunt cifrurile de flux sigure din punct de vedere computațional?

RU: Почему поточные шифры вычислительно безопасны?

VI: Tại sao các mật mã dòng lại an toàn về mặt tính toán?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.