[PATCH] Add the ability to generate quality random IPs without any duplicates

[Brandon Enright <bmenrigh () ucsd edu>]

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


Hey all, it's Friday and this week has burnt me out on "work things" so
I decided to tackle something fun.

Attached is a patch that adds a new random IP generation algorithm
option, -iU that generates unique (no duplicate) random IPs.  It does
so using constant memory (12 bytes of state).

So the first thing you're probably asking is:

Q: Why?

A: Because sometimes people want to scan exactly N hosts randomly, they
really don't want to scan a host twice, and they don't want to
pre-generate and then sort | uniq the list.


Q: How?

A: I'm exploiting a property of LCGs
(http://en.wikipedia.org/wiki/Linear_congruential_generator) that
causes them to not repeat for the duration of their period.  I've also
taken care of the nasty properties of LCGs that make them pretty
undesirable for IP scanning.


Q: Why not just replace -iR with this new -iU option instead of having
both?

A: Sometimes I want *really* high quality IPs.  Sometimes I don't want
to be bothered with duplicates. This patch is small, I think there is a
place for both.


Q: So how did you take care of all of those terrible properties of LCGs?

A: I'm glad you asked ;-)  Here is how I did it:


An LCG like the one you get out of rand() produces only a single
sequence.  The seed value you give rand picks where you are in the
sequence but it never changes the actual sequence.  Also, the linear
ordering of subsequent outputs of an LCG fall onto the surface of a
series of hyperplanes when plotted in n-space.

To fix the obvious linear correlation between outputs I introduce two
32 bit tweak values picked randomly.  I then take the output of the
LCG, rotate it, XOR by a tweak, stuff it in a different LCG, rotate it,
and then XOR by the other tweak.

This fix is really good but it isn't cryptographically secure.  It gets
rid of all of the reasonably measurable biases while preserving the
uniqueness offered by the original LCG.  It can't pass all the various
randomness tests out there in part because no duplicates is itself a
violation of several of the tests.

It does work as advertised:

$ ./nmap -iR 10000000 -v -sL -n -oG - | egrep '^Host' | awk '{print $2}' | sort | uniq | wc -l
9984393

$ ./nmap -iU 10000000 -v -sL -n -oG - | egrep '^Host' | awk '{print $2}' | sort | uniq | wc -l
10000000


Q: But how good can the output really be?

A: Pretty good.  Here's the evidence:

First, I wrote a perl script to use the "delayed coordinates" trick on
the IP output of Nmap to plot the linear correlation in 3D:

http://noh.ucsd.edu/~bmenrigh/nmap_rand_ips/ips_to_points.pl

You can use it like:

$ cat ~/rc4_ips.txt | ./ips_to_points.pl > ~/rc4_points.txt

Second, I plot the results in gnuplot using:

# 3d dot plot
set xyplane 0
set xrange[0:65535]
set yrange[0:65535]
set zrange[0:65535]
splot "rc4_points.txt" using 1:2:3 with dots

Here is a plot of 1 million IPs from -iR:

http://noh.ucsd.edu/~bmenrigh/nmap_rand_ips/rc4_plot.png

No obvious bias (RC4 is pretty darn good).


Here is a plot of 1 million IPs using the LCG in this patch *without*
the added tweaks.  For the sake of this plot I also got rid of
ip_is_reserved() because it actually helps the LCG slightly:

http://noh.ucsd.edu/~bmenrigh/nmap_rand_ips/lcg_plain.png

The bias is obvious.  All the points are on hyperplanes.


Here is the LCG again but this time with ip_is_reserved():

http://noh.ucsd.edu/~bmenrigh/nmap_rand_ips/lcg_withnoresv.png

The bias is still obvious but not as bad.


Now, here is the LCG after the tweak:

http://noh.ucsd.edu/~bmenrigh/nmap_rand_ips/lcg_tweaked.png

Clearly if there is a bias in this graph, it can't be seen with the eye.


Q: Why haven't you included a patch to the man page and other
documentation?

A: If people like this idea and want to include it with Nmap I will.


Q: Is this email *finally* done????

A: Yup :-p


Brandon


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

iEYEARECAAYFAkqPSnIACgkQqaGPzAsl94IpQgCfVPPLCvrYFzCbObO3wQs0OfAA
wk4AniM4gjd6b8dF4ji/tAJwDX7UWbu/
=wIkj
-----END PGP SIGNATURE-----

Attachment: unique_rand.txt
Description:

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