[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