I was just pondering about php rand() function, and thinking about how I could remake it, and I came up completely stupified.
How do random number generators work?
Random Numbers – How Do Random Number Generators Work?
numbersrandom
Related Solutions
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'suniqid).
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.
Update for PHP 7:
PHP 7.0 introduces random_bytes and random_int as core functions. They use the underlying system's CSPRNG implementation, making them free from the problems that a seeded random number generator has. They're effectively similar to openssl_random_pseudo_bytes, only without needing an extension to be installed. A polyfill is available for PHP5.
*: 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.
This is a known bug which isn't related to PHP, but inherant to the windows API used by PHP. The random function of this API is very bad.
This problem will not exist on Linux or MacOS (or any other system).
You can learn more about this here: http://cod.ifies.com/2008/05/php-rand01-on-windows-openssl-rand-on.html
If it is more visible with some value, this is mostly because of the dimensions of the image, and the clear lines formed by the pattern. This is definitively linked to our perception, some patterns looks more random than others.
The human brain random function is very buggy. What we see as random or not isn't reliable at all. This is a known phenomenon but off topic here.
Best Answer
Random Number Generators(RNGs) are really generating pseudorandom numbers, since it's impossible to actually generate a TRULY random number. The only really truly random things are acts of God, like lightning.
This wikipedia article might be able to help you out in the explanation: http://en.wikipedia.org/wiki/Random_number_generators
From what I understand, there are basically two parts of an RNG: the seed, and then the random number chosen from that seed. When you seed the RNG, you are giving it an equivalent to a starting point. That starting point then has a bunch of numbers that are "inside" of it that the program chooses from. In PHP, you can use srand() to "shuffle" the seeds, so you almost always get a different answer. You can then use rand(min, max) to go into the seed and choose a number between the min and the max, inclusive.
WARNING, POSSIBLE CHEESY ANALOGY AHEAD!
Think of each 'seed' as an ice chest, and then the random numbers as ice cubes. Let's say you have 1000 ice chests and each chest has 1000 ice cubes inside. At the county fair, they'll choose an ice chest to start using for drinks, and they can only use one ice cube. However, they only need ice cubes bigger than 1 cubic inch. So they'll choose a chest at random between those 1000 chests, and then they'll choose an ice cube inside that chest at random. If it works for the size they want, they use it. If it's not, they put it back in the chest with the others. If they want to make it a little more fun they change chests beforehand for total obliviousness, if you will!
As for how PHP actually physically chooses the seed and the random number, I don't have enough knowledge for that(which is probably what you were wondering the most about!). I wouldn't try and redo the rand() function; for most web based applications that you'll make, rand() should suffice for any random number you'll need.
Also check out linear congruential generators, this might be more of what you're looking for if you want the dirty details: http://en.wikipedia.org/wiki/Linear_congruential_generator
Hope this helps!