Page 1 of 1

Generating Random Numbers

Posted: Tue Dec 16, 2008 7:23 am
by kaisellgren
Hello guys and gals!

I want to strike up a discussion about generating random numbers in PHP, or should I say "with PHP". First of all, I will tell somethings that I know and one thing to be told is that the random number generation provided by PHP is not so "random". This applies to both rand() and mt_rand(). Both of these algorithms are seeded by a single 32-bit dword when they are first used in a process or one of the seeding functions srand() or mt_srand() is called. These random number generators are not enough for cryptographic usage. These 32-bit seeds have to be guessed and the amount of previously generated random numbers too in order to exploit their weaknesses. These functions seem fairly enough to protect from brute forcing, as the brute forcer has to spend its whole life on it.

Let's discuss more about weak seading first.

I often see something like this being used in scripts:

Code: Select all

mt_srand((double)microtime()*1000000);
These kind of approaches are very weak mainly, because microtime() gives a factor between 0 to 1 while the *1000000 is a factor of 1000000 obviously that means there are only 1000000 possible seeds which is strength of only 20-bits.

Because of weak seedings, not-so-truly randoms, problems with PHP's internal seedings, ... we have to find another way to do it.

Method #1

Code: Select all

if (($handle = @fopen('/dev/urandom','rb'))) // Remember to put parenthesis around the clause, so we assign the boolean success into our if statement :)
{
$rand = fread($handle,8); // 8 is just an example that we might want to use, type 64 for to get 512 bits strong random
fclose($handle);
}
In this method we rely on the Unix urandom to retrieve a random number. If that didn't work for any reason we might want to try now method 2.

Method #2

Code: Select all

if (($handle = @fopen('/dev/random','rb')))
{
$rand = fread($handle,8);
fclose($handle);
}
This time we rely on the /dev/random and we hope it works. The difference between urandom and random is that the u stands for unlocked, which reuses the internal pool to produce more pseudo-random bits. I prefer using urandom over random mainly, because urandom can be trusted more since the way of filling these randoms is different -- sometimes especially after boot the /dev/random is empty and the pool has to be first filled with some random data from device noise.

What other methods would you might use for generating random numbers?

I've been thinking about these:

Code: Select all

/usr/local/apache2/conf/rand.dat
/dev/egd-pool
/usr/local/ssl/bin/openssl
It's clear that these do not often exist in systems... and especially if we are working on an IIS, we won't be able to use at least the (u)randoms. :P

Another way of generating more random numbers without relying on these outside resources is to make a seeding system that is different from all other scripts even if they are on the same server. The following demonstration example is thanks to Stefan Esser.

Code: Select all

function rand2($min = 0,$max = 0)
 {
  global $rnd_value,$gseed;
  $seed = $gseed;
 
  // Reset $rnd_value after 14 uses
  // 32(md5) + 40(sha1) + 40(sha1) / 8 = 14 random numbers from $rnd_value
  if ( strlen($rnd_value) < 8 ) {
    $rnd_value = md5( uniqid(microtime() . mt_rand(), true ) . $seed );
    $rnd_value .= sha1($rnd_value);
    $rnd_value .= sha1($rnd_value . $seed);
    $seed = md5($seed . $rnd_value);
    $gseed = $seed;
  }
 
  // Take the first 8 digits for our value
  $value = substr($rnd_value, 0, 8);
 
  // Strip the first eight, leaving the remainder for the next call to rand2().
  $rnd_value = substr($rnd_value, 8);
 
  $value = abs(hexdec($value));
 
  // Reduce the value to be within the min - max range
  // 4294967295 = 0xffffffff = max random number
  if ( $max != 0 )
    $value = $min + (($max - $min + 1) * ($value / (4294967295 + 1)));
 
  return abs(intval($value)); 
}
Before using the above function even for the first time, we make an initial random number, where something like uniqid() should be fair enough.. and we must store the $rnd_value and $gseed in a file, or preferabely in a database. If it's stored in a file, it must be outside the document root or other way protected.

So now I have said what I have been thinking, now it's your time to shed some light on us about what you know and possibly fix/improve my sentences or grammatic errors :D

Re: Generating Random Numbers

Posted: Tue Dec 16, 2008 10:37 am
by Hannes2k
Hi,
if I do not have access to /dev/urandom I build normaly a md5/sha1 hash from mt_rand/rand + user informations (HTTP referer, which browser, POST and GET vars, SID etc.) + system informations (memory_usage etc.).

Especially if the users sends some data (with HTTPS) and you want to decrypt these data, you can create the md5/sha1 from the data, mix it up with some additional data (user+system informations etc.) and then you get a relatively good random number.

Re: Generating Random Numbers

Posted: Tue Dec 16, 2008 11:37 am
by kaisellgren
Hannes2k wrote:Hi,
if I do not have access to /dev/urandom I build normaly a md5/sha1 hash from mt_rand/rand + user informations (HTTP referer, which browser, POST and GET vars, SID etc.) + system informations (memory_usage etc.).

Especially if the users sends some data (with HTTPS) and you want to decrypt these data, you can create the md5/sha1 from the data, mix it up with some additional data (user+system informations etc.) and then you get a relatively good random number.
Yeah I agree system information that varies is help, but I still would not like to include the built in (mt_)rand to prevent look up tables, guessing, etc

In general for generating randoms, passing browser info might not be a good idea -- since the attacker (yes we always think about attackers ;)) knows and can even set it h(im/er)self. Giving an attacker the choice of affecting the random is no way a good idea.

If we are generating session ID's for instance, then the attacker is not the one who created those, so it's safe to use some unchangeable values like the IP. However, user agent is easily 'stolen' and then the attacker 'knows' some part of the session ID already.

Re: Generating Random Numbers

Posted: Thu Dec 25, 2008 3:14 pm
by aditya2071990
PHP's new uniqid() function is weak too?

Re: Generating Random Numbers

Posted: Thu Dec 25, 2008 3:42 pm
by kaisellgren
aditya2071990 wrote:PHP's new uniqid() function is weak too?
uniqid() is not new.

uniqid() is a function that generates, well, a unique id. It's based on information you give plus other information such as the time in microseconds and on process id and running time of the linear congruential generator. Thus, the randomness should be fairly well IF the data provided within is too.

If you are using it like uniqid(mt_rand(),true) then it's not "safe". The strength of your algorithm is as weak as the weakest node in your chain. In this case the weakest node is the mt_rand(), so it's not anyway stronger than it.

One way of generating a good random strong session id would be to read /dev/(u)random and pass the random value to hash('sha512',uniqid($the_rand.$_SERVER['REMOTE_ADDR'].implode('',fstat(__FILE__,'r')).memory_get_usage(),true)) that is strong. I assume you wanted to create a session id since that is often where uniqid() is needed for.

Re: Generating Random Numbers

Posted: Fri Feb 13, 2009 10:49 pm
by tkmorris
Wonderful! Based on what I've seen on the web, this topic included, I was able to think about this:

Code: Select all

function genRandom($len, $chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789')
{
    $string = '';
    $charlen = strlen($chars);
    while($stringlen < $len)
    {
        if(($handle = @fopen('/dev/urandom','rb')))
        {
            $rand = fread($handle,1);
            fclose($handle);
        }
        $ord = ord($rand);
        $reason = $ord / strlen($chars);
        if($reason > 1)
            $string .= $chars{$ord};
        else
        {
            $pos = floor($reason) * $ord;
            $pos = $ord - $pos;
            $string .= $chars{$pos};
        }
        $stringlen = strlen($string);
        //  echo "ord = $ord<br />reason = $reason<br />";
    }
    return $string;
}
I did similar things, so this is a special case, where I've to control the output, even with some problems, as I can only use ascii[no real problem for most persons].

Re: Generating Random Numbers

Posted: Sat Feb 14, 2009 1:41 pm
by kaisellgren
tkmorris wrote:Wonderful! Based on what I've seen on the web, this topic included, I was able to think about this:

Code: Select all

function genRandom($len, $chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789')
{
    $string = '';
    $charlen = strlen($chars);
    while($stringlen < $len)
    {
        if(($handle = @fopen('/dev/urandom','rb')))
        {
            $rand = fread($handle,1);
            fclose($handle);
        }
        $ord = ord($rand);
        $reason = $ord / strlen($chars);
        if($reason > 1)
            $string .= $chars{$ord};
        else
        {
            $pos = floor($reason) * $ord;
            $pos = $ord - $pos;
            $string .= $chars{$pos};
        }
        $stringlen = strlen($string);
        //  echo "ord = $ord<br />reason = $reason<br />";
    }
    return $string;
}
I did similar things, so this is a special case, where I've to control the output, even with some problems, as I can only use ascii[no real problem for most persons].
That is kind of slow. Why reopening the file again and again?

Re: Generating Random Numbers

Posted: Sat Feb 14, 2009 5:35 pm
by tkmorris
I did not looked at it, was just sharing:

Code: Select all

function genRandom($len, $chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789')
{
    $string = '';
    $charlen = strlen($chars);
    if(($handle = @fopen('/dev/urandom','rb')))
    {
        while($stringlen < $len)
        {
            $rand = fread($handle,1);
            $ord = ord($rand);
            $reason = $ord / strlen($chars);
            if($reason > 1)
                $string .= $chars{$ord};
            else
            {
                $pos = floor($reason) * $ord;
                $pos = $ord - $pos;
                $string .= $chars{$pos};
            }
            $stringlen = strlen($string);
            //echo "<pre>ord = $ord\nreason = $reason</pre>";
        }
        fclose($handle);
    }
    return $string;
}
And yes, it is slow :mrgreen:
There's no reason to actually do that.