Find out what a random number generator was seeded

问题:

I've got an unmanaged c++ console application in which I'm using srand() and rand(). I don't need this to solve a particular problem, but was curious: is the original seed passed to srand() stored somewhere in memory that I can query? Is there any way to figure out what the seed was?

回答1:

The seed is not required to be stored, only the last random number returned is.

Here's the example from the manpage:

       static unsigned long next = 1;

       /* RAND_MAX assumed to be 32767 */
       int myrand(void) {
           next = next * 1103515245 + 12345;
           return((unsigned)(next/65536) % 32768);
       }

       void mysrand(unsigned seed) {
           next = seed;
       }

回答2:

If you have a simple linear congruential generator, for which you have several values this yields a system of equations:

 v1 = ( seed * a + b ) % m
 v2 = (   v1 * a + b ) % m;
 v3 = (   v2 * a + b ) % m;
... 

If you know the first value, you can go backwards in the sequence:

seed = (v1 - b)/a (mod m)

You don't know the seed uniquely, you only know it mod m (which is usually fine since (0 < seed < m) anyways) If v1 - b is negative you need to add m's until its positive again.

You might also look at the Chinese Remainder Theorem, though its not an exact match.

回答3:

I don't know what your level of assembly proficiency is, or whether you have access to the source code / debugging symbols for the unmanaged app, but outside of that sort of trickery, there is no feasible way to determine the original seed value. The entire point of random number generators is to come up with a way to give you unpredictable numbers - the relationship between any two given calls to rand() should not be deducible. In cryptographically strong pseudo random number generators, it would be considered a serious flaw to be able to guess the seed based on a generated random number.

The easiest way to do it, would be to start the application under a debugger and set a breakpoint where srand() is called - then just look at the passed parameter.

Next would be to disassemble the app and find out the circumstances of the srand call. It's entirely possible that it's being seeded with the current time - then you can try a bunch of guesses (you can probably narrow it down to a few thousand or so) and see if any give the same sequence of random numbers that the app is using. (Of course this assumes you have some way of knowing what the random values being generated are). It's also possible that the seed is something dumb like '0' all the time.

回答4:

Theoretically, not - the seed value is used to compute the next random value and that value is (theoretically) used to seed the next random number and so on.

Security wise, being able to peek into the seed (whether the original one or a new one) is a serious security problem so I expect that you shouldn't be able to look into it even though it must be stored somewhere.