I looked at the V8 Math.Random() internal implementation today from a cryptographer perspective. It's based on two Marsaglia MWC generators running in parallel. The low 16-bit outputs of each are concatenated into a 32-bit output. It's seeded with /dev/urandom, which is good.

The problem is that each output gives away half the internal state of the generator, so you can recover the full state given a few outputs with just 2^^17 runs of the Math.Random() generator, offline. Interestingly, back when I was working on a good fast simple PRNG I came up with the exact same construction. I found that dual-MWC is the fastest option available after exhaustively trying them all.

I ended up using different constants: https://github.com/catid/libcat/blob/master/AbyssinianPRNG.hpp

The difference is that I combine the outputs with ROL(r0, K) + r1 instead of just r0 || r1. So to recover the internal state is a lot harder. The extra mixing step is very cheap and helps randomness. Brute force would take 2^^64 attempts without some more advanced trickery.

The problem is that each output gives away half the internal state of the generator, so you can recover the full state given a few outputs with just 2^^17 runs of the Math.Random() generator, offline. Interestingly, back when I was working on a good fast simple PRNG I came up with the exact same construction. I found that dual-MWC is the fastest option available after exhaustively trying them all.

I ended up using different constants: https://github.com/catid/libcat/blob/master/AbyssinianPRNG.hpp

The difference is that I combine the outputs with ROL(r0, K) + r1 instead of just r0 || r1. So to recover the internal state is a lot harder. The extra mixing step is very cheap and helps randomness. Brute force would take 2^^64 attempts without some more advanced trickery.

last edit by catid
edited (>30 days ago) 9:36pm Tue. Jan 21st 2014 PST