Is it possible for this to work with Chrome's Math.random?

[innsternet]

I saw you said about it only working on java.util.Random and Firefox which uses that or a pretty close replica. Would it be possible to predict the next random generated numbers in Chrome also?

Thanks.

[fta2012]

The source code for Chrome's Math.random seems to be here:
https://github.com/v8/v8/blob/4.6.85/src/math.js#L131

Chrome doesn't use the same PRNG algorithm as the one in this repo (which is a linear congruential generator) but you can reverse it to recover the seed in a similar way.

I thought it was a fun problem so I took a shot at it here: https://gist.github.com/fta2012/57f2c48702ac1e6fe99b. Let me know if that works for you.

Just curious though, what's the application for this?

[innsternet]

Ah that's awesome and definitely works using Chrome but unfortunately not for what I needed it for but I really appreciate it anyway and it will be useful. Basically the application is that I am trying to prove from a security standpoint that the way a certain site is generating it's random numbers is broken and predictable. I know they use Node.js on the backend which would generate the random numbers using Math.random() and shoot them forward to the frontend and I was under the impression that if you could get it predicting the upcoming values on Chrome then it would work (at least I thought anyway because Chrome uses the V8 Javascript engine and so does node.js so I still really puzzled as to why it doesn't work).

For example if I did:

for (var i = 0; i < 10; i++) {
 console.log(Math.random());
}

in the chrome console and then use what you produced it can predict the upcoming numbers perfectly but that same exact code in a node.js script and then being ran and using the output in your code and it can't predict the upcoming values.
(node.js script output: http://pastebin.com/WJMzJQhv and I was just testing here https://jsfiddle.net/wLvmh7gj/1/ using first two values like with Chrome)

Edit:
Just worked out that their implementations are slightly different.
https://github.com/joyent/node/blob/d13d7f74d794340ac5e126cfb4ce507fe0f803d5/deps/v8/src/math.js

https://code.google.com/p/chromium/codesearch#chromium/src/v8/src/math.js&q=MathRandom&sq=package:chromium&type=cs&l=130

Damn, I adjusted the 18030 to 18273 which was the only difference I could see and it still doesn't work. Any ideas?

[fta2012]

Check your node version? I just tried it and it seems to work after replacing 18030 with 18273.

[innsternet]

Yep my version was a little bit behind and now I have updated and it predicts nodejs math.random() perfectly 👍 Thanks. Still unfortunately doesn't match up with the site so I guess they must be using a cryptographically secure RNG.

Thanks again!

[fta2012]

No problem!

[innsternet]

Sorry to open this back up lol. Would it be possible to edit this to in a way brute force the middle values so I can then get the proper state after that; for example:

At the moment you need 2 sequential numbers like:

• Generated a random number (I know the value)
• Generated a random number (I know the value)
• outcome: because they are sequential and I know the values I can just plug them in and get the upcoming values.

But imagine this scenario:

• Generated random number (I know the value)
• Generated x amount of random numbers (Which I don't know the values, lets imagine x is between 1-10 for now)
• Generated random number (I know the value)

Would it be possible to create the states from that scenario using maybe brute force or something?

Thanks, I appreciate your help by the way : >

[fta2012]

It will be harder to just unroll the expression and work backwards if there's more than one iteration since there are more dependent variables. It was easy for consecutive iterations since you could basically express the unknowns using algebra/modular arithmetic rather than with bit ops. So you probably need to take a different approach (I'm not sure how off the top of my head).

But if you want to naively brute force 32 bits then you won't have to think about this as hard. =P You can just try all 2^32 rngstate (the state is 64bits but 32bits is known from your first observations) for a few iterations each and see if any of them produce your second observation. Probably feasible on GPU?

[fta2012]

Actually that comment about brute forcing is wrong. The rngstate is separate into two parts that could be bruteforced independently so you only have to do 2^16 twice, which is very easy.

[innsternet]

Awesome, I'll give that a go then and yeah it will definitely be a lot faster on the GPU but I have never used the CUDA GPU toolkit packages before and I'm guessing they aren't simple (maybe I'll learn it this weekend 🎱 ) but for now I guess I'll just stick with the CPU calculations for now even though it will be a bit longer. Just to confirm could you double check this (https://jsfiddle.net/24yenjn5/) and just tell me I am getting the first 16 known bits of each state correctly right?

[fta2012]

Don't know if you saw my second comment but 2^16 is really small and will definitely run fast enough on CPU in less than a second. Your fiddle looks correct to me although you should probably write it like:

  var x_upper = x >>> 16;
  var x_lower = x & 0xFFFF;
  return [x_upper, x_lower];

[innsternet]

Yep thanks, just finished a quick mock up now and sent it on it's first run I'll let you know the outcome :)

[fta2012]

I also just updated the gist to handle gaps (but needs to know the exact number skipped). Let me know if that works for you.

[innsternet]

Thanks you didn't need to though! I had just finished my implementation in C++ and it worked and cracked the state correctly and could predict the next numbers perfectly and also matches the web application I was testing it on originally! 👍 Also just so you know I ended up using 3 outputs and then brute forcing the last 32 bits and then matching it across the 3 outputs. Now I can finally sleep at night and not be haunted by my crypto nightmares lol. Appreciate all your help, you're a saint.

[fta2012]

Yup no problem. Please let me know if you end up doing anything cool with it!

[skepticfx]

Recently at BlackHat, these people demonstrated a practical attack on breaking Node.js's Math.random()
https://youtu.be/-HzCUZDLXTc?t=9m35s

[fta2012]

That's really awesome, thanks for sharing!

In our convo above, @innsR and I actually worked how to do this given just two nonconsecutive observations of Math.random() on both node and chrome! So we have a slightly stronger result than requiring three consecutive observations like in that talk. My implementation was to linked to here: https://gist.github.com/fta2012/57f2c48702ac1e6fe99b. You just need to change a constant to make it work on node.

@innsR, did you ever publish your c++ implementation?