Messages in this thread | ![/](/images/icornerl.gif) | | Subject | Re: Route cache performance under stress | From | Scott A Crosby <> | Date | 08 Apr 2003 01:14:55 -0500 |
| |
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
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| ![\](/images/icornerr.gif) |