Nmap Development mailing list archives
Re: [PATCH] Add the ability to generate quality random IPs without any duplicates
From: bmenrigh () ucsd edu
Date: Sat, 22 Aug 2009 00:02:51 -0700 (PDT)
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
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 bmenrigh (Aug 22)
- 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)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates David Fifield (Aug 21)