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

[bmenrigh () ucsd edu]

> On Sat, Aug 22, 2009 at 01:31:23AM +0000, Brandon Enright wrote:
> > 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.
>
> What made you think of this technique? Is there a paper or something you
> can point me to? Or did it just come from trial and error?
>
> David Fifield

Sorry I'm using a crappy webmail client on a friends laptop and I don't
have any good references on number theory sitting in front of me.  I'll
try to provide a meaningful response though.

I thought of using a LCG with its known period as a way to produce a
non-repeating sequence of IPs some months ago.  I suppose it's somewhat
obvious but I didn't think of exploiting the property to give Nmap
non-repeating "random" IPs until recently.

I was hesitant to implement something using just an LCG though because of
their poor quality.  I didn't know how to fix these problems though so
I've been sitting on the idea.

Lately I've been doing some amateur cryptanalysis on some of the SHA-3
candidates (I helped knock NKNS 2D and Spectral Hash out ;-) and as part
of that, I've been going back and reviewing some of the work done on DES
and other algorithms.  It occurred to me that what a block cipher really
is, is just a random-looking mapping from [0 .. 2^block size] back onto
itself.  You can show that a block cipher is a collision free mapping in
one block (for a given key) with trivial proof-by-contradiction.

Unfortunately I wasn't aware of a 32bit block cipher so I set out to build
one.  I decided that since we weren't "decrypting" the key could just be
random, and since I didn't have to worry about a key schedule I just made
the two round keys (tweak1 and tweak2) random.  I figure since the goal
isn't to create something cryptographically secure, two rounds should be
enough.  I decided a round would be a LCG followed by a XOR of the round
key.  Because the output of a LCG with a power-of-2 period like the ones
I'm using has much shorter cycles in the lower bits, I decided to rotate
the lower bits up before each XOR.

This is roughly the principle a SHA-1 round is based on.  This is also the
principal that the Xorshift PRNG is based on
(http://en.wikipedia.org/wiki/Xorshift).

These ideas all came together while I was standing in the shower earlier
this week.  I thought the idea was based on sound principles.  I
implemented it, tested it, it seemed to work.  Before I started I though I
might need to add a third "round" but I was happy with the test of only
two rounds.

As a side note, I decided to use random round keys rather than hard-coded
ones (my original plan) because if the keys are the same between
invocations, then even if the seed is different, the IPs are coming from
the same sequence, just a different spot in the sequence.  I didn't want
somebody to be able to compute all 2^32 IPs in sequence and then be able
to use a lookup table to figure out the current state.  With random round
keys this routine can generate 2^64 different sequences.

I don't want to claim that this is good cryptography.  I'll go out on a
limb though and say these are pretty good random IPs considering they are
collision free.

Brandon



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