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

[David Fifield <david () bamsoftware com>]

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

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