array to generate words

[Daniel Dyer]

Daniel Dyer wrote


If I remember correctly, the SecureRandom potentially uses a lot of time
during initialization to "collect entropi". Can you possibly state
whether or not generator initialization is included in the factor 8 you
mention above?

That's a good point and something I should have considered. My benchmark
does not include the time taken to instantiate the SecureRandom object,
but I guess it's possible that the entropy gathering is deferred until the
first request is made (I haven't looked at the SecureRandom source). I'll
try it again later but make a few requests before I start timing and see
what the difference is. The benchmark generates 1 million random ints, 1
million random doubles and 1 million Gaussians. For SecureRandom it takes
less than 4 seconds under Windows and about 30 seconds under Linux on my
laptop. If the SecureRandom is getting its entropy from /dev/random it
shouldn't take 26 seconds. My guess, and that's all it is, is that it
something to do with the SHA-1 implementation in the Linux version of
JCE. I have written an RNG that uses the AES block cipher and seeds
itself from /dev/random and it completes the benchmark in under 2 seconds
under Linux.

Dan.

 

[Daniel Dyer]

Daniel Dyer wrote:

[me:]

I have produced my own direct Java port of the original C

Blimey, that was quick ;-)

I meant previously

The C code, and therefore my Java port also, is a whole bunch of magic
numbers and bit manipulations. I've no idea how it actually works.

How does using something like RC4 compare for speed/quality ?

I've used AES. The quality is the same according to Diehard, but the
Mersenne Twister is about 3 times faster. The AES implementation is still
twice as fast as SecureRandom though. I read somewhere that a non-linear
generator like AES is preferable to a linear generator like the Mersenne
Twister for certain types of simulation, though I don't know the details.

Dan.

 

[Chris Uppal]

Daniel Dyer wrote:

[me:]

I have produced my own direct Java port of the original C

Blimey, that was quick ;-)

and the
peformance is quite impressive even though I have made no attempt to
optimise it. The throughput is better than java.util.Random and the
output is much more random according to the Diehard tests.

How does using something like RC4 compare for speed/quality ?

-- chris

 

[Filip Larsen]

Daniel Dyer wrote

My benchmark
does not include the time taken to instantiate the SecureRandom object,
but I guess it's possible that the entropy gathering is deferred until the
first request is made (I haven't looked at the SecureRandom source). I'll
try it again later but make a few requests before I start timing and see
what the difference is. The benchmark generates 1 million random ints, 1
million random doubles and 1 million Gaussians. For SecureRandom it takes
less than 4 seconds under Windows and about 30 seconds under Linux on my
laptop.

Doing that test with Java 1.4.2, I get the relative speed of Random to
the SecureRandom (Sun provider) at around 3 to 8 depending on OS and
whether -server or -client is used. Best was server on Windows where
SecureRandom ran the test only 3 times as slow as Random (3062 ms vs.
1047 ms). Worst was client on Windows with a factor 8 (5078 ms vs. 625
ms). In the Linux test the ratios were between 6.5 (server) to 8
(client). The Linux hardware was different but the test ran in times
comparable to the Windows test. Instantiation and warm-up of Sun's
SecureRandom took around 200-800 ms in all cases.

So my guess would be that the 30 seconds you see on Linux must be an
issue not related to the actual generation of numbers. Perhaps the
generator is not seeding from /dev/random or perhaps its a different
provider with a non-performing implementation?


Regards,

 

[britishdan]

Filip, it seems you are right. Previously I was not specifying which
algorithm or provider to use. When I re-run the tests specifying to
use the "SHA1PRNG" algorithm with the Sun provider, I get the same
results as you on both Windows and Linux, using Java 1.5.0_06.

I checked what implementation was being used on Linux by default and it
is still the Sun provider but it uses an algorithm called "NativePRNG",
which appears to be much slower than the non-native default. So my
previous advice about performance on Linux should be qualified with
this information.

SecureRandom is still slow, even on Windows, it's just not necessarily
as slow as I stated.

 

[Daniel Dyer]

Filip, it seems you are right. Previously I was not specifying which
algorithm or provider to use. When I re-run the tests specifying to
use the "SHA1PRNG" algorithm with the Sun provider, I get the same
results as you on both Windows and Linux, using Java 1.5.0_06.

I checked what implementation was being used on Linux by default and it
is still the Sun provider but it uses an algorithm called "NativePRNG",
which appears to be much slower than the non-native default. So my
previous advice about performance on Linux should be qualified with
this information.

SecureRandom is still slow, even on Windows, it's just not necessarily
as slow as I stated.

Just to avoid any confusion, this post is from me. I went looking for the
thread on Google Groups and posted the reply on there. I thought it would
be clever enough to use the name I gave it in the "From" field.

Dan.

 

[Oliver Wong]

Searching for:
"mersenne twister" java
produces lots of promising-looking hits. (Not limited to implementations
of
that particular PRNG)

Note thought that while Mersenne Twister produces a nice sequence of
random numbers for simulations, it is not cryptographically secure; that is,
an attacker can easily[*] recognize an MT-generated sequence, and predict
the next elements.

Use MT for games and simulations, but not for encryption, passwords,
etc.

- Oliver

[*] Where "easily" means "relative to random number generators which ARE
considered cryptographically secure".

 

[Chris Uppal]

Note thought that while Mersenne Twister produces a nice sequence of
random numbers for simulations, it is not cryptographically secure; that
is, an attacker can easily[*] recognize an MT-generated sequence, and
predict the next elements.

That why I (idly) asked Daniel if he'd tested the performance of RC4 used as a
PRNG. It should be pretty fast, but I haven't got around to measuring it
myself. OTOH, I don't know how well RC4 approximates to "random" -- it could
be very non-random but still secure (e.g. if it doubled-up every output byte
;-)

-- chris

 

[Daniel Dyer]

Searching for:
"mersenne twister" java
produces lots of promising-looking hits. (Not limited to
implementations of
that particular PRNG)

Note thought that while Mersenne Twister produces a nice sequence of
random numbers for simulations, it is not cryptographically secure; that
is, an attacker can easily[*] recognize an MT-generated sequence, and
predict the next elements.

Use MT for games and simulations, but not for encryption, passwords,
etc.

Indeed. Away from work one of my interests is evolutionary algorithms.
The Mersenne Twister is excellent for these because of its statistical
qualities and blinding speed. At work I'm mostly involved in the online
gambling industry. We don't use algorithms like the Mersenne Twister for
these for precisely the reason you mention. Although it's very unlikely,
if an attacker could observe all of the random output of the RNG for a
long enough sequence, they could relatively easily reverse engineer the
seed and predict all future output of the RNG, thus losing our clients
lots of money.

Dan.