This entry was posted on Tuesday, August 17th, 2010 at 4:36 am and is filed under algorithms, C99, hacks, wtf, Zen. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

rand() does not return a random number, it returns a pseudo-random number. Its behaviour is therefore predictable and consistent when srand() is called with a constant value.

With such a behaviour, it takes just a bit of analysis to build an input that can be transformed to something predictable using that generator.

More specifically, glibc implements rand() as a linear congruential generator with a modulus of 2^32, a multiplier of 1103515245 and an increment of 12345.

Does seeding the generator with its increment has a particular effect I didn’t know about?

——-

Excerpt from “ISO/IEC 9899: Programming languages — C, Second edition”:

“The srand function uses the argument as a seed for a new sequence of pseudo-random
numbers to be returned by subsequent calls to rand. If srand is then called with the
same seed value, the sequence of pseudo-random numbers shall be repeated.”

The behavior of the pseudo-random generator is predictible if, and only if, you have all the information about its internal state. While in previous versions of gcc it seemed to use a basic LCG, in the version I have it uses a considerably more elaborate generator.

Inspecting the code for rand() you see it’s quite the usine à gaz:

/* If we are using the trivial TYPE_0 R.N.G., just do the old linear
congruential bit. Otherwise, we do our fancy trinomial stuff, which is the
same in all the other cases due to all the global variables that have been
set up. The basic operation is to add the number at the rear pointer into
the one at the front pointer. Then both pointers are advanced to the next
location cyclically in the table. The value returned is the sum generated,
reduced to 31 bits by throwing away the "least random" low bit.
Note: The code takes advantage of the fact that both the front and
rear pointers can't wrap on the same call by not testing the rear
pointer if the front one has wrapped. Returns a 31-bit random number. */
int
__random_r (buf, result)
struct random_data *buf;
int32_t *result;
{
int32_t *state;
if (buf == NULL || result == NULL)
goto fail;
state = buf->state;
if (buf->rand_type == TYPE_0)
{
int32_t val = state[0];
val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
state[0] = val;
*result = val;
}
else
{
int32_t *fptr = buf->fptr;
int32_t *rptr = buf->rptr;
int32_t *end_ptr = buf->end_ptr;
int32_t val;
val = *fptr += *rptr;
/* Chucking least random bit. */
*result = (val >> 1) & 0x7fffffff;
++fptr;
if (fptr >= end_ptr)
{
fptr = state;
++rptr;
}
else
{
++rptr;
if (rptr >= end_ptr)
rptr = state;
}
buf->fptr = fptr;
buf->rptr = rptr;
}
return 0;
fail:
__set_errno (EINVAL);
return -1;
}

So it's not always the linear congruential generator that gets called. In my version of "methinks it is like a weasel" (and Ideone's) uses the complicated generator.

This being said, you're quite right about predictability. Now, we only have to find a way to exploit the information contained in the random sequence to do actual work (but I guess there'sn't much we can do).

rand() does not return a random number, it returns a pseudo-random number. Its behaviour is therefore predictable and consistent when srand() is called with a constant value.

With such a behaviour, it takes just a bit of analysis to build an input that can be transformed to something predictable using that generator.

More specifically, glibc implements rand() as a linear congruential generator with a modulus of 2^32, a multiplier of 1103515245 and an increment of 12345.

Does seeding the generator with its increment has a particular effect I didn’t know about?

——-

Excerpt from “ISO/IEC 9899: Programming languages — C, Second edition”:

“The srand function uses the argument as a seed for a new sequence of pseudo-random

numbers to be returned by subsequent calls to rand. If srand is then called with the

same seed value, the sequence of pseudo-random numbers shall be repeated.”

The behavior of the pseudo-random generator is predictible if, and only if, you have

allthe information about its internal state. While in previous versions of gcc it seemed to use a basic LCG, in the version I have it uses a considerably more elaborate generator.Glibc 2.9.x is found at http://ftp.gnu.org/gnu/glibc/

Inspecting the code for rand() you see it’s quite the

usine à gaz:So it's not always the linear congruential generator that gets called. In my version of "methinks it is like a weasel" (and Ideone's) uses the complicated generator.

This being said, you're quite right about predictability. Now, we only have to find a way to exploit the information contained in the random sequence to do actual work (but I guess there'sn't much we can do).