From: tcmay@got.net (Timothy C. May)
Date: Tue, 29 Aug 95 12:54:10 PDT
To: cypherpunks@toad.com
Subject: Poisson numbers for random keyspace assignment
Message-ID: <ac68b5601a0210040a9d@[205.199.118.202]>
MIME-Version: 1.0
Content-Type: text/plain


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."