5 ms·

Infinite Noise true random number generator

91 points by widea 12y ago

steeve 12y ago
I've always wondered why TRNG like this one were not included in computers already. I know modern CPU also take advantage of physics phenomena (supposedly), but still... Cool product, and great execution.
- TheLoneWolfling 12y ago
  The problem is that it's pretty much impossible to verify that a supplied RNG is actually a secure RNG and isn't backdoored.
  - ars 12y ago
    That's not entirely true. You can mix the entropy of the hardware RNG with other entropy. And interesting thing about entropy is you can never make it worse - you can never reduce entropy by mixing in an independent stream from elsewhere. (A dependent stream is different, it might cancel out something else.) So you can still use the hardware RNG without hurting anything, unless you think it's so sophisticated it's able to figure out your other sources of entropy and exactly cancel them out.
    - desdiv 12y ago
      Let's say your kernel currently compiles N bits of entropy per second from various sources. If you add a new hardware RNG that produces 1024N bps, you won't be able to simply append the two streams together to get 1025N bps, because that would be extremely unsafe like you pointed out. The best you can do is periodically xor the output of the hardware RNG onto itself ten times so that you get N bps, and you xor that with the original trusted entropy stream. By the end of the day you still only have N bps, it's just that these new N bps have "better randomness". This is why hardware RNG is such a hard sell. Constructs like clockspeed, FLOPS, memory bandwidth, I/O throughput are easy to understand when compared to the more abstract idea of "better randomness".
      - ars 12y ago
        I don't think you have understood this. You don't xor the RNG to itself - why would you do that? That's not safe if the RNG is backdoored. (Never xor dependent streams together!) Instead you just xor all the random sources you can find together, and use that final value as the random value. Even if you xor a well known value into your random value you have no in any way harmed the randomness of your existing value - it's still random. So the hardware RNG can never make it worse. And you keep saying 'bps' - bits per second, which makes no sense in this context. The goal is not to increase the throughput of the random stream by using a hardware generator (you might reduce cpu usage, but that's not the goal), the goal is simply better random values.
        UweSchmidt 12y ago
        Any vendor of hardware RNGs can easily and secretly be forced to build in a backdoor (including the one we're discussing here, as you kinda need to trust that these tiny little microchips do what they claim to do). Actually, selling fake TRNGs would be a low cost, high reward excercise for any intelligence agency anyway. Corrupted TRNGs don't make things worse, but also not better, and you keep depending on your existing entropy sources, whatever their quality may be. Therefore providing computers with TRNGs made by Intel etc. would only create a false sense of security.
        ars 12y ago
        I think you majorly underestimate the "easily" part. You can make a pattern with your RNG, but once mixed it's pretty useless. Making one that can handle that is not in the slightest easy. > would only create a false sense of security. You are assuming that your only adversary is the chip maker, but this type of RNG (if it were even possible to make it) would still be helpful in the other 99.99% of uses for randomness.
    - TheLoneWolfling 12y ago
      That is true in the case of independent sources. But a backdoored RNG is probably not an independent source!
      - hdevalence 12y ago
        See, for instance, http://blog.cr.yp.to/20140205-entropy.html http://blog.cr.yp.to/20140205-entropy.html for a writeup by djb on a possible way to exploit this in practice.
        ars 12y ago
        You oversell the "in practice" part. That is not in the slightest possible in practice. His writeup assumes the attacker knows everything about the way the random stream is generated. But a mass market CPU would not be able to do that.
        TheLoneWolfling 12y ago
        It doesn't need to. Even a simple "replace a RNG xor a register with <backdoored RNG>" in the microcode would catch almost everything. And remember - microcode updates happen all the time, and are not open. It's entirely possible that the microcode is updated in response to the type of RNG verification - in other words, with the attacker knowing everything about the way the random stream is generated, as you say.
        ars 12y ago
        I was not able to parse your sentence in quotes, so I can not reply to it. It seems like you think the random stream is generated mathematically. It's not, it's based on various timing events, mouse movements, keyboard, etc. A mass market CPU would not be able to handle any of that. You could always get the CPU random number first, then the external randomness - it would have to predict the future to do anything about it. > the microcode is updated in response to the type of RNG verification Hu? I don't understand what you mean. What RNG verification? You would have to tune to the microcode to the specific version and settings of the OS getting the random data, including which hardware was attached. You massively underestimate how hard this would be. Yes, perhaps the NSA could do it for a single well known adversary - maybe - I doubt it, but maybe. But it would certainly be impossible in mass.
  - rtpg 12y ago
    so how does this key help? How can you know this isn't backdoored somehow?
- bigiain 12y ago
  Some do: http://scruss.com/blog/2013/06/07/well-that-was-unexpected-the-raspberry-pis-hardware-random-number-generator/ http://scruss.com/blog/2013/06/07/well-that-was-unexpected-t...
- frozenport 12y ago
  Perhaps random number aren't in demand, beyond the resources currently supplied?
thrownaway2424 12y ago
From a full-system threat analysis standpoint this seems like a truly bad idea. You think you have some kind of fancy rng but actually what you have is an rng that your adversary can sneak in and swap out with an infinite generator of zeroes while you're in the bathroom of the airplane. Essentially you've made yourself way more vulnerable to rng attacks than you would have been with a regular entropy source. If you bought one of these you'd have to be totally committed to keeping it on your person at all times.
- ape4 12y ago
  Maybe the driver can verify that the real thing is there.
  - SlyShy 12y ago
    Indeed, they say that it looks for a deviation from expected random noise.
    - TheLoneWolfling 12y ago
      ...So someone replaces it with known random stream. Or, say, a known PRNG.
    - oh_sigh 12y ago
      The malicious device could simply respond with a bunch of random bits which were recorded earlier.
    - frozenport 12y ago
      This isn't my field, but I'm not sure if they should check for 3% or 0.3%.
- timmclean 12y ago
  If you XOR'd this RNG's output with, say, /dev/urandom, you could mitigate that risk significantly (you would be no worse off than before).
- 12y ago
analog31 12y ago
This is an aside, but I'm curious why the noise in the reverse voltage of a Zener is preferable to just the Gaussian noise generated by a resistor. There must be a practical reason.
- thrownaway2424 12y ago
  Zeners are just noisier.
- jacquesm 12y ago
  The reverse breakdown voltage is all over the place due to avalanche effects. You might get as much as 50 mV of pure noise out of a single Zener junction if you're lucky and it won't take much amplification at all (which might negatively affect your randomness) to get to a level that you can quantize easily. You could even do it un-amplified with the right biasing.
PhantomGremlin 12y ago
The article has a "drive-by" disparagement: Intel's DRNG appears controllable through a software based power droop attack If true, this is big news. I did some quick Googling and couldn't find any confirmation. Anybody have a link to the potential flaw in Intel's RNG?
- kalerv0 12y ago
  I tried to google Atmel backdoor and I didn't find anything...
walterbell 12y ago
John Denker wrote a page on RNGs, http://www.av8n.com/computer/htm/secure-random.htm http://www.av8n.com/computer/htm/secure-random.htm "There is no algorithm that can generate entropy. Therefore any HRNG depends on input from some hardware device. It is necessary to calibrate the input device. For example, the entropy available from a soundcard depends on the input impedance, gain, bandwidth, and temperature. Calibration is not easy. It requires skill in a number of areas, including physics, electrical engineering, programming, and cryptography. However, just because it is hard is no excuse for skipping this step. ... My favorite proverb of all is the one that says for every proverb, there is an equal and opposite proverb. In this case, we should note that the proverb about not putting all your eggs in one basket is not necessarily a sound engineering principle. The right answer depends on the margin of error and on the per-basket failure rate. It also greatly depends on the chance of correlated, uncorrelated, and anti-correlated basket failures. Sometimes the best way to get your eggs from point A to point B is to put them all in one basket and take really good care of that basket. ... The phrase “random number generator” should be parsed as follows: It is a random generator of numbers. It is not a generator of random numbers."
- aragot 12y ago
  Obligatory quote: http://dilbert.com/strip/2001-10-25 http://dilbert.com/strip/2001-10-25 - "9, 9, 9, 9... -Are you sure that's random? -That's the problem with randomness: You can never be sure."
grondilu 12y ago
The other day I tried to snap photos from my webcam with my finger obstructing the objective. I looked at the files in binary and it was apparently always different (the image itself looked visually always the same though : full black). I made a hash of an hundred files made this way and could not find any collision. Could this be considered as a TRNG?
- roywiggins 12y ago
  Yes, I know there have been projects that try to use this as a source of entropy: https://medium.com/the-physics-arxiv-blog/quantum-random-number-generator-created-using-a-smartphone-camera-602f88552b64 https://medium.com/the-physics-arxiv-blog/quantum-random-num...
- nitrogen 12y ago
  You'd probably want to make sure that the noise you see in the images is truly random (e.g. caused by cosmic rays or heat), rather than power supply or EMI noise.
- deleted 12y ago
  [deleted]
JacobEdelman 12y ago
I can't think of any use case for this that you can't already get with hardware random number generators that computers have built-in. For most people TRNG's are only useful for things like generating keys and such, something that not much entropy is needed for. Typing in random letters and hashing them would suffice.
- mistercow 12y ago
  > Typing in random letters and hashing them would suffice. That seems pretty iffy to me. Humans are really bad at generating randomness, and the entropy from "randomly" typing letters is going to be far less than you think. It's better to go with hard drive and network latency, or the least significant bits of keypress times, which are far noisier than which keys were pressed.
tzs 12y ago
> This USB key RNG also demonstrates what I feel should be considered best-practices for TRNGs. It is low cost, reasonably fast, and has no firmware that can be used to PWN your computer. The USB key can easily be taken apart (with care!) using a toothless dinner knife, so the board can be compared to those on the github site. It's interesting to compare to another well known USB RNG, the Simtec's Entropy Key[1], which apparently is no longer available. The Entropy Key takes the opposite approach both on firmware and on easy of taking it apart. Here's an overview of how Entropy Key worked (more detail on the "technical" tab on their site). They have two separate reverse biased PN junctions generating random streams. These streams are each tested using Maurer's universal statistical test for random bit generators, and their entropy is conservatively estimated. If the test fails or the entropy is too low, it is a fatal error and the device stops sending random data to the host, and reports an error. The two streams are also xor'ed together, and that combined stream is tested with Maurer's test and its entropy is estimated. If this fails, it is fatal. (Combining the streams this way detects if the two generators have become correlated). The two streams go through von Neumann debiasing, and are tested again with Maurer's test, and the entropy is estimated. If the test fails, or the entropy is varying too widely, fatal error. The streams then go into a 256-bit cryptographic hash. When enough bits have gone in so that the input entropy is at least 150% of the number of output bits of the hash, the output is taken. The hash output is mixed into a bit pool. When the pool has taken in at least 50% more entropy than it could possibly hold, a new pool is started. Enough pools are maintained to have 20000 bits of total pool data. The pool blocks are then tested following FIPS 140-2. The 20000 bits are then available for delivery to the host. The protocol for host communication encrypts the data blocks that contain the random bits, using a session key based on a shared secret between the device and the host. The device is filled with epoxy, and opening the case should destroy it. So, are they any security experts who can comment on which is closer to best practice? A minimal device that just delivers fairly raw bits, with all the statistical testing and other processing necessary for good random numbers up to the host, and with no protection against hardware tampering (other than hoping that tampering would mess up the stream in a way the host will notice)? Or a device that does the testing and processing, and delivers ready to use random bits to the host, and that tries to prevent tampering? I would think that even with the simple approach, you should put two theoretically identical generators on the device. That way, if someone does try to influence the device by external means, you have a better chance of detecting it because if it influences both devices the same way you'll get correlations. [1] http://www.entropykey.co.uk http://www.entropykey.co.uk

91 points by widea 12y ago

I've always wondered why TRNG like this one were not included in computers already. I know modern CPU also take advantage of physics phenomena (supposedly), but still... Cool product, and great execution.

TheLoneWolfling 12y ago
The problem is that it's pretty much impossible to verify that a supplied RNG is actually a secure RNG and isn't backdoored.
- ars 12y ago
  That's not entirely true. You can mix the entropy of the hardware RNG with other entropy. And interesting thing about entropy is you can never make it worse - you can never reduce entropy by mixing in an independent stream from elsewhere. (A dependent stream is different, it might cancel out something else.) So you can still use the hardware RNG without hurting anything, unless you think it's so sophisticated it's able to figure out your other sources of entropy and exactly cancel them out.
  - desdiv 12y ago
    Let's say your kernel currently compiles N bits of entropy per second from various sources. If you add a new hardware RNG that produces 1024N bps, you won't be able to simply append the two streams together to get 1025N bps, because that would be extremely unsafe like you pointed out. The best you can do is periodically xor the output of the hardware RNG onto itself ten times so that you get N bps, and you xor that with the original trusted entropy stream. By the end of the day you still only have N bps, it's just that these new N bps have "better randomness". This is why hardware RNG is such a hard sell. Constructs like clockspeed, FLOPS, memory bandwidth, I/O throughput are easy to understand when compared to the more abstract idea of "better randomness".
    - ars 12y ago
      I don't think you have understood this. You don't xor the RNG to itself - why would you do that? That's not safe if the RNG is backdoored. (Never xor dependent streams together!) Instead you just xor all the random sources you can find together, and use that final value as the random value. Even if you xor a well known value into your random value you have no in any way harmed the randomness of your existing value - it's still random. So the hardware RNG can never make it worse. And you keep saying 'bps' - bits per second, which makes no sense in this context. The goal is not to increase the throughput of the random stream by using a hardware generator (you might reduce cpu usage, but that's not the goal), the goal is simply better random values.
      - UweSchmidt 12y ago
        Any vendor of hardware RNGs can easily and secretly be forced to build in a backdoor (including the one we're discussing here, as you kinda need to trust that these tiny little microchips do what they claim to do). Actually, selling fake TRNGs would be a low cost, high reward excercise for any intelligence agency anyway. Corrupted TRNGs don't make things worse, but also not better, and you keep depending on your existing entropy sources, whatever their quality may be. Therefore providing computers with TRNGs made by Intel etc. would only create a false sense of security.
        ars 12y ago
        I think you majorly underestimate the "easily" part. You can make a pattern with your RNG, but once mixed it's pretty useless. Making one that can handle that is not in the slightest easy. > would only create a false sense of security. You are assuming that your only adversary is the chip maker, but this type of RNG (if it were even possible to make it) would still be helpful in the other 99.99% of uses for randomness.
  - TheLoneWolfling 12y ago
    That is true in the case of independent sources. But a backdoored RNG is probably not an independent source!
    - hdevalence 12y ago
      See, for instance, http://blog.cr.yp.to/20140205-entropy.html http://blog.cr.yp.to/20140205-entropy.html for a writeup by djb on a possible way to exploit this in practice.
      - ars 12y ago
        You oversell the "in practice" part. That is not in the slightest possible in practice. His writeup assumes the attacker knows everything about the way the random stream is generated. But a mass market CPU would not be able to do that.
        TheLoneWolfling 12y ago
        It doesn't need to. Even a simple "replace a RNG xor a register with <backdoored RNG>" in the microcode would catch almost everything. And remember - microcode updates happen all the time, and are not open. It's entirely possible that the microcode is updated in response to the type of RNG verification - in other words, with the attacker knowing everything about the way the random stream is generated, as you say.
        ars 12y ago
        I was not able to parse your sentence in quotes, so I can not reply to it. It seems like you think the random stream is generated mathematically. It's not, it's based on various timing events, mouse movements, keyboard, etc. A mass market CPU would not be able to handle any of that. You could always get the CPU random number first, then the external randomness - it would have to predict the future to do anything about it. > the microcode is updated in response to the type of RNG verification Hu? I don't understand what you mean. What RNG verification? You would have to tune to the microcode to the specific version and settings of the OS getting the random data, including which hardware was attached. You massively underestimate how hard this would be. Yes, perhaps the NSA could do it for a single well known adversary - maybe - I doubt it, but maybe. But it would certainly be impossible in mass.
- rtpg 12y ago
  so how does this key help? How can you know this isn't backdoored somehow?
bigiain 12y ago
Some do: http://scruss.com/blog/2013/06/07/well-that-was-unexpected-the-raspberry-pis-hardware-random-number-generator/ http://scruss.com/blog/2013/06/07/well-that-was-unexpected-t...
frozenport 12y ago
Perhaps random number aren't in demand, beyond the resources currently supplied?

thrownaway2424 12y ago

From a full-system threat analysis standpoint this seems like a truly bad idea. You think you have some kind of fancy rng but actually what you have is an rng that your adversary can sneak in and swap out with an infinite generator of zeroes while you're in the bathroom of the airplane. Essentially you've made yourself way more vulnerable to rng attacks than you would have been with a regular entropy source. If you bought one of these you'd have to be totally committed to keeping it on your person at all times.

ape4 12y ago
Maybe the driver can verify that the real thing is there.
- SlyShy 12y ago
  Indeed, they say that it looks for a deviation from expected random noise.
  - TheLoneWolfling 12y ago
    ...So someone replaces it with known random stream. Or, say, a known PRNG.
  - oh_sigh 12y ago
    The malicious device could simply respond with a bunch of random bits which were recorded earlier.
  - frozenport 12y ago
    This isn't my field, but I'm not sure if they should check for 3% or 0.3%.
timmclean 12y ago
If you XOR'd this RNG's output with, say, /dev/urandom, you could mitigate that risk significantly (you would be no worse off than before).
12y ago

analog31 12y ago

This is an aside, but I'm curious why the noise in the reverse voltage of a Zener is preferable to just the Gaussian noise generated by a resistor. There must be a practical reason.

thrownaway2424 12y ago
Zeners are just noisier.
jacquesm 12y ago
The reverse breakdown voltage is all over the place due to avalanche effects. You might get as much as 50 mV of pure noise out of a single Zener junction if you're lucky and it won't take much amplification at all (which might negatively affect your randomness) to get to a level that you can quantize easily. You could even do it un-amplified with the right biasing.

PhantomGremlin 12y ago

The article has a "drive-by" disparagement: Intel's DRNG appears controllable through a software based power droop attack If true, this is big news. I did some quick Googling and couldn't find any confirmation. Anybody have a link to the potential flaw in Intel's RNG?

kalerv0 12y ago
I tried to google Atmel backdoor and I didn't find anything...

walterbell 12y ago

John Denker wrote a page on RNGs, http://www.av8n.com/computer/htm/secure-random.htm http://www.av8n.com/computer/htm/secure-random.htm "There is no algorithm that can generate entropy. Therefore any HRNG depends on input from some hardware device. It is necessary to calibrate the input device. For example, the entropy available from a soundcard depends on the input impedance, gain, bandwidth, and temperature. Calibration is not easy. It requires skill in a number of areas, including physics, electrical engineering, programming, and cryptography. However, just because it is hard is no excuse for skipping this step. ... My favorite proverb of all is the one that says for every proverb, there is an equal and opposite proverb. In this case, we should note that the proverb about not putting all your eggs in one basket is not necessarily a sound engineering principle. The right answer depends on the margin of error and on the per-basket failure rate. It also greatly depends on the chance of correlated, uncorrelated, and anti-correlated basket failures. Sometimes the best way to get your eggs from point A to point B is to put them all in one basket and take really good care of that basket. ... The phrase “random number generator” should be parsed as follows: It is a random generator of numbers. It is not a generator of random numbers."

aragot 12y ago
Obligatory quote: http://dilbert.com/strip/2001-10-25 http://dilbert.com/strip/2001-10-25 - "9, 9, 9, 9... -Are you sure that's random? -That's the problem with randomness: You can never be sure."

grondilu 12y ago

The other day I tried to snap photos from my webcam with my finger obstructing the objective. I looked at the files in binary and it was apparently always different (the image itself looked visually always the same though : full black). I made a hash of an hundred files made this way and could not find any collision. Could this be considered as a TRNG?

roywiggins 12y ago
Yes, I know there have been projects that try to use this as a source of entropy: https://medium.com/the-physics-arxiv-blog/quantum-random-number-generator-created-using-a-smartphone-camera-602f88552b64 https://medium.com/the-physics-arxiv-blog/quantum-random-num...
nitrogen 12y ago
You'd probably want to make sure that the noise you see in the images is truly random (e.g. caused by cosmic rays or heat), rather than power supply or EMI noise.
deleted 12y ago
[deleted]

JacobEdelman 12y ago

I can't think of any use case for this that you can't already get with hardware random number generators that computers have built-in. For most people TRNG's are only useful for things like generating keys and such, something that not much entropy is needed for. Typing in random letters and hashing them would suffice.

mistercow 12y ago
> Typing in random letters and hashing them would suffice. That seems pretty iffy to me. Humans are really bad at generating randomness, and the entropy from "randomly" typing letters is going to be far less than you think. It's better to go with hard drive and network latency, or the least significant bits of keypress times, which are far noisier than which keys were pressed.

tzs 12y ago

> This USB key RNG also demonstrates what I feel should be considered best-practices for TRNGs. It is low cost, reasonably fast, and has no firmware that can be used to PWN your computer. The USB key can easily be taken apart (with care!) using a toothless dinner knife, so the board can be compared to those on the github site. It's interesting to compare to another well known USB RNG, the Simtec's Entropy Key[1], which apparently is no longer available. The Entropy Key takes the opposite approach both on firmware and on easy of taking it apart. Here's an overview of how Entropy Key worked (more detail on the "technical" tab on their site). They have two separate reverse biased PN junctions generating random streams. These streams are each tested using Maurer's universal statistical test for random bit generators, and their entropy is conservatively estimated. If the test fails or the entropy is too low, it is a fatal error and the device stops sending random data to the host, and reports an error. The two streams are also xor'ed together, and that combined stream is tested with Maurer's test and its entropy is estimated. If this fails, it is fatal. (Combining the streams this way detects if the two generators have become correlated). The two streams go through von Neumann debiasing, and are tested again with Maurer's test, and the entropy is estimated. If the test fails, or the entropy is varying too widely, fatal error. The streams then go into a 256-bit cryptographic hash. When enough bits have gone in so that the input entropy is at least 150% of the number of output bits of the hash, the output is taken. The hash output is mixed into a bit pool. When the pool has taken in at least 50% more entropy than it could possibly hold, a new pool is started. Enough pools are maintained to have 20000 bits of total pool data. The pool blocks are then tested following FIPS 140-2. The 20000 bits are then available for delivery to the host. The protocol for host communication encrypts the data blocks that contain the random bits, using a session key based on a shared secret between the device and the host. The device is filled with epoxy, and opening the case should destroy it. So, are they any security experts who can comment on which is closer to best practice? A minimal device that just delivers fairly raw bits, with all the statistical testing and other processing necessary for good random numbers up to the host, and with no protection against hardware tampering (other than hoping that tampering would mess up the stream in a way the host will notice)? Or a device that does the testing and processing, and delivers ready to use random bits to the host, and that tries to prevent tampering? I would think that even with the simple approach, you should put two theoretically identical generators on the device. That way, if someone does try to influence the device by external means, you have a better chance of detecting it because if it influences both devices the same way you'll get correlations. [1] http://www.entropykey.co.uk http://www.entropykey.co.uk