OpenBSD bug in the random() function • Hacker News Board

Re: OpenBSD bug in the random() function

#11

Post by DHowett » Tue, Mar 20, 2012, 6:38 PM UTC

calloc wrote: post #4

Or why maybe using random() is a terrible idea. Use arc4random() instead on FreeBSD/OpenBSD/Mac OS X for a MUCH better random number generation, and best of all it is auto-seeded. Obligatory XKCD: http://xkcd.com/221/

The only caveat is that you then have to wrap it in an #ifdef if you want source portability. The thing random() has over arc4random() is exactly that - it's part of the standard C library on most platforms.

For discussion: Why is random() not already arc4random() on platforms that provide the arc4 variant? Is it for speed's sake? Different implementations of libc functions will seed differently, so it's not a cross-platform seed stability concern. Is the problem that you can't seed it with a fixed value and get the same pseudorandom sequence?

Re: OpenBSD bug in the random() function

#12

Post by marshray » Tue, Mar 20, 2012, 7:02 PM UTC

Yrlec wrote: post #9

gcp wrote: post #7

Earlier quoted context omitted.

The Java Random class uses a 48-bit LCG with a 35-bit multiplier. Because of this, small seed values won't be able to "wrap around" the full range of the LCG and will cause starting sequences that are all but random relative to each other. Put differently, you're seeing that 35/48 = 0.73. I'd consider this a bug in Java, but it's a common one. Qt has the same problem. Could have been avoided by cycling the seed throu…

Interesting, thanks! Any particular reason they limit the multiplier to 35 bits and the output to 48 bits? Edit: just noticed that Java limits the output to 32 bits, not 48 ( http://en.wikipedia.org/wiki/Linear_congruential_generator ). How does it create 64 bit values, like long and double?

Probably it generates 32 bits twice.

Re: OpenBSD bug in the random() function

#13

Post by marshray » Tue, Mar 20, 2012, 7:04 PM UTC

dfc wrote: post #2

It seems like the right thing to do would be to spend the time composing the email to tech@o.o and then write the blog post.

I've tried pointing out a deficiency in the system RNG to those guys before.

They're not as grateful as you'd think.

Re: OpenBSD bug in the random() function

#14

Post by marshray » Tue, Mar 20, 2012, 7:07 PM UTC

tedunangst wrote: post #6

Yrlec wrote: post #3

While not exactly a bug, but if you run this code in Java: for(int i = 0; i It prints the following sequence (at least on JDK 7 and Win 7): 0.730967787376657 0.7308781907032909 0.7311469360199058 0.731057369148862 0.7306094602878371 0.730519863614471 0.7307886238322471 0.7306990420600421 0.7302511331990172 0.7301615514268123 I know that you're not supposed to recreate the Random-instance like that but it's still a bi…

I know nothing about java's random number generator, but your seeds are also very similar to each other.

For any decent RNG, even a lightweight one, that shouldn't matter.

Re: OpenBSD bug in the random() function

#15

Post by ajb » Tue, Mar 20, 2012, 7:14 PM UTC

marshray wrote: post #14

tedunangst wrote: post #6

Earlier quoted context omitted.

I know nothing about java's random number generator, but your seeds are also very similar to each other.

For any decent RNG, even a lightweight one, that shouldn't matter.

Indeed. When Knuth found was informed of this problem in a random number generator of his, he fixed it: http://news.ycombinator.com/item?id=3730348

There is an obvious use case for this: you have a test which is run N times where you want to have different random numbers in each run, but you also want to be able to go to run X and debug it without running all the previous ones.

Re: OpenBSD bug in the random() function

#16

Post by caladri » Tue, Mar 20, 2012, 7:16 PM UTC

DHowett wrote: post #11

calloc wrote: post #4

Or why maybe using random() is a terrible idea. Use arc4random() instead on FreeBSD/OpenBSD/Mac OS X for a MUCH better random number generation, and best of all it is auto-seeded. Obligatory XKCD: http://xkcd.com/221/

The only caveat is that you then have to wrap it in an #ifdef if you want source portability. The thing random() has over arc4random() is exactly that - it's part of the standard C library on most platforms. For discussion: Why is random() not already arc4random() on platforms that provide the arc4 variant? Is it for speed's sake? Different implementations of libc functions will seed differently, so it's not a cross-…

Yes, because of the need for pseudorandom sequences. In FreeBSD this comes up every so often, but the reality is that there's a lot of AI and simulation/modeling code that uses the libc random functions (either rand(3) or random(3)) and expects reproducible behavior with the same seed both throughout the life of a program and across multiple executions.

Re: OpenBSD bug in the random() function

#17

Post by gcp » Tue, Mar 20, 2012, 7:23 PM UTC

Yrlec wrote: post #9

gcp wrote: post #7

Earlier quoted context omitted.

The Java Random class uses a 48-bit LCG with a 35-bit multiplier. Because of this, small seed values won't be able to "wrap around" the full range of the LCG and will cause starting sequences that are all but random relative to each other. Put differently, you're seeing that 35/48 = 0.73. I'd consider this a bug in Java, but it's a common one. Qt has the same problem. Could have been avoided by cycling the seed throu…

Interesting, thanks! Any particular reason they limit the multiplier to 35 bits and the output to 48 bits? Edit: just noticed that Java limits the output to 32 bits, not 48 ( http://en.wikipedia.org/wiki/Linear_congruential_generator ). How does it create 64 bit values, like long and double?

Any particular reason they limit the multiplier to 35 bits and the output to 48 bits?

Good question. There appears to be no good justification for this, but the generator is guaranteed by the docs. So it's possible the initial implementation was bad and everybody is required to follow it since.

Re: OpenBSD bug in the random() function

#18

Post by gonzo » Tue, Mar 20, 2012, 7:31 PM UTC

marshray wrote: post #13

dfc wrote: post #2

It seems like the right thing to do would be to spend the time composing the email to tech@o.o and then write the blog post.

I've tried pointing out a deficiency in the system RNG to those guys before. They're not as grateful as you'd think.

OpenBSD is full of navel-gazing.

Re: OpenBSD bug in the random() function

#19

Post by tptacek » Tue, Mar 20, 2012, 7:42 PM UTC

calloc wrote: post #4

Or why maybe using random() is a terrible idea. Use arc4random() instead on FreeBSD/OpenBSD/Mac OS X for a MUCH better random number generation, and best of all it is auto-seeded. Obligatory XKCD: http://xkcd.com/221/

You use random() when you need the statistical appearance of random numbers, and potentially the ability to generate the same sequence deterministically. It's not intended for the same use case as arc4random() (which is itself probably not one of the best CSPRNGs).

Re: OpenBSD bug in the random() function

#20

Post by tedunangst » Tue, Mar 20, 2012, 8:19 PM UTC

ajb wrote: post #15

marshray wrote: post #14

Earlier quoted context omitted.

For any decent RNG, even a lightweight one, that shouldn't matter.

Indeed. When Knuth found was informed of this problem in a random number generator of his, he fixed it: http://news.ycombinator.com/item?id=3730348 There is an obvious use case for this: you have a test which is run N times where you want to have different random numbers in each run, but you also want to be able to go to run X and debug it without running all the previous ones.

Did you intend to link to this page? I'm already here.