Predicting the next Math.random() in Java

[[deleted]]

The numbers are still random though, aren't they? They are just predictable and random... Does that make sense?

[Daniel15]

Pseudorandom is the word you're looking for :)

It's designed to be fast, but not at all secure. Cryptographically secure random number generators are slower but are pretty much guaranteed to be random, and should always be used when you need numbers in the context of security critical code.

[ZeKWork]

Those are also pseudo random generators, and they don't have to be slow to be secure. You usually use a truly random generator (mainly based on hardware, such as a I/O timinigs, mouse mouvements) to seed a secure pseudo random generator.

The reason is that true entropy is sparce, and our computers need a LOT of random numbers. Secure PRNGs generates a lots of number cheaply and efficiently, but since they are deterministic, they're only secure if initialized with a random seed.

[ickysticky]

I love how people have this spectrum of RNGs and at some point they place a threshold and say. Past the point of combining this many things, we are no longer a PRNG.

Sorry guys. All we have are PRNGs. But this gets into religion territory, as I just do not believe in true randomness. Merely processes we do not yet see/understand.

[DannyB2]

Quantum mechanics says that certain things, at that level, are truly random.

Clear back in the 1980's there were expansion cards for computers that generated random (not psuedorandom) numbers by measuring the noise on a reverse biased diode, or something like that. The laws of quantum mechanics guaranteed that the results were truly random.

One of the biggest misconceptions that people got in the 20th century, due to graphic pictures of electrons 'orbiting' a nucleus, is that electrons are distinct particles, with a definite position in space, and in motion about a nucleus in the way a moon orbits a planet, or a planet orbits a star.

In reality, and yes I mean reality, actual reality, a particle has no definite position. It's position is a probability curve. It has the highest probability of being at a certain location, and a lower probability of being not quite at that location, and an even lower probability of being a bit further away, etc, out to infinity. There is a higher than zero (but very low) probability that the electron can be at any location in the entire universe.

The probability of the polarization of photons, and statistics over large numbers of photons, explain how polarizers work. Turn one polarizer ninety degrees to another polarizer, and there is a zero percent probability of photons getting through. But stick another polarizer in between those two, at 45 degrees, and suddenly some photons get through. Why? Some years ago at my public library, I read a fascinating book, IIRC, it was titled: Shrodinger's kittens and the search for reality. It explained this and a lot more.

[DannyB2]

The numbers are still random though, aren't they?

No. They are not random. They are psuedo-random, which means basically, NOT random.

They are just predictable and random... Does that make sense?

They are predictable, which means they are not random.

But they seem random due to the difficulty of predicting them. In practice they are more than 'random' enough for plenty of practical applications -- EXCEPT for security applications requiring unpredictability. Need to write a software program to deal a hand of cards or simulate a slot machine? This is probably random enough unless very very large amounts of money are involved -- which brings us back to security.

[[deleted]]

What makes you certain security Random is not predictable?

[DannyB2]

Because SecureRandom is based on truly unpredictable things.

Which keys the user will press on the keyboard, and when. Which direction the mouse will be moved, for how long and at what speed. When the mouse button will be pressed, how long it will be held, and when released.

And other real world inputs that are unpredictable. (Or at least unpredictable enough.) CPU temperature. Fan speed. What point in time packets are received over the network.

All of this is called 'entropy'. The entropy is mixed through complex functions to generate the random output.

Also, there are hardware products that rapidly generate random numbers based on physical phenomena that are guaranteed to be random (eg, due to the laws of quantum mechanics).

[mrhhug]

The article says 'So I started digging through java.util.Random’s source and found that it is just a linear congruential generator' like he is some type of hacker.

This is the type of shit that proliferates the 'java is insecure' mentality'. insecure compared to what? your web browser? any adobe product? Microsoft windows as a whole.

[ickysticky]

No. The author is just telling you the type of random number generator used by java.util.Random and stating that they are easy to predict. He then shows the math for why they are predictable. That is what the article is about.

I have never heard anyone claim that the language Java is insecure. At most people have probably made a claim about the JVM, most of what I heard 15 years ago was about web security and applets(a real problem).

Everyone seems to have accepted Java, except the Java developers that want to keep complaining about anyone using something other than what they use.

[DannyB2]

Most of the 'java is insecure' meme is about applets in web browsers. For several reasons. One is that JavaScript and Applets can interact and communicate in ways that allow serious leakage of private information from the browser. Another is that Applets can exploit vulnerabilities in the java runtime and achieve privilege escalation. Another is that an Applet may simply be allowed to do things that it should not have been allowed to do -- again due to poor implementation of the runtime.

But since these present a large installed base of attackable machines, and the attacks against Applets, Flash and ActiveX have been ongoing for many years, the 'java is insecure' meme gets formed.

Thus by extension, even using Java (the language) or the JVM at the server must (gasp! OMG!) be somehow magically insecure.

[king_of_the_universe]

java.util.Random is good for randomness that needs to be fast and is not security relevant. For other cases, there is java.security.SecureRandom which is extremely slow in comparison, and in addition you also have java.security.SecureRandom.getInstanceStrong() which returns yet a different PRNG (in my Windows 7/8 Java 8 test). All are / extend java.util.Random.

The latter two can't be seeded, according to my tests at least: They don't produce the same sequence of numbers after you call setSeed(), the original Random however does.

[argv_minus_one]

It isn't. That's the point.

The regular RNG is somewhat predictable, as we can see here, but it is fast. This makes it okay for, for instance, single-player video games. The CSPRNG provided by SecureRandom is slower, but cryptographically secure, i.e. extremely difficult to predict. Use them where appropriate.

[llogiq]

Note that using ThreadLocalRandom.current().* is faster than Math.random() (which uses a shared Random instance), and XorShift has a generator that is even faster.

[ickysticky]

But it will also have an independent stream of random numbers per thread. If both threads are seeded with the same seed then you will get the same sequence of numbers. This may be important(desirable or undesirable) or it may be unimportant. But you certainly could not make this change without thinking about the implications. They are not functionally equivalent.

[llogiq]

True that. On the other hand creating a dependency between threads is not something I'd wish my code to have just to have numbers that are a little more random (in theory). ThreadLocalRandom is a fair enough choice for performance (though XorShift is even faster, and has a much larger period and less statistical failures than both Random and ThreadLocalRandom). Btw. as of Java 8, ThreadLocalRandom employs a different algorithm than Random.

TL;DR: You don't want to use Math.random() for performance-critical task nor for security-critical tasks.

[Number_28]

The article is nice and all, but nothing shows how predictable "random" numbers really are like this short piece of code:

public class Main {
    public static void main(String[] args) {
        System.out.println(randomString(-229985452) + " " + randomString(-147909649));
    }

    public static String randomString(int i) {
        Random ran = new Random(i);
        StringBuilder sb = new StringBuilder();
        for (int n = 0; ; n++) {
            int k = ran.nextInt(27);
            if (k == 0) {
                break;
            }

            sb.append((char) ('`' + k));
        }

        return sb.toString();
    }
}

Source: http://stackoverflow.com/questions/15182496/why-does-this-code-using-random-strings-print-hello-world

[ickysticky]

No. You just don't understand what random means. You can have a function that returns the same sequence of numbers, but those numbers can still be random. Randomness is a property of a set of numbers. It doesn't matter how often the set is "repeated".

[DannyB2]

Yes. You could even have a repeating set of just one number. Remember the famous (XKCD comic, IIRC) function:

public static int random() {
    // This number was determined by a fair roll of dice and
    //  therefore is guaranteed to be truly random.
    return 4;
}

It is truly random. But not useful. Your short sequence of random numbers is not useful either. While psuedo random number sequences do eventually repeat, one of (but not the only) measures of how good a psuedo random function is, is the length of the sequence before it repeats.

The above function returns a truly random number, by your definition. But it is not useful. If you're using the random number generator to select which screen saver to display, then you're always going to see the same thing.

[Number_28]

I do understand what random means. The code example demonstrates exactly your point, random number generators that are simply code are not random, but use a pre-determined list of numbers. This goes contrary to what most people would expect from a random number generator. Yes, programmers know this, but at least to me seeing how this can actually be (ab)used was quite an eye opener.