Re: [Bug]? -iR <num_hosts> on windows XP generates duplicate targets

[doug () hcsw org]

On Wed, Apr 30, 2008 at 09:44:42PM +0000 or thereabouts, Brandon Enright wrote:
> Incidentally, it is these short cycles in the lower bits that often
> defeat poorly implemented LCGs.  Storm (the worm) is a recent example
> of this LCG cycle in the lower bits problem.

Heh ya.. Worms authors frequently screw this up. Remember slammer/sapphire?

http://www.caida.org/publications/papers/2003/sapphire/sapphire.html

Also there was an interesting talk at CanSecWest 08 about worms skewing
PRNGs deliberately so as to target specific IP blocks (like specific
countries or companies):

Malicious Cryptography - Fr?d?ric Raynal, Sogeti/Cap-Gemini

(can't seem to find slides online anywhere, sorry)

> Finally, one thing that hasn't been addressed in this patch is that on
> *nix, Nmap first tries "arandom" and then "urandom" before trying
> "random".

I didn't notive that Nmap falls back on /dev/random. I agree, Nmap should never
use this device for performance reasons. In addition, this could be highly
undesirable because every time you run Nmap you could deplete your randomness
pool. Even falling back on rand(3) would be preferable IMO. Nmap does NOT need
cryptographic random numbers (at least for -iR). It is enough that they are
uniformly distributed and always have a large period.

Embedding a PRNG into Nmap might be a good idea for portability reasons (but
no other reasons). Note that this will not give a significant performance boost
because Nmap Does The Right Thing(tm) and takes (by default) 2048 bytes of random
data for every read() syscall from /dev/arandom instead of the more naive approach
of read()ing every time you need a random number. This buffer size could be
increased to arbitrarily amortise down the cost of the open(), read(), and close()
syscalls required for the use of kernel PRNGs.

Doug

PS The /dev/random point could be moot anyways. Does anybody know of a unix
with /dev/random but no /dev/arandom or /dev/urandom?

PPS /dev/random is (I think) currently a linuxism anyways and will not
work on for example OpenBSD (instead use /dev/srandom for *s*trong random
numbers).

PPPS If you're looking for a good PRNG, ISSAC is a lesser known one but
is actually an extremely good algorithm:

http://burtleburtle.net/bob/rand/isaacafa.html

Compared to ISSAC, "RC4 is three times slower, more biased, has a shorter
minimum and average cycle length..". (BTW OpenBSD /dev/arandom uses this
*a*lleged RC4.) Also, unlike Mersenne Twister (which is a linear recursion)
ISSAC is believed to be cryptographically secure (like (A)RC4). Full disclosure:
An implementation of mine is mirrored on the ISSAC page so obviously take my
opinion with a grain of salt.

PPPPS Bet you've never seen this many post scriptums before. :)

Attachment: signature.asc
Description: Digital signature

_______________________________________________
Sent through the nmap-dev mailing list
http://cgi.insecure.org/mailman/listinfo/nmap-dev
Archived at http://SecLists.Org