Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I've read in numerous sources that the output of PHP's rand() is predictable as its a PRNG, and I mostly accept that as fact simply because I've seen it in so many places.

I'm interested in a proof-of-concept: how would I go about predicting the output of rand()? From reading this article I understand that the random number is a number returned from a list starting at a pointer (the seed) -- but I can't imagine how this is predictable.

Could someone reasonably figure out what random # was generated via rand() at a given moment in time within a few thousand guesses? or even 10,000 guesses? How?

This is coming up because I saw a auth library which uses rand() to produce a token for users who have lost passwords, and I assumed this was a potential security hole. I've since replaced the method with hashing a mixture of openssl_random_pseudo_bytes(), the orignal hashed password, and microtime. After doing this I realized that if I were on the outside looking in, I'd have no idea how to guess the token even knowing it was a md5 of rand().

share|improve this question
    
"but I can't imagine how this is predictable"? You need to read up on "en.wikipedia.org/wiki/Linear_congruential_generator first so that you can begin to imagine how it's predictable. Then you can revise your question to eliminate the astonishment and move to the more practical issues of reverse engineering the PHP rand function source to see how it works. –  S.Lott May 13 '11 at 22:00
    
"I assumed this was a potential security hole"? Only if Evil Hacker could get some user's random password, use a rainbow table to undo the MD5 hash to recover the original (pre-hash) value and then guarantee that they made the very next password request. Theoretically possible, I suppose. But only if they had a working rainbow table for a random number. –  S.Lott May 13 '11 at 22:15
    
@S.Lott - its not a matter of a password. The system lets you reset the password and emails you a token which is used in a URL. The token is generated via MD5(rand()). If you can predict the output of rand() you could change anyone's password, without having the hash for the original, or knowing the original. –  Erik May 13 '11 at 22:17
    
@Erik. Right. Replace "random password" with "random token" if that helps. The token can only be abused if someone can unwind the MD5 hash to recover the random number AND assure that they will get the next random number. Predicting the next rand is only one small part. Undoing the MD5 is the hard part. –  S.Lott May 13 '11 at 22:34
1  
Note that MD5(rand()) only has the same security as rand(). It's practical to build a lookup table of MD5(rand()) -> rand() for the very limited set of numbers involved. With rand()'s limited domain you could try simple brute force unless there is a mechanism in place preventing repeated attempts. –  MZB May 14 '11 at 15:29

3 Answers 3

up vote 18 down vote accepted

The ability to guess the next value from rand is tied to being able to determine what srand was called with. In particular, seeding srand with a predetermined number results in predictable output! From the PHP interactive prompt:

[charles@charles-workstation ~]$ php -a
Interactive shell

php > srand(1024);
php > echo rand(1, 100);
97
php > echo rand(1, 100);
97
php > echo rand(1, 100);
39
php > echo rand(1, 100);
77
php > echo rand(1, 100);
93
php > srand(1024);
php > echo rand(1, 100);
97
php > echo rand(1, 100);
97
php > echo rand(1, 100);
39
php > echo rand(1, 100);
77
php > echo rand(1, 100);
93
php > 

This isn't just some fluke. Most PHP versions* on most platforms** will generate the sequence 97, 97, 39, 77, 93 when srand'd with 1024.

To be clear, this isn't a problem with PHP, this is a problem with the implementation of rand itself. The same problem appears in other languages that use the same (or a similar) implementation, including Perl.

The trick is that any sane version of PHP will have pre-seeded srand with an "unknown" value. Oh, but it isn't really unknown. From ext/standard/php_rand.h:

#define GENERATE_SEED() (((long) (time(0) * getpid())) ^ ((long) (1000000.0 * php_combined_lcg(TSRMLS_C))))

So, it's some math with time(), the PID, and the result of php_combined_lcg, which is defined in ext/standard/lcg.c. I'm not going to c&p here, as, well, my eyes glazed over and I decided to stop hunting.

A bit of Googling shows that other areas of PHP don't have the best randomness generation properties, and calls to php_combined_lcg stand out here, especially this bit of analysis:

Not only does this function (gettimeofday) hand us back a precise server timestamp on a silver platter, it also adds in LCG output if we request "more entropy" (from PHP's uniqid).

Yeah that uniqid. It seems that the value of php_combined_lcg is what we see when we look at the resulting hex digits after calling uniqid with the second argument set to a true value.

Now, where were we?

Oh yes. srand.

So, if the code you're trying to predict random values from doesn't call srand, you're going to need to determine the value provided by php_combined_lcg, which you can get (indirectly?) through a call to uniqid. With that value in hand, it's feasible to brute-force the rest of the value -- time(), the PID and some math. The linked security issue is about breaking sessions, but the same technique would work here. Again, from the article:

Here's a summary of the attack steps outlined above:
  • wait for the server to reboot
  • fetch a uniqid value
  • brute force the RNG seed from this
  • poll the online status to wait for target to appear
  • interleave status polls with uniqid polls to keep track of current server time and RNG value
  • brute force session ID against server using the time and RNG value interval established in polling

Just replace that last step as required.

(This security issue was reported in an earlier PHP version (5.3.2) than we have currently (5.3.6), so it's possible that the behavior of uniqid and/or php_combined_lcg has changed, so this specific technique might not be workable any longer. YMMV.)

On the other hand, if the code you're trying to product calls srand manually, then unless they're using something many times better than the result of php_combined_lcg, you're probably going to have a much easier time guessing the value and seeding your local generator with the right number. Most people that would manually call srand also wouldn't realize how horrible of an idea this is, and thus aren't likely to use better values.

It's worth noting that mt_rand is also afflicted by the same problem. Seeding mt_srand with a known value will also produce predictable results. Basing your entropy off of openssl_random_pseudo_bytes is probably a safer bet.

tl;dr: For best results, don't seed the PHP random number generator, and for goodness' sake, don't expose uniqid to users. Doing either or both of these may cause your random numbers to be more guessable.


*: The Suhosin security patch changes the behavior of rand and mt_rand such that they always re-seed with every call. Suhosin is provided by a third party. Some Linux distributions include it in their official PHP packages by default, while others make it an option, and others ignore it entirely.

**: Depending on the platform and the underlying library calls being used, different sequences will be generated than documented here, but the results should still be repeatable unless the Suhosin patch is used.

share|improve this answer
    
Thanks Charles -- between your answer and reading the link on linear congruence generator from Tangurena I feel I have a better grasp on it. I already "knew" that using rand() in this fashion was a bad idea, but know I know why. –  Erik May 14 '11 at 15:58
    
Wow, props for a thorough well spelled out answer, thanks! –  David Hobs Mar 4 at 23:28

the output of PHP's rand() is predictable as its a PRNG

It is a linear congruence generator. That means you have a function that is effectively: NEW_NUMBER = (A * OLD_NUMBER + B) MOD C. If you chart NEW_NUMBER vs OLD_NUMBER you will start to see diagonal lines. Some of the notes on PHP's RAND documentation give examples of how to do so.

This is coming up because I saw a auth library which uses rand() to produce a token for users who have lost passwords, and I assumed this was a potential security hole.

On a windows machine, the max value of RAND is 2^15. This gives the attacker only 32,768 possibilities to check.

Could someone reasonably figure out what random # was generated via rand() at a given moment in time within a few thousand guesses? or even 10,000 guesses? How?

While this article isn't exactly the one you are looking for, it shows how some researchers took an existing implementation of a random number generator and used it to make money on Texas Holdem. There are 52! possible shuffled decks, but the implementation used a 32-bit random number generator (which is the max number out of mt_getrandmax on a windows machine), and seeded it with the time in milliseconds since midnight. This reduced the number of possible shuffled decks from about 2^226 to about 2^27 making it possible to search in real time and know what deck has been dealt.

After doing this I realized that if I were on the outside looking in, I'd have no idea how to guess the token even knowing it was a md5 of rand().

I'd recommend using something in the SHA-2 family as the feds consider md5 broken. Some folks use google to decrypt md5 hashes because they are so common. Just hash something then throw the hash into a google search - basically google has become a giant rainbow table.

share|improve this answer

It is really more accurate to say that given a randomly generated number, the next one is relatively predictable. There are only so many numbers it can be. But that doesn't mean that you could guess it, more that you could write a program that does, pretty quickly.

share|improve this answer
1  
I think the next number is entirely deterministic. Not "relatively" but absolutely. The issue with pseudo-random number generators is that a sequence will pass statistical tests. Two adjacent numbers, while totally deterministic, will have may statistical properties in common with actual random numbers. –  S.Lott May 13 '11 at 22:36
1  
The next number is entirely deterministic. That's what the "pseudo" in pseudo-random number generator means. On the other hand, the information needed to determine that next number is next-to-impossible to acquire in practice. –  Rein Henrichs May 13 '11 at 22:46
    
@S.Lott - I was under the impression that a number could appear multiple times in the 2^32 possible outputs and that each time it appears may be followed by a different number. But given a seed of X, returning a result of Y, the next result will always be the same. Thus, in practice, there might be a handful of numbers that follow Y. I may be wrong though; it's a long time since I really looked at PRNGs. –  pdr May 13 '11 at 22:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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