mailing list archives
PRNG benchmark results and proposal
From: Brandon Enright <bmenrigh () ucsd edu>
Date: Mon, 5 May 2008 00:45:05 +0000
-----BEGIN PGP SIGNED MESSAGE-----
Rather than go off coding without a solid idea of the strengths and
weakness of various PRNG options, Fyodor suggested that I benchmark our
I went ahead and wrote a little stand-alone C application to test each
PRNG option we've come up with:
* rand() (using a byte at a time like on Windows)
* rand() (using a short at a time like on *nix)
For each option, I tested how long it takes to generate 0x0FFFFFFF
bytes (256 megs). I used the same interface Nmap uses with
get_random_bytes() using a 2kb cache and get_random_u32() to get 4
bytes at a time. This helps amortize the cost of opening /dev/urandom
but is actually slower for most of the other options.
I've run each PRNG 3 times on two different computers. The first group
of 3 times is a fast Pentium 4 (x86). The second group of three is a
_very_ fast Xeon (x86_64).
Quite surprisingly, /dev/urandom is at least as slow as OpenSSL. The
calls to rand() are fast but as discussed in a previous thread, can be
of very poor quality. DNet's ARC4 PRNG is by far the fastest option
and offers arguably as high a quality random stream as /dev/urandom or
So, I propose we change all random number generation to use DNet's PRNG
at all times. It is fast, portable C, already included in Nmap, and
quite a bit higher quality than we actually /need/.
Assuming this is a good choice, the hard part is in deciding /how/ we
include it. The caching provided by the current get_random_bytes()
routine is unnecessary overhead if we use dnet. Also, DNet's rand.c
library provides nearly the exact same API as Nmap's nbase_rnd.c but
uses different typedef'd named sizes (u32 vs uint32_t for example).
Also, we probably don't want to cause nbase to depend on dnet.
Here's how I suggest we precede:
* We re-write rand.c to the nbase coding style, typedef'd names, and
nbase_rnd API (this is a nearly 1-to-1 translation in all regards)
while eliminating unneeded functionality (adding entropy, random
* Remove rand.c from dnet; our stripped-down version of dnet doesn't
actually make use of it anyways
* All of Nmap's existing calls into nbase_rnd can be left alone, all
calls to rand() be adapted to new nbase_rnd implementation
The primary reason for the proposed re-write is not to side-step DNet's
BSD license. If we wrap rand.c with nbase_rnd we'll have a layer of
redundancy that will add inefficiency. It will also add a dependency
to nbase that it doesn't currently have. The re-write is short and
simple so the benefit will outweigh the cost of the re-write.
I'd like someone to weigh in on BSD/GPL licensing conflicts before I
proceed to either use rand.c or re-write rand.c for nbase_rnd.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (GNU/Linux)
-----END PGP SIGNATURE-----
Sent through the nmap-dev mailing list
Archived at http://SecLists.Org
- PRNG benchmark results and proposal Brandon Enright (May 05)