Misuse of Math.random() to generate random integers

[dimitri-xyz]

In

browser-laptop/app/extensions/brave/content/scripts/adInsertion.js

Lines 74 to 75 in 57e6965

	var segments = ['IAB2', 'IAB17', 'IAB14', 'IAB21', 'IAB20']
	var segment = segments[Math.floor(Math.random() * 4)]

That is:

var segments = ['IAB2', 'IAB17', 'IAB14', 'IAB21', 'IAB20']
var segment = segments[Math.floor(Math.random() * 4)]

The last value 'IAB20' is excluded from the range of random() and will never be chosen.

Here's another bug:

browser-laptop/tools/lib/transactionHelpers.js

Line 48 in 57e6965

const count = Math.round(Math.random() * 100)

 const count = Math.round(Math.random() * 100)

In this case, both 0 and 100 are part of the results, but only occur half as frequently as the other numbers. To see why this happens consider:

 const zeroOneTwo = Math.round(Math.random() * 2)

all numbers from 0 to 0.49999 will return 0
all numbers from 0.5 to 1.4999 will return 1
all numbers from 1.5 to 1.9999 will return 2

So 1 occurs with probbility 1/2 and 0 and 2 are returned with probability 1/4 each.
This is very different from the expected uniform distribution (1/3,1/3,1/3).

The problem here is the flooring or rounding of floating point random numbers to obtain integers.
I think the "proper" way to obtain random integers in a given range is to use randomInt from random-lib

There are many more instances of this in the code. Just do a search for random() to find them.

[bsclifton]

We do use random-lib in our ledger (payments) code; it wouldn't be hard to rework other instances to call that instead

Docs on Math.random() explaining the exclusivity issue shown in the first example (4 never being possible because 1 is excluded from Math.random results)

Good find, thanks @dimitri-xyz!

[cndouglas]

Which instances are worth fixing? https://github.com/brave/browser-laptop/search?l=JavaScript&q=random&type=Code&utf8=%E2%9C%93
Here is an example for the new tab page backgrounds: (js/about/newtab.js)

@@ -19,7 +19,7 @@ const urlutils = require('../lib/urlutil')
 const siteTags = require('../constants/siteTags')
 const config = require('../constants/config')
 const backgrounds = require('../data/backgrounds')
-const {random} = require('../../app/common/lib/randomUtil')
+const random = require('random-lib')
 
 const ipc = window.chrome.ipcRenderer
 
@@ -65,7 +65,7 @@ class NewTabPage extends React.Component {
     return this.state.showImages && !!this.state.backgroundImage
   }
   get randomBackgroundImage () {
-    const image = Object.assign({}, backgrounds[Math.floor(random() * backgrounds.length)])
+    const image = Object.assign({}, backgrounds[random.randomInt({ min: 0, max: backgrounds.length })])
     image.style = {backgroundImage: 'url(' + image.source + ')'}
     return image
   }

[dimitri-xyz]

@liunkae ,

Fixing this turns out to be more complicated than I thought. There are 2 separate issues here:

1. Inadvertently excluding boundary values when generating random numbers
2. Generating a non-uniform (i.e. biased) probability distribution

I think we should fix (1) now, but leave (2) for later.

To fix the first issue, fix all instances where a floating-point random value obtained through random() is later turned into an Integer. The conversion can be made by truncation, rounding, flooring, etc. The key is to think floating-point random number later converted into an integer. We just have to be careful to know whether the "large" boundary value should be included. Your example looks good, but I don't know the code and, thus I don't know if we should include only length-1 or should also include length. You'd have to investigate each case. Maybe @bsclifton or someone else should pitch in here on how to do that.

The second problem (non-uniform distribution) turns out to be worse than I thought. The Mozilla Docs are suggesting an incorrect way to do it (getRandomInt and getRandomIntInclusive are biased) and random-lib's randomInt() is also incorrectly generating its integers and causing a small bias. The bias is really small in most cases, so for most applications it will be fine. I will work with them to fix those issues.

The correct way to generate random integers is Rejection Sampling.

[fardog]

I'm the author of random-lib.

@liunkae for the options passed to randomInt, min is inclusive and max is exclusive, so that would be the correct fix. (see docs)

As to fixing the bias issue, @dimitri-xyz has written up a very thorough blog post detailing the issue with the algorithm mozilla details and i'll be attempting to fix this issue over the next week or so (if anyone has the time to get to this faster, pull requests are very welcome!). I'll update here once a version is available that removes the bias.

Edit: and after reading their blog post thoroughly, it looks like this bias is really really small; so while I'll definitely want to get it fixed, as @dimitri-xyz highlights it's probably not a huge concern in the interim.

[333aleix333]

Hi! I think I have corrected all the flooring and all the rounding, but I'm new and I don't know what should I do now.
Thanks!

[fardog]

@liunkae wanted to let you know this hasn't been forgotten; i've written up a separate module—rejection-sampled-int—which implements the rejection sampling algorithm and should make for unbiased integers from nodejs/browser crypto. However, I haven't had this audited yet, so I haven't integrated it into random-lib yet. It is also significantly slower, as you might imagine, so for areas where the bias is not as much of a concern, you may find it faster to use a biased method such as the ones already in random-lib, if using crypto.randomBytes is desired for entropy.

Anyhow, if anyone has a chance to audit that module, it'd be hugely appreciated. Then, brave can just use that module as necessary; it doesn't seem to use any functions of random-lib aside from random integers, so there's no need for the whole library.

(n.b. there is actually a PR up for random-lib which uses rejection-sampled-int for integers; but i'm not merging it until an audit has been done: fardog/node-random-lib#14)

[diracdeltas]

@dimitri-xyz thanks for pointing out this issue and the detailed explanations. Although we are not currently using Math.random and random-lib for purposes that require cryptographic randomness (such as generating crypto keys), I labeled this issue under security to make sure that these libraries are not misused in the future.

@333aleix333 thanks. please fork our repository, push your changes to the fork, then open a pull request against our repository. see here for some instructions: https://gist.github.com/Chaser324/ce0505fbed06b947d962

[fardog]

random-lib has been updated to version 3.0, which should solve this issue; see here for the changes. It's now backed by rejection-sampled-int for integers, which I also wrote. I would definitely appreciate additional sets of eyes on it, as it's not gone through any formal audit, yet I have tested the features in both libraries heavily.

The API also changed in this version as the old one had behaviors that were very awkward, however conversion to the new API is super-straightforward since there wasn't much surface there to begin with.

Let me know if you have any questions!

[arsalankhalid]

If that's the case, you guys should close this issue! @bsclifton

[bsclifton]

@arsalankhalid looks like we're still using version 2.1.0. Did you want to submit a PR to update the version? 😄 Should be as easy as:
npm -i random-lib@latest --save

[fardog]

There were API changes between v2 and v3. It should not be very involved, but it will require a few more changes. See https://github.com/fardog/node-random-lib/blob/master/CHANGELOG.md#300

I had intended to submit a pr, but wasn't able to get the brave browser tests working on my local machine in the short time I was able to allocate. If someone has the chance though, it should not be a significant change set.

[lunaticmonk]

@bsclifton Do we need an update for the random-lib? If yes, can I submit a PR?

[fardog]

I just put up a PR for it. tests aren't running right on my local machine, but looks like they're passing in CI; should be good?

Note that this still needs to be updated in other brave projects (bat-publisher, ledger-publisher, etc); i'll open tickets there, but unsure when/if i'll get to it, so someone definitely should if they have the time!

[fardog]

submitted prs to bat-publisher and bat-client, since the others are deprecated ^