Re: Route cache performance under stress

[Scott A Crosby <scrosby@cs.rice.edu>]

Please CC me on any replies:


The suggested code here is problematic.

   RND1 = random_generated_at_start_time() ;
   RND2 = random_generated_at_start_time() ;
   /* RND2 may be 0 or equal to RND1, all cases seem OK */
   x = (RND1 - saddr) ^ (RND1 - daddr) ^ (RND2 + saddr + daddr);
   reduce(x)

For instance, if the table is assumed to have size N, bucket
collisions can be generated by:

   saddr=daddr= k*N  for all k.

Or, a different attack, if I assume that reduce(x) determines the
bucket by masking off, say, the lowest 12 bits, then:

   saddr=0xXXXXXAAA
   daddr=0xYYYYYBBB

Where, XXX, YYY are anything, AAA, BBB are arbitrarily chosen.

Now, lets look at the various terms:
 (RND1 - saddr)         = 0xUUUUUCCC
 (RND1 - daddr)         = 0xUUUUUDDD
 (RND2 + saddr + daddr) = 0xUUUUUEEE

The U's are all unknown, but the CCC, DDD, and EEE---the only thing
that we care about---are constant. Thus, the lowest 12 bits of x will
be constant. If those are the only bits that are used, then the
attacker has complete freedom to forge the highest 20 bits of saddr
and daddr.

With that function, you'd probably be better off masking off the high
order bits. At least there's a chance of a carry from the UUUU's
propagating into the bits you mask off.

I'm rusty with statistical analysis of cryptographic algorithms, but I
suspect demons may be lurking from that avenue too.


What might work better is to have a good universal hash function, h,
then do:

   h_k(saddr) - h_k(daddr)

Perhaps the simplest is:

  h_k(x) = x * k (mod P)

where P is a prime, and $ 0<= k < P$ is a random variable determined
at bootup.

Scott