Nmap Development mailing list archives
Re: [PATCH] Add the ability to generate quality random IPs without any duplicates
From: David Fifield <david () bamsoftware com>
Date: Fri, 28 Aug 2009 12:14:56 -0600
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
Current thread:
- [PATCH] Add the ability to generate quality random IPs without any duplicates Brandon Enright (Aug 21)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates David Fifield (Aug 21)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates David Fifield (Aug 23)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates Brandon Enright (Aug 23)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates Fyodor (Aug 23)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates Brandon Enright (Aug 23)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates Brandon Enright (Aug 28)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates Fyodor (Aug 28)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates David Fifield (Aug 28)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates Brandon Enright (Sep 01)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates Fyodor (Sep 08)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates Brandon Enright (Sep 08)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates Brandon Enright (Aug 23)