What does it mean to break non-invertible stream cipher?

Tom

9/13/23, 12:15 AM

Let's consider for simplicity Middle-Square Weyl Sequence RNG:

https://arxiv.org/pdf/1704.00358.pdf

We can choose there parameter for independent stream generation, we can call it key. Let's consider we would use it as a stream cipher, so stream is xored with plaintext.

But what it mean to broke such a cipher? Even if we hack the key, we can't compute the seed in invertible way, beacuse regardless of the fact that minimal period of that PRNG is guaranteed, there is non-invertible transformation. We are loosing some bits after every step.

In that case it is not enough to find a key. When we would say that this cipher is broken? Does there have to be a seed recovery, to conclude that cipher is broken? Or maybe we could be talking about varying degrees of breaking such cipher? Because on one hand if we break the key, we can usually generate next bits of the stream. But so what if we can't read the strem backwards until we get the seed back.

What is more important in such a case for the victim, that the attacker does not learn the key or the seed?

0 + 0

stream-cipher

kelalaka

9/13/23, 9:14 AM

I don't get it. If you know the key, the rest are public. Do you mean key stream with the key?

Tom

9/13/23, 10:09 AM

@kelalaka If we use seed as a key_1 and internal key as a key_2, even if we know the key_2, we still don't know key_1. And we can't reverse such generator, because it is non-invertible. If you have key_2 and all state of the generator there is no one way to go backwards. So you don't know for sure what was previous state. You can find several different previous states with key_2, which would give actual state. Or maybe I'm wrong?

kelalaka

9/13/23, 10:18 AM

Forget the article. RNG for Cryptography is not about the internals - that is the ultimate aim if possible - indistinguishability from random or equivalently next bit is.

Tom

9/13/23, 11:05 AM

Let's consider that you know w=1, s=1 and result=3 of that PRNG. Can you tell what x was squared? It could be every number which gives high bits 00000000000000000000000000000011. Low bits can be any you want. So you can find quite much of x, which after squaring and adding 2 will give you such number. For example 2305843002771243007, because 2305843002771243007^2 mod 2^64 = 12884901889. And (12884901889+2) >> 32 is exactly 3. Other example is 6917529034083532801. It could also be our x, we don't know that, even though we have the key "s". That's why even having key, you can't invert it 1:1.

Tom

9/13/23, 11:23 AM

I'm not telling this would be hard to invert or cryptographically secure, I believe the opposite. This is trivial example to show how may non-invertible stream cipher look like. And to think what does it mean to break such an cipher, because, as I showed, knowing key does not allow for clear seed recovery.

Elon Musk

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

EN: What does it mean to break non-invertible stream cipher?

TH: การทำลายรหัสสตรีมที่ไม่สามารถเปลี่ยนกลับได้หมายความว่าอย่างไร

RO: Ce înseamnă să rupi cifrul fluxului care nu poate fi inversat?

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

VI: Việc phá vỡ mật mã dòng không thể đảo ngược có nghĩa là gì?

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.