Hacker News Reader

Comment by dantillberg | Hacker News Reader

I believe it's also generally an anti-pattern to do things like "num = rand() % max" or "num = rand() & bit_mask" where rand() returns an integer from a pseudo-random number generator, right?

PHP may not do a very good job at ensuring an even distribution throughout the space of possible integers, but for PRNGs in general (especially the quick & dirty ones), the worst place to grab bits from is the least-significant bits.

(my source is that I hung out with a copy of Numerical Recipes in college; Numerical Recipes has a nice chapter for learning about PRNGs, along with example code for a number of implementations)

View on HN

It is OK to do (rand() % modulus) when (modulus + 1) divides (MAX_RAND + 1). Otherwise you will end up with non-uniform distribution.

But yes, in general the rand-modulo pair is an anti-pattern.

Actually the modulus needs to divide the number of possible output of rand(), which is by definition (MAX_RAND - MIN_RAND + 1), if you want to have a uniform distribution (assuming your rand function has a uniform distribution).

In the specific case of mt_rand, MIN_RAND is 0 by default, then the modulus needs to divide (MAX_RAND + 1).

In the general case, there's no rule in any uniform continuous implementation of rand such as (modulus + 1) needs to divide a specific number.

Whoops, you are right, I should have written (modulus) and not (modulus + 1). Another reason why this is an anti-pattern :). Thanks for correcting me!

Yes, don't use % even with a CSPRNG!

https://stackoverflow.com/a/31374501/2224584

It's true that's an anti-pattern, but it's not a particularly exploitable one in most of the places that really need CSPRNGs.

Agreed. It's a red flag for "expect more exploitable issues to be found around the corner" and can result in biased distributions, but it by itself does not break a RNG.

Oh? I get perfectly sane results using modulo, as it should if it is actually a completely random number: http://3v4l.org/nIBGT

You found the exception! Congratulations!

You're using a bucket size which is a power of 2. A random byte fits on the interval of [0, 255] which is evenly distributed modulo 256, which if you reduce mod 2^N for 1 < N < 8 will still produce a uniform distribution.

If you copied my JS code into your console and changed the 54 to 64 the bias evaporates. Hooray :D

However, for arbitrary ranges, you should use an unbiased selection strategy to ensure a uniform distribution.

http://3v4l.org/EgfPR - notice 0 is significantly more common than the other values when reduced mod 17

http://3v4l.org/LXmKq - same with mod 15

https://defuse.ca/generating-random-passwords.htm

Reply on news.ycombinator.com