Various Random things (Was: Java 8 RFC 7189139: BigInteger's staticRandom field can be a source of bottlenecks)

[Bradford Wetmore]

Sorry, I haven't been following the Random discussions until now, I 
haven't been subscribed to core-lib-dev in a while.

I was specifically asked to comment on Brian's proposed change.

Paul pointed out something Bill Pugh wrote:

 > Right, see here:
 >
 > 
http://mail.openjdk.java.net/pipermail/core-libs-dev/2012-January/009176.html
 >
 > "I spent some time looking at the implementation of SecureRandom and
 > of sun.security.provider.NativePRNG. The implementation of NativePRNG
 > uses a static singleton to perform all of the work, so that looked
 > like the concurrency bottleneck. But when I rewrote that class, it
 > turns out that even removing all of the Java level concurrency
 > bottlenecks, we still can't generate concurrent secure random
 > numbers, because the NativePRNG reads /dev/urandom for each byte, and
 > that is inherently sequential and is the bottleneck to the entire
 > process of generating secure random numbers."

What Bill Pugh wrote is correct for NativePRNG.

"new SecureRandom()" chooses its implementation based on the most 
preferred provider.  Different OS's have different preferred 
implementations:

     Solaris (x86/sparc):  PKCS11 (from the SunPKCS11 provider)
     Linux:                NativePRNG
     MacOS:                NativePRNG
     Windows:              SHA1PRNG

PKCS11 probably has a similar OS bottleneck.  SHA1PRNG doesn't go to 
native MSCAPI after the initial seeding of the class, so on windows you 
would just have Java level contention.

A bit of background:  SHA1PRNG is the only implementation that is 
available on all platforms.  How the class is initially seeded depends 
on some additional steps not mentioned in the threads I've seen to date 
(getSystemEntropy), and NativeSeedGenerators from the underlying OS:

     src/share/classes/sun/security/provider/SecureRandom.java
     src/share/classes/sun/security/provider/SeedGenerator.java
     src/*/classes/sun/security/provder/NativeSeedGenerator.java

Bill also wrote in that email:

 > add the following method to BigInteger
 > public boolean isProbablePrime(int certainty, Random end) ,
 > which allows primality testing with arbitrary Random objects.
 > In many cases, using a well seeded normal Random object will work
 > just fine, and this will give users the ability to provide their own
 > Random objects

This sounds like a very good solution to me.  That way someone can 
decide whether they want to take the hit with SecureRandom, or if Random 
is good enough.

Paul Sandoz wrote:

 > I don't know about the PRNG requirements for Miller-Rabin but the
 > changes to TLR in review might be a possible substitute for SR in
 > this case, since TLR will be updated to use the same PRNG algorithm
 > as SplittableRandom, which passes DieHarder tests.  Otherwise, i
 > think we may just be stuck with SR.

In my brief read of the Miller-Rabin tests, it just selects several 
random values to use for guessing whether another number selected by a 
different random number generator is prime or not.  Given initial seed 
values (i.e. one not set via new Random(seed) constructor), manipulating 
the Random implementation to ensure a steady stream of strong liars 
seems rather difficult.

In addition we run a secondary test which reduces that attack surface 
(LucasLehmer).

So offhand, I wouldn't commit to saying if SecureRandom is necessary or 
not, but it wouldn't surprise me.

But I think Bill's suggestion is worth pursuing.

Various comments:

Paul Sandoz wrote:

 > Perhaps it would also allow us to deprecate Random in a future JDK?

SecureRandom is a subclass of Random, so I'm wondering how it will be 
perceived to have the "secure" version based on a deprecated base class. 
  I know the underlying implementations are *COMPLETELY* different, but 
I've been working with this code for a while now.

 > Perhaps there could be factory methods to obtain a PRNG based on
 > generator properties rather than picking a specific class.

There is an RFE for something like that (similar to 
SecureRandom.getInstance()), but I can't find it at the moment.

Martin Buchholz wrote:

 > full support for a variety of generators and distributions is a
 > career path)

Yes, I'm hoping to add some more crypto PRNGs, ala NIST Special 
Publication 800-90A in JDK 9.

Brad