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

[Brandon Enright <bmenrigh () ucsd edu>]

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

On Thu, 01 May 2008 21:33:18 -0500 or thereabouts Kris Katterjohn
<katterjohn () gmail com> wrote:
> Brandon Enright wrote:
> > 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".  If a box doesn't offer [au]random but does offer random
> > Nmap will block -- /dev/random doesn't provide randomness as fast
> > as Nmap uses it.  The use of /dev/random should be dropped in favor
> > of falling back on rand() or in the future, OpenSSL.
>
> Per your suggestion of OpenSSL, this is a 4.20ALPHA4 CHANGELOG entry:
>
> o Nmap no longer gets random numbers from OpenSSL when it is available
>   because that turned out to be slower than Nmap's other methods
>   (e.g. /dev/urandom on Linux, /dev/arandom on OpenBSD, etc.).  Thanks
>   to Marek Majkowski for reporting the problem.

Yeah, I'd forgotten about this.  Marek is right that OpenSSL will
produce random numbers very slowly compared to a PRNG.  Cryptographic
quality random sequences require both more computation and outside
input (entropy mixing).

> WRT to the /dev/random hanging, I see what you mean!  I edited
> nbase_rnd.c and Nmap immediately hangs and strace confirms it's from a
> read(/dev/random).

I did the same.  I was not able to run -iR 5000 even with hours of
waiting.  I love Linux but this really is the fault of the kernel
developers not recognizing the problem or accepting patches to
"fix" /dev/random.  Yarrow, Fortuna, and other RNG schemes have been
coded up but haven't been integrated.

> But what are the odds of you mentioning this hanging so soon after
> this (bit hostile) email[1] which mentions the exact behavior Nmap
> exhibits when I only use /dev/random?

I followed your link because I don't recall that email but I don't think
you got the link correct since I don't see any mention of /dev/random
and the "... -iR 10000 .. (No response)" on the page is probably some
other issue.

> Apparently his Linux box
> doesn't have urandom (or it's a very strange coincidence since I've
> never had Nmap just hang immediately for any other reason..)

Nmap gets a few random numbers for sequence numbers and such.  Have you
tested the effect of /dev/random on a regular scan?  /dev/random should
have 512 bytes available at the start of the scan which should last a
while.

> Given the options of /dev/random, rand() and OpenSSL, it looks like
> rand() may be the answer since random hangs and OpenSSL was slow.

There is a compromise that I think is a better option than rand() that
I'll comment on below.

> Good find.
>
> > Brandon
>
> Thanks,
> Kris Katterjohn
>
> [1] http://seclists.org/nmap-dev/2008/q2/0182.html

Okay, here's how I see -iR being used:

1) Someone wants to scan a few random-ish hosts and doesn't care (much)
about how the hosts are chosen

2) Someone expects random to be random and wants quality scan samples
of the Internet

3) Someone wants a list of random IPs for some other use and knows
Nmap is probably the best/easiest/only tool out there to spit out N
random IPs via -iR and -sL

For user 1 it doesn't matter what we use because it doesn't matter
(much) if the IPs are really random.  For users 2 and 3 though, this is
basically an IP based Monte Carlo simulation and Nmap should do (within
reason) the best it can at picking random IPs.

So lets assume that our goal is for Nmap to provide quality "random"
IPs.  There are a few conflicting goals here:

* Nmap should be as fast as possible
* IPs should be as random as possible
* Nmap should (within reason) be of the same quality across all OSes

Obviously not all of these goals can be achieved at the same time so a
compromise must be struck.

At one extreme we go for pure quality and use cryptographically secure
random numbers from /dev/random or OpenSSL.  This is slow and blocks.

The next level compromise is to use a PRNG.  At one extreme we use MT
which as PRNGs go, is rather slow but provides _very_ high quality
pseudo-random numbers.  The other extreme is to use rand() and leave it
up to the OS to decide how "random" those numbers are.

*nix is not the issue here because it offers /dev/[au]random and rand()
is of pretty high quality. On Windows (and probably other obscure OSes)
rand() is terrible and something probably should be done to work around
it.

MT is probably overkill but we can still use a simple LCG like:

R(i+1) = (a · R(i) + b mod 2^32) mod m
with a = 1664525, b = 1013904223, m = 2^32

This LCG produces a complete cycle (all 2^32 numbers) with a relatively
high-quality ordering.

We can get 4 bytes of "randomness" out of each call and only a few
lines of C are needed.

One thing to be very mindful about with LCGs is that they exhibit a
very strong linear correlation.  One example of this is picking points
or colors with successive calls to the LCG.  Nmap actually does this.
If you pick an IP byte-by-byte you have a 4-space coordinate system,
namely (x.y.z.w).  If you do this with an LCG the points always end up
on hyperplanes in your N-space.

This probably doesn't make much sense on first pass so to illustrate
the point, I've generated a 3-space plot out of all of the possible IPs
Nmap on Windows can generate.

That is, the IP 1.2.3.4 would become two points: (1,2,3) and (2,3,4).
Because of the number of points this creates the plot I've made is a
sample of them.  The points would be quite a bit denser (but still be
on the same planes) if all the date were used.

You can get two slightly different views of this plot here:

http://noh.ucsd.edu/~bmenrigh/on_edge.png
http://noh.ucsd.edu/~bmenrigh/slight_angle.png

These plots are using real data as gathered by Nmap on Windows.

3-space makes the effect pretty dramatic and if we could "see" 4-space
it would be even more pronounced.  2-space doesn't offer a very good
view of this but the effect is there mathematically.

If we use a PRNG that gives us 4 bytes at a time we don't have to worry
about this geometry problem on a per-IP basis (successive IPs are still
correlated).

All my ranting really comes down to this: we can create nmap_rand() and
nmap_rand_seed() routines that will work on all 32 (and higher bit)
computers using less than a dozen lines of C.  Doing this will provide
a good fast compromise if we can't/don't use OpenSSL/dev-random/rand()/etc.

I'll code up and test a patch to implement this over the weekend.

Brandon

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

iEYEARECAAYFAkgakFIACgkQqaGPzAsl94K/NQCgttOMS5cZohKvntF0wRWPd+O+
PaQAnRAMi4P5fV08MLwmi0JaHAbpoZVb
=hcZ7
-----END PGP SIGNATURE-----

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