8
$\begingroup$

If I have a poor PRNG, could a cryptographically secure hash function make a better output?

Say the PRNG can produce as much numbers as you wish, reasonably random, but not good enough to be used in crypto applications.

If I split the PRNG output into chunks, say $128..512$ bits, and feed those to a cryptographically secure hash function, could it be that the result is somehow "better" or more secure than the original pseudo random string?

If I got it right Fortuna does something like that. Could it be?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

Yes, you can certainly do this, and there has been a lot of theoretical work in the area. At a high level, what this is called is a randomness extractor (Wikipedia):

A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weakly random entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent from the source and uniformly distributed.

Dodis, et. al. study different practical constructions of randomness extraction, including using CBC-MAC, Cascade, and HMAC. Your proposal is most similar to the Cascade method they talk about. For which they say:

In Section 4 we study the cascade (or Merkle-Damgard) chaining used in common hash functions such as MD5 and SHA-1. We show these families to be good extractors when modeling the underlying compression function as a family of random functions. However, in this case we need a stronger assumption on the entropy of the input distribution.

See the paper for the exact requirements. It has been a little while since I have thoroughly parsed that paper, but I believe that CBC-MAC and HMAC have better security guarantees (fewer assumptions).

Another paper you may be interested in is A model and architecture for pseudo-random generation with applications to /dev/random by Barak and Halevi. They present a construction which uses an extractor to build a PRNG. They note that their construction is similar to Fortuna. They do list some potential issues they see with the Fortuna construction that you may find interesting (depending on what you are really trying to accomplish). For their extractor in $\S$4.1, they describe some of the tradeoffs between using AES-CBC and HMAC-SHA1 and in the end state that:

A candidate cipher for this implementation is Rijndael, which has a variant with 256-bit blocks. (This last alternative would probably be our choice if we had to actually implement a robust generator.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Hmm... if the input is still pseudo random (and thus deterministic), this approach can run out of different states. The amount of bits of internal state of different PRNGs varies and could be rather low. Unless one has any sort of source of true randomness, one risks ending up with only, say, 2^64 different reasonably random sequences or some such. $\endgroup$
    – Eugene Ryabtsev
    Commented Jul 20, 2015 at 14:44
  • $\begingroup$ @EugeneRyabtsev, you are correct. No deterministic process can increase the amount of entropy. That is the whole point of a randomness extractor, it increases the entropy rate. Given a long string of bits (say thousands of bits) with a low entropy rate, we can create a much shorter string (say hundreds of bits) that has a higher entropy rate (say close to 1). $\endgroup$
    – mikeazo
    Commented Jul 20, 2015 at 14:58
  • $\begingroup$ Yep. The "entropy" tag was not added by the asker, who mentioned only a PRNG, and you talk low-entropy sources (bad RNGs, not bad PRNGs), so I'm just making sure it connects. $\endgroup$
    – Eugene Ryabtsev
    Commented Jul 20, 2015 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.