Can I make a PRNG that is secure even when state can be modified by user?

Question

I am interested in making a PRNG which, after being initially seeded, can accept and incorporate client data as the only ongoing source of "entropy". It is not directly for a cryptographic purpose, but I wish to get a sense of how much the resulting system might compromise the integrity of the generator.

A simplified design based on SHA1, might be:

1. Internal state is 160 bits, initially set from a source of good entropy (assume this source cannot be attacked), and hidden from all client systems.

2. Generator is a SHA1 of the internal state - let's call it Foo.rand():

   a. The return value sent to client is 80 bits, A xor B, where A is first 80 bits and B second 80 bits of the original digest.

   b. The internal state changed by xor-ing it with the original 160-bit digest.

3. The client system can at any time send a 160-bit string and it will be xor-ed with the current internal state. Let's call this Foo.alter_state( data ). In reality there might be some transformations, and access to the whole state at once is not likely either. But I think this captures the essence of what I am doing in a worst-case scenario.

figlesquidge helpfully commented more formal notation for the above: \begin{align} \mathbf{Init}_s(k):& s\leftarrow k &\text{where secret key $k$ has full ($2n$-bit) entropy} \\ \mathbf{Update}_s(v):& s \leftarrow s\oplus v &\text{Add to digest state} \\ \mathbf{Read}_s:& h \leftarrow H(s) &\text{for some secure hash function $H$} \\ & \mathrm{Update}_s(h) \\ & d \leftarrow \mathrm{MSB}_n(h) \oplus \mathrm{LSB}_n(h) \\ & \mathrm{Return} \ d \end{align}

The end user might turn "attacker" (in essence they have agreed to use the PRNG as a source of randomness, but have a vested interest in controlling the values output by Foo.rand()). Such an attacker has full knowledge of the above, and can call Foo.rand() and Foo.alter_state( data ) completely freely, but cannot peek at the internal state directly. Is there any way that they could discover the internal state via these methods more efficiently than brute-forcing the initial or current value?

If there is an attack better than brute-forcing the state, is it predictably constrained (e.g. it is equivalent to brute-forcing something with half or quarter the number of state bits,so I could increase the size of initial state and maintain an attitude of "not as secure as a cryptographic PRNG with the same size of internal state, but still not hackable for practical purposes")?

I tried to think through some attacks on this system, but am not anywhere near experienced enough to judge whether I have missed something obvious.

I think one key aspect of the system is folding the digest in step 2a - it ensures that an attacker cannot use Foo.alter_state( data ) to repeatedly set the state back to an unknown but identical original, and probe the effects of changing each bit. But is it enough? Does this still leak too much state?

The choice of SHA1 is for simplicity, and any cryptographic hash would do (in theory). I could also consider an HMAC variant if that helped in any way. E.g. instead of simply folding the digest in step 2a, the return value was the HMAC of the original digest, and the secret for the HMAC would be set using a good entropy source, kept hidden and not altered. I feel this would probably mean even if the initial system was easily compromised, the worst-case scenario would resolve to brute-forcing the secret. However, I'd like to know that I was doing this for a reason, and not just cryptalchemy.

Answer 1

This is not secure. There is a distinguishing attack that involves about $2^{41}$ invocations of the interface.

Define $f(x) = \text{MSB}_{80}(x) \oplus \text{LSB}_{80}(x)$. Consider applying the following operation, which I'll call "Leap":

1. Call Read. Call the result $d$.

2. Call Update $(0 \, || \, d)$ (i.e., call Update passing the 160-bit value obtained by concatenating 80 zero bits followed by $d$).

Notice that if $s$ is the state before a Leap operation and $s'$ is the state afterwards, then $f(s)=f(s')$.

The attack will involve applying the Leap operation about $2^{40}$ times. If you examine the internal state $s_i$ after the $i$th Leap operation, it will satisfy $f(s_i)=c$, where $c$ is some constant that is the same for all of them (in fact, $c=f(k)$, where $k$ is the initial state).

Thus, each $s_i$ comes from a space of $2^{80}$ possibilities, and each $s_i$ is basically a random element from that space. Now by the birthday paradox, once you have $2^{40}$ randomly chosen elements from a universe of size $2^{80}$, there is a pretty good chance that some pair of those elements will be the same. This means we expect to find some indices $i,j$ such that $s_i=s_j$, i.e., where the state after the $i$th Leap operation is the same as the state after the $j$th Leap operation.

But of course the behavior of the PRNG is a deterministic function of the state. Therefore, the behavior of the PRNG at time $i+t$ will be the same as the behavior at time $j+t$. In particular, the sequence of outputs at times $j,j+1,j+2,\dots$ will be a repeat of the sequence of outputs at times $i,i+1,i+2,\dots$.

In other words, if you perform a bunch of Leap operations, the PRNG will enter a cycle and start repeating after about $2^{40}$ steps. This is too fast. It's something that a true-random generator would not exhibit. It allows to distinguish the output of the PRNG from truly random, and to predict future outputs (assuming we continue to apply Leap operations).

By academic standards, this would count as a break of the PRNG, since $2^{40}$ operations is feasible. By practical standards, it might not be an enormous risk, because it requires that the adversary has a way to alternate Read and Update operations and that the adversary has total control over all of the Update operations -- but it's still a break, by the standards that cryptographers use.

A possible fix would be to change your Update operation to

$$s \gets H(s,v).$$