3
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Shouldn't you use $max - $min when calculating $ivSize and than basically add $min? \$\endgroup\$ – TheConstructor Nov 22 '14 at 21:09
  • \$\begingroup\$ 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. \$\endgroup\$ – Xenos Nov 22 '14 at 21:34
  • \$\begingroup\$ @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? \$\endgroup\$ – Nicolas Bouvrette Nov 22 '14 at 22:53
  • \$\begingroup\$ @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() \$\endgroup\$ – Nicolas Bouvrette Nov 22 '14 at 23:03
  • \$\begingroup\$ 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) \$\endgroup\$ – Xenos Nov 22 '14 at 23:14
2
\$\begingroup\$
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);
}
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Nicolas Bouvrette Nov 23 '14 at 13:25
  • \$\begingroup\$ 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 :) \$\endgroup\$ – Nicolas Bouvrette Nov 23 '14 at 13:33
  • \$\begingroup\$ I managed to fix it using return $r %($max - $min + 1)+ $min; But I'm not sure this is the best approach? \$\endgroup\$ – Nicolas Bouvrette Nov 23 '14 at 14:00
  • \$\begingroup\$ 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. \$\endgroup\$ – Xenos Nov 23 '14 at 14:31
  • \$\begingroup\$ 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? \$\endgroup\$ – Nicolas Bouvrette Nov 23 '14 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.