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

[David Fifield <david () bamsoftware com>]

On Fri, Aug 28, 2009 at 07:03:21AM +0000, Brandon Enright wrote:
> I think this brings up a few questions.
>
> 1) Why did RC4 score WEAK on 5 tests?  I think this is bad luck.  I
> think it would pass those tests and score weak on others if tested
> again.
>
> 2) Why did the original patch fail a few tests?  The tests that did
> poorly were the bit pair count tests (the output was too uniform), and
> the lagged sums tests (there was some linear correlation in the
> dimensions tested).  It also failed a couple different minimum distance
> tests in 2 and 3 dimensions.  I think the output was too uniform.
>
> 3) Why did your first attempt at adding S-boxes to the tweak make it
> so much worse? This took me a day to figure out but I didn't undo the
> S-box transform properly.  I tried to fix this in a second s-box
> attempt.
>
> 4) Why did the second attempt at using s-boxes also do poorly?  My best
> explanation is that Dieharder was finding some pattern in my s-boxes
> that would have gone away with more rounds.
>
> 5) Why when you got rid of s-boxes and just added an additional round
> to the original tweak did it do better than RC4?  Adding the additional
> round clearly helped improve the tweak.  It only beat RC4 by chance
> though.  If the tests were to be run again RC4 would beat it once in a
> while too.
>
> 6) Why did 3-round tweak version do so well when no-duplicates violates
> obvious randomness properties?  First, Dieharder rarely treats the
> output as 32 bit numbers and if it treats them as less there will be
> duplicates.  Second, Dieharder implements tests that don't use a lot of
> memory.  Figuring out that there aren't any duplicates can consume a
> lot of memory.  Third, I think this is a weakness of Dieharder and I
> have some ideas for how to fix it.  I plan on working on formalizing my
> ideas and submitting them so that Dieharder can be improved.
>
>
> So I think the answer is that we should switch -iR to use my tweak with
> 3 rounds.  I'm not attaching a patch here because my testing has made a
> real mess of a bunch of code and it will take me a while to clean it
> up.  If there are no objections I'll check something in tomorrow.  If
> people want to do independent testing, let me know and I'll write up a
> quick Nmap+Dieharder how-to.  Running Dieharder is anything but quick
> though.

These are great results and an entertaining analysis. I support you
making the change.

David Fifield

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