Is there a practical way to predict previous/next C rand() output if i have some of the values? How many values do i need? Do they need to be consequent? If it depends on compiler - for which implementations is it possible and how?
asked Feb 27, 2013 at 19:16
1 Answer
It depends on the rand() implementation... the standard (POSIX / Single Unix) gives a sample implementation but any system is free to have something better.
You can see the sample code there. If that exact code is used, then the internal state is a 32-bit integer, and it suffices to get two successive 16-bit output values to recompute the internal state. Actually, any 32 bits of output are sufficient, with the generic reconstruction algorithm known as "brute force": it won't take long, for a computer, to try all possible 32-bit internal states until one is found, which matches the observed output. It is possible to recompute the state waaaaaaaaay faster by doing some linear algebra, but since brute force works well, why bother ?
In usual Linux systems, rand() is an alias for random() which is much better, but still not "good", as far as randomness goes. The srandom() function still initializes the internal state with a 32-bit seed, which is amenable to brute force. You just lose the linear algebra shortcuts; or, at least, things require a bit more mathematics. random() is not a cryptographically secure PRNG and its internal state can be rebuilt by observing some output bits. The simplest method is still brute force, and it works well.
(Also, if the application did not bother to call srandom(), then the initial seed is always 1, so brute force will work very well.)
answered Feb 27, 2013 at 19:45
-
And what if you don't get consequent values, because someone manage to nab a value before you? Can you rotate the sequence backwards? Feb 27, 2013 at 19:51
-
Do rand() on unix read /dev/random? Or is it still an once initialized PRNG? Feb 27, 2013 at 19:53
-
3You can do a lot of maths, but brute force will work even better. Non-cryptographically secure PRNG can usually be inverted (i.e. state is recovered) quite efficiently as long as you know how many values were generated between the one you got. As for
/dev/random(which should be/dev/urandom, by the way), it is normally not used to initialize non-cryptographic PRNG (there is little point in seeding an awfully weak PRNG with a strong seed).– Tom LeekFeb 27, 2013 at 19:59 -
How probably are collisions? How many values do i need to hold the probability low enough? \n Have you tested it by yourself? Feb 27, 2013 at 20:13
rand(). C is a language, andrand()is a function provided by a library for that language. The libraries that are used are entirely dependant on the compiler suite you're using, because the RNG thatrand()is based on is not mandated by the spec. You'll need to specify which compiler and libraries you're using.rand(). If you use say MS Visual Studio with the MS C Run-time library, the rand() function may be implemented completely differently. See: en.wikipedia.org/wiki/C_standard_library#Implementationsrand()implementations are horrible beyond believe. They're broken even for basic numerical work.