If you want a cryptographically strong random numbers in Java, you use SecureRandom. Unfortunately, SecureRandom can be very slow. If it uses /dev/random on Linux, it can block waiting for sufficient entropy to build up. How do you avoid the performance penalty?
Has anyone used Uncommon Maths as a solution to this problem?
Can anybody confirm that this performance problem has been solved in JDK 6?
This question is related to
java
performance
security
random
entropy
My experience has been only with slow initialization of the PRNG, not with generation of random data after that. Try a more eager initialization strategy. Since they're expensive to create, treat it like a singleton and reuse the same instance. If there's too much thread contention for one instance, pool them or make them thread-local.
Don't compromise on random number generation. A weakness there compromises all of your security.
I don't see a lot of COTS atomic-decay–based generators, but there are several plans out there for them, if you really need a lot of random data. One site that always has interesting things to look at, including HotBits, is John Walker's Fourmilab.
Many Linux distros (mostly Debian-based) configure OpenJDK to use /dev/random for entropy.
/dev/random is by definition slow (and can even block).
From here you have two options on how to unblock it:
Option 1, Improve entropy
To get more entropy into /dev/random, try the haveged daemon. It's a daemon that continuously collects HAVEGE entropy, and works also in a virtualized environment because it doesn't require any special hardware, only the CPU itself and a clock.
On Ubuntu/Debian:
apt-get install haveged
update-rc.d haveged defaults
service haveged start
On RHEL/CentOS:
yum install haveged
systemctl enable haveged
systemctl start haveged
Option 2. Reduce randomness requirements
If for some reason the solution above doesn't help or you don't care about cryptographically strong randomness, you can switch to /dev/urandom instead, which is guaranteed not to block.
To do it globally, edit the file jre/lib/security/java.security in your default Java installation to use /dev/urandom (due to another bug it needs to be specified as /dev/./urandom).
Like this:
#securerandom.source=file:/dev/random
securerandom.source=file:/dev/./urandom
Then you won't ever have to specify it on the command line.
Note: If you do cryptography, you need good entropy. Case in point - android PRNG issue reduced the security of Bitcoin wallets.
If you want truly "cryptographically strong" randomness, then you need a strong entropy source. /dev/random is slow because it has to wait for system events to gather entropy (disk reads, network packets, mouse movement, key presses, etc.).
A faster solution is a hardware random number generator. You may already have one built-in to your motherboard; check out the hw_random documentation for instructions on figuring out if you have it, and how to use it. The rng-tools package includes a daemon which will feed hardware generated entropy into /dev/random.
If a HRNG is not available on your system, and you are willing to sacrifice entropy strength for performance, you will want to seed a good PRNG with data from /dev/random, and let the PRNG do the bulk of the work. There are several NIST-approved PRNG's listed in SP800-90 which are straightforward to implement.
You should be able to select the faster-but-slightly-less-secure /dev/urandom on Linux using:
-Djava.security.egd=file:/dev/urandom
However, this doesn't work with Java 5 and later (Java Bug 6202721). The suggested work-around is to use:
-Djava.security.egd=file:/dev/./urandom
(note the extra /./)
It sounds like you should be clearer about your RNG requirements. The strongest cryptographic RNG requirement (as I understand it) would be that even if you know the algorithm used to generate them, and you know all previously generated random numbers, you could not get any useful information about any of the random numbers generated in the future, without spending an impractical amount of computing power.
If you don't need this full guarantee of randomness then there are probably appropriate performance tradeoffs. I would tend to agree with Dan Dyer's response about AESCounterRNG from Uncommons-Maths, or Fortuna (one of its authors is Bruce Schneier, an expert in cryptography). I've never used either but the ideas appear reputable at first glance.
I would think that if you could generate an initial random seed periodically (e.g. once per day or hour or whatever), you could use a fast stream cipher to generate random numbers from successive chunks of the stream (if the stream cipher uses XOR then just pass in a stream of nulls or grab the XOR bits directly). ECRYPT's eStream project has lots of good information including performance benchmarks. This wouldn't maintain entropy between the points in time that you replenish it, so if someone knew one of the random numbers and the algorithm you used, technically it might be possible, with a lot of computing power, to break the stream cipher and guess its internal state to be able to predict future random numbers. But you'd have to decide whether that risk and its consequences are sufficient to justify the cost of maintaining entropy.
Edit: here's some cryptographic course notes on RNG I found on the 'net that look very relevant to this topic.
Something else to look at is the property securerandom.source in file lib/security/java.security
There may be a performance benefit to using /dev/urandom rather than /dev/random. Remember that if the quality of the random numbers is important, don't make a compromise which breaks security.
It sounds like you should be clearer about your RNG requirements. The strongest cryptographic RNG requirement (as I understand it) would be that even if you know the algorithm used to generate them, and you know all previously generated random numbers, you could not get any useful information about any of the random numbers generated in the future, without spending an impractical amount of computing power.
If you don't need this full guarantee of randomness then there are probably appropriate performance tradeoffs. I would tend to agree with Dan Dyer's response about AESCounterRNG from Uncommons-Maths, or Fortuna (one of its authors is Bruce Schneier, an expert in cryptography). I've never used either but the ideas appear reputable at first glance.
I would think that if you could generate an initial random seed periodically (e.g. once per day or hour or whatever), you could use a fast stream cipher to generate random numbers from successive chunks of the stream (if the stream cipher uses XOR then just pass in a stream of nulls or grab the XOR bits directly). ECRYPT's eStream project has lots of good information including performance benchmarks. This wouldn't maintain entropy between the points in time that you replenish it, so if someone knew one of the random numbers and the algorithm you used, technically it might be possible, with a lot of computing power, to break the stream cipher and guess its internal state to be able to predict future random numbers. But you'd have to decide whether that risk and its consequences are sufficient to justify the cost of maintaining entropy.
Edit: here's some cryptographic course notes on RNG I found on the 'net that look very relevant to this topic.
There is a tool (on Ubuntu at least) that will feed artificial randomness into your system. The command is simply:
rngd -r /dev/urandom
and you may need a sudo at the front. If you don't have rng-tools package, you will need to install it. I tried this, and it definitely helped me!
Source: matt vs world
If your hardware supports it try using Java RdRand Utility of which I'm the author.
Its based on Intel's RDRAND instruction and is about 10 times faster than SecureRandom and no bandwidth issues for large volume implementation.
Note that this implementation only works on those CPU's that provide the instruction (i.e. when the rdrand processor flag is set). You need to explicitly instantiate it through the RdRandRandom() constructor; no specific Provider has been implemented.
Using Java 8, I found that on Linux calling SecureRandom.getInstanceStrong() would give me the NativePRNGBlocking algorithm. This would often block for many seconds to generate a few bytes of salt.
I switched to explicitly asking for NativePRNGNonBlocking instead, and as expected from the name, it no longer blocked. I have no idea what the security implications of this are. Presumably the non-blocking version can't guarantee the amount of entropy being used.
Update: Ok, I found this excellent explanation.
In a nutshell, to avoid blocking, use new SecureRandom(). This uses /dev/urandom, which doesn't block and is basically as secure as /dev/random. From the post: "The only time you would want to call /dev/random is when the machine is first booting, and entropy has not yet accumulated".
SecureRandom.getInstanceStrong() gives you the absolute strongest RNG, but it's only safe to use in situations where a bunch of blocking won't effect you.
According to the documentation, the different algorithms used by SecureRandom are, in order of preference:
Since you asked about Linux, I'm ignoring the Windows implementation, and also SunPKCS11 which is only really available on Solaris, unless you installed it yourself — and then you wouldn't be asking this question.
According to those same documentation, what these algorithms use are
SHA1PRNG
Initial seeding is currently done via a combination of system attributes and the java.security entropy gathering device.
NativePRNG
nextBytes() uses /dev/urandom
generateSeed() uses /dev/random
NativePRNGBlocking
nextBytes() and generateSeed() use /dev/random
NativePRNGNonBlocking
nextBytes() and generateSeed() use /dev/urandom
That means if you use SecureRandom random = new SecureRandom(), it goes down that list until it finds one that works, which will typically be NativePRNG. And that means that it seeds itself from /dev/random (or uses that if you explicitly generate a seed), then uses /dev/urandom for getting the next bytes, ints, double, booleans, what-have-yous.
Since /dev/random is blocking (it blocks until it has enough entropy in the entropy pool), that may impede performance.
One solution to that is using something like haveged to generate enough entropy, another solution is using /dev/urandom instead. While you could set that for the entire jvm, a better solution is doing it for this specific instance of SecureRandom, by using SecureRandom random = SecureRandom.getInstance("NativePRNGNonBlocking"). Note that that method can throw a NoSuchAlgorithmException if NativePRNGNonBlocking is unavailable, so be prepared to fallback to the default.
SecureRandom random;
try {
random = SecureRandom.getInstance("NativePRNGNonBlocking");
} catch (NoSuchAlgorithmException nsae) {
random = new SecureRandom();
}
Also note that on other *nix systems, /dev/urandom may behave differently.
/dev/urandom random enough?Conventional wisdom has it that only /dev/random is random enough. However, some voices differ. In "The Right Way to Use SecureRandom" and "Myths about /dev/urandom", it is argued that /dev/urandom/ is just as good.
The users over on the Information Security stack agree with that. Basically, if you have to ask, /dev/urandom is fine for your purpose.
I faced same issue. After some Googling with the right search terms, I came across this nice article on DigitalOcean.
I am merely quoting the relevant part from the article here.
Based on the HAVEGE principle, and previously based on its associated library, haveged allows generating randomness based on variations in code execution time on a processor. Since it's nearly impossible for one piece of code to take the same exact time to execute, even in the same environment on the same hardware, the timing of running a single or multiple programs should be suitable to seed a random source. The haveged implementation seeds your system's random source (usually /dev/random) using differences in your processor's time stamp counter (TSC) after executing a loop repeatedly
Follow the steps in this article. https://www.digitalocean.com/community/tutorials/how-to-setup-additional-entropy-for-cloud-servers-using-haveged
I have posted it here
I haven't hit against this problem myself, but I'd spawn a thread at program start which immediately tries to generate a seed, then dies. The method which you call for randoms will join to that thread if it is alive so the first call only blocks if it occurs very early in program execution.
The problem you referenced about /dev/random is not with the SecureRandom algorithm, but with the source of randomness that it uses. The two are orthogonal. You should figure out which one of the two is slowing you down.
Uncommon Maths page that you linked explicitly mentions that they are not addressing the source of randomness.
You can try different JCE providers, such as BouncyCastle, to see if their implementation of SecureRandom is faster.
A brief search also reveals Linux patches that replace the default implementation with Fortuna. I don't know much more about this, but you're welcome to investigate.
I should also mention that while it's very dangerous to use a badly implemented SecureRandom algorithm and/or randomness source, you can roll your own JCE Provider with a custom implementation of SecureRandomSpi. You will need to go through a process with Sun to get your provider signed, but it's actually pretty straightforward; they just need you to fax them a form stating that you're aware of the US export restrictions on crypto libraries.
I had a similar problem with calls to SecureRandom blocking for about 25 seconds at a time on a headless Debian server. I installed the haveged daemon to ensure /dev/random is kept topped up, on headless servers you need something like this to generate the required entropy.
My calls to SecureRandom now perhaps take milliseconds.
Use the secure random as initialization source for a recurrent algorithm; you could use then a Mersenne twister for the bulk work instead of the one in UncommonMath, which has been around for a while and proven better than other prng
http://en.wikipedia.org/wiki/Mersenne_twister
Make sure to refresh now and then the secure random used for the initialization, for example you could have one secure random generated per client, using one mersenne twister pseudo random generator per client, obtaining a high enough degree of randomization
On Linux, the default implementation for SecureRandom is NativePRNG (source code here), which tends to be very slow. On Windows, the default is SHA1PRNG, which as others pointed out you can also use on Linux if you specify it explicitly.
NativePRNG differs from SHA1PRNG and Uncommons Maths' AESCounterRNG in that it continuously receives entropy from the operating system (by reading from /dev/urandom). The other PRNGs do not acquire any additional entropy after seeding.
AESCounterRNG is about 10x faster than SHA1PRNG, which IIRC is itself two or three times faster than NativePRNG.
If you need a faster PRNG that acquires entropy after initialization, see if you can find a Java implementation of Fortuna. The core PRNG of a Fortuna implementation is identical to that used by AESCounterRNG, but there is also a sophisticated system of entropy pooling and automatic reseeding.
Source: Stackoverflow.com