14

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?

Smit Johnth
  • 1,709
  • 4
  • 17
  • 23
  • 6
    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 '13 at 19:35
  • @polinomial I mean particularly C rand() and a working algorithm/code to do it. – Smit Johnth Feb 27 '13 at 19:42
  • More links that cover this: [Not so random numbers - take 2](http://ptsecurity.com/download/random_numbers_take_two_eng.pdf), [Pwning random number generators](https://media.blackhat.com/bh-us-12/Briefings/Argyros/BH_US_12_Argyros_PRNG_WP.pdf), [State recovery attacks on pseudorandom generators](http://subs.emis.de/LNI/Proceedings/Proceedings74/GI-Edition74.-6.pdf), [Predicting values from an LCG](http://crypto.stackexchange.com/questions/2086/predicting-values-from-a-linear-congruential-generator) – Polynomial Feb 27 '13 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 '13 at 19:44
  • 4
    @SmitJohnth - What polynomial means, is that if you use gcc with glibc 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: http://en.wikipedia.org/wiki/C_standard_library#Implementations – dr jimbob Feb 27 '13 at 19:45
  • >_If it depends on compiler - for which implementations is it possible and how?_< You can convert things you posted above to answer. – Smit Johnth Feb 27 '13 at 19:46
  • 3
    Typical `rand()` implementations are horrible beyond believe. They're broken even for basic numerical work. – CodesInChaos Feb 27 '13 at 21:44
  • Is this somehow relevant? http://security.stackexchange.com/questions/4268/cracking-a-linear-congruential-generator – Smit Johnth Feb 28 '13 at 21:25

1 Answers1

14

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

Tom Leek
  • 168,808
  • 28
  • 337
  • 475
  • 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 '13 at 19:51
  • Do rand() on unix read /dev/random? Or is it still an once initialized PRNG? – Smit Johnth Feb 27 '13 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 '13 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 '13 at 20:13