# Secure random number generator

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;
}

• Shouldn't you use $max -$min when calculating $ivSize and than basically add $min? – TheConstructor Nov 22 '14 at 21:09
• For $min=0,$max=14 then $s = (($r%15)+15)%15. Since $r>0 then +15)%15 is useless, so $s = $r%15. For $r in {0..254}, $s is in {0..14} and for $r=255 (the $r max), $s=0. The value 0 has one more chance to appear: p(0)=18/256=7.03% when others have p(1,..,14)=17/256=6.64%. Output is not equiprobable. Not sure how it can impact the security. – Xenos Nov 22 '14 at 21:34
• @TheConstructor Actually unless I misunderstood, $ivSize is in bytes so I'm converting$max into Hex, and then measuring the Hex's string length which something will omit the leading "0" (e.g. 0fff will be fff). So then I'm either adding 0 or 1 to the length depending if the length is odd or even. Then I divide by 2 to get the Byte size. Does that make sense? – Nicolas Bouvrette Nov 22 '14 at 22:53
• @Xenos Very interesting finding... any suggestion on how to fix that? Not sure if it has any impact either but other options I found was using floats which I suspect would cause similar behavior due to the lack of precision of round() – Nicolas Bouvrette Nov 22 '14 at 23:03
• You can use $ivSize = ceil(log($max-$min, 0x100));instead. ceil(log(N,k)) counts how many digit N has in base k (byte is a 256-base where digits are 0..255) – Xenos Nov 22 '14 at 23:14 ## 1 Answer 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); }  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) plus one remaining interval I. Then, we map each [KN..(K+1)N[ to [0..N-1].

So far, each value from [0..N-1] has exactly S ways to be picked.

Now, let's deal with the remaining interval I (might be an empty interval). If $r is in that interval, then we cannot do anything with it: we cannot easily match elements from I with elements from [0..N-1] because their size mismatch (I has less elements). We could group elements from [0..N-1] and then match these elements with I but that's far too complex for the earn. So, if $r is in that remaining I, easy way is just to pick another $r. Since I has h = (0x7fffffff+1)%N elements, that's why we keep picking random values as long as $r > (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 <= $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); }  • Wow awesome - I just tested it and the$min / $max seems to have no impact on the return value. I'll see if I figure out why but it does look equiprobable – Nicolas Bouvrette Nov 23 '14 at 13:25 • Ok I have no idea how to repair this.. I will most likely need your help to fix the$min / $max situation because all I can think of it add the modulo at the end but that would defeat the purpose of your fix :) – Nicolas Bouvrette Nov 23 '14 at 13:33 • I managed to fix it using return$r %($max -$min + 1)+ $min; But I'm not sure this is the best approach? – Nicolas Bouvrette Nov 23 '14 at 14:00 • You're right, I've focused on the proba and forgot to map each [KN..(K+1)N[ to [0..N-1] (iow, the return). Your fix is OK for 2nd code, use bcmod for first one since $N (the $max -$min +1) can be grater than 0x7fffffff. – Xenos Nov 23 '14 at 14:31
• Very cool work... much appreciated! By the way your last update returns value from [$min,$max+1]. This seems to solve it though but I'm sure you got a nicer implementation in mind: return bcmod($r, ($max - $min + 1)) +$min; Also I'm not sure, but what is the main different between the two versions? – Nicolas Bouvrette Nov 23 '14 at 14:40