A periodic PRNG based on hash function?

Question

I need a PRNG which provides 128 bytes numbers.

Let's say that given a symmetric key $K$ and an internal state $s$ I use the PRF HMAC-SHA512 this way:

The output is PRNG($K, s$) = HMAC-SHA512$_K$($s$ || 0x01) || HMAC-SHA512$_K$($s$ || 0x02) where $||$ represents a concatenation. The next state is $s_{i+1}$ = HMAC-SHA512$_K$($s_i$ || 0x03) || HMAC-SHA512$_K$($s_i$ || 0x04).

I am wondering if my PRNG can be periodic?

I mean, is it possible that given the initial internal state of the PRNG noted $s_0$ and the symmetric key $K$, to have an integer $n$ such that $s_n = s_0$?

Answer 1

Any PRNG with a finite state size is eventually periodic. The maximum period possible is $2^n$ for an $n$-bit state, but the average with a well mixed state is $2^{n/2}$.

Here the hash function used is SHA-512, but the state is 1024 bits. A first guess would be a period of $2^{512}$, rather than the $2^{256}$ mephisto gives.

Let's look at the cycles. Both halves of the state are generated with HMAC-SHA512, so they would enter cycles of about $2^{256}$. However, because the inputs are different, they have their separate cycle structure. The two cycles are likely to be different lengths. The overall cycle is about as long as the least common multiple of the two lengths.

Two uniformly distributed random numbers have a small expected GCD, meaning the LCM would be close to their product. The lengths here are not uniformly distributed, but I believe the same is still more or less true. So the cycle length should be close to the $2^{512}$ expected with a 1024-bit state.

Answer 2

Yes, this PRG is theoretically periodic. Approximately after generating $2^{512}$ outputs a state will be generated that collides with a previous state. (A previous version of this answer said $2^{256}$ as I missed that two outputs are used for the state. Otus answer pointed out this mistake.) This follows from the birthday problem.

However, $2^{512}$ is so large that with overwhelming probability this will never happen in practice. As this is a statistical property it is also not possible for an attacker to increase that probability. Hence, you can safely assume that this behaves like a PRG that is not periodic.