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:
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.
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.
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.