Can a PRNG be made into a CSPRNG by hashing the outputs?

Question

So I was contemplating this answer to my last question, and it got me thinking:

If I understand it right, one of the required properties of a CSPRNG is that it resists leaking information about its internal state from the outputs it produces.

So say we have a PRNG that meets all other properties of a CSPRNG (I do not yet trust myself to know what all those are), but is suspected of leaking too much of its state in the outputs.

My intuition is that we can maybe make it a CSPRNG by running its outputs through a hashing algorithm already known to be suitable for cryptography.

An example: say the PRNG has 128 bits of state, and produces 128-bit numbers as its output. If I were to, say, run it 8 times, I would have 1024 bits. Say I then feed that into SHA-512/256 or similar, and return the two 128-bit pieces of the digest as the new outputs.

So in this example I get two outputs of my new composed PRNG for every eight runs of the underlying PRNG. This might be less efficient than a proper CSPRNG, and might have washed out whatever other properties the PRNG might have had. But is it now a CSPRNG?

I suspect the answer is either "no" or "only if the original PRNG [...]" or maybe at best "the general gist is in the right direction but your specific example would not be because [...]", or some combination of those.

I also know that naive attempts to compose primitives like this without proper understanding can actually cause other problems.

It just occurred to me that some operations, like XOR and the hashing functions used in cryptography, can "destroy" information, in the sense that more than one possible input can produce the same output, while still retaining the right "randomness" properties.

That naively seems like what we need to reduce how much a PRNG's outputs reveal about its state, and I'm looking for some check if that is right or in what ways it is wrong.

And it seems like "can I turn a PRNG into a CSPRNG by running a secure hash on all of its outputs?" is a good question to explore at least some of that.

Answer 1

No, the question's construction is not guaranteed to turn a PRNG into a CSPRNG. In some cases, the hashing worsens the generator. In more, undesirable characteristics remain detectable after hashing. There are better methods to build a CSPRNG from a hash.

---

The question's construction, hereafter WBCSPRNG for Would-Be Cryptographicaly Secure Pseudo RNG, is a PRNG with the same input characteristics and state size (within a few bits depending on how that's counted) as the original PRNG. It has a period demonstrably not smaller than the PRNG by a large factor (at worse 1024/256=4) under the hypothesis that the hash behaves as a random oracle. I do not see anything else comforting that can be said unless we add some hypothesis about the PRNG.

In particular, we can devise a PRNG, with a large state and long period, such that the WBCSPRNG fails most existing PRNG test suites, when the original PRNG consistently passes them. Start from a good CSPRNG, and modify it so that after having output 1023 bits, the next bit is produced by hashing these and a zero bit, summing the 256 bits yielding $b\in[0,256]$, outputting zero if $b<128$, one if $b>128$, and the low-order bit of the hash otherwise.

Our constructed PRNG is no longer a CSPRNG, but still pass any pre-existing RNG test (no pre-existing RNG test will catch how the extra bit is generated). Yet the WBCSPRNG is biased towards zero, and most RNG test suites will detect that.

---

The above counterexample is maliciously constructed, and in a way that needs to know the hash, which we could forbid. That's not good enough: a whole class of accidental defects are amplified. For example, if a PRNG has the undesirable characteristic that the first 1024-bit block of each 2⁴²-bit output block is identical, the WBCSPRNG has the characteristic that the first 256-bit block of each 2⁴⁰-bit output block is identical, which is likely to cause issue sooner.

The hypothesis when academically evaluating the security of a CSPRNG is that its design is public, here including the WCSPRNG's hash step and the PRNG. If the PRNG has the characteristic that a class of 1024-bit blocks are likely to appear in its output, that again can be detectable in the WCSPRNG output, after testing 4 times less bits.

---

The method has no practical interest as a way to construct a CSPRNG, for we do not need a PRNG to make a CSPRNG out of a hash such as SHA-512/256, and one more efficient than the question's one: we hash the seed input, set a counter to that, then to produce 256 bits of output we hash the state then increment it.