Tell me more ×
IT Security Stack Exchange is a question and answer site for IT security professionals. It's 100% free, no registration required.
up vote 6 down vote favorite

This question already has an answer here:

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?

share|improve this question
5  
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. – Polynomial Feb 27 at 19:35
@polinomial I mean particularly C rand() and a working algorithm/code to do it. – Smit Johnth Feb 27 at 19:42
4  
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. – Polynomial Feb 27 at 19:44
4  
@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 – dr jimbob Feb 27 at 19:45
3  
Typical rand() implementations are horrible beyond believe. They're broken even for basic numerical work. – CodesInChaos Feb 27 at 21:44
show 3 more comments

marked as duplicate by Polynomial, Iszi, this.josh, Gilles, AJ Henderson Mar 1 at 21:29

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

up vote 7 down vote

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

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.