5 ms·

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?

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/

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/