Gathering entropy in web apps to create (more) secure random numbers

Question

after several days of research and discussion i came up with this method to gather entropy from visitors (u can see the history of my research here)

when a user visits i run this code:

$entropy=sha1(microtime().$pepper.$_SERVER['REMOTE_ADDR'].$_SERVER['REMOTE_PORT'].
$_SERVER['HTTP_USER_AGENT'].serialize($_POST).serialize($_GET).serialize($_COOKIE)); 

note: pepper is a per site/setup random string set by hand.

then i execute the following (My)SQL query:

$query="update `crypto` set `value`=sha1(concat(`value`, '$entropy')) where name='entropy'";

that means we combine the entropy of the visitor's request with the others' gathered already.

that's all.

then when we want to generate random numbers we combine the gathered entropy with the output:

$query="select `value` from `crypto` where `name`='entropy'";
//...
extract(unpack('Nrandom', pack('H*', sha1(mt_rand(0, 0x7FFFFFFF).$entropy.microtime())))); 

note: the last line is a part of a modified version of the crypt_rand function of the phpseclib.

please tell me your opinion about the scheme and other ideas/info regarding entropy gathering/random number generation.

ps: i know about randomness sources like /dev/urandom. this system is just an auxiliary system or (when we don't have (access to) these sources) a fallback scheme.

Answer 1

In the best scenario, your biggest danger is a local user disclosure of information exploit. In the worst scenario, the whole world can predict your data. Any user that has access to the same resources you do: the same log files, the same network devices, the same border gateway, or the same line that runs between you and your remote connections allows them to sniff your traffic by unwinding your random number generator.

How would they do it? Why, basic application of information theory and a bit of knowledge of cryptography, of course!

You don't have a wrong idea, though! Seeding your PRNG with real sources of randomness is generally quite useful to prevent the above attacks from happening. For example, this same level of attack can be exploited by someone that understands how /dev/random gets populated on a per-system basis if the system has low entropy or its sources of randomness are reproducible.

If you can sufficiently secure the processes that seed your pool of entropy (for example, by gathering data from multiple sources over secure lines), the likelihood that someone is able to listen in becomes smaller and smaller as you get closer and closer to the desirable cryptographic qualities of a one-time pad.

In other words, don't do this in PHP, using a single source of randomness fed into a single Mersenne twister. Do it properly, by reading from your best, system-specific alternative to /dev/random, seeding its entropy pool from as many secure, distinct sources of "true" randomness as possible. I understand you've stated that these sources of randomness are inaccessible, but this notion is strange when similar functions are afforded to all major operating systems. So, I suppose I find the concept of an "auxiliary system" in this context to be dubious.

This will still be vulnerable to an attack by a local user cognizant of your sources of entropy, but securing the machine and increasing the true entropy within /dev/random will make it far more difficult for them to do their dirty work short of a man-in-the-middle attack.

As for cases where /dev/random is indeed accessible, you can seed it fairly easily:

• Look at what options exist on your system for using /dev/hw_random
• Embrace rngd (or a good alternative) for defining your sources of randomness
• Use rng-tools for inspecting and improving your randomness profile
• And finally, if you need a good, strong source of randomness, consider investing in more specialized hardware.

Best of luck in securing your application.

---

PS: You may want to give questions like this a spin at Security.SE and Cryptography.SE in the future!

Answer 2

Use Random.Org

If you need truly random numbers, use random.org. These numbers are generated via atmospheric noise. Besides library for PHP, it also has a http interface which allows you to get truly random numbers by simple requests:

https://www.random.org/integers/?num=10&min=1&max=6&col=1&base=10&format=plain&rnd=new

This means that you can simply retrieve the real random numbers in PHP without any additional PECL exension on the server.

If you don't like other users to be able to "steal" your random numbers (as MrGomez' argues), just use https with a certificate checking. Here follows an example with https certificate checking:

$url = "https://www.random.org/integers/?num=10&min=1&max=6&col=1&base=10&format=plain&rnd=new";
$ch = curl_init();
curl_setopt($ch, CURLOPT_URL, $url);
curl_setopt($ch, CURLOPT_RETURNTRANSFER, true);
curl_setopt($ch, CURLOPT_SSL_VERIFYPEER, true);
curl_setopt($ch, CURLOPT_SSL_VERIFYHOST, 2);
$response = curl_exec($ch);
if ($response === FALSE)
        echo "http request failed: " . curl_error($ch);
else
        echo $response;    
curl_close($ch);

If you need more information on how to create https requests:

• Make a HTTPS request through PHP and get response
• http://unitstep.net/blog/2009/05/05/using-curl-in-php-to-access-https-ssltls-protected-sites/

More on security

Again, some might argue that if the attacker queries random.org at the same time as you, he might get the same numbers and predict.. I don't know if random.org would even work this way, but if you are really concerned, you may lessen the chance by fooling the attacker with dummy request which you throw out, or use only a certain part of the random numbers you get.

As MrGomez notes in his comment, this shall not be considered as an ultimate solution to security, but only as one of possible sources of entropy.

Performance

Of course, if you need a blitz latency then doing one random.org request per one client request might not be best idea... but what about just doing one bigger request to pre-cache the random numbers like every 5 minutes?

Answer 3

To come to the point, as far as i know there is no way to generate entrophy inside a PHP script, sorry for this non-answer. Even if you look at well etablished scripts like phppass, you will see, that their fallback system cannot do some magic.

The question is, whether you should try it anyway or not. Since you want to publish your system under GPL, you propably don't know in what scenario it will be used. In my opinion it's best then to require a random source, or to fail fast (die with an appropriate error message), so a developer who wants to use your system, knows immediately, that there is a problem.

To read from the random source, you could call the mcrypt_create_iv() function...

$randomBinaryString = mcrypt_create_iv($length, MCRYPT_DEV_URANDOM);

...this function reads from the random pool of the operating system. Since PHP 5.3 it does it on Windows servers as well, so you can leave it to PHP to handle the random source.

Answer 4

If you have access to /dev/urandom you can use this:

function getRandData($length = 1024) {
    $randf  = fopen('/dev/urandom', 'r');
    $data   = fread($randf, $length);
    fclose($randf);
    return $data;
}

UPDATE: of course you should have some backup in case opening the device fails

Answer 5

Update 2: Code Review Warning to Everyone: Dont use The code in the original question. It's a security liability. If this code is online anywhere Remove it as it open the whole system, network and database to a malevolent user. Your not only exposing your code but all of your users data.

Do not ever Serialize user inputs. If in your code your already doing it, Stop your server and change your code. This is a great exemple of Not doing crypto by yourself.

Update 1: For real security you need to have UN-guessable randomess in your entropy. A suitable option to add entropy has your Question refer-to is to use the Delta of your script's execution time Not microtime() by itself . Because the Delta Rely on the load of your server. And so is a combination of the hardware environment, temperature, network load, power load, disk access, Cpu usage and voltage fluctuation which together are unpredictable.

Using Time(), timestamp or microtime is a flaw in your implementation.

Script execution Delta Exemple code coming:

@martinstoeckli stated correctly that a Suitable Random generation for crypto is from

 mcrypt_create_iv($lengthinbytes, MCRYPT_DEV_URANDOM);

but is outside the requirements of not having a crypto module

In SQL use the RAND() in conjunction with your generated number. http://www.tutorialspoint.com/mysql/mysql-rand-function.htm

Php offer as well the Rand() function

http://php.net/manual/en/function.rand.php

they wont give you the same number so you could use both.

Answer 6

should you have access to client side, you can enable mouse movement tracking - this is what true crypt is using for extra level of entropy.

Answer 7

as i have said before, my rand function is a modified version of phpseclib's crypt_random function. u could see it in the link given on my first post. at least the author of the phpseclib cryptographic library confirmed it; not enough for ordinary apps? i don't speak of extreme/theoretical security, just speak about practical security to the extent really needed and at the same time 'easily'/'sufficiently low cost' available for almost all of the ordinary applications on the web.

phpseclib's crypt_random effectively and silently falls back to the mt_rand (which u should know is really weak) in the worst case (no openssl_random_pseudo_bytes or urandom available), but my function uses a much more secure scheme in such cases. it's just a fall back to a scheme that brute-forcing/predicting its output is much harder and (should be) in practice sufficient for all ordinary apps/sites. it uses possible (in practice very likely and hard to predict/circumvent) extra entropy that is gathered over time which quickly becomes almost impossible to know for outsiders. it adds this possible entropy to the mt_rand's output (and also to the output of other sources: urandom, openssl_random_pseudo_bytes, mcrypt_create_iv). if u are informed u should know, this entropy can be added but not subtracted. in the (almost surely really rare) worst case, that extra entropy would be 0 or some too tiny amount. in the mediocre case, which i think is almost all of the cases, it would be even more than practically necessary, i think. (i have had vast cryptography studies, so when i say i think, it is based on a much more informed and scientific analysis than ordinary programmers).

see the full code of my modified crypt_random:

function crypt_random($min = 0, $max = 0x7FFFFFFF)
{
    if ($min == $max) {
        return $min;
    }

    global $entropy;

    if (function_exists('openssl_random_pseudo_bytes')) {
        // openssl_random_pseudo_bytes() is slow on windows per the following:
        // http://stackoverflow.com/questions/1940168/openssl-random-pseudo-bytes-is-slow-php
        if ((PHP_OS & "\xDF\xDF\xDF") !== 'WIN') { // PHP_OS & "\xDF\xDF\xDF" == strtoupper(substr(PHP_OS, 0, 3)), but a lot faster
            extract(unpack('Nrandom', pack('H*', sha1(openssl_random_pseudo_bytes(4).$entropy.microtime()))));
            return abs($random) % ($max - $min) + $min; 
        }
    }

    // see http://en.wikipedia.org/wiki//dev/random
    static $urandom = true;
    if ($urandom === true) {
        // Warning's will be output unles the error suppression operator is used.  Errors such as
        // "open_basedir restriction in effect", "Permission denied", "No such file or directory", etc.
        $urandom = @fopen('/dev/urandom', 'rb');
    }
    if (!is_bool($urandom)) {
        extract(unpack('Nrandom', pack('H*', sha1(fread($urandom, 4).$entropy.microtime()))));
        // say $min = 0 and $max = 3.  if we didn't do abs() then we could have stuff like this:
        // -4 % 3 + 0 = -1, even though -1 < $min
        return abs($random) % ($max - $min) + $min;
    }


    if(function_exists('mcrypt_create_iv') and version_compare(PHP_VERSION, '5.3.0', '>=')) {
        @$tmp16=mcrypt_create_iv(4, MCRYPT_DEV_URANDOM);
        if($tmp16!==false) {
            extract(unpack('Nrandom', pack('H*', sha1($tmp16.$entropy.microtime()))));
            return abs($random) % ($max - $min) + $min;
        }
    }


    /* Prior to PHP 4.2.0, mt_srand() had to be called before mt_rand() could be called.
       Prior to PHP 5.2.6, mt_rand()'s automatic seeding was subpar, as elaborated here:

       http://www.suspekt.org/2008/08/17/mt_srand-and-not-so-random-numbers/

       The seeding routine is pretty much ripped from PHP's own internal GENERATE_SEED() macro:

       http://svn.php.net/viewvc/php/php-src/tags/php_5_3_2/ext/standard/php_rand.h?view=markup */
    static $seeded;
    if (!isset($seeded) and version_compare(PHP_VERSION, '5.2.5', '<=')) { 
        $seeded = true;
        mt_srand(fmod(time() * getmypid(), 0x7FFFFFFF) ^ fmod(1000000 * lcg_value(), 0x7FFFFFFF));
    }

    extract(unpack('Nrandom', pack('H*', sha1(mt_rand(0, 0x7FFFFFFF).$entropy.microtime()))));
    return abs($random) % ($max - $min) + $min;

}

$entropy contains my extra entropy which comes from all requests parameters' entropy combined till now + current request's parameters entropy + the entropy of a random string (*) set by hand at the installation time.

*: length: 22, composed of lower and uppercase letters + numbers (more than 128 bits of entropy)

Answer 8

rn_rand() should be getting used not rand()