9 ms·

The History of Random.org (2009)

176 points by unilynx 7y ago

vortico 7y ago
How does one take a biased noise source source (like atmospheric noise with a certain spectral density) and convert it to a stream of uncorrelated random bits? I've never understood this.
- petters 7y ago
  Simpler problem: how do you take a biased coin and convert it into a perfect source of random bits? You flip the coin twice. If it comes up differently, you pick the first one. Otherwise you repeat. That will produce 50/50 random bits, no matter what the probability of the coin is.
  - devit 7y ago
    Assuming that the probability distribution of each coin flip is independent from previous results.
    - petters 7y ago
      Yes
  - vortico 7y ago
    This case is easy because the coin toss is independent. Radio noise is a time-dependent signal.
    - petters 7y ago
      Still, I thought it was a good starting example for the post I responded to.
    - mbreese 7y ago
      I always had it in my head that the way to do this with a random noise source was to do what is done with radiation. Because radiation is emitted randomly, but time dependent, you can measure the time differences between three (four?) events. If the time between A-B is greater than the time between B-C, the random bit is a one otherwise, it’s a zero. I think it works with just three events, but I’m not sure. You could do the same with audio noise by looking for peaks above a certain value and using a similar time function. I don’t know if that is really how it is done, so I might be misremembering.
- lisper 7y ago
  Take the biased source and run it through a cryptographic hash. As long as the input contains more bits of entropy than the length of the output, the result will be essentially 100% random.
  - vortico 7y ago
    Cool, I think this explains it. What crytographic hashes are available that take a limited stream of bits over time and generate an arbitrary number of bits when requested?
    - lvh 7y ago
      Real CSPRNG designs are a bit more complex, having at least a state (like a hash function) but also an output mechanism to let it generate more bits. One way to do that is to “compress” all your input entropy into a single state, and then use that as the key for a stream cipher, like AESCTR or Salsa20.
    - lisper 7y ago
      Hashes always generate a fixed-size output (that's the definition of a hash). So if you have a hash with an n-bit output, you run it on an input of m>=n bits to get n random bits, then repeat that process as necessary. You choose m so that it contains >= n bits of entropy. When it doubt, overestimate m. You can also "seed" subsequent round of the has with the output from the previous round. That helps protect against certain kinds of failures. It's not really necessary, but it's not hard to do either so you might as well do it.
- bloak 7y ago
  You use a cryptographic hash function. The Linux kernel does something similar for /dev/random: https://en.wikipedia.org/wiki//dev/random https://en.wikipedia.org/wiki//dev/random If you needed to simulate a single fair coin toss using a biased but at least somewhat random coin you might toss it twenty times, feed the sequence of results ("HTHTT...") into sha256sum, and take the first bit of the output.
- i_am_proteus 7y ago
  If the actual distribution of the noise one is sampling from is known, use the CDF of the noise to obtain a true random variable. That's exactly what the biased coin example does.
  - vortico 7y ago
    I imagine this approach would be insecure because an attacker could easily change the distribution from miles away. And I don't think it solves the problem of radio noise being time-dependent random variables.
  - mortehu 7y ago
    The coin toss example works when the distribution is unknown, and relies purely on independence and stationarity.
- mehrdadn 7y ago
  Other people have mentioned how it's done in practice but there have been recent advances on this on the theoretical front as well. Here's one I know of: https://threatpost.com/academics-make-theoretical-breakthrough-in-random-number-generation/118150/ https://threatpost.com/academics-make-theoretical-breakthrou...
- tzs 7y ago
  Here's a pretty good description of how one company does it in their hardware random number generator [1]. Generally along the same lines people have already described, with the addition of testing throughout the process so that you can have some confidence that it is all working. [1] http://www.entropykey.co.uk/tech/ http://www.entropykey.co.uk/tech/
nintendo1889 7y ago
all one has to do is to find their microphone and play repeated noises into it! https://i.guim.co.uk/img/static/sys-images/Film/Pix/pictures/2009/4/30/1241095118372/John-Cusack-in-Say-Anythi-002.jpg?width=300&quality=85&auto=format&fit=max&s=81710795e7c24c765ddfbadc3287ec5c https://i.guim.co.uk/img/static/sys-images/Film/Pix/pictures...
turdnagel 7y ago
Kind of surprised at the lack of information about the current setup, which is certainly most sophisticated and therefore the most interesting. How did they manage to distribute the servers? What are they using now as a source of randomness? Are there still notes on these nodes to keep away?
- deleted 7y ago
  [deleted]
jackfoxy 7y ago
Australian National University generates a random bit stream by measuring the quantum fluctuations of the vacuum. http://qrng.anu.edu.au/index.php http://qrng.anu.edu.au/index.php A few years ago I created a F# .NET library to consume this stream in varying ways. https://jackfoxy.github.io/RandomBits/ https://jackfoxy.github.io/RandomBits/
- doubleunplussed 7y ago
  The fatal flaw of course is that everyone accessing their stream gets the same random data, making it substantially less random in the sense of others not being able to predict it. So do not use for cryptography!
  - qrbLPHiKpiux 7y ago
    I use it for my passwords and I have a icon on my iPhone to get to it quick
  - jackfoxy 7y ago
    I'm not a crypto expert. But I do know this stream is a firehose. Somewhere on the site is says how much data is generated. I forget. Naively I would think at least for some applications there would be no way to determine what part of the stream had been sampled. And the stream connection is over https.
    - progval 7y ago
      > there would be no way to determine what part of the stream had been sampled So the problem become to determine the offset of the stream you looked at, which is an integer that probably fits in 64 bits.
  - unilynx 7y ago
    They're not very explicit, but their FAQ indicates that they are buffering random data and they sometimes even turn the generators off. Which would suggest that they're not repeating the same random data to multiple users Interestingly most clues about how their system work are given in the 'paranormal' section of their FAQ on https://www.random.org/faq/ https://www.random.org/faq/
cpach 7y ago
I really hope that people don’t use random.org in prod. Use /dev/urandom instead. https://sockpuppet.org/blog/2014/02/25/safely-generate-random-numbers/ https://sockpuppet.org/blog/2014/02/25/safely-generate-rando...
- folkhack 7y ago
  You wouldn't believe how many "engineers" I've seen open up random.org's string generator, and fiddle with the settings + copy a string from it only to drop it into a terminal for a root password/etc. Point-in-case, I saw 2-3 "DevOps" engineers do it in my last position... over a screen share..! When you'd bring it up to people they would just roll their eyes and call you paranoid. =(
  - smallbigfish 7y ago
    Devops = not quite a dev + not quite a sys admin.
    - giancarlostoro 7y ago
      Maybe true of junior devops that has never done any sysadmin or much programming outside of school. Theres always people who are skilled at their job in whatever field.
    - ASalazarMX 7y ago
      Devops usually means "it's faster and cheaper because we don't have a dedicated sysadmin". The union of good developers and good syadmins is narrow like that of developers and designers.
      - clwk 7y ago
        I think you mean 'intersection'.
        ASalazarMX 7y ago
alpb 7y ago
Related: Cloudflare offices in SF has a lava lamp wall called LavaRand lava lamps as a secondary source of randomness for their production servers. https://blog.cloudflare.com/randomness-101-lavarand-in-production/ https://blog.cloudflare.com/randomness-101-lavarand-in-produ... https://blog.cloudflare.com/lavarand-in-production-the-nitty-gritty-technical-details https://blog.cloudflare.com/lavarand-in-production-the-nitty... https://www.fastcompany.com/90137157/the-hardest-working-office-design-in-america-encrypts-your-data-with-lava-lamps https://www.fastcompany.com/90137157/the-hardest-working-off...
nemo1618 7y ago
I find it a little concerning that RANDOM.ORG doesn't make it clear that it a trusted service, and cannot be relied on for secure entropy. The only mention is this, buried in the FAQ: >anyone genuinely concerned with security should not trust anyone else (including RANDOM.ORG) to generate their cryptographic keys. But the problems go beyond cryptographic keys. If you use RANDOM.ORG to pick lottery winners, you're trusting that the numbers you get are as truly random as they claim. In particular, the operators of RANDOM.ORG could trivially inject deterministic entropy (generated from, e.g., AES-encrypting successive integers) and this would be completely undetectable, even to statistical tests. IMO the site needs a big, scary disclaimer on the front page that describes what applications it is appropriate for, and which ones should use a more secure source of entropy.
- dorfsmay 7y ago
  Typo? Did you mean s/that it a/that it is not a/ ? edit: given stan_rogers' comment bellow and a direct communication with nemo1618 the typo is just the missing "is". The sentence should read: "doesn't make it clear that it is a trusted service."
  - stan_rogers 7y ago
    No. The idea is that you use their service as opposed to running something on your own machine, which eliminates you as a nefarious source of hanky-panky. Think about running their list randomizer to pick one or more names from, say, a list of raffle entrants. The "trust" isn't that the result is going to be cryptographically random or anything like that, it's just an external service you can't monkey with, which avoids accusations of cheating.
- vortico 7y ago
  I don't feel that it's their responsibility to tell people that they are such a service. This should be obvious to anyone who needs secure randomness.
sleavey 7y ago
I bet their email servers get a huge amount of spam. I've made up a fair few addresses for airport WiFi using "[xyz]@random.com".
- unilynx 7y ago
  Well fortunately they’re .org. But next time, consider example.com/net/org.
  - cpeterso 7y ago
    Or mailinator.com or one of its many aliases.
arittr 7y ago
As awesome as the original post is, for me the best part of this was becoming aware of Michael Larson and Press Your Luck. Just a great story.
- TazeTSchnitzel 7y ago
  Tragic ending though :(
cpeterso 7y ago
I keep a silly little script that could, in theory, be used to pull random entropy from a remote source: strace -CTiv -ttt nice -n 19 curl -LNv $URL 2>&1 | shasum -a 512 $URL could be "https://news.yahoo.com" https://news.yahoo.com", "https://news.google.com" https://news.google.com", "https://wikipedia.org/wiki/Special:Random" https://wikipedia.org/wiki/Special:Random", or some other website that returns a large, unique result for each request. Even if someone was sniffing or logging the HTTP response, they wouldn't know all the local timing information reported by curl and strace.
- ThePirateofOz 7y ago
  Why visit a website, when you could do it yourself? #!/bin/bash read -p "How many digits? " numlen head /dev/urandom | LC_CTYPE=C tr -dc 'A-Za-z0-9' | fold -w $numlen | head -n 1
ian0 7y ago
Really cool to see this here. Mads supervised my undergraduate thesis, I remember him explaining the random.org setup when I asked about the servers & radio sitting in the corner of his office. A super friendly and smart guy. Of note, his office also contained a pretty legendary kendo sword linked up to sensors (this was early 2000s). Ostensibly to assist with technique, but Im pretty sure it was for light sabre visualisations...

176 points by unilynx 7y ago

How does one take a biased noise source source (like atmospheric noise with a certain spectral density) and convert it to a stream of uncorrelated random bits? I've never understood this.

petters 7y ago
Simpler problem: how do you take a biased coin and convert it into a perfect source of random bits? You flip the coin twice. If it comes up differently, you pick the first one. Otherwise you repeat. That will produce 50/50 random bits, no matter what the probability of the coin is.
- devit 7y ago
  Assuming that the probability distribution of each coin flip is independent from previous results.
  - petters 7y ago
    Yes
- vortico 7y ago
  This case is easy because the coin toss is independent. Radio noise is a time-dependent signal.
  - petters 7y ago
    Still, I thought it was a good starting example for the post I responded to.
  - mbreese 7y ago
    I always had it in my head that the way to do this with a random noise source was to do what is done with radiation. Because radiation is emitted randomly, but time dependent, you can measure the time differences between three (four?) events. If the time between A-B is greater than the time between B-C, the random bit is a one otherwise, it’s a zero. I think it works with just three events, but I’m not sure. You could do the same with audio noise by looking for peaks above a certain value and using a similar time function. I don’t know if that is really how it is done, so I might be misremembering.
lisper 7y ago
Take the biased source and run it through a cryptographic hash. As long as the input contains more bits of entropy than the length of the output, the result will be essentially 100% random.
- vortico 7y ago
  Cool, I think this explains it. What crytographic hashes are available that take a limited stream of bits over time and generate an arbitrary number of bits when requested?
  - lvh 7y ago
    Real CSPRNG designs are a bit more complex, having at least a state (like a hash function) but also an output mechanism to let it generate more bits. One way to do that is to “compress” all your input entropy into a single state, and then use that as the key for a stream cipher, like AESCTR or Salsa20.
  - lisper 7y ago
    Hashes always generate a fixed-size output (that's the definition of a hash). So if you have a hash with an n-bit output, you run it on an input of m>=n bits to get n random bits, then repeat that process as necessary. You choose m so that it contains >= n bits of entropy. When it doubt, overestimate m. You can also "seed" subsequent round of the has with the output from the previous round. That helps protect against certain kinds of failures. It's not really necessary, but it's not hard to do either so you might as well do it.
bloak 7y ago
You use a cryptographic hash function. The Linux kernel does something similar for /dev/random: https://en.wikipedia.org/wiki//dev/random https://en.wikipedia.org/wiki//dev/random If you needed to simulate a single fair coin toss using a biased but at least somewhat random coin you might toss it twenty times, feed the sequence of results ("HTHTT...") into sha256sum, and take the first bit of the output.
i_am_proteus 7y ago
If the actual distribution of the noise one is sampling from is known, use the CDF of the noise to obtain a true random variable. That's exactly what the biased coin example does.
- vortico 7y ago
  I imagine this approach would be insecure because an attacker could easily change the distribution from miles away. And I don't think it solves the problem of radio noise being time-dependent random variables.
- mortehu 7y ago
  The coin toss example works when the distribution is unknown, and relies purely on independence and stationarity.
mehrdadn 7y ago
Other people have mentioned how it's done in practice but there have been recent advances on this on the theoretical front as well. Here's one I know of: https://threatpost.com/academics-make-theoretical-breakthrough-in-random-number-generation/118150/ https://threatpost.com/academics-make-theoretical-breakthrou...
tzs 7y ago
Here's a pretty good description of how one company does it in their hardware random number generator [1]. Generally along the same lines people have already described, with the addition of testing throughout the process so that you can have some confidence that it is all working. [1] http://www.entropykey.co.uk/tech/ http://www.entropykey.co.uk/tech/

nintendo1889 7y ago

all one has to do is to find their microphone and play repeated noises into it! https://i.guim.co.uk/img/static/sys-images/Film/Pix/pictures/2009/4/30/1241095118372/John-Cusack-in-Say-Anythi-002.jpg?width=300&quality=85&auto=format&fit=max&s=81710795e7c24c765ddfbadc3287ec5c https://i.guim.co.uk/img/static/sys-images/Film/Pix/pictures...

turdnagel 7y ago

Kind of surprised at the lack of information about the current setup, which is certainly most sophisticated and therefore the most interesting. How did they manage to distribute the servers? What are they using now as a source of randomness? Are there still notes on these nodes to keep away?

deleted 7y ago
[deleted]

jackfoxy 7y ago

Australian National University generates a random bit stream by measuring the quantum fluctuations of the vacuum. http://qrng.anu.edu.au/index.php http://qrng.anu.edu.au/index.php A few years ago I created a F# .NET library to consume this stream in varying ways. https://jackfoxy.github.io/RandomBits/ https://jackfoxy.github.io/RandomBits/

doubleunplussed 7y ago
The fatal flaw of course is that everyone accessing their stream gets the same random data, making it substantially less random in the sense of others not being able to predict it. So do not use for cryptography!
- qrbLPHiKpiux 7y ago
  I use it for my passwords and I have a icon on my iPhone to get to it quick
- jackfoxy 7y ago
  I'm not a crypto expert. But I do know this stream is a firehose. Somewhere on the site is says how much data is generated. I forget. Naively I would think at least for some applications there would be no way to determine what part of the stream had been sampled. And the stream connection is over https.
  - progval 7y ago
    > there would be no way to determine what part of the stream had been sampled So the problem become to determine the offset of the stream you looked at, which is an integer that probably fits in 64 bits.
- unilynx 7y ago
  They're not very explicit, but their FAQ indicates that they are buffering random data and they sometimes even turn the generators off. Which would suggest that they're not repeating the same random data to multiple users Interestingly most clues about how their system work are given in the 'paranormal' section of their FAQ on https://www.random.org/faq/ https://www.random.org/faq/

cpach 7y ago

I really hope that people don’t use random.org in prod. Use /dev/urandom instead. https://sockpuppet.org/blog/2014/02/25/safely-generate-random-numbers/ https://sockpuppet.org/blog/2014/02/25/safely-generate-rando...

folkhack 7y ago
You wouldn't believe how many "engineers" I've seen open up random.org's string generator, and fiddle with the settings + copy a string from it only to drop it into a terminal for a root password/etc. Point-in-case, I saw 2-3 "DevOps" engineers do it in my last position... over a screen share..! When you'd bring it up to people they would just roll their eyes and call you paranoid. =(
- smallbigfish 7y ago
  Devops = not quite a dev + not quite a sys admin.
  - giancarlostoro 7y ago
    Maybe true of junior devops that has never done any sysadmin or much programming outside of school. Theres always people who are skilled at their job in whatever field.
  - ASalazarMX 7y ago
    Devops usually means "it's faster and cheaper because we don't have a dedicated sysadmin". The union of good developers and good syadmins is narrow like that of developers and designers.
    - clwk 7y ago
      I think you mean 'intersection'.
      - ASalazarMX 7y ago

alpb 7y ago

Related: Cloudflare offices in SF has a lava lamp wall called LavaRand lava lamps as a secondary source of randomness for their production servers. https://blog.cloudflare.com/randomness-101-lavarand-in-production/ https://blog.cloudflare.com/randomness-101-lavarand-in-produ... https://blog.cloudflare.com/lavarand-in-production-the-nitty-gritty-technical-details https://blog.cloudflare.com/lavarand-in-production-the-nitty... https://www.fastcompany.com/90137157/the-hardest-working-office-design-in-america-encrypts-your-data-with-lava-lamps https://www.fastcompany.com/90137157/the-hardest-working-off...

nemo1618 7y ago

I find it a little concerning that RANDOM.ORG doesn't make it clear that it a trusted service, and cannot be relied on for secure entropy. The only mention is this, buried in the FAQ: >anyone genuinely concerned with security should not trust anyone else (including RANDOM.ORG) to generate their cryptographic keys. But the problems go beyond cryptographic keys. If you use RANDOM.ORG to pick lottery winners, you're trusting that the numbers you get are as truly random as they claim. In particular, the operators of RANDOM.ORG could trivially inject deterministic entropy (generated from, e.g., AES-encrypting successive integers) and this would be completely undetectable, even to statistical tests. IMO the site needs a big, scary disclaimer on the front page that describes what applications it is appropriate for, and which ones should use a more secure source of entropy.

dorfsmay 7y ago
Typo? Did you mean s/that it a/that it is not a/ ? edit: given stan_rogers' comment bellow and a direct communication with nemo1618 the typo is just the missing "is". The sentence should read: "doesn't make it clear that it is a trusted service."
- stan_rogers 7y ago
  No. The idea is that you use their service as opposed to running something on your own machine, which eliminates you as a nefarious source of hanky-panky. Think about running their list randomizer to pick one or more names from, say, a list of raffle entrants. The "trust" isn't that the result is going to be cryptographically random or anything like that, it's just an external service you can't monkey with, which avoids accusations of cheating.
vortico 7y ago
I don't feel that it's their responsibility to tell people that they are such a service. This should be obvious to anyone who needs secure randomness.

sleavey 7y ago

I bet their email servers get a huge amount of spam. I've made up a fair few addresses for airport WiFi using "[xyz]@random.com".

unilynx 7y ago
Well fortunately they’re .org. But next time, consider example.com/net/org.
- cpeterso 7y ago
  Or mailinator.com or one of its many aliases.

arittr 7y ago

As awesome as the original post is, for me the best part of this was becoming aware of Michael Larson and Press Your Luck. Just a great story.

TazeTSchnitzel 7y ago
Tragic ending though :(

cpeterso 7y ago

I keep a silly little script that could, in theory, be used to pull random entropy from a remote source: strace -CTiv -ttt nice -n 19 curl -LNv $URL 2>&1 | shasum -a 512 $URL could be "https://news.yahoo.com" https://news.yahoo.com", "https://news.google.com" https://news.google.com", "https://wikipedia.org/wiki/Special:Random" https://wikipedia.org/wiki/Special:Random", or some other website that returns a large, unique result for each request. Even if someone was sniffing or logging the HTTP response, they wouldn't know all the local timing information reported by curl and strace.

ThePirateofOz 7y ago
Why visit a website, when you could do it yourself? #!/bin/bash read -p "How many digits? " numlen head /dev/urandom | LC_CTYPE=C tr -dc 'A-Za-z0-9' | fold -w $numlen | head -n 1

ian0 7y ago

Really cool to see this here. Mads supervised my undergraduate thesis, I remember him explaining the random.org setup when I asked about the servers & radio sitting in the corner of his office. A super friendly and smart guy. Of note, his office also contained a pretty legendary kendo sword linked up to sensors (this was early 2000s). Ostensibly to assist with technique, but Im pretty sure it was for light sabre visualisations...