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 (http://docs.oracle.com/javase/7/docs/api/java/util/Random.html) 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?
EDIT: Re @Tom's question - 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 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 dice 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.
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...