8 ms·

Behind Intel's New Random-Number Generator

170 points by synacksynack 15y ago

learc83 15y ago
Now that's a perfect example of something that seems obvious in hindsight, but obviously wasn't since the problem has existed for so long without a solution. It's also nice to see a more EE oriented post on hacker news now and again.
- rwg 15y ago
  VIA's "Nehemiah" core C3 CPUs had hardware random number generation, as well as hardware AES assist, way back in 2003. (And, of course, VIA's "PadLock" instructions and Intel's RdRand instruction + AES-NI instructions are totally different. Hooray for continued x86 instruction set fragmentation!) Edit: It just occurred to me that you're probably referring to the implementation, not the existence of a hardware RNG in x86. Doh!
  - wmf 15y ago
    Yeah, IIRC VIA is using the same ring oscillator style that Intel used to use. This article is about a new, lower-power RNG design.
    - marshray 15y ago
      The idea that a hardware RNG would ever need to consume a noticeable amount of power on a 20W CPU seems strange to me. Lots of low power chips have them. A quick search returns a paper titled "A 2.92μW Hardware Random Number Generator".
      - jbri 15y ago
        Having a look at that paper, the actual rate at which it produces bits is very low - for 2.92μW, they're producing only 500 bits per second. For an embedded device that might be suitable, but for a consumer or server machine you need a much higher bitrate.
        tedunangst 15y ago
        You only need a little "grade-A" random to seed an appropriate high bitrate algorithm from time to time.
        marshray 15y ago
        No one has ever broken a properly designed CSPRNG properly seeded with more than 100 or 200 bits of entropy, total.
- marshray 15y ago
  No. There has been no shortage of perfectly workable designs for hardware random number generators patented over the years. If anything, it's something that engineering types with a fondness for crypto obsess about too much. The reality is that it's just not that hard to generate quality random numbers after a few seconds have passed after bootup on a busy system. Nothing needs gigabit rates of random numbers. The cases where applications have had lousy random numbers have all been boneheaded implementation bugs (like the early 90s Netscape one the reference). There are two reasons why this had not been implemented until now: 1. Low demand. It's entirely practical for applications to generate random numbers in software, especially with help from the kernel. With a hardware RNG on some chips, a fallback implementation would still have to be available and people who care about their CSPRNGs in software wouldn't fully trust Intel's numbers anyway. 2. Additional design, documentation, and testing burden. Every feature has a cost. The cryptographic qualities of random numbers are nearly impossible to test as a black box.
  - palish 15y ago
    Speaking as a graphics programmer, I hope to see this hardware-level randomness eventually incorporated into GPUs. Randomness on a GPU is hard, and there are so many ways that a RNG can improve visual quality. For example, adding a tiny amount of film grain to the final rendered image would most easily be done with RNG. Another example: it's common for renderers to accumulate the scene's illumination into a HDR texture, and then radially blur it. The goal is to approximate the halo you observe around light sources at night time. The problem is, a Gaussian blur is perfectly smooth --- so the resulting glow typically ends up being a perfectly smooth blurry circle of light. But a real photograph of the same scene rarely has smooth glows. The image exhibits all kinds of subtle noise in the light's corona. After all, a photograph results from interaction of light with the camera lens, multiple scattering in outdoor scenes, chromatic dispersion, interaction between polarized light and certain materials, ... and many, many more phenomena. So rather than try to model each of those physical lighting effects in realtime, it would be wonderful to have a "RNG()" shader function to simply add a smidgen of unpredictability to our realtime rendering techniques. The closer your final image resembles nature, the better it looks --- and nature is many things, but she is not a perfectly smooth BRDF lighting model! So yeah... It would be frickin' sweet to have this RNG on a GPU.
mdda 15y ago
It's easy to see that {process-id, parent-id, timestamp} can lead to a pretty predictable random number seed. But Amazon also had another easily available source of randomness : the timestamps of other customer's orders. Why not generate a random #, and index to a random customer, and re-seed? One extra DB lookup and you've got a whole lot more randomness (like a private lava-lamp) to access.
- bdonlan 15y ago
  Both sides have to generate secure random numbers in order to perform an ephemeral diffie-helmann exchange securely; if the client's random number is insecure, a man in the middle attack becomes possible. Non-DH-based exchanges are even worse - the entire exchange hinges on a random number generated by the _client_. The server effectively doesn't even have a chance to generate a random number at all.
  - deleted 15y ago
    [deleted]
  - mdda 15y ago
    But surely the client could use human input as it's source of randomness too : After all, in this case (browser purchases) the user is going to be hitting keys and/or moving the mouse.
    - ars 15y ago
      It could, and today it does. But back then it didn't.
- shabble 15y ago
  Using a physical process is generally going to be harder to exploit than a software one. There's going to be the possibility of uneven distribution (customer order timestamps may cluster at certain parts of the day, rather than being evenly distributed), as well as the (granted, small) possibility that on some small site without Amazon scale, the attacker can generate enough entries that it can reasonably assume one of them will be picked by the random index. One interesting story about exploiting a poor RNG in Online Poker: http://www.cigital.com/papers/download/developer_gambling.php http://www.cigital.com/papers/download/developer_gambling.ph... https://webcache.googleusercontent.com/search?q=cache:AdC18Y8C6UkJ:taeb-blog.sartak.org/2009/03/predicting-and-controlling-nethacks.html https://webcache.googleusercontent.com/search?q=cache:AdC18Y... is another one, where the PRNG seed for a shared Nethack server wasn't random enough, and could be discovered and synchronised for fun and cheaty profit.
shabble 15y ago
It seems like it's (ab)using the metastability[1] of the dual inverter circuit as the input source. Since metastable states can persist for arbitrary long periods (with asymptotic probability), the bias testing and reset mechanisms are needed. I assume they're controlling the system to ensure that the thermal noise dominates, and that the de-bias feedback loop and signal conditioner can strip out any low frequency thermal changes (like, temperature forcing through heavily loading CPU). There are some really neat attacks that use thermal system properties to leak or force information. A submission from a while back: http://news.ycombinator.com/item?id=2872274 http://news.ycombinator.com/item?id=2872274 struck me as particularly sneaky. [1] https://secure.wikimedia.org/wikipedia/en/wiki/Metastability_in_electronics https://secure.wikimedia.org/wikipedia/en/wiki/Metastability...
- cpeterso 15y ago
  Is there a risk that, after running for a long time, the dual inverter circuit (hardware) could degrade into a "stuck" or severely biased state? At some point, the conditioner probably can't compensate. Is there a method for software to query the RdRand's "health"?
  - marshray 15y ago
    Yes, the instruction that returns random bits returns a flag indicating that the bits were successfully obtained. I guarantee you somebody somewhere is going to forget to check that flag.
    - chadgeidel 15y ago
      Sounds like that is built into the RdRand instruction. From the article: "We really like to sleep well at night, so we've built in additional circuitry that tests to make sure that the concentrating machinery is always working with bit streams that aren't too biased. If it detects a biased output, we tag it as unhealthy and refine it to meet our standards. This way, only healthy pairs of bit streams are combined."
  - Daniel_Newby 15y ago
yuhong 15y ago
"The nominally random number Netscape [1.x] used to form a secret key was based on just three values—time of day, process identification number, and parent-process identification number—all of them predictable. This allowed the attackers to reduce the number of keys that they needed to try, and to find the right one much sooner than Netscape had anticipated." Another reason to disable SSLv2 on servers, BTW.
- marshray 15y ago
  SSLv2 is horribly broken and should be disabled, but technically, that's a different bug of Netscape's. :-)
Empedocles99 15y ago
I thought the 40-bit keys were used due to cryptographic export restrictions, and not lack of randomness? http://en.wikipedia.org/wiki/40-bit_encryption http://en.wikipedia.org/wiki/40-bit_encryption Seems to agree with me.
- deleted 15y ago
  [deleted]
- oasisbob 15y ago
  The authors didn't cite Netscape because the 40-bit key is too short, they cited it because the the PNRG in the SSL implementation was faulty. They link to this page with more details: http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html
snowtiger 15y ago
it seems IEEE server down (code 500) to me

170 points by synacksynack 15y ago

Now that's a perfect example of something that seems obvious in hindsight, but obviously wasn't since the problem has existed for so long without a solution. It's also nice to see a more EE oriented post on hacker news now and again.

rwg 15y ago
VIA's "Nehemiah" core C3 CPUs had hardware random number generation, as well as hardware AES assist, way back in 2003. (And, of course, VIA's "PadLock" instructions and Intel's RdRand instruction + AES-NI instructions are totally different. Hooray for continued x86 instruction set fragmentation!) Edit: It just occurred to me that you're probably referring to the implementation, not the existence of a hardware RNG in x86. Doh!
- wmf 15y ago
  Yeah, IIRC VIA is using the same ring oscillator style that Intel used to use. This article is about a new, lower-power RNG design.
  - marshray 15y ago
    The idea that a hardware RNG would ever need to consume a noticeable amount of power on a 20W CPU seems strange to me. Lots of low power chips have them. A quick search returns a paper titled "A 2.92μW Hardware Random Number Generator".
    - jbri 15y ago
      Having a look at that paper, the actual rate at which it produces bits is very low - for 2.92μW, they're producing only 500 bits per second. For an embedded device that might be suitable, but for a consumer or server machine you need a much higher bitrate.
      - tedunangst 15y ago
        You only need a little "grade-A" random to seed an appropriate high bitrate algorithm from time to time.
      - marshray 15y ago
        No one has ever broken a properly designed CSPRNG properly seeded with more than 100 or 200 bits of entropy, total.
marshray 15y ago
No. There has been no shortage of perfectly workable designs for hardware random number generators patented over the years. If anything, it's something that engineering types with a fondness for crypto obsess about too much. The reality is that it's just not that hard to generate quality random numbers after a few seconds have passed after bootup on a busy system. Nothing needs gigabit rates of random numbers. The cases where applications have had lousy random numbers have all been boneheaded implementation bugs (like the early 90s Netscape one the reference). There are two reasons why this had not been implemented until now: 1. Low demand. It's entirely practical for applications to generate random numbers in software, especially with help from the kernel. With a hardware RNG on some chips, a fallback implementation would still have to be available and people who care about their CSPRNGs in software wouldn't fully trust Intel's numbers anyway. 2. Additional design, documentation, and testing burden. Every feature has a cost. The cryptographic qualities of random numbers are nearly impossible to test as a black box.
- palish 15y ago
  Speaking as a graphics programmer, I hope to see this hardware-level randomness eventually incorporated into GPUs. Randomness on a GPU is hard, and there are so many ways that a RNG can improve visual quality. For example, adding a tiny amount of film grain to the final rendered image would most easily be done with RNG. Another example: it's common for renderers to accumulate the scene's illumination into a HDR texture, and then radially blur it. The goal is to approximate the halo you observe around light sources at night time. The problem is, a Gaussian blur is perfectly smooth --- so the resulting glow typically ends up being a perfectly smooth blurry circle of light. But a real photograph of the same scene rarely has smooth glows. The image exhibits all kinds of subtle noise in the light's corona. After all, a photograph results from interaction of light with the camera lens, multiple scattering in outdoor scenes, chromatic dispersion, interaction between polarized light and certain materials, ... and many, many more phenomena. So rather than try to model each of those physical lighting effects in realtime, it would be wonderful to have a "RNG()" shader function to simply add a smidgen of unpredictability to our realtime rendering techniques. The closer your final image resembles nature, the better it looks --- and nature is many things, but she is not a perfectly smooth BRDF lighting model! So yeah... It would be frickin' sweet to have this RNG on a GPU.

mdda 15y ago

It's easy to see that {process-id, parent-id, timestamp} can lead to a pretty predictable random number seed. But Amazon also had another easily available source of randomness : the timestamps of other customer's orders. Why not generate a random #, and index to a random customer, and re-seed? One extra DB lookup and you've got a whole lot more randomness (like a private lava-lamp) to access.

bdonlan 15y ago
Both sides have to generate secure random numbers in order to perform an ephemeral diffie-helmann exchange securely; if the client's random number is insecure, a man in the middle attack becomes possible. Non-DH-based exchanges are even worse - the entire exchange hinges on a random number generated by the _client_. The server effectively doesn't even have a chance to generate a random number at all.
- deleted 15y ago
  [deleted]
- mdda 15y ago
  But surely the client could use human input as it's source of randomness too : After all, in this case (browser purchases) the user is going to be hitting keys and/or moving the mouse.
  - ars 15y ago
    It could, and today it does. But back then it didn't.
shabble 15y ago
Using a physical process is generally going to be harder to exploit than a software one. There's going to be the possibility of uneven distribution (customer order timestamps may cluster at certain parts of the day, rather than being evenly distributed), as well as the (granted, small) possibility that on some small site without Amazon scale, the attacker can generate enough entries that it can reasonably assume one of them will be picked by the random index. One interesting story about exploiting a poor RNG in Online Poker: http://www.cigital.com/papers/download/developer_gambling.php http://www.cigital.com/papers/download/developer_gambling.ph... https://webcache.googleusercontent.com/search?q=cache:AdC18Y8C6UkJ:taeb-blog.sartak.org/2009/03/predicting-and-controlling-nethacks.html https://webcache.googleusercontent.com/search?q=cache:AdC18Y... is another one, where the PRNG seed for a shared Nethack server wasn't random enough, and could be discovered and synchronised for fun and cheaty profit.

shabble 15y ago

It seems like it's (ab)using the metastability[1] of the dual inverter circuit as the input source. Since metastable states can persist for arbitrary long periods (with asymptotic probability), the bias testing and reset mechanisms are needed. I assume they're controlling the system to ensure that the thermal noise dominates, and that the de-bias feedback loop and signal conditioner can strip out any low frequency thermal changes (like, temperature forcing through heavily loading CPU). There are some really neat attacks that use thermal system properties to leak or force information. A submission from a while back: http://news.ycombinator.com/item?id=2872274 http://news.ycombinator.com/item?id=2872274 struck me as particularly sneaky. [1] https://secure.wikimedia.org/wikipedia/en/wiki/Metastability_in_electronics https://secure.wikimedia.org/wikipedia/en/wiki/Metastability...

cpeterso 15y ago
Is there a risk that, after running for a long time, the dual inverter circuit (hardware) could degrade into a "stuck" or severely biased state? At some point, the conditioner probably can't compensate. Is there a method for software to query the RdRand's "health"?
- marshray 15y ago
  Yes, the instruction that returns random bits returns a flag indicating that the bits were successfully obtained. I guarantee you somebody somewhere is going to forget to check that flag.
  - chadgeidel 15y ago
    Sounds like that is built into the RdRand instruction. From the article: "We really like to sleep well at night, so we've built in additional circuitry that tests to make sure that the concentrating machinery is always working with bit streams that aren't too biased. If it detects a biased output, we tag it as unhealthy and refine it to meet our standards. This way, only healthy pairs of bit streams are combined."
- Daniel_Newby 15y ago

yuhong 15y ago

"The nominally random number Netscape [1.x] used to form a secret key was based on just three values—time of day, process identification number, and parent-process identification number—all of them predictable. This allowed the attackers to reduce the number of keys that they needed to try, and to find the right one much sooner than Netscape had anticipated." Another reason to disable SSLv2 on servers, BTW.

marshray 15y ago
SSLv2 is horribly broken and should be disabled, but technically, that's a different bug of Netscape's. :-)

Empedocles99 15y ago

I thought the 40-bit keys were used due to cryptographic export restrictions, and not lack of randomness? http://en.wikipedia.org/wiki/40-bit_encryption http://en.wikipedia.org/wiki/40-bit_encryption Seems to agree with me.

deleted 15y ago
[deleted]
oasisbob 15y ago
The authors didn't cite Netscape because the 40-bit key is too short, they cited it because the the PNRG in the SSL implementation was faulty. They link to this page with more details: http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html

snowtiger 15y ago

it seems IEEE server down (code 500) to me