Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Behind Intel's New Random-Number Generator

spectrum.ieee.org

Post reply on HN
Print view View original

31–40 of 43 posts

Re: Behind Intel's New Random-Number Generator

#31

Post by ghshephard »

Daniel_Newby wrote: post #21
marshray wrote: post #15

Earlier quoted context omitted.

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 ca…

Nothing needs gigabit rates of random numbers. Consider a Monte Carlo algorithm on a 2 GHz processor, with a 50 instruction cycle inner loop, using a 64 bit random value per loop: it needs 2.5 Gb/sec of random bits.

Perhaps this should be better written as "Nothing needs gigabit rates of _cryptographically strong_ random numbers."

Using a megabit rates of cryptographically strong random numbers to seed a PRNG would be fine for most purposes.

Can anyone think of a reason why you would want/use gigabit rates of truly random numbers instead of using a slower rate to see a PRNG?

Re: Behind Intel's New Random-Number Generator

#32

Post by palish »

Dylan16807 wrote: post #28
palish wrote: post #18

Earlier quoted context omitted.

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 text…

In what way is randomness on a GPU hard? The nVidia SDK apparently comes with a few of them, and you can implement an LCG in handful of arithmetic operations. If you need a seed feed it in from the CPU. I don't see the benefit of having a high-cryptographic-quality RNG for rendering.

You'll have to take my word for it, or try it yourself: there are visually noticeable repetitive patterns that are a direct result of the naive PRNG.

For example I once modeled raindrops as falling billboards that struck the ground at some random (x,y) in your field of view, followed by a "splash" animation billboard where it struck the ground. I started by using C rand() to determine the random (x,y) of the raindrop. And it looked terrible! The raindrops would mysteriously clump together in sinewave-like patterns, and seemingly avoid some spots altogether.

I dropped in a Mersenne Twister RNG and the problem instantly went away. I didn't change a thing except the RNG.

So yeah, a few arithmetic ops gets you rand() quality. But humans are unfortunately good at noticing the overall bias in the resulting patterns.

And you'll run into similar problems when e.g. trying to implement a non-repeating perlin noise function on a GPU. I tried it with a weighted combination of several different perlin noise textures... but I had to be very careful about aliasing artificts in some of the more interesting effects; while also being careful of avoiding visually-repetitive patterns (which almost always occur).

The value of Intel's RNG, I'd imagine, is that it's uniformly random and also unbiased -- meaning repetitive moire patterns won't show up in your results.

Of course it's not deterministic, which is tricky, but I can still think of several use cases for something like this.

Re: Behind Intel's New Random-Number Generator

#33

Post by algorias »

ghshephard wrote: post #31
Daniel_Newby wrote: post #21

Earlier quoted context omitted.

Nothing needs gigabit rates of random numbers. Consider a Monte Carlo algorithm on a 2 GHz processor, with a 50 instruction cycle inner loop, using a 64 bit random value per loop: it needs 2.5 Gb/sec of random bits.

Perhaps this should be better written as "Nothing needs gigabit rates of _cryptographically strong_ random numbers." Using a megabit rates of cryptographically strong random numbers to seed a PRNG would be fine for most purposes. Can anyone think of a reason why you would want/use gigabit rates of truly random numbers instead of using a slower rate to see a PRNG?

>Using a megabit rates of cryptographically strong random numbers to seed a PRNG would be fine for most purposes.

And that's exactly what the hardware described in the article does for you.

Re: Behind Intel's New Random-Number Generator

#35

Post by marshray »

palish wrote: post #32
Dylan16807 wrote: post #28

Earlier quoted context omitted.

In what way is randomness on a GPU hard? The nVidia SDK apparently comes with a few of them, and you can implement an LCG in handful of arithmetic operations. If you need a seed feed it in from the CPU. I don't see the benefit of having a high-cryptographic-quality RNG for rendering.

You'll have to take my word for it, or try it yourself: there are visually noticeable repetitive patterns that are a direct result of the naive PRNG. For example I once modeled raindrops as falling billboards that struck the ground at some random (x,y) in your field of view, followed by a "splash" animation billboard where it struck the ground. I started by using C rand() to determine the random (x,y) of the raindrop…

So what you need is a high-quality Pseudorandom Number Generator (PRNG). You do not need a Cryptographically Secure PRNG.

This is good, what you need can be implemented significantly more efficiently than the CS version. As you mentioned, it doesn't help your application to be truly nondeterministic.

C rand() is about the worst one you can find. Mersenne Twister is great statistically, but it's quite expensive in terms of memory consumption.

As I understand GPU programming, you want to maximize parallelism. Ideally, you would have something small enough to have an independent generator for each processor. You should be able to generate perfectly random-looking numbers using 64 or 128 bits of state storage and a handful of instructions per 32-bits of output.

For example, the Skein hash function and CSPRNG can generate random data at 5 cycles per byte of output. But that's cryptographically secure, you can probably cut its state size and computational expense each in half to get statistical randomness.

Re: Behind Intel's New Random-Number Generator

#36

Post by marshray »

yuhong wrote: post #9

"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.

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

Re: Behind Intel's New Random-Number Generator

#37

Post by T-hawk »

palish wrote: post #32
Dylan16807 wrote: post #28

Earlier quoted context omitted.

In what way is randomness on a GPU hard? The nVidia SDK apparently comes with a few of them, and you can implement an LCG in handful of arithmetic operations. If you need a seed feed it in from the CPU. I don't see the benefit of having a high-cryptographic-quality RNG for rendering.

You'll have to take my word for it, or try it yourself: there are visually noticeable repetitive patterns that are a direct result of the naive PRNG. For example I once modeled raindrops as falling billboards that struck the ground at some random (x,y) in your field of view, followed by a "splash" animation billboard where it struck the ground. I started by using C rand() to determine the random (x,y) of the raindrop…

> But humans are unfortunately good at noticing the overall bias in the resulting patterns.

Humans are also, of course, good at noticing bias in a distribution even when there isn't any. Ask any online poker player about shufflers.

Re: Behind Intel's New Random-Number Generator

#38

Post by tripzilch »

marshray wrote: post #35
palish wrote: post #32

Earlier quoted context omitted.

You'll have to take my word for it, or try it yourself: there are visually noticeable repetitive patterns that are a direct result of the naive PRNG. For example I once modeled raindrops as falling billboards that struck the ground at some random (x,y) in your field of view, followed by a "splash" animation billboard where it struck the ground. I started by using C rand() to determine the random (x,y) of the raindrop…

So what you need is a high-quality Pseudorandom Number Generator (PRNG). You do not need a Cryptographically Secure PRNG. This is good, what you need can be implemented significantly more efficiently than the CS version. As you mentioned, it doesn't help your application to be truly nondeterministic. C rand() is about the worst one you can find. Mersenne Twister is great statistically, but it's quite expensive in ter…

I've been reading New Kind Of Science recently, intrigued by some of Wolfram's grandiose claims I ran some tests and it indeed turns out that the Rule 30 cellular automaton is a very high quality PRNG (as long as you pick the right bits). It's a very simple algorithm and very parallel too.

It's just that my version picked one bit per generation (the middle one) and the period of the PRNG is determined by the size of the buffer, so it might be a bit memory intensive for a GPU, if you need several random bits per pixel. I couldn't find any patterns within the period, though. Also it might be possible to get more than one random bit per generation, though I expect the ones right next to eachother are probably too correlated.

Formula's real simple, if the previous state and the two neighbours are labeled L,M and R, rule 30 boils down to the new state will be L xor (M and A).

Re: Behind Intel's New Random-Number Generator

#39

Post by chadgeidel »

marshray wrote: post #16
cpeterso wrote: post #10

Earlier quoted context omitted.

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"?

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.

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."

Re: Behind Intel's New Random-Number Generator

#40

Post by marshray »

ghshephard wrote: post #31
Daniel_Newby wrote: post #21

Earlier quoted context omitted.

Nothing needs gigabit rates of random numbers. Consider a Monte Carlo algorithm on a 2 GHz processor, with a 50 instruction cycle inner loop, using a 64 bit random value per loop: it needs 2.5 Gb/sec of random bits.

Perhaps this should be better written as "Nothing needs gigabit rates of _cryptographically strong_ random numbers." Using a megabit rates of cryptographically strong random numbers to seed a PRNG would be fine for most purposes. Can anyone think of a reason why you would want/use gigabit rates of truly random numbers instead of using a slower rate to see a PRNG?

Perhaps this should be better written as "Nothing needs gigabit rates of _cryptographically strong_ random numbers."

Yes that's what I meant to say. I probably didn't realize the discussion had widened to include insecure number generation.

Post reply on HN