Difference between java.util.Random and java.security.SecureRandom

My team got handed over some server side code (in Java) that generates random tokens and I have a question regarding the same -

The purpose of these tokens is fairly sensitive - used for session id, password reset links etc. So they do need to be cryptographically random to avoid somebody guessing them or brute force them feasibly. The token is a "long" so it is 64 bits long.

The code currently uses the java.util.Random class to generate these tokens. The documentation for java.util.Random clearly states the following:

> Instances of java.util.Random are not cryptographically secure. Consider instead using SecureRandom to get a cryptographically secure pseudo-random number generator for use by security-sensitive applications.

However, the way the code is currently using java.util.Random is this - It instantiates the java.security.SecureRandom class and then uses the SecureRandom.nextLong() method to obtain the seed that is used for instantiating the java.util.Randomclass. Then it uses java.util.Random.nextLong() method to generate the token.

So my question now - Is it still insecure given that the java.util.Random is being seeded using java.security.SecureRandom? Do I need to modify the code so that it uses java.security.SecureRandom exclusively to generate the tokens?

Currently the code seed's the Random once at startup

The standard Oracle JDK 7 implementation uses what's called a Linear Congruential Generator to produce random values in java.util.Random.

Taken from java.util.Random source code (JDK 7u2), from a comment on the method protected int next(int bits), which is the one that generates the random values:

> This is a linear congruential pseudorandom number generator, as defined by D. H. Lehmer and described by Donald E. Knuth in The Art of Computer Programming, Volume 3: Seminumerical Algorithms, section 3.2.1.

Predictability of Linear Congruential Generators

Hugo Krawczyk wrote a pretty good paper about how these LCGs can be predicted ("How to predict congruential generators"). If you're lucky and interested, you may still find a free, downloadable version of it on the web. And there's plenty more research that clearly shows that you should never use an LCG for security-critical purposes. This also means that your random numbers are predictable right now, something you don't want for session IDs and the like.

How to break a Linear Congruential Generator

The assumption that an attacker would have to wait for the LCG to repeat after a full cycle is wrong. Even with an optimal cycle (the modulus m in its recurrence relation) it is very easy to predict future values in much less time than a full cycle. After all, it's just a bunch of modular equations that need to be solved, which becomes easy as soon as you have observed enough output values of the LCG.

The security doesn't improve with a "better" seed. It simply doesn't matter if you seed with a random value generated by SecureRandom or even produce the value by rolling a die several times.

An attacker will simply compute the seed from the output values observed. This takes significantly less time than 2^48 in the case of java.util.Random. Disbelievers may try out this experiment, where it is shown that you can predict future Random outputs observing only two(!) output values in time roughly 2^16. It takes not even a second on a modern computer to predict the output of your random numbers right now.

###Conclusion

Replace your current code. Use SecureRandom exclusively. Then at least you will have a little guarantee that the result will be hard to predict. If you want the properties of a cryptographically secure PRNG (in your case, that's what you want), then you have to go with SecureRandom only. Being clever about changing the way it was supposed to be used will almost always result in something less secure...

A random has only 48 bits where as SecureRandom can have upto 128 bits. So the chances of repeating in securerandom is very small.

Random uses the system clock as the seed/or to generate the seed. So they can be reproduced easily if the attacker knows the time at which the seed was generated. But SecureRandom takes Random Data from your os(they can be interval between keystrokes etc - most os collect these data store them in files - /dev/random and /dev/urandom in case of linux/solaris) and uses that as the seed.
So if the small token size is okay(in case of Random), you can continue using your code without any changes, since you are using SecureRandom to generate the seed. But if you want larger tokens(which cannot be subject to brute force attacks) go with SecureRandom -
In case of random just 2^48 attempts are required, with todays advanced cpu's it is possible to break it in practical time. But for securerandom 2^128 attempts will be required, which will take years and years to break even with today's advanced machines.

See http://resources.infosecinstitute.com/random-number-generation-java/"> this link for more details.
EDIT
After reading the links provided by @emboss, it is clear that the seed, however random it maybe, should not be used with java.util.Random. It is very easy to calculate the seed by observing the output.

Go for SecureRandom - Use Native PRNG (as given in the link above) because it takes random values from the /dev/random file for each call to nextBytes(). This way an attacker observing the output will not be able to make out anything unless he is controlling the contents of the /dev/random file(which is very unlikely)
The sha1 prng algorithm calculates the seed only once and if your VM is running for months using the same seed, it might be cracked by an attacker who is passively observing the output.

NOTE - If you are calling the nextBytes() faster than your os is able to write random bytes(entropy) into the /dev/random, you might land into trouble when using NATIVE PRNG. In that case use a SHA1 PRNG instance of SecureRandom and every few minutes(or some interval), seed this instance with the value from nextBytes() of a NATIVE PRNG instance of SecureRandom. Running these two parallely will ensure that you are seeding regularly with true random values, while also not exhausting the entropy obtained by the Operating System.

If you run twice java.util.Random.nextLong() with the same seed, it will produce the same number. For security reasons you want to stick with java.security.SecureRandom because it's a lot less predictable.

The 2 Classes are similar, I think you just need to change Random to SecureRandom with a refactoring tool and most of your existing code will work.

If changing your existing code is an affordable task, I suggest you use the SecureRandom class as suggested in Javadoc.

Even if you find the Random class implementation uses the SecureRandom class internally. you should not take it for granted that:

1. Other VM implementations do the same thing.
2. Implementation of the Random class in future versions of the JDK still use the SecureRandom class

So it's a better choice to follow the documentation suggestion and go directly with SecureRandom.

The current reference implementation of java.util.Random.nextLong() makes two calls to the method next(int) which directly exposes 32 bit of the current seed:

protected int next(int bits) {
    long nextseed;
    // calculate next seed: ...
    // and store it in the private "seed" field.
    return (int)(nextseed >>> (48 - bits));
}

public long nextLong() {
    // it's okay that the bottom word remains signed.
    return ((long)(next(32)) << 32) + next(32);
}

The upper 32 bit of the result of nextLong() are the bits of the seed at the time. Since the width of the seed is 48 bit (says the javadoc), it suffices* to iterate over the remaining 16 bit (that's only 65.536 tries) to determine the seed which produced the second 32 bit.

Once the seed is known, all following tokens can easily be computed.

Using the output of nextLong() directly, partly the secret of the PNG to a degree that the entire secret can be computed with very little efford. Dangerous!

* There is some effort needed if the second 32 bit are negative, but one can find that out.

The seed is meaningless. A good random generator differs in the chosen primenumber. Every random generator starts from a number and iterates through a 'ring'. Which means, you come from one number to the next, with the old internal value. But after a while you reach the beginning again and start all over again. So you run cycles. (the return value from a random generator is not the internal value)

If you use a prime number for creating a ring, all numbers in that ring gets chosen, before you complete a full cycle through all possible numbers. If you take non prime numbers, not all numbers are chosen and you get shorter cycles.

Higher prime numbers mean, longer cycles, before your returning to the first element again. So, the secure random generator just has a longer cycle, before reaching the beginning again, thats why it is safer. You can't predict the number generation as easy as with shorter cycles.

With other words: You have to replace all.

I will try to use very basic words so that you can easily understand the difference between Random and secureRandom and importance of SecureRandom Class.

Ever wonder how OTP(one time password) is generated? To generate an OTP we too use Random and SecureRandom class. Now to make your OTP strong, SecureRandom is better because it took 2^128 try, to crack the OTP which is nearly impossible by present machine but if used Random Class then your OTP can be cracked by someone who can harm your data because it took just 2^48 try, to crack.