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

Question

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

Solution 1

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...

Solution 2

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 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.

Solution 3

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.

Solution 4

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.

Solution 5

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.

View more solutions

Comments

[Peter Štibraný]

Once seeded, output from java.util.Random is deterministic sequence of numbers. You may not want that.

[Tom Anderson]

Does the code seed the Random once at startup, or does it seed a new one for every token? Hopefully, this is a stupid question, but i thought i'd check.

[Vishy]

Random only has a 48-bit internal state and will repeat after 2^48 calls to nextLong() which means that it won't produce all possible long or double values.

[Thorsten S.]

There is another severe problem. 64bits means 1.84*10^19 possible combinations which is too few to withstand a sophisticated attack. There are machines out there which cracked a 56 bit DES code (factor 256 less) with 90*10^9 keys per second in 60 hours. Use 128 bits or two longs !

[Palpatim]

I don't believe the original question stated that the java.util.Random implementation used SecureRandom internally, it said their code uses SecureRandom to seed the Random. Still, I agree with both the answers so far; it's best to use SecureRandom to avoid an explicitly deterministic solution.

[Robert]

If you take two instances of any PRNG and seed it with the same value you always get the same random numbers, even using SecureRandom does not change that. All PRNGs are deterministic and therefore predictable if you know the seed.

[Peter Štibraný]

There are different SecureRandom implementations, some are PRNGs, some are not. On the other hand, java.util.Random is always PRNG (as defined in its Javadoc).

[emboss]

It requires much less than 2^48 to predict a Random, the OP shouldn't be using Random at all.

[Ashwin]

@emboss : I am talking about bruteforce.

[gresdiplitude]

Very helpful, may be you could also explain how SecureRandom works (just like you explain how Random works)..

[Azulflame]

That defeats the purpose of secureRandom

[Azulflame]

I know, learned that lesson the hard way. But a tough cypher and hard-to-find source works well. Notch could learn something on that (he encodes his user's password in a .lastlogin file, encoded with basic encryption using "passwordfile" as the key)

[Joel Coehoorn]

The real question here: if java can produce a more secure prng with a similar API, why didn't they just replace the broken one?

[emboss]

@JoelCoehoorn It's not that Random is broken - it should just be used in different scenarios. Of course, you could always use SecureRandom. But in general, SecureRandom is noticeably slower than pure Random. And there are cases where you are only interested in good statistical properties and excellent performance, but you don't really care about security: Monte-Carlo simulations are a good example. I made comments about that in a similar answer, maybe you'll find it useful.

[emboss]

@Vaishali Thanks! If I get the time, I'll try to lose a few words about the default SecureRandom implementation. In the meantime, maybe you'll find this interesting...

[Yves Martin]

Take care with Linux: it can reach entropy exhaustion (more in VM than with hardware) ! Look at /proc/sys/kernel/random/entropy_avail and check with some thread dumps that there is no too long wait when reading on /dev/random

[ingyhere]

Correct. See how to quickly crack java.util.random at jazzy.id.au/default/2010/09/20/… !

[Boaz]

Notice that Oracle JRE (at least 1.7) works with /dev/urandom by default and not /dev/random so the suffix of your answer is no longer correct. to verify check $JAVA_HOME/lib/security/java.security for the securerandom.source property

[artspb]

The fresh article on the same subject. There's also implementation inside that able to predict double values. (franklinta.com/2014/08/31/…)

[maxpolk]

Our java.security file had securerandom.source=file:/dev/urandom instead of file:///dev/urandom (two slashes after colon for file protocol, then one more slash for root of filesystem), causing it to fall back to /dev/random, which caused problems with entropy pool exhaustion. Couldn't edit it, so had to set a system property java.security.egd to the right one at app startup.

[Amrinder Arora]

@emboss The "experiment" provided on the blog actually does not work - the if condition never comes out as true. Other people on that blog comment list have also made that comment.

[ShHolmes]

If anyone is looking for a pdf version - I've found a link: vdocuments.mx/download/how-to-predict-congruential-generator‌​s

[Charlie Reitzel]

In practice, new SecureRandom() uses /dev/urandom so you don't need to set securerandom.source. /dev/random should almost never be used. It will block most of the time for a very long time and the additional entropy is only slight. So, unless you really have a good reason, always use /dev/urandom.

[Charlie Reitzel]

On Linux, if you use new SecureRandom() and, thus, /dev/urandom you will continually pull in additional entropy from the OS device. It is not, strictly speaking, a pseudo-random number generator (PRNG). It is a hybrid PRNG-enhanced-with-entropy, so to speak (and a nice piece of engineering).