rand() implementation not really random

[peppsac]

rand() implementation from library.js exhibits an odd behaviour.

#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <string.h>

int main() {
    #define N 8
    int counter[N], i;
    memset(counter, 0, sizeof(counter));
    srand(time(NULL));

    for (i=0; i<1000; i++) {
        counter[rand() % N]++;
    }

    for (i=0; i<N; i++) {
        printf("%d  ", counter[i]);
    }
    printf("\n");
    return 0;
}

Compiling with emcc and executing with "node a.out.js" outputs:
$ node a.out.js
999 1 0 0 0 0 0 0
$ node a.out.js
996 4 0 0 0 0 0 0
$ node a.out.js
999 1 0 0 0 0 0 0

Replacing rand() implementation by

return Math.random() * 0x7FFFFFFF;

produces the correct result.

[kripken]

Yup, turns out it's hard to do random number generation properly... we were doing it wrong.

There are some decent ways to do it in 32 bits, but they all run into JS numeric limits since they end up doing 64-bit math.

So I switched it to Math.random like you suggest. (Note though that it needs to be 0x80000000 and not 0x7fffffff, and needs a Math.floor). Fixed in incoming branch.

Downside of this is we ignore the seed now, so results are not reproducible. But I think it's the right tradeoff.

Thanks for filing!

[paulshapiro]

Hi @kripken,

I hear Math.random is not suitable for usage in applications which require 'randomness' with a higher number of bits of entropy. window.crypto is recommended instead (for which I have some slightly disorganized code). Does it make sense to switch away from Math.random?

Thanks

[paulshapiro]

Actually, I made a mistake. Didn't realize that crypto would of course be equivalent to window.crypto. However, how about just removing the Math.random call and throwing to warn? For my case I mustn't take the risk of keeping it in.

Thanks!

Reference:

var random_device;
if (typeof crypto !== "undefined") { // typical modern browser
    var randomBuffer = new Uint8Array(1);
    random_device = (function() {
        crypto.getRandomValues(randomBuffer);
        return randomBuffer[0]
    })
} else if (ENVIRONMENT_IS_NODE) {
    random_device = (function() {
        return require("crypto")["randomBytes"](1)[0]
    })
} else { // danger zone
    random_device = (function() {
        return Math.random() * 256 | 0
    })
}
FS.createDevice("/dev", "random", random_device);
FS.createDevice("/dev", "urandom", random_device);

[paulshapiro]

Sorry to spam but I think an initialization parameter to toggle present behavior to a throw could work.. or even a fallback (callback) function (for the purpose of displaying alerts etc) which can preferentially return undef/null/zero random value, which would result in a throw

[kripken]

I see what you mean here. However, I think in JS you just need to add 1 line, like

Math.random = function() { throw 'unsafe' };

Which is easy to add for those that need it, so I think adding an emscripten option is overkill.

[paulshapiro]

That's an interesting point. Nice solution. Thanks!

[paulshapiro]

@kripken now that I've finally gotten around to actually implementing this, I realize I have a small handful of trivial usages of Math.random that it would be fairly awkward to work around. I have settled on making a 'random' interface fn and having all of them implement it. Not quite optimal.

[paulshapiro]

@kripken Turns out our other users are blocked by this too, and the solution of throwing does not work for them. I would like to request that we move the throw to emscripten's fallback random case as well. I do not think it's reasonable to fall back to a bad RNG when the device of /dev/random is so generalized and is generally thought to be a good source of entropy.

mymonero/mymonero-core-js#54 (comment)

[kripken]

Where in emscripten do you need to call your custom random function?

If it's in a function in the JS library, then you can just override it with another JS library, for example.

[paulshapiro]

@kripken No, it's not that… there's a Math.random call as a fallback in the emscripten implementation of the random_device - I think that's unsafe and in any case it must be removed for my cryptographic application, but afaict it would require modifying emscripten's sourcecode or textual replacement in what gets emitted.

[kripken]

I see. Yeah, I guess it makes sense to throw there - a PR with that sounds good.

[msorvig]

This now throws on modern browsers for me.

Is the crypto feature detection In library_fs.js correct? It looks for crypto, but I think it should look for window.crypto.

[kripken]

This regressed, but was fixed in fb03abc (in 1.38.27).