Race Conditions == Random Number Generation

My silly random number generator:<p>strace -Tiv -ttt nice -n 19 curl -Lv --raw <a href="https://google.com/news" rel="nofollow">https:&#x2F;&#x2F;google.com&#x2F;news</a> 2&gt;&amp;1 | shasum -a 512 | dd bs=1 count=2 2&gt;&#x2F;dev&#x2F;null<p>This assumes Google News serves frequently changing content. The noncanonical Google News URL generates extra entropy from an <i>HTTP 302 Moved Temporarily</i> to an <i>HTTP 301 Moved Permanently</i> to an <i>HTTP 200 OK</i> with the final news page. strace and nice and curl add entropy from OS syscall timings and HTTP headers.<p>(OS X doesn&#x27;t have strace, so you can just skip it.)

Using OS thread functionality to do some useful work is always amusing.<p>This reminds me of sleep sort. For those unfamiliar, sleepsort is where you have an unsorted array, then have 1 thread per element sleep for the amount of time specified by that element, then append it to a list.

This is a remarkably poor idea.<p>Thread scheduling may be difficult to predict precisely. This is a radically different property than being random.<p>A good source of randomness is becomes no more predictable given previous outputs. Being able to predict the next output precisely would obviously break a random number generator. But being able to weight the odds of the next output also break a random number generator; it&#x27;s less obvious, but most certainly enough to beat the house in any gamble.<p>Which thread wins race conditions is certainly not random. CPU cache lines will create biases, the implementation of your processor&#x27;s pipelining of memory fences is likely predictable, and on and on.<p>Use a CSPRNG.<p>A counterargument might begin with &quot;But I don&#x27;t need cryptographically valid randomness!&quot;, to which I would respond &quot;then why are you thinking about this at all?&quot; Cryptographically valid randomness is not hard from either a programmer braintime perspective (there are libraries, unless you take up deep issues with modern CSPRNGs) or a CPU-time perspective (CSPRNGs can spit bytes faster than your disk can accept them). If you don&#x27;t need cryptographic randomness, then there are other even faster sources of psudeorandomness; use those, not this mechanism for creating CPU waste heat.

I once found a bad implementation of this idea in a common commercial crypto library. I calculated from observation of a bunch of runs that they were achieving about 45 bits of entropy in practice, and taking six seconds of wall time and a shitload of power in the process.

To the OP: for additional amusement and possibly some educational epiphanies, try compiling and running this on your smartphone (assuming it&#x27;s a multi core ARM).<p>The cache coherency rules are different in ARM and Intel CPUs, you should see quite different result from unsynchronized access to same memory locations. On ARM, you need to be more careful with explicit memory barriers, especially when you attempt to write lock-free code, or you&#x27;re in kernel space.<p>I expect that on ARM, you&#x27;re going to see a lot less random because an entire cache line written to by one core will replace another cache line written to by another core, thereby showing only the randomness contribution of one core.

I made a silly one that uses the GPU to generate numbers.<p><a href="http://www.anfractuosity.com/projects/rndgpu/" rel="nofollow">http:&#x2F;&#x2F;www.anfractuosity.com&#x2F;projects&#x2F;rndgpu&#x2F;</a>

Color me impressed. I do wonder if there&#x27;s any way to reliably influence the pattern of the mutations. On the surface, with the differences in thread-scheduling patterns, I&#x27;d say it seems like a meaningful improvement on the randomness of the system PRNG.<p>If you have a sufficiently well-developed model of thread-scheduling patterns, then the randomness reduces in quality to that of the system&#x27;s PRNG. But thread-scheduling is a serious pain, so this seems promising.

run it through dieharder please, just for fun.

How does this compare to dakarand? <a href="http://dankaminsky.com/2012/08/15/dakarand/" rel="nofollow">http:&#x2F;&#x2F;dankaminsky.com&#x2F;2012&#x2F;08&#x2F;15&#x2F;dakarand&#x2F;</a>

I&#x27;d find it way more interesting if it started from a non-random buffer. Like this I can&#x27;t tell how much of the randomness comes from the initial seed...

Those who are pointing out that the CPU &amp; threads operate in a deterministic manner should consider that the universe may operate under the same principles. Maybe some day a computer can watch live video of someone rolling a die &amp; predict what it will settle on before it is settled. There may be no concept of &quot;random&quot;, only more or less predictable to humans or algorithms they create.

I think the Linux &#x2F;dev&#x2F;random already do this to some extent.

generator.c:<p><pre><code> &#x2F;&#x2F; For each byte in the buffer, use its value to index into another &#x2F;&#x2F; byte and XOR the two. </code></pre> This seems to be the <i>only</i> mixing that happens in the entire algorithm, after the initial rand seeding.<p>I&#x27;m not a cryptographer, but this smells <i>extremely</i> insecure to me. If the random seed is all zeroes this generator will generate all zeroes for perpetuity, no?<p>Even if you get a decent initial seed, I still strongly suspect this RNG strategy will be very statistically leaky, will tend to equilibria, and will generally be easily breakable in practice. An RGB visualization in the context of RNG means next to nothing.<p>Please children, don&#x27;t do your own crypto.

I&#x27;m not sure undefined behaviors are so much unpredictable...