Randomness

I'm not sure treeprng is "pseudorandom enough" (let's say "PRE"), never mind secure, so allow me to reiterate:

WARNING:You may have noticed that this code calls a cryptographic hash function. That does NOT mean this code is secure. treeprng is NOT a cryptographic pseudorandom number generator. Do NOT use it in a crypto or security-sensitive application.

---

Of course whether treeprng is PRE raises the question what PRE means in this context.

HowItWorks describes how uses of the API translate into hash digests that become the pseudorandom bits, and how a typical use might involve lots of small variations on inputs to the hash.

One type of problem would be hash collisions being more likely than birthday paradox calculations would suggest.

Another type of problem would be if hash outputs got bad grades in standard PRNG statistical tests, e.g. the TryHarder suite.

For both issues the possible ways a program might seed the tree adds to the complexity, especially if outputs are fed back into seeds. There are certainly ways to find loops in random functions, but I believe these take on the order of a birthday-paradox of work, ~sqrt(2 ** digest size). And a program could easily produce arbitrarily smaller loops or more likely collisions by truncating the outputs. I would like an easy rule of thumb about how not to build a bad PRNG out of a good PRNG.

--SteveWitham