Linear congruential generator: How important is setting seed?

Question

I'm learning about linear congruential generator in an algorithms and data structures course. After thinking about RNG implementation we've been using (a=429493445, c=907633385, mod=4294967296, X is _uint32), one thing came to my mind: Program has a function for setting seed.

How important would that function be in C and C++?

Here's my line of thought: Once the program starts, OS assigns addresses to all used variables. Data which is in memory location given to seed can be interpreted as a number.

I understand that in small computers it may happen that operating system (if there is one) assigns several times same address to seed but wouldn't data contained in that address be different every time? Unless the system sets all free RAM to some value after every start, data contained in RAM would be pretty much random itself and provide good enough seed.

Even if data contained in space given to seed was used by another program, I don't see how would that make an impact on the generator itself.

Answer 1

One thing about PRNGs is that they deliver a reproducible sequence when you know their parameters and once you set the initial seed. So in that regard, it's only natural to expose this 'feature' in an API. Many applications need this form of determinism, and real RNG devices can't provide it.

Edit: To answer your actual question it is wrong to assume that the data in stack variables is random, almost all unix systems clear the stack and heap (initialise it with 0) as a security measure, imagine you could read a password string left in memory by the previous process.

Answer 2

Random memory can be used as a seed. However, because the memory allocation algorithms in the operating system aren't random and the data generated by other programs also usually follows some pattern, I wouldn't consider it a perfect seed. It depends on the purpose of your application - I definitely wouldn't use it in a banking system for example. If you want more randomness, you can use this as one part of the seed and then mutiply it by other random seeds from different sources.

Answer 3

While for unserious playing around with RNGs, seeding with "junk in memory" probably will work OK. But it is really a bad way to do things: You have no guarantee that the data in memory is random, even though it can be. In security applications (which I guess are not relevant here, since you're using a linear congruence generator) you don't want parts of the environment not under your control (RAM) to act as seed. In other applications, such as scientific computing, you want your results to be reproducible. What you do then is usually to let the user choose a seed for himself, and provide an option to sample the OS RNG for a seed (/dev/random on UNIX-like systems).

The bottom line is: If you want a random seed, get it from a good source of randomness. Pretty much any easily accessible source provided by your OS will be better than "hey, what's in RAM at this location today?". Sampling from for example /dev/urandom is no more difficult than sampling RAM, and it's the Right Thing To Do (for non-security-sensitive things, of course).

Edit: Here's how to sample /dev/urandom on GNU/Linux using C:

int seed;
FILE* urandom = fopen("/dev/urandom", "r");
fread(&seed, sizeof(int), 1, urandom);
fclose(urandom);

Now seed holds an integer ready to be used as a seed for your PRNG (you may need a different datatype).

Wikipedia has some nice information on /dev/random and /dev/urandom.

Answer 4

OpenSSL does use uninitialized memory to generate part of its randomness initialization. There was some noise 2 years ago when Debian did remove this, thinking that it was a bug to use uninitialized variables.

Note that this was not the only source of entropy in OpenSSL

So yes, uninitialized memory can be used as a source of randomness. But be carefull to really understand what you are doing !