Comment by eslaught | Hacker News Reader

Comment by eslaught | Hacker News Reader

Parent Full thread

> decoupling the global PRNG into several independent ones

Given this is 2020, I'm guessing you probably already solved this one, but this is something I had to do for a concurrent fuzzer I wrote recently.

Basically my solution is to make SipHash the PRNG. The way this works is you make a tuple of your seed and any other information you want to hash (at minimum, a "channel" number, so you get different streams of random numbers, and a sequence number). You hash the tuple and increment the sequence number and return.

Because it's literally just a hash function, it's easy to reason about its properties: same input in, same output out. As long as the hash function is high enough quality, you avoid bias in the output even when the input has low entropy (thus why I chose SipHash).

There's an Apache-licensed implementation here for anyone who cares. My implementation has streams inside each channel associated with hashable objects, just to make it easier to subdivide the channels.

https://github.com/StanfordLegion/fuzzer/blob/master/src/det...

https://github.com/StanfordLegion/fuzzer/blob/master/src/det...

https://github.com/StanfordLegion/fuzzer/blob/master/src/det...

> Because it's literally just a hash function, it's easy to reason about its properties: same input in, same output out.

Don't all PRNGs have this property?

Hash based PRNGs can be surprisingly tricky to reason about. For example, the other common way to turn hash functions into PRNGs (state = hash{state}) often leads to severe flaws from state space collapse, among other issues.

Can you explain what you mean by state space collapse?

Basically, state space collapse is when the state space of the PRNG is substantially lower than what it "should" be given the number of bits involved. I give an example in the sibling comment with blake2b where the actual period is 10% of the ideal case due to rho structures.

Thanks, this is fascinating.

Re-reading your comment above, I had missed that you were assigning the output of the hash function back into the state. I.e., something like:

    state = initial_seed
    def random():
        state = hash(state)
        return state

Whereas I was proposing something more along the lines of:

    seq_num = 0
    def random():
        result = hash([initial_seed, seq_num])
        seq_num += 1
        return result

If I understand correctly, hash collisions (which are inevitable) will cause the former to loop around in a cycle shorter than the size of the theoretical state space. Whereas the latter (I don't think?) suffers from this. But it may still have bad statistical properties, depending on the hash function.

For what it's worth, I did a (very informal) comparison of MurmurHash3 vs SipHash when I started my approach and found that MurmurHash3 (despite being advertised as passing the avalanche test) gave very statistically biased results. Something that should have generated a uniform distribution definitely did not. Whereas when I tested SipHash the output looked (at least to an untrained eye) essentially indistinguishable from a true random source.

Your parallel comment seems to indicate that there isn't a lot of great practical reading on this topic; I don't suppose you've seen a discussion anywhere going through anything like the approaches above, and whether there is a way to do it "properly"?

Yeah, you got it. The construction you used isn't susceptible to this particular flaw, though it still has others (e.g. predictability of the state updates, related-input attacks, etc). If the state size is reasonably close to the output size, you might still have statistical issues for similar reasons that the iterative construction fails. Whether any of these are relevant depends on the context.

I've been meaning to write some kind of public exploration on this stuff so people can tell me some other source explains it better, but haven't made the time to do more than write code like the blake2b demo I had handy to spit out numbers.

Do you know anywhere I could read more about this?

For the mathematical background (i.e. the theory and behavior in idealized models), standard cryptography books are excellent. I recall that both Serious Cryptography and Handbook of Applied Cryptography have excellent introductions to the topic of rho structures that underlie the specific issue I mentioned. Where I've found them lacking is getting a practical understanding of how important these issues are in the specific situations we see in the real world.

For example, if you were to run Blake2b in 8 bit mode with the above construction, what would your PRNG period actually be? In the ideal case it would 2^(8). In practice, the best you'll get is 26 or 10% of the ideal case. There's a significant probability you won't get that either for a given seed, as much of the state space actually drops into a lower period cycle. The issue is that a real hash isn't the correct construction here, even though a mathematically ideal hash would be fine.

I'm not aware of any actual reference material for that kind of stuff and the people I've met who are knowledgeable learned from seeing other's mistakes.

Reply on news.ycombinator.com