patternphpMinor
Secure random number generator
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.
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 are0x00000000...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.