7 ms·

There's Math.random(), and then there's Math.random() (2015)

35 points by corentin88 3y ago

byronvickers 3y ago
Weird to see this show up on HN - I was just looking at this page a couple of days ago. I have a little puzzle I've been trying to solve in my spare time; maybe someone here can point me in the right direction. The puzzle is: given a float from Math.random(), suppose you know only whether it is greater than it is then 0.5 (i.e you only see the result of a coin flip which depends on Math.random()). What is a practical method to reverse out the state of the xorshift+ generator, given multiple such successive observations of the output? Any input appreciated!
- Retr0id 3y ago
  I've been studying this myself just a few days ago! tl;dr For a "Math.random() > 0.5" function, you need ~128 successive outputs, each of which leaks exactly 1 bit of the state at that particular iteration, and then you "just" solve a system of linear equations over gf(2) to recover the full state for any given iteration. You can use z3 to solve it automagically, or you can write your own gaussian elimination solver (which works out much faster than z3 in practice). Math isn't exactly my strong suit, so it took me quite a bit of bashing my head against the wall to make sense of things and turn it into code, so I've been planning on writing a blog post that explains this all in-depth (or at least, as much depth as I understand it). For Chrome, there's an added catch in that it generates random numbers in batches, and returns those batches in reverse-order, so you'd need to do a small brute-force to identify where the batch boundaries are in your output sequence. For Firefox and Safari, there's an added catch in that they add together the two halves of the state before returning it. This can also be worked around with a small brute force.
  - twotwotwo 3y ago
    It's fun it's exactly 1:1 and you don't need any more output than the state! It's sort of sad it isn't all AES-CTR or ChaCha12. Fast enough not to be the bottleneck in your webpage, and if you find any hint of a pattern in the output, good news, you get to publish a paper on it!
    - azeemba 3y ago
      The intention is that web.crypto is used when reversing should be difficult. The goal for Math.random is to have much lower memory and speed impact. You can certainly disagree with their priorities but given those priorities, it makes sense to go with a much simpler algorithm that can be reversed easily.
      - twotwotwo 3y ago
        Sorry, I know you should be using a CSPRNG API for cryptography, and probably my glib phrasing there obscured that. I'm saying the cost of running actual cryptographic primitives has dropped a ton over time: on computers from decades ago a cheaper flavor of pseudorandomness was clearly necessary, now hardware AES is very cheap. And webpages aren't typically massive doing HPC simulations or other things that will be bound by the PRNG taking a few cycles per byte. So the memory/CPU benefit of keeping the bad PRNG around is not obviously still worth it to me. In your words, I think I disagree with their priorities, particularly because the cost savings are not what they used to be.
    - kevincox 3y ago
      If you need secure random values you should be using https://developer.mozilla.org/en-US/docs/Web/API/Crypto/getRandomValues https://developer.mozilla.org/en-US/docs/Web/API/Crypto/getR.... Absolutely do not use `Math.random` for anything requiring security.
      - twotwotwo 3y ago
        Sorry, to clarify, I know CSPRNG APIs are exposed and what you use for safe randomness. What I'm saying is that outside rare, extreme situations--maybe some HPC Monte Carlo simulation where you need gobs of randomness--you might as well use strong primitives for all your randomness, because they work well and are now plenty cheap for the use case with hardware support, etc. The games to find a fast non-cryptographic function that passes enough statistical tests, etc., don't make as much sense to me when cryptographic randomness costs a few cycles a byte. There is not much upside to every standard library exposing a bad random generator that we have to warn people not to use. The handful of people that really need xorshift128+ can figure something out. Maybe still a position you disagree with, but at least clearer without the sarcastic gloss.
- maple3142 3y ago
  In V8 engine, Math.random is implemented using xorshift128, which is a completely linear PRNG with 128 bits of state. Since you can recover 1 bit from each output, 128 outputs should be enoguh for you to setup a GF(2) linear system and solve for the state. Once you have the state, all you need is to simulate how V8 output future random values from state. There are a series of challenges called "fastrology" from PlaidCTF 2023, which is about predicting Math.random() given some partial output (e.g. Math.floor(Math.random() * k)) with several variants. You can try to find writeups for that challenges, those solvers should be easy to adapt to predicting Math.random()>0.5 .
deleted 3y ago
[deleted]
virexene 3y ago
“the 2⁵² numbers between 0 and 1 that double precision floating point can represent” it's a bit of a nitpick, but i believe there are 1023×2⁵² such numbers, which is quite a bit more. there are 2⁵² double precision floats in just [0.5;1)!
- mbauman 3y ago
  That's not a nitpick at all — it has huge ramifications for how `Math.random()` needs to be interpreted. Many folks want it (and transformations of it!) to behave as though it were a true random variable sampled from a theoretically ideal [0, 1) uniform distribution. But it's not, and will never be. It can only ever return values that have been rounded down to some floating point number. Even if you realize this, you still might expect it to be able to return _any_ floating point number x∈[0, 1) with `eps(x)` probability. But that's not typically the case, either. Typical implementations round down to the previous multiple of `eps(1.0)` or `eps(0.5)`.
  - fanf2 3y ago
    For more on this topic see https://news.ycombinator.com/item?id=37926005 https://news.ycombinator.com/item?id=37926005
    - mbauman 3y ago
      That article makes the same unstated assumption, attempting to treat `random()`'s output (and transformations thereof) as true random variables. But it just changes the rounding mode and bin size in a manner that _happens_ to work better for some transforms like log. It changes the fundamental property of the distribution — the cdf — without stating it. With floating point realizations of [0, 1) intervals: cdf(p) = P(random() < p) := p With (0, 1] intervals: cdf(p) = P(random() <= p) := p
      - corsix 3y ago
        Using your cdf framing, while there is a point about [0, 1) versus (0, 1] intervals, the bigger point of the article is about whether said cdf holds for any IEEE-754 double-precision p, or whether it only holds for p of the form i*2^-53 (for integer i).
paulpauper 3y ago
Make no mistake however: even though xorshift128+ is a huge improvement over MWC1616, it still is not cryptographically secure. For use cases such as hashing, signature generation, and encryption/decryption, ordinary PRNGs are unsuitable. The Web Cryptography API introduces window.crypto.getRandomValues, a method that returns cryptographically secure random values, at a performance cost. If the 256 bit private key of the encryption is derived from a large character set ( A-Z, 1-9, etc.), it does not matter if the RNG is not perfect. I am assuming it's not an online channel. This is explained in more detail here https://www.reddit.com/r/cryptography/comments/fw2cdu/can_you_retrieve_aes_key_that_was_generated_using/ https://www.reddit.com/r/cryptography/comments/fw2cdu/can_yo...
paulddraper 3y ago
I don't understand why you'd want a floating point random. It just seems like a terrible idea (as opposed to int)
- fanf2 3y ago
  Many of the algorithms for generating random numbers from different distributions want to start with uniform floats in [0,1) or (0,1]
- adrian_b 3y ago
  The random floating-point numbers are not general-purpose, they are needed in applications whose input parameters are floating-point numbers. For instance they are needed for testing the implementation of various functions of FP numbers, or for the so-called Monte-Carlo methods used for numerical integration, especially in multiple dimensions or for the solution of certain systems of equations with partial derivatives, or for the simulation of how some industrial product, e.g. an electronic integrated circuit, behaves when its components have random values of their characteristic parameters, within their accepted tolerances, as it always happens in any industrial production process, or the random numbers may be used in an optimization problem, to search through the possible solution space. For random floating-point numbers it is frequent to need various other probability density distributions than uniform. In most cases the best way to generate pseudo-random FP numbers is to derive them from uniform pseudo-random integers, using an appropriate method that will ensure the desired probability density distribution.
- spacechild1 3y ago
  In my field (music, video, games) random floating point numbers are ubiquitous.
- xigoi 3y ago
  The uniform distribution of real numbers is easy to convert to other distributions, so if you want a language to have only one randomness function, it's a reasonable choice.
- extraduder_ire 3y ago
  This is in javascript. All of the numbers are in floating point. (or were, initially)
SeanLuke 3y ago
In Java there's just Math.random(), and it's been broken, with WONTFIX, since 1998. Java's random number generator returns exceptionally non-random values, but Sun, er, Oracle, won't fix it because of the most insane of reasons: unlike in any reasonable language, Java's PRNG essentially has a contract to be deterministic. There's seemingly a worry that someone, somewhere, is actually relying on java.util.Random to always produce the same random number sequence for a given seed from Java version to version.
- alex_duf 3y ago
  Why is it unreasonable that given the same seed the same sequence will be generated? It's useful for generative art and video games at least. Sure it shouldn't be used for security...
  - SeanLuke 3y ago
    Because it permanently prevents all bugfixes for a major library class. And java.util.Random has some whopping bugs. If you need determinism, then the proper thing to do is use your own RNG. There's been a good Mersenne Twister implementation on Java since 1999. But a system-wide generator should never be beholden to determinism.
    - jibe 3y ago
      If you need determinism, and the standard library is deterministic, it seems reasonable to use the standard library.
      - SeanLuke 3y ago
        Even if its high bits go 1 0 1 0 1 0 1 0 ... ?
        _a_a_a_ 3y ago
        I would say that's a bug in the RNG, nothing to do with any determinism issue

35 points by corentin88 3y ago

Weird to see this show up on HN - I was just looking at this page a couple of days ago. I have a little puzzle I've been trying to solve in my spare time; maybe someone here can point me in the right direction. The puzzle is: given a float from Math.random(), suppose you know only whether it is greater than it is then 0.5 (i.e you only see the result of a coin flip which depends on Math.random()). What is a practical method to reverse out the state of the xorshift+ generator, given multiple such successive observations of the output? Any input appreciated!

Retr0id 3y ago
I've been studying this myself just a few days ago! tl;dr For a "Math.random() > 0.5" function, you need ~128 successive outputs, each of which leaks exactly 1 bit of the state at that particular iteration, and then you "just" solve a system of linear equations over gf(2) to recover the full state for any given iteration. You can use z3 to solve it automagically, or you can write your own gaussian elimination solver (which works out much faster than z3 in practice). Math isn't exactly my strong suit, so it took me quite a bit of bashing my head against the wall to make sense of things and turn it into code, so I've been planning on writing a blog post that explains this all in-depth (or at least, as much depth as I understand it). For Chrome, there's an added catch in that it generates random numbers in batches, and returns those batches in reverse-order, so you'd need to do a small brute-force to identify where the batch boundaries are in your output sequence. For Firefox and Safari, there's an added catch in that they add together the two halves of the state before returning it. This can also be worked around with a small brute force.
- twotwotwo 3y ago
  It's fun it's exactly 1:1 and you don't need any more output than the state! It's sort of sad it isn't all AES-CTR or ChaCha12. Fast enough not to be the bottleneck in your webpage, and if you find any hint of a pattern in the output, good news, you get to publish a paper on it!
  - azeemba 3y ago
    The intention is that web.crypto is used when reversing should be difficult. The goal for Math.random is to have much lower memory and speed impact. You can certainly disagree with their priorities but given those priorities, it makes sense to go with a much simpler algorithm that can be reversed easily.
    - twotwotwo 3y ago
      Sorry, I know you should be using a CSPRNG API for cryptography, and probably my glib phrasing there obscured that. I'm saying the cost of running actual cryptographic primitives has dropped a ton over time: on computers from decades ago a cheaper flavor of pseudorandomness was clearly necessary, now hardware AES is very cheap. And webpages aren't typically massive doing HPC simulations or other things that will be bound by the PRNG taking a few cycles per byte. So the memory/CPU benefit of keeping the bad PRNG around is not obviously still worth it to me. In your words, I think I disagree with their priorities, particularly because the cost savings are not what they used to be.
  - kevincox 3y ago
    If you need secure random values you should be using https://developer.mozilla.org/en-US/docs/Web/API/Crypto/getRandomValues https://developer.mozilla.org/en-US/docs/Web/API/Crypto/getR.... Absolutely do not use `Math.random` for anything requiring security.
    - twotwotwo 3y ago
      Sorry, to clarify, I know CSPRNG APIs are exposed and what you use for safe randomness. What I'm saying is that outside rare, extreme situations--maybe some HPC Monte Carlo simulation where you need gobs of randomness--you might as well use strong primitives for all your randomness, because they work well and are now plenty cheap for the use case with hardware support, etc. The games to find a fast non-cryptographic function that passes enough statistical tests, etc., don't make as much sense to me when cryptographic randomness costs a few cycles a byte. There is not much upside to every standard library exposing a bad random generator that we have to warn people not to use. The handful of people that really need xorshift128+ can figure something out. Maybe still a position you disagree with, but at least clearer without the sarcastic gloss.
maple3142 3y ago
In V8 engine, Math.random is implemented using xorshift128, which is a completely linear PRNG with 128 bits of state. Since you can recover 1 bit from each output, 128 outputs should be enoguh for you to setup a GF(2) linear system and solve for the state. Once you have the state, all you need is to simulate how V8 output future random values from state. There are a series of challenges called "fastrology" from PlaidCTF 2023, which is about predicting Math.random() given some partial output (e.g. Math.floor(Math.random() * k)) with several variants. You can try to find writeups for that challenges, those solvers should be easy to adapt to predicting Math.random()>0.5 .

deleted 3y ago

[deleted]

virexene 3y ago

“the 2⁵² numbers between 0 and 1 that double precision floating point can represent” it's a bit of a nitpick, but i believe there are 1023×2⁵² such numbers, which is quite a bit more. there are 2⁵² double precision floats in just [0.5;1)!

mbauman 3y ago
That's not a nitpick at all — it has huge ramifications for how `Math.random()` needs to be interpreted. Many folks want it (and transformations of it!) to behave as though it were a true random variable sampled from a theoretically ideal [0, 1) uniform distribution. But it's not, and will never be. It can only ever return values that have been rounded down to some floating point number. Even if you realize this, you still might expect it to be able to return _any_ floating point number x∈[0, 1) with `eps(x)` probability. But that's not typically the case, either. Typical implementations round down to the previous multiple of `eps(1.0)` or `eps(0.5)`.
- fanf2 3y ago
  For more on this topic see https://news.ycombinator.com/item?id=37926005 https://news.ycombinator.com/item?id=37926005
  - mbauman 3y ago
    That article makes the same unstated assumption, attempting to treat `random()`'s output (and transformations thereof) as true random variables. But it just changes the rounding mode and bin size in a manner that _happens_ to work better for some transforms like log. It changes the fundamental property of the distribution — the cdf — without stating it. With floating point realizations of [0, 1) intervals: cdf(p) = P(random() < p) := p With (0, 1] intervals: cdf(p) = P(random() <= p) := p
    - corsix 3y ago
      Using your cdf framing, while there is a point about [0, 1) versus (0, 1] intervals, the bigger point of the article is about whether said cdf holds for any IEEE-754 double-precision p, or whether it only holds for p of the form i*2^-53 (for integer i).

paulpauper 3y ago

Make no mistake however: even though xorshift128+ is a huge improvement over MWC1616, it still is not cryptographically secure. For use cases such as hashing, signature generation, and encryption/decryption, ordinary PRNGs are unsuitable. The Web Cryptography API introduces window.crypto.getRandomValues, a method that returns cryptographically secure random values, at a performance cost. If the 256 bit private key of the encryption is derived from a large character set ( A-Z, 1-9, etc.), it does not matter if the RNG is not perfect. I am assuming it's not an online channel. This is explained in more detail here https://www.reddit.com/r/cryptography/comments/fw2cdu/can_you_retrieve_aes_key_that_was_generated_using/ https://www.reddit.com/r/cryptography/comments/fw2cdu/can_yo...

paulddraper 3y ago

I don't understand why you'd want a floating point random. It just seems like a terrible idea (as opposed to int)

fanf2 3y ago
Many of the algorithms for generating random numbers from different distributions want to start with uniform floats in [0,1) or (0,1]
adrian_b 3y ago
The random floating-point numbers are not general-purpose, they are needed in applications whose input parameters are floating-point numbers. For instance they are needed for testing the implementation of various functions of FP numbers, or for the so-called Monte-Carlo methods used for numerical integration, especially in multiple dimensions or for the solution of certain systems of equations with partial derivatives, or for the simulation of how some industrial product, e.g. an electronic integrated circuit, behaves when its components have random values of their characteristic parameters, within their accepted tolerances, as it always happens in any industrial production process, or the random numbers may be used in an optimization problem, to search through the possible solution space. For random floating-point numbers it is frequent to need various other probability density distributions than uniform. In most cases the best way to generate pseudo-random FP numbers is to derive them from uniform pseudo-random integers, using an appropriate method that will ensure the desired probability density distribution.
spacechild1 3y ago
In my field (music, video, games) random floating point numbers are ubiquitous.
xigoi 3y ago
The uniform distribution of real numbers is easy to convert to other distributions, so if you want a language to have only one randomness function, it's a reasonable choice.
extraduder_ire 3y ago
This is in javascript. All of the numbers are in floating point. (or were, initially)

SeanLuke 3y ago

In Java there's just Math.random(), and it's been broken, with WONTFIX, since 1998. Java's random number generator returns exceptionally non-random values, but Sun, er, Oracle, won't fix it because of the most insane of reasons: unlike in any reasonable language, Java's PRNG essentially has a contract to be deterministic. There's seemingly a worry that someone, somewhere, is actually relying on java.util.Random to always produce the same random number sequence for a given seed from Java version to version.

alex_duf 3y ago
Why is it unreasonable that given the same seed the same sequence will be generated? It's useful for generative art and video games at least. Sure it shouldn't be used for security...
- SeanLuke 3y ago
  Because it permanently prevents all bugfixes for a major library class. And java.util.Random has some whopping bugs. If you need determinism, then the proper thing to do is use your own RNG. There's been a good Mersenne Twister implementation on Java since 1999. But a system-wide generator should never be beholden to determinism.
  - jibe 3y ago
    If you need determinism, and the standard library is deterministic, it seems reasonable to use the standard library.
    - SeanLuke 3y ago
      Even if its high bits go 1 0 1 0 1 0 1 0 ... ?
      - _a_a_a_ 3y ago
        I would say that's a bug in the RNG, nothing to do with any determinism issue