Find out what a random number generator was seeded with in C++

Question

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?

Daughterly

Answer 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;
       }

Motile

Answer 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.

Quiteria

Did you just say "simply try all 64-bit seeds"? Just how fast of a computer do You have? :D – Sergias

Try all 64-bit seeds? That's 18,446,744,073,709,551,616 different possibilities - a bit beyond feasible. – Moyna

What you could do with a little bit of information on where the seed came from, is try a few million guesses. Often srand is seeded with the current time. If you know roughly when the generator was first seeded, you can make a pretty good guess at what the value of time() was at that point. – Moyna

yea, um 64 perhaps a bit much now, but you could definitely try all 32 bit numbers with modern hardware. Note that you dont need to try all 2^64 values, just those < m – Quiteria

I think you can recover the a and b for the linear congruential generator, and once that's known, and you know v1 and m, seed follows. – Touchandgo

Answer 3

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.

Siemens

I assume that 'should' is supposed to be 'shouldn't' (since as it is it doesn't make much sense) – Olsen

I dont know what your rand() function uses, but most good ones maintain a shuffle table, not just a 'current' state. – Quiteria

-1. rand() is not cryptographically secure at all. It is very easy to work backwards. – Stamey

I never claimed rand() is cryptographically secure, but being able to peek into the seed is problematic even if you're not doing cryptography :-) – Siemens

Answer 4

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.

Moyna

-1. rand() is not cryptographically secure; it almost always returns the high-order bits of a LCG. The output of a couple of calls to rand() is generally sufficient to deduce the current state and thus work backwards. – Stamey