Secure random number generator

Question

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

• TheConstructor: Shouldn't you use $max - $min when calculating $ivSize and than basically add $min?
• Xenos: 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.
• Nicolas Bouvrette: @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: @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()
• Xenos: 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)

Answer 1

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

• Nicolas Bouvrette: 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: 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: I managed to fix it using return $r %($max - $min + 1)+ $min; But I'm not sure this is the best approach?
• Xenos: 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.
• Nicolas Bouvrette: 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?