# How to predict C rand()? [duplicate]

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?

• Note that "C rand()" isn't a defined thing as part of the spec. It's entirely dependant on which compiler / libs you're using. Commented Feb 27, 2013 at 19:35
• @polinomial I mean particularly C rand() and a working algorithm/code to do it. Commented Feb 27, 2013 at 19:42
• As I said, there's no such thing as C's `rand()`. C is a language, and `rand()` 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 that `rand()` is based on is not mandated by the spec. You'll need to specify which compiler and libraries you're using. Commented Feb 27, 2013 at 19:44
• @SmitJohnth - What polynomial means, is that if you use gcc with glibc <stdlib.h> will have one implementation of `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#Implementations Commented Feb 27, 2013 at 19:45
• Typical `rand()` implementations are horrible beyond believe. They're broken even for basic numerical work. Commented Feb 27, 2013 at 21:44

## 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.)

• And what if you don't get consequent values, because someone manage to nab a value before you? Can you rotate the sequence backwards? Commented Feb 27, 2013 at 19:51
• Do rand() on unix read /dev/random? Or is it still an once initialized PRNG? Commented Feb 27, 2013 at 19:53
• You 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). Commented Feb 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? Commented Feb 27, 2013 at 20:13