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

[Brandon Enright <bmenrigh () ucsd edu>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Wed, 23 Apr 2008 20:05:39 -0700 or thereabouts Fyodor
<fyodor () insecure org> wrote:

> On Thu, Apr 24, 2008 at 01:54:45AM +0000, Brandon Enright wrote:
> > The problem here is that the rng is being seeded with time every
> > time it is called.
>
> I don't think it is.  Here is the code with more context:
>
>       if (badrandomwarning == 0) {
>       badrandomwarning++;
>       /*      error("WARNING: your system apparently does not
> offer /dev/urandom or /dev/random.  Reverting to less secure
> version."); */ /* Seed our random generator */
>       gettimeofday(&tv, NULL);
>       srand((tv.tv_sec ^ tv.tv_usec) ^ getpid());
>       }
>
> badrandomwarning is a static variable.  So this block should only be
> called once.  And when I uncomment the error message, I indeed only
> see it printed once.

Yep, I was too hasty in my glancing through code.

> HOWEVER, removing the srand() does seem to fix the issue on Windows.
> But I'm not really included to do that unless we have to, because I'd
> rather the library not require that of callers.
>
> I just tried removing the /dev/random stuff on Linux, and Linux still
> seems to generate good IPs using the same srand()/rand() code.  So it
> may be something specific to Windows or maybe their srand()/rand()
> implementation.

It seems that Visual Studio uses a RAND_MAX of 32767 while GCC uses a
RAND_MAX of 2147483647.

> I've only had a few minutes to look at this, but it isn't clear what
> the problem is.

Digging deeper into Windows documentation on this turns up:

Remarks
The rand function returns a pseudorandom integer in the range 0 to RAND_MAX (32767). Use the srand function to seed the 
pseudorandom-number generator before calling rand.

(http://msdn2.microsoft.com/en-us/library/398ax69y(VS.80).aspx)

That max suggests to me that rand() on Windows only has 2^15 states
and that the cycle we are seeing comes from calling more than 2^15
times.

One way to check is to store the first call to rand() in a static var
and then check how many calls it takes before the same value is
returned.  I suspect that if we are just running into a very short
cycle problem then we'll also run into the even/odd alternation issue.

even/odd alternation is devastating when trying to generate reasonably
random IPs.

We may want to do a #ifdef WIN32 and use rand_s().

> Cheers,
> -F

If anyone has documentation on what LCG Visual Studio is using I'd love
to see it.

It's really pathetic that we're in 2008 and compilers and operating
systems still don't provide good psuedo-random functions like the
Mersenne Twister.

Brandon

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (GNU/Linux)

iEYEARECAAYFAkgP/5cACgkQqaGPzAsl94KlZACgw16JGtB9pgwSBFZU4NjHFGCs
irAAn1mjM9UQvOYc8waatkCP1M46GHgw
=n6bh
-----END PGP SIGNATURE-----

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