Perl: output of rand() is partially predictable?

Question

I was playing around with perl's rand() and noticed that when supplying an argument larger than 2^32, the last bits of the output becomes predictable.

The most clear way I found of illustrating it is with the following script:

srand(); for $i (1..10) { printf "%4x\n",rand(2**48)%2**16 }

Whenever I execute that the output is

5101
6378
2a23
62f2
8d15
effc
9657
2d16
f669
40c0

(It's not just the first 10 values, but I didn't see a point copying a long list of "random" numbers)

The call to srand() is superfluous, but it's there to make it easy to supply an argument, and see that it doesn't change anything.

I've tried this on:

• Debian squeeze having perl 5.10 (randbits=48)
• Debian wheezy having perl 5.14 (randbits=48)
• Debian jessie having perl 5.20 (randbits=48)

I know rand() is not supposed to be cryptographically secure, but the last 16 bits being predictable is worse than what I had understood. Am I using any of the function(s) wrong?

Answer 1

It's not just the implementation of the "default" seed (srand called with no argument or not called at all), as you might think from Schwern's answer that was linked in a comment; all srand calls (and so all means of initializing the RNG state) are subject to this problem.

Currently (since 5.20) perl uses its own RNG implementation based on FreeBSD's drand48 and srand48; prior to that, perl used drand48 and srand48 if available, so the behavior on Linux was effectively the same. In either case, the srand implementation only uses 32 bits of input, placing them in the upper 32 bits of the 48-bit RNG state; the lower 16 bits are initialized to 0x330e. If you run 0x330e through one round of the LCG algorithm (only the bottom 16 bits of the previous state are necessary to get the bottom 16 bits of the next state), multiplying by 0xe66d and adding 0x000b, you end up with 0x5101 which is the first value you observe.

Obviously this predictability in the lower bits is bad, and I'm not sure why it hasn't been addressed especially now that perl has its own RNG implementation that could easily be 48-bit clean. Obviously it's less damaging than having the high bits always initialized to a known state, however.

At the moment, I would recommend that if you want to do anything serious with perl's RNG, use it for at most 32 bits per call, combining multiple calls if necessary to get greater precision/range.