4 ms·
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-
by dantillberg 11y ago
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)
- sarciszewski 11y agoYes, don't use % even with a CSPRNG! https://stackoverflow.com/a/31374501/2224584 https://stackoverflow.com/a/31374501/2224584
- tptacek 11y agoIt's true that's an anti-pattern, but it's not a particularly exploitable one in most of the places that really need CSPRNGs.
- paragon_init 11y agoAgreed. 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.
- lucb1e 11y agoOh? I get perfectly sane results using modulo, as it should if it is actually a completely random number: http://3v4l.org/nIBGT http://3v4l.org/nIBGT
- sarciszewski 11y agoYou 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 http://3v4l.org/EgfPR - notice 0 is significantly more common than the other values when reduced mod 17 http://3v4l.org/LXmKq http://3v4l.org/LXmKq - same with mod 15 https://defuse.ca/generating-random-passwords.htm https://defuse.ca/generating-random-passwords.htm
- foobar2020 11y agoIt 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.
- esnard 11y agoActually 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.
- foobar2020 11y agoWhoops, you are right, I should have written (modulus) and not (modulus + 1). Another reason why this is an anti-pattern :). Thanks for correcting me!