Stream Ciphers and cycling questions

Question

• For all PRNGs (including CSPRNGs) lets say there is a sequence x, y, z, then when the PRNG cycles back to x, then the sequence following it will be exactly the same as before. Is this true for all PRNGs?

• Are there any rules about minimum cycle length for CSPRNGs used for Stream Cipher? Because if a cycle happens, then the One Time Pad is no longer a One Time Pad and becomes insecure, right?

• What are the average cycle lengths for commonly used Stream Cipher algorithms?

• Is it not possible to prevent cycling by making the algorithm dependent on what it is encrypting - i.e. something like

The stream cipher is used for encrypting communication between Alice and Bob. Alice's key is K1 & Bob's is K2. This is the conversation

Alice: Hello, Bob
Bob: Hello, Alice
Alice: How are you? 

So

1. K1 is used to generate the stream for encrypting "Hello, Bob" and it's sent.

2. The next stream generated not only depends on state of the PRNG after generating the stream for "Hello, Bob" but "Hello, Bob" is also used as input for this stream. And this will be used for encryption "How are you?" and so on.

Answer 1

A PRNG has an internal finite state. The value of that state determines all subsequent outputs; that's the point of the PRNG being a deterministic engine. Whenever the PRNG produces a new output element, its internal state evolves into a new value. Since the internal state is finite in size, it is a mathematical certainty that the PRNG, at some points, enters a cycle and never leaves it.

The details are worth analysing:

• The PRNG will enter a cycle, not necessarily start on the cycle. For instance, if the PRNG state $S$ has size $n$ bits, and, when the PRNG outputs an element, the state $S$ is replaced with $h(S)$ for some hash function $h$ with an output of $n$ bits, then, on average, the cycle will be reached after about $2^{n/2}$ steps, and the cycle length will also be about $2^{n/2}$. You won't get back to the initial state.

• This is about the internal state, not the output. If you get at some point output element $x$, then later on obtain $x$ again, then you did not necessarily completed or even entered a cycle, because two distinct internal state values may yield the same output element.

• In practice, for a cryptographically secure PRNG, the cycle cannot be completed or even reached, it is way too large for that. The cycle length used to be a sort of traditional measure of "security" but it does not play this role nowadays. Any cycle length beyond $2^{128}$ is as good as "infinite".

A stream cipher is an encryption system specialized in the encryption of bulk data. Many stream ciphers operate like PRNG: from they key, they produce a long sequence of pseudorandom bits, which is combined by XOR with the data to encrypt or decrypt. In such a case, the internal PRNG state is not impacted in any way with the data that is encrypted. However, some other stream ciphers modify their internal state by injecting the encrypted data as well. When the data is injected, this changes the situation with regards to cycles: if the data to encrypt is not cyclic, then you won't get a cycle.

Block ciphers can be turned into stream ciphers by using some modes of operation, in particular CFB, OFB and CTR. The CFB mode injects the encrypted data into the internal state; OFB and CTR do not. With a block size of $n$ bits (e.g. $n = 128$ for AES), then CTR offers a cycle length of exactly $2^n$ blocks, i.e. $n2^n$ bits; OFB cycle length is more random (if you are terribly unlucky you could hit a short cycle).

A condition for a stream cipher to be deemed "secure" is that its output is computationally indistinguishable from randomness even when encrypted a long sequence of zeros. A consequence is that in a secure stream cipher, the cycle cannot be fully walked or even simply reached in practical terms. Beyond that point, cycle length has no meaning for security.