How to deal with a slow SecureRandom generator

Question

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

User · Answer

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.

User · Answer

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

User · Answer

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

User · Answer

If you want true random data  then unfortunately you have to wait for it  This includes the seed for a SecureRandom PRNG  Uncommon Maths can t gather true random data any faster than SecureRandom  although it can connect to the internet to download seed data from a particular website  My guess is that this is unlikely to be faster than  dev random where that s available   If you want a PRNG  do something like this   SecureRandom getInstance  SHA1PRNG      What strings are supported depends on the SecureRandom SPI provider  but you can enumerate them using Security getProviders   and Provider getService     Sun is fond of SHA1PRNG  so it s widely available  It isn t especially fast as PRNGs go  but PRNGs will just be crunching numbers  not blocking for physical measurement of entropy   The exception is that if you don t call setSeed   before getting data  then the PRNG will seed itself once the first time you call next   or nextBytes    It will usually do this using a fairly small amount of true random data from the system  This call may block  but will make your source of random numbers far more secure than any variant of  hash the current time together with the PID  add 27  and hope for the best   If all you need is random numbers for a game  though  or if you want the stream to be repeatable in future using the same seed for testing purposes  an insecure seed is still useful

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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    Improve entropy  or Reduce randomness requirements    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

User · Answer

According to the documentation  the different algorithms used by SecureRandom are  in order of preference   On most  NIX systems  NativePRNG SHA1PRNG NativePRNGBlocking NativePRNGNonBlocking   On Windows systems  SHA1PRNG Windows-PRNG    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  quot NativePRNGNonBlocking quot    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  quot NativePRNGNonBlocking quot      catch  NoSuchAlgorithmException nsae        random   new SecureRandom       Also note that on other  nix systems   dev urandom may behave differently   Is  dev urandom random enough  Conventional wisdom has it that only  dev random is random enough  However  some voices differ  In  quot The Right Way to Use SecureRandom quot  and  quot Myths about  dev urandom quot   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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

I faced same issue  After some Googling with the right search terms  I came across this nice article on DigitalOcean    haveged is a potential solution without compromising on security   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   How to install haveged  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

User · Answer

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

User · Answer

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

User · Answer

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

[java] How to deal with a slow SecureRandom generator?

Examples related to java

Examples related to performance

Examples related to security

Examples related to random

Examples related to entropy