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


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?

  • $\begingroup$ I don't get it. If you know the key, the rest are public. Do you mean key stream with the key? $\endgroup$
    – kelalaka
    May 13 at 9:14
  • $\begingroup$ @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? $\endgroup$
    – Tom
    May 13 at 10:09
  • $\begingroup$ 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. $\endgroup$
    – kelalaka
    May 13 at 10:18
  • $\begingroup$ 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. $\endgroup$
    – Tom
    May 13 at 11:05
  • $\begingroup$ 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. $\endgroup$
    – Tom
    May 13 at 11:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.