5 ms·

Race Conditions == Random Number Generation

91 points by dasmithii 12y ago

emhs 12y ago
Color me impressed. I do wonder if there's any way to reliably influence the pattern of the mutations. On the surface, with the differences in thread-scheduling patterns, I'd say it seems like a meaningful improvement on the randomness of the system PRNG. If you have a sufficiently well-developed model of thread-scheduling patterns, then the randomness reduces in quality to that of the system's PRNG. But thread-scheduling is a serious pain, so this seems promising.
- gh02t 12y ago
  I'm pretty sure you can reduce the entropy of the output by saturating the processor or memory. If the various accesses are being spread out more because other processes are executing then you're going to have substantially less entropy. Sounds like bait for a DoS attack... hit the server really hard and all of a sudden the RNG is producing bad random numbers. I doubt it's more efficient than something like Mersenne Twister. Generating entropy this way is pretty damn expensive in terms of processor cycles.
breathoftea 12y ago
generator.c: // For each byte in the buffer, use its value to index into another // byte and XOR the two. This seems to be the only mixing that happens in the entire algorithm, after the initial rand seeding. I'm not a cryptographer, but this smells extremely insecure to me. If the random seed is all zeroes this generator will generate all zeroes for perpetuity, no? 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. Please children, don't do your own crypto.
- mcross 12y ago
  It also uses 100% CPU until the threads are stopped. The author did not make any claims that it was cryptographically secure. It's just a toy that he shared - an interesting way to perhaps generate something useful from something that is normally undesirable.
  - dasmithii 12y ago
    I suppose the 100% CPU is (very) unnecessary. Maybe I'll include a variable sleeping time determined by current buffer values. That way, thread synchronization would be further disorganized, and CPU power wouldn't be wasted quite as much. In that case, it's important that mutations take place between every byte outputted tough.
- nathan7 12y ago
  The visualisation means next to nothing for proving it's good. But the visualisation seems to show patterns, which says plenty.
  - dasmithii 12y ago
    It seems to be an improvement from the notoriously poor rand() of PHP. (not confident in the credibility of this article) http://boallen.com/assets/images/randbitmap_computer.png http://boallen.com/assets/images/randbitmap_computer.png
    - ars 12y ago
      It's not a PHP function, it's a C library function that PHP is using. On Linux rand() doesn't suffer from the problem.
  - LnxPrgr3 12y ago
    If I look at it too long, I see "patterns" in the output of OS X's /dev/random too: http://codeanarchy.com/files/yarrow.png http://codeanarchy.com/files/yarrow.png Random doesn't always look random. To make matters worse, we're biased towards seeing patterns in noise: http://en.wikipedia.org/wiki/Clustering_illusion http://en.wikipedia.org/wiki/Clustering_illusion
    - praptak 12y ago
      ...and my repost from https://news.ycombinator.com/item?id=4821942 https://news.ycombinator.com/item?id=4821942. A bookmarklet (paste in address bar) to show truly random and "evened out" dot distributions side by side. (Don't laugh at my Javascript): javascript:"<html><body><canvas id=\"tutorial\" width=\"200\" height=\"200\">foo</canvas><-><canvas id=\"tutorial2\" width=\"200\" height=\"200\">foo</canvas><script>var canvas = document.getElementById('tutorial');var ctx = canvas.getContext('2d');ctx.fillStyle = \"rgb(000,0,0)\";for (var i=0;i<400;i++) {ctx.fillRect (Math.random() * 200,Math.random() * 200, 2, 2); };</script><script>var canvas = document.getElementById('tutorial2');var ctx = canvas.getContext('2d');ctx.fillStyle = \"rgb(000,0,0)\";for (var i=0;i<20;i++) for(var j=0;j<20;j++) for(k=0;k<1;k++) {ctx.fillRect (i * 10 + Math.random() * 10, j * 10 + Math.random() * 10, 2, 2); };</script></body></html>"
- deleted 12y ago
  [deleted]
heavenlyhash 12y ago
This is a remarkably poor idea. Thread scheduling may be difficult to predict precisely. This is a radically different property than being random. 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's less obvious, but most certainly enough to beat the house in any gamble. Which thread wins race conditions is certainly not random. CPU cache lines will create biases, the implementation of your processor's pipelining of memory fences is likely predictable, and on and on. Use a CSPRNG. A counterargument might begin with "But I don't need cryptographically valid randomness!", to which I would respond "then why are you thinking about this at all?" 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't need cryptographic randomness, then there are other even faster sources of psudeorandomness; use those, not this mechanism for creating CPU waste heat.
- sillysaurus3 12y ago
  I don't think the author was presenting this as an alternative to a CSPRNG. (Or rather, I hope they weren't.) It seems like more of a fun hack than anything else. I wish they explicitly warned people not to actually use this, but it's still an interesting side project.
  - heavenlyhash 12y ago
    Right. As an amusement, this is great, and I can hardly improve upon the visual aid of monkeys frenzying over a lego structure. And indeed even as an educational opportunity to explore how very much not-random CPU scheduling over unguarded memory is, this is also probably a gem. But I should hate to see anyone mistake this concept for useful.
    - dasmithii 12y ago
      I've added a note in the readme. Sorry to have been misleading.
gamegoblin 12y ago
Using OS thread functionality to do some useful work is always amusing. 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.
- dasmithii 12y ago
  Interesting. Though sleep sort is obnoxious (& hilarious), I'm sure it could be of use in educational situations. It's both elegant and intuitive. Thought provoking, maybe?
  - AnthonyMouse 12y ago
    In reality sleep sort is not actually doing the sorting, it's just asking the OS to do it using a traditional sorting algorithm, because the OS will have to sort all the sleep timers to determine the order in which to wake up the threads.
    - personjerry 12y ago
      I think that's only true in a single threaded system
      - jacquesm 12y ago
        No, the OS still needs to maintain a sorted list, and that list likely has either a single thread that maintains it or some locking mechanism. Whenever the OS is looking for something to run it will inspect the head of that list to see if the current time >= the time at which that thread should be woken up. And if it can't find anything there then it will check the 'runnable' queue (processes that are CPU bound) and if there is nothing there then it will default to some idle loop.
    - deleted 12y ago
      [deleted]
    - 12y ago
joshribakoff 12y ago
Those who are pointing out that the CPU & 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 & predict what it will settle on before it is settled. There may be no concept of "random", only more or less predictable to humans or algorithms they create.
- dasmithii 12y ago
  [author here] It's difficult to have meaningful discussion (w/ regard to randomness) when involving more philosophical principles. For those who believe wholeheartedly in a deterministic universe, the concept is utter nonsense. That's why it's important that pragmatic folk focus on practical and statistical randomness, rather than universal randomness. By practical, I mean that the information required to predict generated numbers is simply not available. It may exist; it may not; but regardless, it's inaccessible to those in need of it. In this case, I'm not certain if sufficient thread-scheduling information is available to derive accurate predictions, or if separate processes could be of effect without altering the speed at which RNG state mutation occurs simultaneously. Being interdependent on other thread & process CPU usage, my approach might be another case of "the act of observation changing the thing observed". But then again, I'm know little of both cryptography and CPU scheduling. This comment, like this project, is largely speculative.
  - Eridrus 12y ago
    The issue I've always had with this & dakarand are that they might not be easily predictable, but it is probably possible to influence their output into something you can more easily predict.
- pjc50 12y ago
  There's a book "The Newtonian Casino" which describes doing something similar with roulette wheels .. in the 1980s.
- DanBC 12y ago
  Doesn't "sensitive dependance on initial conditions" place severe limitations on what we can predict?
joshribakoff 12y ago
Those who are pointing out that order the threads finish in are deterministic at the atomic level 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 & predict what it will settle on before it is settled. There may be no concept of "random".
cpeterso 12y ago
My silly random number generator: strace -Tiv -ttt nice -n 19 curl -Lv --raw https://google.com/news https://google.com/news 2>&1 | shasum -a 512 | dd bs=1 count=2 2>/dev/null This assumes Google News serves frequently changing content. The noncanonical Google News URL generates extra entropy from an HTTP 302 Moved Temporarily to an HTTP 301 Moved Permanently to an HTTP 200 OK with the final news page. strace and nice and curl add entropy from OS syscall timings and HTTP headers. (OS X doesn't have strace, so you can just skip it.)
- bdhe 12y ago
  A lot of the time, the randomness used must be secret (for nonces etc.) but your solution is an interesting way to implement a CRS (http://en.wikipedia.org/wiki/Common_reference_string_model http://en.wikipedia.org/wiki/Common_reference_string_model) which is very useful in some cryptographic primitives. A CRS is a common string, typically random, that anyone can access, but cannot be controlled by any one party. Another typical thought-implementation of this is using stock market prices -- predict those accurately and you'd do better things with your time than break some crypto protocols.
jokoon 12y ago
I'm not sure undefined behaviors are so much unpredictable...
sklivvz1971 12y ago
I'd find it way more interesting if it started from a non-random buffer. Like this I can't tell how much of the randomness comes from the initial seed...
ctz 12y ago
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.
baq 12y ago
run it through dieharder please, just for fun.
deutronium 12y ago
I made a silly one that uses the GPU to generate numbers. http://www.anfractuosity.com/projects/rndgpu/ http://www.anfractuosity.com/projects/rndgpu/
exDM69 12y ago
To the OP: for additional amusement and possibly some educational epiphanies, try compiling and running this on your smartphone (assuming it's a multi core ARM). 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're in kernel space. I expect that on ARM, you'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.
atoponce 12y ago
How does this compare to dakarand? http://dankaminsky.com/2012/08/15/dakarand/ http://dankaminsky.com/2012/08/15/dakarand/
yuhong 12y ago
I think the Linux /dev/random already do this to some extent.

91 points by dasmithii 12y ago

emhs 12y ago

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

gh02t 12y ago
I'm pretty sure you can reduce the entropy of the output by saturating the processor or memory. If the various accesses are being spread out more because other processes are executing then you're going to have substantially less entropy. Sounds like bait for a DoS attack... hit the server really hard and all of a sudden the RNG is producing bad random numbers. I doubt it's more efficient than something like Mersenne Twister. Generating entropy this way is pretty damn expensive in terms of processor cycles.

breathoftea 12y ago

generator.c: // For each byte in the buffer, use its value to index into another // byte and XOR the two. This seems to be the only mixing that happens in the entire algorithm, after the initial rand seeding. I'm not a cryptographer, but this smells extremely insecure to me. If the random seed is all zeroes this generator will generate all zeroes for perpetuity, no? 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. Please children, don't do your own crypto.

mcross 12y ago
It also uses 100% CPU until the threads are stopped. The author did not make any claims that it was cryptographically secure. It's just a toy that he shared - an interesting way to perhaps generate something useful from something that is normally undesirable.
- dasmithii 12y ago
  I suppose the 100% CPU is (very) unnecessary. Maybe I'll include a variable sleeping time determined by current buffer values. That way, thread synchronization would be further disorganized, and CPU power wouldn't be wasted quite as much. In that case, it's important that mutations take place between every byte outputted tough.
nathan7 12y ago
The visualisation means next to nothing for proving it's good. But the visualisation seems to show patterns, which says plenty.
- dasmithii 12y ago
  It seems to be an improvement from the notoriously poor rand() of PHP. (not confident in the credibility of this article) http://boallen.com/assets/images/randbitmap_computer.png http://boallen.com/assets/images/randbitmap_computer.png
  - ars 12y ago
    It's not a PHP function, it's a C library function that PHP is using. On Linux rand() doesn't suffer from the problem.
- LnxPrgr3 12y ago
  If I look at it too long, I see "patterns" in the output of OS X's /dev/random too: http://codeanarchy.com/files/yarrow.png http://codeanarchy.com/files/yarrow.png Random doesn't always look random. To make matters worse, we're biased towards seeing patterns in noise: http://en.wikipedia.org/wiki/Clustering_illusion http://en.wikipedia.org/wiki/Clustering_illusion
  - praptak 12y ago
    ...and my repost from https://news.ycombinator.com/item?id=4821942 https://news.ycombinator.com/item?id=4821942. A bookmarklet (paste in address bar) to show truly random and "evened out" dot distributions side by side. (Don't laugh at my Javascript): javascript:"<html><body><canvas id=\"tutorial\" width=\"200\" height=\"200\">foo</canvas><-><canvas id=\"tutorial2\" width=\"200\" height=\"200\">foo</canvas><script>var canvas = document.getElementById('tutorial');var ctx = canvas.getContext('2d');ctx.fillStyle = \"rgb(000,0,0)\";for (var i=0;i<400;i++) {ctx.fillRect (Math.random() * 200,Math.random() * 200, 2, 2); };</script><script>var canvas = document.getElementById('tutorial2');var ctx = canvas.getContext('2d');ctx.fillStyle = \"rgb(000,0,0)\";for (var i=0;i<20;i++) for(var j=0;j<20;j++) for(k=0;k<1;k++) {ctx.fillRect (i * 10 + Math.random() * 10, j * 10 + Math.random() * 10, 2, 2); };</script></body></html>"
deleted 12y ago
[deleted]

heavenlyhash 12y ago

This is a remarkably poor idea. Thread scheduling may be difficult to predict precisely. This is a radically different property than being random. 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's less obvious, but most certainly enough to beat the house in any gamble. Which thread wins race conditions is certainly not random. CPU cache lines will create biases, the implementation of your processor's pipelining of memory fences is likely predictable, and on and on. Use a CSPRNG. A counterargument might begin with "But I don't need cryptographically valid randomness!", to which I would respond "then why are you thinking about this at all?" 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't need cryptographic randomness, then there are other even faster sources of psudeorandomness; use those, not this mechanism for creating CPU waste heat.

sillysaurus3 12y ago
I don't think the author was presenting this as an alternative to a CSPRNG. (Or rather, I hope they weren't.) It seems like more of a fun hack than anything else. I wish they explicitly warned people not to actually use this, but it's still an interesting side project.
- heavenlyhash 12y ago
  Right. As an amusement, this is great, and I can hardly improve upon the visual aid of monkeys frenzying over a lego structure. And indeed even as an educational opportunity to explore how very much not-random CPU scheduling over unguarded memory is, this is also probably a gem. But I should hate to see anyone mistake this concept for useful.
  - dasmithii 12y ago
    I've added a note in the readme. Sorry to have been misleading.

gamegoblin 12y ago

Using OS thread functionality to do some useful work is always amusing. 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.

dasmithii 12y ago
Interesting. Though sleep sort is obnoxious (& hilarious), I'm sure it could be of use in educational situations. It's both elegant and intuitive. Thought provoking, maybe?
- AnthonyMouse 12y ago
  In reality sleep sort is not actually doing the sorting, it's just asking the OS to do it using a traditional sorting algorithm, because the OS will have to sort all the sleep timers to determine the order in which to wake up the threads.
  - personjerry 12y ago
    I think that's only true in a single threaded system
    - jacquesm 12y ago
      No, the OS still needs to maintain a sorted list, and that list likely has either a single thread that maintains it or some locking mechanism. Whenever the OS is looking for something to run it will inspect the head of that list to see if the current time >= the time at which that thread should be woken up. And if it can't find anything there then it will check the 'runnable' queue (processes that are CPU bound) and if there is nothing there then it will default to some idle loop.
  - deleted 12y ago
    [deleted]
  - 12y ago

joshribakoff 12y ago

Those who are pointing out that the CPU & 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 & predict what it will settle on before it is settled. There may be no concept of "random", only more or less predictable to humans or algorithms they create.

dasmithii 12y ago
[author here] It's difficult to have meaningful discussion (w/ regard to randomness) when involving more philosophical principles. For those who believe wholeheartedly in a deterministic universe, the concept is utter nonsense. That's why it's important that pragmatic folk focus on practical and statistical randomness, rather than universal randomness. By practical, I mean that the information required to predict generated numbers is simply not available. It may exist; it may not; but regardless, it's inaccessible to those in need of it. In this case, I'm not certain if sufficient thread-scheduling information is available to derive accurate predictions, or if separate processes could be of effect without altering the speed at which RNG state mutation occurs simultaneously. Being interdependent on other thread & process CPU usage, my approach might be another case of "the act of observation changing the thing observed". But then again, I'm know little of both cryptography and CPU scheduling. This comment, like this project, is largely speculative.
- Eridrus 12y ago
  The issue I've always had with this & dakarand are that they might not be easily predictable, but it is probably possible to influence their output into something you can more easily predict.
pjc50 12y ago
There's a book "The Newtonian Casino" which describes doing something similar with roulette wheels .. in the 1980s.
DanBC 12y ago
Doesn't "sensitive dependance on initial conditions" place severe limitations on what we can predict?

joshribakoff 12y ago

Those who are pointing out that order the threads finish in are deterministic at the atomic level 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 & predict what it will settle on before it is settled. There may be no concept of "random".

cpeterso 12y ago

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

bdhe 12y ago
A lot of the time, the randomness used must be secret (for nonces etc.) but your solution is an interesting way to implement a CRS (http://en.wikipedia.org/wiki/Common_reference_string_model http://en.wikipedia.org/wiki/Common_reference_string_model) which is very useful in some cryptographic primitives. A CRS is a common string, typically random, that anyone can access, but cannot be controlled by any one party. Another typical thought-implementation of this is using stock market prices -- predict those accurately and you'd do better things with your time than break some crypto protocols.

jokoon 12y ago

I'm not sure undefined behaviors are so much unpredictable...

sklivvz1971 12y ago

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

ctz 12y ago

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.

baq 12y ago

run it through dieharder please, just for fun.

deutronium 12y ago

I made a silly one that uses the GPU to generate numbers. http://www.anfractuosity.com/projects/rndgpu/ http://www.anfractuosity.com/projects/rndgpu/

exDM69 12y ago

To the OP: for additional amusement and possibly some educational epiphanies, try compiling and running this on your smartphone (assuming it's a multi core ARM). 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're in kernel space. I expect that on ARM, you'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.

atoponce 12y ago

How does this compare to dakarand? http://dankaminsky.com/2012/08/15/dakarand/ http://dankaminsky.com/2012/08/15/dakarand/

yuhong 12y ago

I think the Linux /dev/random already do this to some extent.