HiveBrain v1.2.0
Get Started
← Back to all entries
patternphpMinor

Secure random number generator

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
randomnumbersecuregenerator

Problem

I just wrote this function and I was curious if anyone could find any flaws in it.

It look pretty secure to me but I just want to make sure since I'm no cryptography expert.

function urandom_rand($min, $max) {

    if ($max <= $min) {
        trigger_error('Minimum value must be greater than maximum value.');
    }

    $maxHex = dechex($max);
    $maxHexLength = strlen($maxHex);
    $ivSize = (int)($maxHexLength + ($maxHexLength % 2)) / 2;
    // Reads bytes from /dev/urandom (or its Windows equivalent) - byte size is based on max value
    $r = hexdec(bin2hex(mcrypt_create_iv($ivSize, MCRYPT_DEV_URANDOM)));
    // Min/max modulo conversion to avoid using floats/round which is imprecise and prone to attacks
    $r = (($r - $min) % ($max - $min + 1) + ($max - $min + 1)) % ($max - $min + 1) + $min;
    return $r;
}

Solution

function urandom_rand($min = 0, $max = 0x7FFFFFFF)
{
    $min = (int)$min;
    $max = (int)$max;
    if ($max  0x7FFFFFFF)
        trigger_error('Values must be between 0 and 2147483647.');

    $M = bcadd(0x7FFFFFFF,1); // (up bound of iv)+1
    $N = bcadd($max-$min, 1); // how many different values this function can return
    $h = bcmod($M, $N); // the last h integers from unpack are "invalids"

    do
    {
        $bytes = mcrypt_create_iv(4, MCRYPT_DEV_URANDOM);
        $r = unpack("N", $bytes)[1] & 0x7FFFFFFF;
    } while ($r > ($M-$h));
    return (bcmod($r, $N) + $min);
}


Valid values for $bytes are

0x00000000...0xffffffff

After the unpack(), every value from $bytes is matching exactly one value of:

-0x80000000..0x00000000..0x7ffffffff

So, perfect-equiprobability. After bitwise &, every value from unpack() matches exactly two values of:

0x00000000..0x7ffffffff

Now, we cut that interval into S sub-intervals of [KN..(K+1)N[ (S>=1 because $max (0x7fffffff+1)-h.

Only problem you can have is that the function
urandom_rand() may take anytime to execute, since it loops until it luckily gets a $r outside I.

Here is one scenario of exploiting the inequiprobability problem:

Let's say you pick a random number out of
{0,1,...14}, expecting a probability of p(0)=P(1)=...=p(14)=1/15=6.67%. People can bet on a number, and they will get 14.5x their bet if they win (the 0.5x remaining is your commission).

If you actually have
p(0)=7.03% and p(1)=..=p(14)=6.64% then one can bet on 0 and expect 7.03% chances to win 14.5x their bet. So they averagely win 7.03%*14.5=1.01935. Since it's greater than 1, you can keep betting forever and be a winner, despite the casino's commission.

There are probably similar betting game applied to cryptography.

Last correction to my comment about
ceil(log(N,k)) (I was tired yesterday night): correct formula is

floor(log(N,k)+1)

gives the number of digits of
N in base k for N integer and N>=1`

Without using bc function:

function urandom_rand($min = 0, $max = 0x7FFFFFFF)
{
    $min = (int)$min;
    $max = (int)$max;
    if ($max  0x7FFFFFFF)
        trigger_error('Values must be between 0 and 2147483647.');

    // Decrease everything from 1st version by $N to avoid INT overflow
    // if min == 0 and max == 0x7fffffff then these M,N,h will overflow
    // BUT in such case, MNh won't be used (see loop below)
    // 1  ($M - $h));
    return (($r%$N)+$min);
}

Code Snippets

function urandom_rand($min = 0, $max = 0x7FFFFFFF)
{
    $min = (int)$min;
    $max = (int)$max;
    if ($max <= $min)
        trigger_error('Minimum value must be greater than maximum value.');
    if ($min < 0 || $max > 0x7FFFFFFF)
        trigger_error('Values must be between 0 and 2147483647.');

    $M = bcadd(0x7FFFFFFF,1); // (up bound of iv)+1
    $N = bcadd($max-$min, 1); // how many different values this function can return
    $h = bcmod($M, $N); // the last h integers from unpack are "invalids"

    do
    {
        $bytes = mcrypt_create_iv(4, MCRYPT_DEV_URANDOM);
        $r = unpack("N", $bytes)[1] & 0x7FFFFFFF;
    } while ($r > ($M-$h));
    return (bcmod($r, $N) + $min);
}
function urandom_rand($min = 0, $max = 0x7FFFFFFF)
{
    $min = (int)$min;
    $max = (int)$max;
    if ($max <= $min)
        trigger_error('Minimum value must be greater than maximum value.');
    if ($min < 0 || $max > 0x7FFFFFFF)
        trigger_error('Values must be between 0 and 2147483647.');

    // Decrease everything from 1st version by $N to avoid INT overflow
    // if min == 0 and max == 0x7fffffff then these M,N,h will overflow
    // BUT in such case, MNh won't be used (see loop below)
    // 1 <= $max - $min <= 0x7FFFFFFE
    $N = ($max - $min) + 1; // 2 <= $N <= 0x7FFFFFFF
    $M = (0x7FFFFFFF - $N) + 1; // 1 <= $M <= 0x7FFFFFFE
    $h = $M % $N; // 0 <= $h <= $N-1 <= 0x7FFFFFFE

    do
    {
        $bytes = mcrypt_create_iv(4, MCRYPT_DEV_URANDOM);
        $r = unpack("N", $bytes)[1] & 0x7FFFFFFF;
        if ($min == 0 && $max == 0x7FFFFFFF)
            return $r; // direct corresponding
    } while (($r - $N) > ($M - $h));
    return (($r%$N)+$min);
}

Context

StackExchange Code Review Q#70595, answer score: 3

Revisions (0)

No revisions yet.