Jeff Simmons (
Fri, 2 May 1997 20:30:48 -0700 (PDT)

Here's a little thought experiment for you.

Imagine there are 100 keys. I pick 25 at random, you pick 25 at random.
So together we've picked 50. We're half way through the keyspace, and
together we have a 50% chance of having found the right key.

Wrong of course. Since I've covered 25% of the keyspace, each of your
choices has a 25% chance of being one of the keys I've already picked.
So the number of dual-picked keys, on average will be 25% of 25, or
6.25 duplicates.

So together we've only searched 43.75 unique keys. We have to search 6.25 more
keys together, or 3.125 each. Now the odds of picking identical keys are
slightly higher, say 30% (way too high, but it's a thought experiment).
So say we have to search 4 more keys each to get to 50 unique, counting

So on average, if I pick 29 keys and you pick 29 keys, we'll have each have
picked 21 unique keys, and 8 that were duplicated. Total searched - 58.
Total unique - 50. 58/50 = 1.16 *ON AVERAGE* this is the penalty for
not cooperating.

The serious math to get the exact number is left as an exercise for the

Jeff Simmons

Hey, man, got any spare CPU cycles? Help crack DES.