At 12:03 PM 8/29/95, Damien Doligez wrote: ...
But you fail to take into account the probability that the search will have to go that far.
This is how I compute the expected cost of the random search.
The probability of finding the key upon searching the k-th segment is:
k-1 p(k) = (1 - 1/n) . 1/n
The expected cost is the sum of all possible costs, weighted by their probability: ___ ___ \ \ i-1 e = > i p(i) = 1/n > i (1 - 1/n) /__ /__ i = 1..oo i = 1..oo ...
I haven't checked Damien's notation and confirmed the results, but I have another way of looking at it, which I think produces the same results. Last night (but it didn't arrive at my site until moments ago, for some reason) I wrote:
On the positive side, let everyone simply attack the keyspace as they see fit, picking random parts to attack. This should not be "worse" than a factor of several from a "perfectly coordinated" attack. (I haven't spent time calculating this, but my intuition is that a random attack, with overlapping keyspace, is not a lot less efficiently attacked than attempting to arrange for no overlaps...just based on my mental picture of dropping line segments randomly on some interval and figuring coverage of the line segment.)
Here's what I meant, in more detail: Imagine the overall keyspace to be searched as a line segment of some length: [------------------------------------------------] Now imagine various people randomly picking starting points and doing some segment, depending on their compute power: [---] [--] [--------] [------] [-] [--------] ...and so on, with the various line segments scattered randomly. Some will overlap, meaning the same keyspace segment is being searched by two or more people. If the total length (summation) of these line segments is the same as the "brute force exhaustion" of the keyspace, we can do some interesting calculations. For example, the "expected" number of hits per point is "1". But some points will be hit 0 times, others will be once, twice, three times, etc. (This is in the nature of random processes, as each line segment is random and "independent" of what other people may have independently picked.) The Poisson distribution fits this situation exactly, with the _actual_ number of hits computed by: P(s;m) = (e ^ -m) (m ^ s) / s! where s is the actual number of hits and m is the expected number. P(s;m) is the probability of seeing s hits when m are expected. s m P(s;m) 0 1 1/e, or .368 1 1 1/e, or .368 2 1 .184 etc. That is, with the "total exhaustion" amount of computation there will be 36.8% of the keyspace left unsearched, simply because nobody's random segments landed on this fraction of the overall segment. If twice, three times, four times, etc. as much effort is put into it (enough to brute force the search space twice, using nonrandom assignment), then s m P(s;m) 0 2 .135 0 3 .0498 0 4 .0183 For s = 0, P(s;m) = e ^ -m Several conclusions can be drawn. Here's what I conclude: * For opportunistic attacks on keys in challenges, the odds are 95% that a key will be found with only twice the total effort (or time) using a totally random method of picking up keyspace to search. * This is probably good enough. (And if one only wants to be 90% sure of finding the key, even less effort is needed.) * And this affects several of the "denial of service" attacks mentioned here by others, including finding the key but not reporting it (for whatever reasons), claiming too much keyspace, etc. This is because some of the same regions are actually being searched two or more times. * This of course gets rid of the assignment problems. * If the intent is to show that keys can opportunistically be found, the random assignment method works pretty well and is "good enough." If, for some reason, a key _had_ to found, then a more careful, nonrandom assignment method would be best. As assignment methods get better, a crossover will occur, and the random assignment method will lose its advantages. --Tim May ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^756839 | black markets, collapse of governments. "National borders are just speed bumps on the information superhighway."