SecureRandom generates statictically biased seeds on certain platforms.

SecureRandom generates random seeds by sampling the machine load.
It does so by counting the number of times a thread manages to yield
while another thread sleeps.

The sleep time is calculated so that the loop count would be ~55000.

Statistical tests (NIST's FIPS 140-1 and DieHard) show that the random seeds
are statistically biased on high-end platforms (where the sleep time is too
short) and on low-end platforms (where the sleep time is too long).

This could considerably lower the security of algorithms that need random
seeding (such as DH, DSA and RSA).

Here's an update on my experiences with secure random:

1.

I wrote a program that samples the computer activity level
by counting loops in a certain period of time (in this case
one second).
This is the same thing that secure random does.
After collecting a bunch of samples I calculated
the standard deviation.
The purpose of the experiment was to put different instructions
inside the loop and find the instruction that gives the most
variance. This was performed on my NT station.

These are my results:

nop 5141
yield 7611
sleep(0) 9349
synchronized(this) 17433
wait(1) 2 (!)

As you can see, the yield itself is not crucial to the
randomness.


2.

I tried to write a version of SecureRandom that uses
two threads "ping-ponging" between them with wait-notify,
but it didn't work: the operation took so long that the VM
only managed to perform a relatively small number of them
in one seconds and the variance was very low.

3.

I hypothesized that sampling the level of activity over longer
periods of time would make the randomness worse. This is because
averaging the entropy over a period of time may eliminate the
variance. This proves to be correct (this is why SecureRandom
behaves very badly on slow machines).

I think I have a solution to this problem: by sampling over a
short period of time (250 milli) I get the count. I then run
it through a permutation that gives me a pseudo random (hard coded
p-box) number. I collect 4 of these numbers (1 second) and xor
them together.

This improves the randomness of the result greatly (on slow
machines) because xor (unlike addition) is non-linear and
thus does not eliminate variance.

4.

I wanted to make sure that this p-box algorithm doesn't fool the
fips-140 test into giving good result even though the entropy
is low. I inserted a statistical bias (by limiting the counter
to a smaller range) and found that the test will fail if
I limit the variance to under 76% it's optimum. (Please email
me for further explanation of this experiment).

This convinced me that the p-box doesn't artificially improve
the test results, rather it actually improves the entropy.

5.

I wrote a new algorithm using the previous conclusions, and
ran the test on as many platforms I could find. Here are the
results:

Windows (NT, 95) using JDK 1.1.4, 1.2 with and w/o Symantec JIT:
PASSED

Solaris on USparc, JDK 1.1.3, 1.2 with and w/o JIT:
PASSED

Netscape Communicator 4.04:
PASSED

MS Internet Explorer 4.0 (ugh!)
PASSED

Borland JBuilder with AppAccelerator:
PASSED

JavaOS on JavaStation:
PASSED

JavaPC on Pentium 200:
FAILED

In addition to the previous points, these will be added to furthur improve the randomness of the seed:

1.

I have written a module that collects entropy from the
system. Most of these are invariant per user, and some
invariant per session. This will not help
SecureRandom pass the fips test (because these sources
do not change throughout the test) but I feel it would
make the seed generation a little more secure.
These are some of the sources I use:

System time and date
System properties (e.g. classpath, username, tempdir)
Filenames from the temp directory
AWT hashes (e.g. SunToolkit changes every session, because
it includes the OS window handle)

2.

I made SecureRandom run in the background (daemon thread).
It starts calculating random data as soon as it loads.
This will allow the rest of the system to continue running
while the random seed is being generated. I believe this would
improve the quality of the randomness because there will be
more system activity during that time.