Predicting the next Math.random() in Java • Hacker News Board

Re: Predicting the next Math.random() in Java

#31

Post by TheLoneWolfling » Mon, Sep 01, 2014, 9:14 PM UTC

MichaelGG wrote: post #30

SeanLuke wrote: post #24

Earlier quoted context omitted.

> Math.random() is simply a super-fast decent RNG Actually, java.util.Random is a horrible, horrible RNG. Its least significant bit (for example) is grotesquely nonrandom. See http://www.alife.co.uk/nonrandom/ for a wonderful demonstration of its awfulness. There are other serious bugs in java.util.Random which Sun, er, Oracle, has steadfastly refused to fix or revise for a decade now due to concerns about "backward…

How did Java and up with such a poor implementation? Certainly these things were known when writing that library?

Java has a number of... questionable, shall we say, design decisions.

Some of it is legacy cruft - Random was first released in, what, 1995?

Some of it is fallout of it being designed by committee - "we need it to pass this bunch of certifications, which means we have to do this bunch of things even though it doesn't make much sense to do so".

And some of it is undoubtedly the classic execution speed / maintainability tradeoff - no-one has unlimited dev time, Oracle included. A LCRNG is simple and well-known.

Re: Predicting the next Math.random() in Java

#32

Post by ygra » Mon, Sep 01, 2014, 9:27 PM UTC

TheLoneWolfling wrote: post #31

MichaelGG wrote: post #30

Earlier quoted context omitted.

How did Java and up with such a poor implementation? Certainly these things were known when writing that library?

Java has a number of... questionable, shall we say, design decisions. Some of it is legacy cruft - Random was first released in, what, 1995? Some of it is fallout of it being designed by committee - "we need it to pass this bunch of certifications, which means we have to do this bunch of things even though it doesn't make much sense to do so". And some of it is undoubtedly the classic execution speed / maintainabilit…

Also they cannot change it now, because its behaviour is documented and people certainly rely on it somewhere.

And it's about km owing what tools to use for what job anyway. I'd you just need to roll a few dice, Random is fine enough. If you need generated passwords, or cryptographic keys, you use SecureRandom. And if you need to run Monte Carlo simulations you'll just implement either MT-19937 or one of the WELL generators.

Re: Predicting the next Math.random() in Java

#33

Post by floody-berry » Mon, Sep 01, 2014, 10:01 PM UTC

SeanLuke wrote: post #24

imaginenore wrote: post #8

If you want cryptographic-quality random numbers, both Java and Javascript have them. Math.random() is simply a super-fast decent RNG. Example: var buf = new Uint32Array(10); window.crypto.getRandomValues(buf); console.log(buf); Outputs things like: [4027145128, 258543382, 1205615760, 2665675208, 4033127244, 2280027866, 3983484449, 510932333, 1911490534, 2609399642] This works in Chrome and FF. IE11 has Crypto.getRan…

> Math.random() is simply a super-fast decent RNG Actually, java.util.Random is a horrible, horrible RNG. Its least significant bit (for example) is grotesquely nonrandom. See http://www.alife.co.uk/nonrandom/ for a wonderful demonstration of its awfulness. There are other serious bugs in java.util.Random which Sun, er, Oracle, has steadfastly refused to fix or revise for a decade now due to concerns about "backward…

Cryptographic doesn't mean slow. If you generate in to a large enough buffer (1-2kb is good), Chacha8 is anywhere from ~1.5 cycles/byte (SSSE-3, Wolfdale) to ~0.5 cycles/byte (AVX2, Haswell). Even unoptimized implementations are still fairly efficient at ~5 cycles/byte.

If you don't care about the cryptographic properties, it could be made even faster by dropping to 6 rounds and tweaking the output step.

Re: Predicting the next Math.random() in Java

#34

Post by sehugg » Mon, Sep 01, 2014, 10:32 PM UTC

SeanLuke wrote: post #24

imaginenore wrote: post #8

If you want cryptographic-quality random numbers, both Java and Javascript have them. Math.random() is simply a super-fast decent RNG. Example: var buf = new Uint32Array(10); window.crypto.getRandomValues(buf); console.log(buf); Outputs things like: [4027145128, 258543382, 1205615760, 2665675208, 4033127244, 2280027866, 3983484449, 510932333, 1911490534, 2609399642] This works in Chrome and FF. IE11 has Crypto.getRan…

> Math.random() is simply a super-fast decent RNG Actually, java.util.Random is a horrible, horrible RNG. Its least significant bit (for example) is grotesquely nonrandom. See http://www.alife.co.uk/nonrandom/ for a wonderful demonstration of its awfulness. There are other serious bugs in java.util.Random which Sun, er, Oracle, has steadfastly refused to fix or revise for a decade now due to concerns about "backward…

An appropriate Xorshift generator is likely much better (and faster) than java.util.Random: http://xorshift.di.unimi.it/

I've used them to improve my hashing collision rate.

Re: Predicting the next Math.random() in Java

#35

Post by ajanuary » Mon, Sep 01, 2014, 11:08 PM UTC

UnoriginalGuy wrote: post #9

drinchev wrote: post #3

How dangerous this prediction can be? I can't stop thinking of java-backended real money, poorly written, gaming websites.

Those likely won't be vulnerable even if they implemented their site using the insecure random function. The reason why this works is that you're the only consumer of Java-randomness, as you add additional consumers it becomes infinitely more difficult. Consumers also don't need to be users, AI players and cards dealt will also consume randomness. You would also need to know the mapping from the random output into th…

You'd have more luck with fixed-odds games. The APIs for those tend to expose the results of the RNG in ways that are fairly easy to piece together. Some of the API responses will literally tell you enough to know "we picked a random number between 0 and x, and the result was y".

Re: Predicting the next Math.random() in Java

#36

Post by [deleted] » Tue, Sep 02, 2014, 12:20 AM UTC

floody-berry wrote: post #33

SeanLuke wrote: post #24

Earlier quoted context omitted.

> Math.random() is simply a super-fast decent RNG Actually, java.util.Random is a horrible, horrible RNG. Its least significant bit (for example) is grotesquely nonrandom. See http://www.alife.co.uk/nonrandom/ for a wonderful demonstration of its awfulness. There are other serious bugs in java.util.Random which Sun, er, Oracle, has steadfastly refused to fix or revise for a decade now due to concerns about "backward…

Cryptographic doesn't mean slow. If you generate in to a large enough buffer (1-2kb is good), Chacha8 is anywhere from ~1.5 cycles/byte (SSSE-3, Wolfdale) to ~0.5 cycles/byte (AVX2, Haswell). Even unoptimized implementations are still fairly efficient at ~5 cycles/byte. If you don't care about the cryptographic properties, it could be made even faster by dropping to 6 rounds and tweaking the output step.

[deleted]

Re: Predicting the next Math.random() in Java

#37

Post by SeanLuke » Tue, Sep 02, 2014, 12:27 AM UTC

TheLoneWolfling wrote: post #27

SeanLuke wrote: post #24

Earlier quoted context omitted.

> Math.random() is simply a super-fast decent RNG Actually, java.util.Random is a horrible, horrible RNG. Its least significant bit (for example) is grotesquely nonrandom. See http://www.alife.co.uk/nonrandom/ for a wonderful demonstration of its awfulness. There are other serious bugs in java.util.Random which Sun, er, Oracle, has steadfastly refused to fix or revise for a decade now due to concerns about "backward…

> There are other serious bugs in java.util.Random which Sun, er, Oracle, has steadfastly refused to fix or revise for a decade now due to concerns about "backward compatibility" (in an RNG!) Backward compatibility in a RNG is actually rather important, weirdly enough. For example, anything that uses deterministic seeds for repeatability of procedural generation or optimization. (Read: Minecraft, among other more imp…

> Backward compatibility in a RNG is actually rather important, weirdly enough. For example, anything that uses deterministic seeds for repeatability of procedural generation or optimization. (Read: Minecraft, among other more important things).

This seems like a very, very bad thing to rely on. Other than Java, how many other languages have guarantees in generator determinism from version to version as part of the language contract? Certainly Lisp considers it an antipattern.

Re: Predicting the next Math.random() in Java

#38

Post by eru » Tue, Sep 02, 2014, 12:49 AM UTC

cornewut wrote: post #20

jonahx wrote: post #15

Earlier quoted context omitted.

True, although honestly your tongue-in-cheek enum example is probably closer to where the line should be.

Also a nice reminder: "Never write your own crypto"

(Outside of education.)

Re: Predicting the next Math.random() in Java

#39

Post by eru » Tue, Sep 02, 2014, 12:54 AM UTC

lutusp wrote: post #12

Hernanpm wrote: post #7

Earlier quoted context omitted.

Real random numbers are useless because everything follow some distribution. Actually random generators in programming languages should be called pseudorandom to avoid confusions.

> Real random numbers are useless because everything follow some distribution. First, real random numbers are quite valuable. Second, yes, all numerical sequences follow a distribution, but one of those distributions is called the "normal distribution", and I think you may be able to guess what that refers to. > Actually random generators in programming languages should be called pseudorandom to avoid confusions. It…

Why is the normal distribution important here? (In programming, people often start from the uniform distribution, don't they?)

Re: Predicting the next Math.random() in Java

#40

Post by cdwhite » Tue, Sep 02, 2014, 1:12 AM UTC

TheLoneWolfling wrote: post #27

SeanLuke wrote: post #24

Earlier quoted context omitted.

> Math.random() is simply a super-fast decent RNG Actually, java.util.Random is a horrible, horrible RNG. Its least significant bit (for example) is grotesquely nonrandom. See http://www.alife.co.uk/nonrandom/ for a wonderful demonstration of its awfulness. There are other serious bugs in java.util.Random which Sun, er, Oracle, has steadfastly refused to fix or revise for a decade now due to concerns about "backward…

> There are other serious bugs in java.util.Random which Sun, er, Oracle, has steadfastly refused to fix or revise for a decade now due to concerns about "backward compatibility" (in an RNG!) Backward compatibility in a RNG is actually rather important, weirdly enough. For example, anything that uses deterministic seeds for repeatability of procedural generation or optimization. (Read: Minecraft, among other more imp…

Also, when you're writing scientific code (Monte Carlo simulations, for example, or disordered systems), the folk wisdom is that you must to keep track of what seed you used. I've never had to use these records myself, but I can image wanting to go back and reproduce exactly the same calculation, for (e.g.) debugging or verifying new code. Now you think about resurrecting some previous grad student's code that only works when used in exactly the right way and has documentation scattered through comments and notebooks---which is perfectly natural, since he probably didn't think anybody else would ever use it---and a change in PRNG algorithm could be immensely frustrating. Or think about trying to re-run old code to compare with new analytical results: you'd want to verify that you're getting exactly the same results, as a way of checking that there isn't some other bitrot hidden away somewhere.

(Now, why one would be using Java for Monte Carlo simulations I haven't the foggiest idea.)