7 ms·

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

124 points by beepill 2y ago

gnabgib 2y ago
(2015) Discussion at the time (229 points, 106 comments) https://news.ycombinator.com/item?id=10751396 https://news.ycombinator.com/item?id=10751396
- dang 2y ago
  Thanks! Macroexpanded: There's Math.random(), and then there's Math.random() (2015) - https://news.ycombinator.com/item?id=38188421 https://news.ycombinator.com/item?id=38188421 - Nov 2023 (49 comments) There's Math.random(), and then there's Math.random() - https://news.ycombinator.com/item?id=10751396 https://news.ycombinator.com/item?id=10751396 - Dec 2015 (106 comments)
maxloh 2y ago
I learned in college that most random number generators use the current timestamp to generate a pseudo-random number. How does this differ cryptographically from algorithms like MWC1616 and xorshift128+ in backend applications? How can a random number generator be vulnerable to attacks in real life? Does it really matter which random number generator you use on a webpage? It's already considered an insecure environment anyway (that's why we have server-side validation).
- tomsmeding 2y ago
  In a class we had to reverse-engineer an application that had encrypted some text file — we had to decrypt it without the key. Turned out the application just used the current unix timestamp as the key. A brute-force search of the past few months didn't take very long. If you include nanoseconds in your key then you have more entropy, of course, but timestamps are guessable, so it's risky.
  - sverhagen 2y ago
    Those nanoseconds aren't really entropy then, are they?
    - lmm 2y ago
      They're entropy for most practical purposes. But there's only 1000 possibilities, so that's less than 10 bits' worth.
      - boothby 2y ago
        Especially if you're writing a file, the creation time is a big hint! Even nanoseconds won't help if you're leaking that many bits from your seed.
      - tomsmeding 2y ago
        That's milliseconds; nanoseconds are 1e-9 seconds. Still, the file creation time remark of sibling is pertinent.
        lmm 2y ago
        I was thinking of the step from milli to nano, so yeah 1e6 not 1e3, 20 bits not 10. But the point stands.
- hapidjus 2y ago
  One attack might be exploiting One Time Passwords. Lets say you send yourself enough tokens to calculate the state, you will then be able to calculate the next token and login as another user. However that should be easily fixed by adding some salt relating to the user, meaning you would only be able to figure out _your_ next token.
- atoav 2y ago
  You can go back into a time before computers and use the most famous examples of how bad RNGs endanger crypto: One Time Pads (OTP). This is basically just a XOR of your message with your random numbers. If your random numbers are bad they leave patterns in the XOR-ed message that can be statistically analyzed and potentially decrypted. Bad PRNGs repeat early and have predictable patterns, as such they form a special attack vector. Whether that is really an issue for any given application, depends on the application (e.g. how shortlived the crypto is and how bad decryption acter the fact is). But if you are asking that question it likely means you don't know enough knowledge to roll your own crypto unless you wanna be in a world of pain. Just because PRNGs appear unpredictable to you does not mean they aren't. If you really wanna go the route, at least add a salt, so something like Hash(application_secret_long_and_random + timestamp_nanosecond_precision)
- masklinn 2y ago
  > I learned in college that most random number generators use the current timestamp to generate a pseudo-random number. > How does this differ cryptographically from algorithms like MWC1616 and xorshift128+ in backend applications? That question doesn’t make any sense. The current timestamp would be a seed to initialise the PRNG, which can be MWC or xorshift. > Does it really matter which random number generator you use on a webpage? That is application dependent. If you’re coding a roulette wheel no, if you’re coding an E2E chat yes. > It's already considered an insecure environment anyway (that's why we have server-side validation). That is also application dependent. The client is considered insecure from the server pov because it is entirely under user control, so the user can mess with anything. But if it is acting entirely on behalf of the user then that can be the point and by design. In the example above, you don’t care that a user fucks up their own crypto, but you do care that the crypto holds for the average user. Even the qualitative difference between two non-CS PRNG can make or break a project due to too small a state space or short a cycle.
  - sverhagen 2y ago
    I don't really disagree with anything you said, but I think the roulette wheel and the E2E chat are funny examples, you could have a high value roulette game and a casual chat about the weather, where the stakes are opposite to your point ;-)
    - cratermoon 2y ago
      I was thinking this myself. When significant amounts of real money are sitting on the spin of the wheel and bouncing of the ball, a bad PRNG like the one discussed in the article would be disastrous.
      - masklinn 2y ago
        Yeah I was thinking less casino thingie and more https://pickerwheel.com https://pickerwheel.com, I guess I used the wrong term for it.
  - tetha 2y ago
- rkangel 2y ago
  They're call PRNG because they are pseudo random. If you know the starting state, you know what sequence they're going to generate. Putting it another way, if you always start them in the same state, they'll always produce the same sequence. So a PRNG needs "seeding". You need some value to put in at the start that is different every time. Using the time on the computer results in a different seed on each run, and so a different number sequence each time. If you need random numbers for cryptography (very good quality random numbers are important for lots of crypto processes) then you need to do more - they need to be completely unpredictable. If you just used the time, someone could seed a copy of the RNG with the same time, and predict the randomness sequence. So what we want is a seed that comes from actual randomness (also called "entropy"). That entropy has to come from somewhere - ideally some hardware source using some statistically random physical effect.
  - simonmales 2y ago
    Well written, h/t.
  - magicalhippo 2y ago
    > Putting it another way, if you always start them in the same state, they'll always produce the same sequence. This can be easy to bump into in fairly trivial cases. For example, initializing by time alone can be problematic if you spawn N threads at once which all do their own seeding. Then they can all reach the seeding process at the same time, relative to the clock used for the seeding. I had that problem with one of my earlier ray tracers, and so had to add add the thread id into the mix to seed the PRNGs.
    - markh1967 2y ago
      A demonstration of exactly this problem (only in older versions of .Net, newer versions use a different seeding method) https://dotnetfiddle.net/tLGMp6 https://dotnetfiddle.net/tLGMp6
    - mturmon 2y ago
      Agreed. I do a lot of Monte Carlo simulations of physical systems (radars, scientific models) in which same or close seeds will cause trouble. You do want a deterministic PRNG (for repeatability of the simulation). But if you seed with time alone, and spawn 100 parallel jobs, you will see repeats or near-repeats which will bias the Monte Carlo averages resulting from your simulation ensemble. In ancient times, you could xor in the PID and the IP address of the host to ensure no seed overlap. Nowadays there are other ways to introduce entropy to the seed, e.g. with dedicated system calls or /dev/random.
- spacechild1 2y ago
  > I learned in college that most random number generators use the current timestamp to generate a pseudo-random number. People typically seed a PRNG with the current time. The actual output sequence is still created with a determinstic algorithm. These two things are really orthogonal.
- Retr0id 2y ago
  xorshift128+ has exactly 128 bits of internal state. After collecting a small number of outputs, it is trivial to determine the internal state by constructing and then solving an equation (where the variables are GF(2) elements), regardless of how the "seed" was initialized. Once you have the internal state, you can predict all future outputs with 100% certainty. This only becomes a problem when people assume this isn't possible (for example, using it to pick lottery numbers) - this is more likely to happen on the server-side than the client-side (and v8 runs on both), but it can be security-relevant in client-only apps too (consider an insecure "password generator" app). https://en.wikipedia.org/wiki/GF(2) https://en.wikipedia.org/wiki/GF(2)
  - Retr0id 2y ago
    By the way, the "password generator app" is not a contrived hypothetical, it was actually one of my first ever bug-bounty payouts.
- markh1967 2y ago
  It's been a while so I can't provide a link but I remember reading about someone who got hold of a video blackjack machine that used a pseudo random number generator and was able to find the seed from only a few hands and then knew exactly which cards would be dealt next. He then went on to empty every machine he could find in the local casinos.
- lmm 2y ago
  > I learned in college that most random number generators use the current timestamp to generate a pseudo-random number. > How does this differ cryptographically from algorithms like MWC1616 and xorshift128+ in backend applications? How can a random number generator be vulnerable to attacks in real life? In the early days of online poker some people made a killing by figuring out all the possible hands from the PRNGs being used and then they could just start a game and look up the hands they'd been dealt in their database.
- deleted 2y ago
  [deleted]
jansan 2y ago
I wonder why there have not been any updates on v8.dev since July 2024. Did Google axe some v8 developer jobs?
- morbicer 2y ago
  Probably because they might be forced to sell it? https://www.bbc.com/news/articles/cp81ppr3l9go.amp https://www.bbc.com/news/articles/cp81ppr3l9go.amp
somat 2y ago
ah, the seed, an innocent implementation detail, but many people latch on to this and missuse random as a hash function. The one I remember was this screwball long term archival system from the early 2000's, zipped business archives on cd, the zip files were password protected. with the password being a hash of several factors about the data(unit, date, etc). A little stupid, but not the worst thing I have ever seen. The bad part was the hashing algorithm used, it was perls rand(). When I saw that I was vaguely horrified and a few test's confirmed my fears, the perl rand function would vary across operating systems and even different version of perl would change it. I think they ended up having to keep an explicit database of all the passwords just to have a fighting chance at opening those files later. not that they ever would. no one ever looks at long term records once they are stored. Anyway, I like how the openbsd folk fixed the old C rand family of functions. they made their seed functions do nothing and tied the generators to a strong kernel random source, that is, they made rand actually random. If your application actually depends on rand as a hash function they provided the old behavior under srand_deterministic(3) "Standards insist that this interface return deterministic results. Unsafe usage is very common, so OpenBSD changed the subsystem to return non-deterministic results by default." makes me laugh every time. http://man.openbsd.org/rand http://man.openbsd.org/rand
- lionkor 2y ago
  That's an interesting story, thanks for sharing. However, it is the reason that (what feels like) every single C function has a footnote, along the lines of "*except on FordBAT OS, where mkdir doesn't create a directory, all floats are inf, and negatives are positive -- because it seemed convenient"
- kevin_thibedeau 2y ago
  > they made rand actually random That is a phenomenally stupid thing to do. There is legitimate need for reproducible pseudo-random sequences derived from a known random seed. If you break seeding that can't be done. This is how fuzz testing with generated inputs works.
  - twic 2y ago
wruza 2y ago
For the curious, xorshift128+: uint64_t a = s[0]; uint64_t b = s[1]; s[0] = b; a ^= a << 23; a ^= a >> 18; a ^= b; a ^= b >> 5; s[1] = a; return a + b; https://stackoverflow.com/a/34432126 https://stackoverflow.com/a/34432126
- Retr0id 2y ago
  Fun fact, the state update function can be modelled as the multiplication of the state vector by a constant matrix (where the vector/matrix elements are all in GF(2)). By raising that matrix to a power n, you can use the resultant matrix to compute n state updates at once, allowing you to "skip ahead" arbitrarily into the output stream. Hypothetically, you could use this to vectorize/parallelize computation of xorshift128+ output sequences in large batches, but I'm not sure anyone's ever bothered to do this because the naive sequential method is so cheap.
  - deleted 2y ago
    [deleted]
  - shiftingleft 2y ago
    The easiest way to parallelize this RNG is to just run it in parallel on multiple states.
  - 8n4vidtmkvmk 2y ago
    I could see some speedrunners wanting to do this. I think it was in Windwaker some speedrunners ran some statistical analysis so they could beat this one mini-game where the odds were stacked against you.
somewhereoutth 2y ago
If anyone wants a seedable, and therefore deterministic PRNG, use the seedrandom package https://www.npmjs.com/package/seedrandom https://www.npmjs.com/package/seedrandom // Global PRNG: set Math.random. seedrandom('hello.', { global: true }); console.log(Math.random()); // Always 0.9282578795792454 I found this useful when using worker threads to 'render' a construction by slices that included some randomness (that should be the same for each thread)
- svachalek 2y ago
  Replacing a system function is a quick and easy hammer but not great for maintenance. It's not clear that calls to Math.random() are now actually going to an npm, and if someone deletes that seedrandom line it's not clear that calls to Math.random() are now not actually going to an npm. For new/clean code it's better to just import a seeded random function for clarity.
kittikitti 2y ago
Thank you so much for this, by coincidence I was looking for good sources about Pseudo Random Number Generators and how we program them. This does the trick and explains the levels of determinism and the most popular PRNG algorithms.
GrantMoyer 2y ago
Xorshift is really cool because of how simple it is to comprehend and implement despite how well it works as a PRNG. The initial paper describing it, "Xorshift RNGs"[1], is surprisingly short and approachable, and I encourage anyone with any interest to read through it. [1]: https://www.jstatsoft.org/article/download/v008i14/916 https://www.jstatsoft.org/article/download/v008i14/916
- pavel_lishin 2y ago
  It doesn't seem to work well for smaller sizes when shifting left by 1. I'm sitting in a waiting room, playing with this on paper with four-digit binary numbers, and so far it seems to rapidly fall into a loop of 1,3,5,15,1... edit: they all fall into their own loops. I forget the term for it, but the pattern is, unless I've made an arithmetic mistake (likely!): 1,3,5,15,1... 2,6,10,14,2... 4,12,4... 7,9,11,(1,3,5,15,1...) 8,8... 14,7,9,11,(1,3,5,15,1...)
  - GrantMoyer 2y ago
    Note that you need to use 3 shifts. All the triplets of shifts listed in the paper should generate sequences with period 2^32-1 or 2^64-1 depending on the state size, because the tables were generated with that constraint. For example the first triplet for a 32 bit state corresponds to the algortihm: def advance_state(state): state ^= state << 1 state ^= state >> 3 state ^= state << 10 return state
    - pavel_lishin 2y ago
      I should really have read the whole paper, but it's hard to read a PDF on my phone :/ I also definitely wasn't up for working with 8-digit binary numbers on my graph paper. What I consider may be weird, but it's not that weird :P (But I did do a little reading about LFSRs, and I wonder if the amount the numbers are shifted by is related to the stuff about arithmetic fields & groups & such... maybe I'll look into it later, but statistically speaking, probably not :) )
codesnik 2y ago
One mistake that bitten me a couple of times is not to reseed after fork(). AFAIR Perl calls srand automatically on fork, and I've been surprised that ruby at circa version 1.8 - didn't, which gave me quite some interesting behavior on production. I'm sure some other runtimes don't do it, too.
eternauta3k 2y ago
What applications care about this improvement, considering it's not cryptographically secure?
- GrantMoyer 2y ago
  I've hit issues with bad quality PRNGs when using them for Monte Carlo path tracing. With a non-uniform PRNG, the simulation can take a lot longer to converge to a clear image, because some ray paths can be severely under or over represented.
paulpauper 2y ago
the solution is to the use the RNG to build a key , not create the key with the bad RNG
pseudosavant 2y ago
Funny to see this coming up again after all these years. I was the person who reported this issue to the Chromium team, 3 years before that blog posts. They marked it as won't fix, multiple times (other people reported it too), before they fixed it. Safari, Firefox, and IE were all already using more robust PRNGs for Math.random() that did not exhibit this issue. https://stackoverflow.com/questions/9550796/why-is-google-chromes-math-random-number-generator-not-that-random https://stackoverflow.com/questions/9550796/why-is-google-ch... https://issues.chromium.org/issues/40404440 https://issues.chromium.org/issues/40404440 I came across it because of some tests I had for a statistics library I was working on. There was a test that created an array with 100k random values that shouldn't have had any collisions, but I consistently got multiple collisions, only in Chrome.
- magicalist 2y ago
  Pretty sure it was [1] that finally got them moving (old hacker news discussion here[2]). Not to take away from your bug report, but there were a bunch :) The main issues were that the spec allows engines to pick their own implementation (including only having 2^32 possible values) and there were benchmarks like sunspider where overfitting encouraged the implementation to be as fast as possible. That was a lot less of an excuse for the RNG they used in 2012-2015 compared to when it was added in 2007 or 2008, but by then there was a decent argument that developers should go to crypto.getRandomValues() if they wanted actual random values, which probably stalled action longer than it should have. > Safari, Firefox, and IE were all already using more robust PRNGs for Math.random This wasn't true at the time. I actually don't remember what Safari was doing in 2012 so I won't say that one for sure, but Firefox and IE were both using garbage RNGs as well, they were probably just generating across the full (or at least more of the) (0, 1] double range so didn't produce the collisions you saw in your testing. [1] https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d https://medium.com/@betable/tifu-by-using-math-random-f1c308... [2] https://news.ycombinator.com/item?id=10598065 https://news.ycombinator.com/item?id=10598065
  - pseudosavant 2y ago
    Safari, Firefox, and IE all had no trouble producing 100k random values without a collision. Chrome couldn't do it without at least two collisions. Chrome's `Math.random()` performance/speed was not measurably better despite, but it could only produce 2^32 random values despite IEEE-754 FP supporting up to 2^53. That is how I found this bug, because only Chrome used low enough entropy. Which is definitely worse. My recollection of that time working on that stats library was that Chrome took many shortcuts to max out things like SunSpider. There were other Chrome specific workarounds I had to implement to address what I considered bugs, but they were definitely in lightly defined areas like `Math.random()`. I couldn't find the original bug I file, but the discussion on it specifically noted that they could just copy the Firefox one (which was noted to be an improvement over Chrome's) but they decided on Won't Fix until someone more important than me drew attention to it. It was trivially fixed within a week once that happened.
brunoborges 2y ago
I am curious what other languages (and runtimes) have been using so far. Anyone knows?
- GrantMoyer 2y ago
  C++ has had a few options since C++11[1]. - Linear congruential generator[2]: xₜ = a xₜ₋₁ + c mod m - Mersenne Twister[3]: too complicated for a few lines - Subtract with carry[3]: k < p carryₜ = [xₜ₋ₖ - xₜ₋ₚ - carryₜ₋₁ < 0] xₜ = xₜ₋ₖ - xₜ₋ₚ - carryₜ₋₁ mod 2ⁿ All three algorithms are fairly popular. (Please excuse the unidiomatic index and constant names, I'm at the mercy of unicode) [1]: https://en.cppreference.com/w/cpp/header/random https://en.cppreference.com/w/cpp/header/random [2]: https://en.wikipedia.org/wiki/Linear_congruential_generator https://en.wikipedia.org/wiki/Linear_congruential_generator [3]: https://en.wikipedia.org/wiki/Mersenne_Twister https://en.wikipedia.org/wiki/Mersenne_Twister [4]: https://en.wikipedia.org/wiki/Subtract_with_carry https://en.wikipedia.org/wiki/Subtract_with_carry
  - adgjlsfhk1 2y ago
    Note that all 3 of these are fairly bad. Xoshiro and PCG are the 2 modern families of good fast rngs.

124 points by beepill 2y ago

(2015) Discussion at the time (229 points, 106 comments) https://news.ycombinator.com/item?id=10751396 https://news.ycombinator.com/item?id=10751396

dang 2y ago
Thanks! Macroexpanded: There's Math.random(), and then there's Math.random() (2015) - https://news.ycombinator.com/item?id=38188421 https://news.ycombinator.com/item?id=38188421 - Nov 2023 (49 comments) There's Math.random(), and then there's Math.random() - https://news.ycombinator.com/item?id=10751396 https://news.ycombinator.com/item?id=10751396 - Dec 2015 (106 comments)

maxloh 2y ago

I learned in college that most random number generators use the current timestamp to generate a pseudo-random number. How does this differ cryptographically from algorithms like MWC1616 and xorshift128+ in backend applications? How can a random number generator be vulnerable to attacks in real life? Does it really matter which random number generator you use on a webpage? It's already considered an insecure environment anyway (that's why we have server-side validation).

tomsmeding 2y ago
In a class we had to reverse-engineer an application that had encrypted some text file — we had to decrypt it without the key. Turned out the application just used the current unix timestamp as the key. A brute-force search of the past few months didn't take very long. If you include nanoseconds in your key then you have more entropy, of course, but timestamps are guessable, so it's risky.
- sverhagen 2y ago
  Those nanoseconds aren't really entropy then, are they?
  - lmm 2y ago
    They're entropy for most practical purposes. But there's only 1000 possibilities, so that's less than 10 bits' worth.
    - boothby 2y ago
      Especially if you're writing a file, the creation time is a big hint! Even nanoseconds won't help if you're leaking that many bits from your seed.
    - tomsmeding 2y ago
      That's milliseconds; nanoseconds are 1e-9 seconds. Still, the file creation time remark of sibling is pertinent.
      - lmm 2y ago
        I was thinking of the step from milli to nano, so yeah 1e6 not 1e3, 20 bits not 10. But the point stands.
hapidjus 2y ago
One attack might be exploiting One Time Passwords. Lets say you send yourself enough tokens to calculate the state, you will then be able to calculate the next token and login as another user. However that should be easily fixed by adding some salt relating to the user, meaning you would only be able to figure out _your_ next token.
atoav 2y ago
You can go back into a time before computers and use the most famous examples of how bad RNGs endanger crypto: One Time Pads (OTP). This is basically just a XOR of your message with your random numbers. If your random numbers are bad they leave patterns in the XOR-ed message that can be statistically analyzed and potentially decrypted. Bad PRNGs repeat early and have predictable patterns, as such they form a special attack vector. Whether that is really an issue for any given application, depends on the application (e.g. how shortlived the crypto is and how bad decryption acter the fact is). But if you are asking that question it likely means you don't know enough knowledge to roll your own crypto unless you wanna be in a world of pain. Just because PRNGs appear unpredictable to you does not mean they aren't. If you really wanna go the route, at least add a salt, so something like Hash(application_secret_long_and_random + timestamp_nanosecond_precision)
masklinn 2y ago
> I learned in college that most random number generators use the current timestamp to generate a pseudo-random number. > How does this differ cryptographically from algorithms like MWC1616 and xorshift128+ in backend applications? That question doesn’t make any sense. The current timestamp would be a seed to initialise the PRNG, which can be MWC or xorshift. > Does it really matter which random number generator you use on a webpage? That is application dependent. If you’re coding a roulette wheel no, if you’re coding an E2E chat yes. > It's already considered an insecure environment anyway (that's why we have server-side validation). That is also application dependent. The client is considered insecure from the server pov because it is entirely under user control, so the user can mess with anything. But if it is acting entirely on behalf of the user then that can be the point and by design. In the example above, you don’t care that a user fucks up their own crypto, but you do care that the crypto holds for the average user. Even the qualitative difference between two non-CS PRNG can make or break a project due to too small a state space or short a cycle.
- sverhagen 2y ago
  I don't really disagree with anything you said, but I think the roulette wheel and the E2E chat are funny examples, you could have a high value roulette game and a casual chat about the weather, where the stakes are opposite to your point ;-)
  - cratermoon 2y ago
    I was thinking this myself. When significant amounts of real money are sitting on the spin of the wheel and bouncing of the ball, a bad PRNG like the one discussed in the article would be disastrous.
    - masklinn 2y ago
      Yeah I was thinking less casino thingie and more https://pickerwheel.com https://pickerwheel.com, I guess I used the wrong term for it.
- tetha 2y ago
rkangel 2y ago
They're call PRNG because they are pseudo random. If you know the starting state, you know what sequence they're going to generate. Putting it another way, if you always start them in the same state, they'll always produce the same sequence. So a PRNG needs "seeding". You need some value to put in at the start that is different every time. Using the time on the computer results in a different seed on each run, and so a different number sequence each time. If you need random numbers for cryptography (very good quality random numbers are important for lots of crypto processes) then you need to do more - they need to be completely unpredictable. If you just used the time, someone could seed a copy of the RNG with the same time, and predict the randomness sequence. So what we want is a seed that comes from actual randomness (also called "entropy"). That entropy has to come from somewhere - ideally some hardware source using some statistically random physical effect.
- simonmales 2y ago
  Well written, h/t.
- magicalhippo 2y ago
  > Putting it another way, if you always start them in the same state, they'll always produce the same sequence. This can be easy to bump into in fairly trivial cases. For example, initializing by time alone can be problematic if you spawn N threads at once which all do their own seeding. Then they can all reach the seeding process at the same time, relative to the clock used for the seeding. I had that problem with one of my earlier ray tracers, and so had to add add the thread id into the mix to seed the PRNGs.
  - markh1967 2y ago
    A demonstration of exactly this problem (only in older versions of .Net, newer versions use a different seeding method) https://dotnetfiddle.net/tLGMp6 https://dotnetfiddle.net/tLGMp6
  - mturmon 2y ago
    Agreed. I do a lot of Monte Carlo simulations of physical systems (radars, scientific models) in which same or close seeds will cause trouble. You do want a deterministic PRNG (for repeatability of the simulation). But if you seed with time alone, and spawn 100 parallel jobs, you will see repeats or near-repeats which will bias the Monte Carlo averages resulting from your simulation ensemble. In ancient times, you could xor in the PID and the IP address of the host to ensure no seed overlap. Nowadays there are other ways to introduce entropy to the seed, e.g. with dedicated system calls or /dev/random.
spacechild1 2y ago
> I learned in college that most random number generators use the current timestamp to generate a pseudo-random number. People typically seed a PRNG with the current time. The actual output sequence is still created with a determinstic algorithm. These two things are really orthogonal.
Retr0id 2y ago
xorshift128+ has exactly 128 bits of internal state. After collecting a small number of outputs, it is trivial to determine the internal state by constructing and then solving an equation (where the variables are GF(2) elements), regardless of how the "seed" was initialized. Once you have the internal state, you can predict all future outputs with 100% certainty. This only becomes a problem when people assume this isn't possible (for example, using it to pick lottery numbers) - this is more likely to happen on the server-side than the client-side (and v8 runs on both), but it can be security-relevant in client-only apps too (consider an insecure "password generator" app). https://en.wikipedia.org/wiki/GF(2) https://en.wikipedia.org/wiki/GF(2)
- Retr0id 2y ago
  By the way, the "password generator app" is not a contrived hypothetical, it was actually one of my first ever bug-bounty payouts.
markh1967 2y ago
It's been a while so I can't provide a link but I remember reading about someone who got hold of a video blackjack machine that used a pseudo random number generator and was able to find the seed from only a few hands and then knew exactly which cards would be dealt next. He then went on to empty every machine he could find in the local casinos.
lmm 2y ago
> I learned in college that most random number generators use the current timestamp to generate a pseudo-random number. > How does this differ cryptographically from algorithms like MWC1616 and xorshift128+ in backend applications? How can a random number generator be vulnerable to attacks in real life? In the early days of online poker some people made a killing by figuring out all the possible hands from the PRNGs being used and then they could just start a game and look up the hands they'd been dealt in their database.
deleted 2y ago
[deleted]

jansan 2y ago

I wonder why there have not been any updates on v8.dev since July 2024. Did Google axe some v8 developer jobs?

morbicer 2y ago
Probably because they might be forced to sell it? https://www.bbc.com/news/articles/cp81ppr3l9go.amp https://www.bbc.com/news/articles/cp81ppr3l9go.amp

somat 2y ago

ah, the seed, an innocent implementation detail, but many people latch on to this and missuse random as a hash function. The one I remember was this screwball long term archival system from the early 2000's, zipped business archives on cd, the zip files were password protected. with the password being a hash of several factors about the data(unit, date, etc). A little stupid, but not the worst thing I have ever seen. The bad part was the hashing algorithm used, it was perls rand(). When I saw that I was vaguely horrified and a few test's confirmed my fears, the perl rand function would vary across operating systems and even different version of perl would change it. I think they ended up having to keep an explicit database of all the passwords just to have a fighting chance at opening those files later. not that they ever would. no one ever looks at long term records once they are stored. Anyway, I like how the openbsd folk fixed the old C rand family of functions. they made their seed functions do nothing and tied the generators to a strong kernel random source, that is, they made rand actually random. If your application actually depends on rand as a hash function they provided the old behavior under srand_deterministic(3) "Standards insist that this interface return deterministic results. Unsafe usage is very common, so OpenBSD changed the subsystem to return non-deterministic results by default." makes me laugh every time. http://man.openbsd.org/rand http://man.openbsd.org/rand

lionkor 2y ago
That's an interesting story, thanks for sharing. However, it is the reason that (what feels like) every single C function has a footnote, along the lines of "*except on FordBAT OS, where mkdir doesn't create a directory, all floats are inf, and negatives are positive -- because it seemed convenient"
kevin_thibedeau 2y ago
> they made rand actually random That is a phenomenally stupid thing to do. There is legitimate need for reproducible pseudo-random sequences derived from a known random seed. If you break seeding that can't be done. This is how fuzz testing with generated inputs works.
- twic 2y ago

wruza 2y ago

For the curious, xorshift128+: uint64_t a = s[0]; uint64_t b = s[1]; s[0] = b; a ^= a << 23; a ^= a >> 18; a ^= b; a ^= b >> 5; s[1] = a; return a + b; https://stackoverflow.com/a/34432126 https://stackoverflow.com/a/34432126

Retr0id 2y ago
Fun fact, the state update function can be modelled as the multiplication of the state vector by a constant matrix (where the vector/matrix elements are all in GF(2)). By raising that matrix to a power n, you can use the resultant matrix to compute n state updates at once, allowing you to "skip ahead" arbitrarily into the output stream. Hypothetically, you could use this to vectorize/parallelize computation of xorshift128+ output sequences in large batches, but I'm not sure anyone's ever bothered to do this because the naive sequential method is so cheap.
- deleted 2y ago
  [deleted]
- shiftingleft 2y ago
  The easiest way to parallelize this RNG is to just run it in parallel on multiple states.
- 8n4vidtmkvmk 2y ago
  I could see some speedrunners wanting to do this. I think it was in Windwaker some speedrunners ran some statistical analysis so they could beat this one mini-game where the odds were stacked against you.

somewhereoutth 2y ago

If anyone wants a seedable, and therefore deterministic PRNG, use the seedrandom package https://www.npmjs.com/package/seedrandom https://www.npmjs.com/package/seedrandom // Global PRNG: set Math.random. seedrandom('hello.', { global: true }); console.log(Math.random()); // Always 0.9282578795792454 I found this useful when using worker threads to 'render' a construction by slices that included some randomness (that should be the same for each thread)

svachalek 2y ago
Replacing a system function is a quick and easy hammer but not great for maintenance. It's not clear that calls to Math.random() are now actually going to an npm, and if someone deletes that seedrandom line it's not clear that calls to Math.random() are now not actually going to an npm. For new/clean code it's better to just import a seeded random function for clarity.

kittikitti 2y ago

Thank you so much for this, by coincidence I was looking for good sources about Pseudo Random Number Generators and how we program them. This does the trick and explains the levels of determinism and the most popular PRNG algorithms.

GrantMoyer 2y ago

Xorshift is really cool because of how simple it is to comprehend and implement despite how well it works as a PRNG. The initial paper describing it, "Xorshift RNGs"[1], is surprisingly short and approachable, and I encourage anyone with any interest to read through it. [1]: https://www.jstatsoft.org/article/download/v008i14/916 https://www.jstatsoft.org/article/download/v008i14/916

pavel_lishin 2y ago
It doesn't seem to work well for smaller sizes when shifting left by 1. I'm sitting in a waiting room, playing with this on paper with four-digit binary numbers, and so far it seems to rapidly fall into a loop of 1,3,5,15,1... edit: they all fall into their own loops. I forget the term for it, but the pattern is, unless I've made an arithmetic mistake (likely!): 1,3,5,15,1... 2,6,10,14,2... 4,12,4... 7,9,11,(1,3,5,15,1...) 8,8... 14,7,9,11,(1,3,5,15,1...)
- GrantMoyer 2y ago
  Note that you need to use 3 shifts. All the triplets of shifts listed in the paper should generate sequences with period 2^32-1 or 2^64-1 depending on the state size, because the tables were generated with that constraint. For example the first triplet for a 32 bit state corresponds to the algortihm: def advance_state(state): state ^= state << 1 state ^= state >> 3 state ^= state << 10 return state
  - pavel_lishin 2y ago
    I should really have read the whole paper, but it's hard to read a PDF on my phone :/ I also definitely wasn't up for working with 8-digit binary numbers on my graph paper. What I consider may be weird, but it's not that weird :P (But I did do a little reading about LFSRs, and I wonder if the amount the numbers are shifted by is related to the stuff about arithmetic fields & groups & such... maybe I'll look into it later, but statistically speaking, probably not :) )

codesnik 2y ago

One mistake that bitten me a couple of times is not to reseed after fork(). AFAIR Perl calls srand automatically on fork, and I've been surprised that ruby at circa version 1.8 - didn't, which gave me quite some interesting behavior on production. I'm sure some other runtimes don't do it, too.

eternauta3k 2y ago

What applications care about this improvement, considering it's not cryptographically secure?

GrantMoyer 2y ago
I've hit issues with bad quality PRNGs when using them for Monte Carlo path tracing. With a non-uniform PRNG, the simulation can take a lot longer to converge to a clear image, because some ray paths can be severely under or over represented.

paulpauper 2y ago

the solution is to the use the RNG to build a key , not create the key with the bad RNG

pseudosavant 2y ago

Funny to see this coming up again after all these years. I was the person who reported this issue to the Chromium team, 3 years before that blog posts. They marked it as won't fix, multiple times (other people reported it too), before they fixed it. Safari, Firefox, and IE were all already using more robust PRNGs for Math.random() that did not exhibit this issue. https://stackoverflow.com/questions/9550796/why-is-google-chromes-math-random-number-generator-not-that-random https://stackoverflow.com/questions/9550796/why-is-google-ch... https://issues.chromium.org/issues/40404440 https://issues.chromium.org/issues/40404440 I came across it because of some tests I had for a statistics library I was working on. There was a test that created an array with 100k random values that shouldn't have had any collisions, but I consistently got multiple collisions, only in Chrome.

magicalist 2y ago
Pretty sure it was [1] that finally got them moving (old hacker news discussion here[2]). Not to take away from your bug report, but there were a bunch :) The main issues were that the spec allows engines to pick their own implementation (including only having 2^32 possible values) and there were benchmarks like sunspider where overfitting encouraged the implementation to be as fast as possible. That was a lot less of an excuse for the RNG they used in 2012-2015 compared to when it was added in 2007 or 2008, but by then there was a decent argument that developers should go to crypto.getRandomValues() if they wanted actual random values, which probably stalled action longer than it should have. > Safari, Firefox, and IE were all already using more robust PRNGs for Math.random This wasn't true at the time. I actually don't remember what Safari was doing in 2012 so I won't say that one for sure, but Firefox and IE were both using garbage RNGs as well, they were probably just generating across the full (or at least more of the) (0, 1] double range so didn't produce the collisions you saw in your testing. [1] https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d https://medium.com/@betable/tifu-by-using-math-random-f1c308... [2] https://news.ycombinator.com/item?id=10598065 https://news.ycombinator.com/item?id=10598065
- pseudosavant 2y ago
  Safari, Firefox, and IE all had no trouble producing 100k random values without a collision. Chrome couldn't do it without at least two collisions. Chrome's `Math.random()` performance/speed was not measurably better despite, but it could only produce 2^32 random values despite IEEE-754 FP supporting up to 2^53. That is how I found this bug, because only Chrome used low enough entropy. Which is definitely worse. My recollection of that time working on that stats library was that Chrome took many shortcuts to max out things like SunSpider. There were other Chrome specific workarounds I had to implement to address what I considered bugs, but they were definitely in lightly defined areas like `Math.random()`. I couldn't find the original bug I file, but the discussion on it specifically noted that they could just copy the Firefox one (which was noted to be an improvement over Chrome's) but they decided on Won't Fix until someone more important than me drew attention to it. It was trivially fixed within a week once that happened.

brunoborges 2y ago

I am curious what other languages (and runtimes) have been using so far. Anyone knows?

GrantMoyer 2y ago
C++ has had a few options since C++11[1]. - Linear congruential generator[2]: xₜ = a xₜ₋₁ + c mod m - Mersenne Twister[3]: too complicated for a few lines - Subtract with carry[3]: k < p carryₜ = [xₜ₋ₖ - xₜ₋ₚ - carryₜ₋₁ < 0] xₜ = xₜ₋ₖ - xₜ₋ₚ - carryₜ₋₁ mod 2ⁿ All three algorithms are fairly popular. (Please excuse the unidiomatic index and constant names, I'm at the mercy of unicode) [1]: https://en.cppreference.com/w/cpp/header/random https://en.cppreference.com/w/cpp/header/random [2]: https://en.wikipedia.org/wiki/Linear_congruential_generator https://en.wikipedia.org/wiki/Linear_congruential_generator [3]: https://en.wikipedia.org/wiki/Mersenne_Twister https://en.wikipedia.org/wiki/Mersenne_Twister [4]: https://en.wikipedia.org/wiki/Subtract_with_carry https://en.wikipedia.org/wiki/Subtract_with_carry
- adgjlsfhk1 2y ago
  Note that all 3 of these are fairly bad. Xoshiro and PCG are the 2 modern families of good fast rngs.