Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Predicting the next Math.random() in Java

franklinta.com

Post reply on HN
Print view View original

21–30 of 58 posts

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

#21

Post by banthar »

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…

This more probable than you think. Java code is likely to use Collections.shuffle(). That method uses internal Random which is used only for shuffling. Shuffling is unlikely to be used for other purposes than shuffling cards. There isn't that many ways to shuffle them either.

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

#22

Post by cynicalkane »

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…

In the event tptacek doesn't show up to explain how awfully wrong this is, I'll do my best to fill in.

An attacker who can predict your PRNG and guess a seeded value knows a potentially infinite number of future random numbers. Now all he needs to do is guess what random numbers, from a very small pool of possible numbers, will show up at what time. Devs often code assuming that PRNG numbers aren't predictable at all, so compromising your RNG is like setting your password to "hunter2" in a situation where nobody thinks about limiting the number of guesses.

Such attacks were famously used to steal a lot of money on PlanetPoker, one of the first poker websites. RNG attacks are also deadly in encryption, where it's reasonable for an attacker to be able to make millions of guesses from his laptop computer.

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

#23

Post by imaginenore »

Osmium wrote: post #13
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…

Devil's advocate, but why not rename "Random" to "AlmostRandom" instead, and call "SecureRandom" just "Random"? It's not unreasonable for a lay programmer to expect "random" to be exactly that; though, obviously, non-experts shouldn't be implementing crypto regardless. But since they will, despite everyone's best advice otherwise, why not reduce their chances of introducing bugs?

Because

1) Even SecureRandom is likely not completely random. Unless they seed with physical/unpredictable randomness.

2) It's much slower

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

#24

Post by SeanLuke »

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 compatibility" (in an RNG!)

> If you want cryptographic-quality random numbers

I think you're confusing "crytographic-quality" with "high quality".

RNGs tend to break down into two different camps. First, there are RNGs meant for simulation of stochastic processes. These RNGs need to be fast, have good periods, and have a very high degree of statistical randomness in their output.

Second, there are RNGs meant for crypto. Speed is less important. Rather it's important that these RNGs provide good statistical randomness, but also it's crucial that, given some M previous output numbers of the RNG, you cannot predict or make any statistical claims about the next number even if you know how the algorithm works. This isn't important for non-crypto RNGs.

For example, Mersenne Twister is a pretty high quality, widely used RNG. But it is not cryptographically secure: if you have about 1500 of the previous output numbers, you can perfectly predict the next number if you know it's MT producing them.

While there are many applications for crypto RNGs, for a great many tasks, a non-crypto RNG would be a better fit.

java.util.Random was meant for non-crypto tasks. And it completely fails at even those tasks.

But SecureRandom is really bad for those tasks too: it is slow. For example, my MersenneTwister implementation is about 9 times faster than SecureRandom; and my non-threadsafe MT implementation is about 36 times faster. That's a big deal if you're pulling down millions and millions of numbers.

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

#26

Post by xxs »

Math.random() should be used only for tests. That's it. Performance sucks as it's shared. ThreadLocalRandom is a lot better if you need fast but not-quality random.

And there is SecureRandom for security concerns.

Last fun fact Math.random() and a Monte Carlo test introduced "CAS in Java" and all that followed with JSR 166.

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

#27

Post by TheLoneWolfling »

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…

> 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 important things).

That being said, things like this are why I wish more programming languages had proper (read: fine-grained) versioning of libraries. "I need to link to a function with this signature, that is one of these versions or any version that has been declared to be compatible with them, preferably the latest version that is so". That sort of thing.

> For example, Mersenne Twister is a pretty high quality, widely used RNG. But it is not cryptographically secure... But SecureRandom is really bad for those tasks too: it is slow. For example, my MersenneTwister implementation is about 9 times faster than SecureRandom

By your own words, you're comparing apples to oranges here...

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

#28

Post by MichaelGG »

Osmium wrote: post #13
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…

Devil's advocate, but why not rename "Random" to "AlmostRandom" instead, and call "SecureRandom" just "Random"? It's not unreasonable for a lay programmer to expect "random" to be exactly that; though, obviously, non-experts shouldn't be implementing crypto regardless. But since they will, despite everyone's best advice otherwise, why not reduce their chances of introducing bugs?

Why not rename comparison functions, too, since they often aren't constant time? And all sorts of other primitives someone might accidentally use?

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

#29

Post by MichaelGG »

UnoriginalGuy wrote: post #11
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.

By that logic nothing should ever be called random (in any context). There are things we can measure but don't understand the source of the entropy, but they aren't random we just haven't figured out the source yet. Most things we consider random are quantifiable and predictable with enough data (be it nature or computers). Plus there are several definitions of the term "random" (English) which are in-line with the p…

I thought quantum processes were truly random.

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

#30

Post by MichaelGG »

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…

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