[Bro] Re: Bug on Anon.cc

Jose M. Gonzalez chema at cs.berkeley.edu
Sun Sep 11 14:59:10 PDT 2005


Ruoming Pang wrote:
> I see. There is some misunderstanding here. We do not take the hash 
> value of 10.0.0.0/8 as the result prefix, but use it to determine 
> whether we flip the 9th bit. And hash value of 10.0.0.0/9 determines 
> whether to flip the 10th bit, and so on. 
Oh, I thought you were meaning that you wanted to anonymize the 
prefix 10.0.0.0/8, as compared to the address 10.0.0.0, from which 
hashing 10.0.0.0/8 is one of 32 steps. 

I'd say the discussion concerns only the padding function, which was 
wrong in both the old code and my patch. 

> By the way, the PAD function in the paper does include the prefix 
> length, instead of padding with only 0.
You're right: the padding requires adding the $i$ value (the prefix 
length). That's actually what makes 128.0.0.0 hash to something 
different than 4 possible values.

Still, you have to get rid of all the bits after the prefix you're 
currently hashing. Moreover, the padding also includes a 1 before the 
zeros (the padding is the same than in RFC 1321. I wonder which is 
the reason for adding a 1. Anyway, I'd respect it). For the old code, 
the prefix should be calculated as:

prefix.prefix = (input & ~(prefix_mask>>(31-i))) | (1<<i);

The code would be now OK. A minor quirk: the way the old code uses $i$
is different from the way the paper uses $i$ (they are related as 
$i_{paper} = 31 - i_{old_code}$). I changed the old code so that $i$ 
is now the same than in the paper. Patch is enclosed. 

-Chema

-------------- next part --------------
Index: Anon.cc
===================================================================
RCS file: /home/portnoy/u2/src/projects/bro/src/Anon.cc,v
retrieving revision 1.1
diff -u -r1.1 Anon.cc
--- Anon.cc	14 Jul 2004 20:15:39 -0000	1.1
+++ Anon.cc	11 Sep 2005 21:42:13 -0000
@@ -99,24 +99,36 @@
 	return output;
 	}
 
+/*
+ * this code is from "On the Design and Performance of Prefix-Preserving 
+ * IP Traffic Trace Anonymization", by Xu et al (IMW 2001)
+ * 
+ * http://www.imconf.net/imw-2001/proceedings.html
+ */
 ipaddr32_t AnonymizeIPAddr_PrefixMD5::anonymize(ipaddr32_t input)
 	{
 	uint8 digest[16];
 	ipaddr32_t prefix_mask = 0xffffffff;
+	input = ntohl(input);
 	ipaddr32_t output = input;
 
 	for ( int i = 0; i < 32; ++i )
 		{
-		prefix.len = 32 - i;
-		prefix.prefix = input & prefix_mask;
+		/* PAD(x_0 ... x_{i-1}) = x_0 ... x_{i-1} 1 0 ... 0 */
+		prefix.len = i + 1;
+		prefix.prefix = (input & ~(prefix_mask>>i)) | (1<<(31-i));
 
+		/* HK(PAD(x_0 ... x_{i-1})) */
 		hmac_md5(sizeof(prefix), (u_char*)(&prefix), digest);
 
-		ipaddr32_t bit_mask = (digest[0] & 1) << i;
+		/* f_{i-1} = LSB(HK(PAD(x_0 ... x_{i-1}))) */
+		ipaddr32_t bit_mask = (digest[0] & 1) << (31-i);
+
+		/* x_i' = x_i ^ f_{i-1} */
 		output ^= bit_mask;
 		}
 
-	return output;
+	return htonl(output);
 	}
 
 AnonymizeIPAddr_A50::~AnonymizeIPAddr_A50()


More information about the Bro mailing list