At 2:49 AM 8/31/95, MONTY HARDER wrote:
[Great statistical summary deleted]
Thanks. Two other people sent me e-mail saying the odds of a keyspace chunk being left uncovered are 1/e, so this part is pretty well known. (With an expectation of "1" of course, as I noted. Interestingly, this was the same formula we used at Intel to figure out chip yields: "What's the probability that a chip will have zero defects given that m defects are the "expected" number?") I wanted to explain the derivation in more detail than just saying 1/e, especially for the more interesting cases where the keyspace gets more coverage. (Where the m = expected value is more than 1.)
TC> * For opportunistic attacks on keys in challenges, the odds are 95% that a TC> key will be found with only twice the total effort (or time) using a TC> totally random method of picking up keyspace to search.
The odds can be improved somewhat by scaling the granularity of the sweep to the size of the sweep. (Align larger chunks on large-chunk boundaries, eliminating the chance of overlap with other large chunks.)
Indeed, this is an effect to consider. That is, each searcher is (presumably) not overlapping, so the results I reported are sort of a bound on the actual numbers. At one end, with lots of searchers doing very small fractions of the total, the results are pure Poisson. At the other end, with a searcher covering most or all of the keyspace, then of course the results are those of nonrandom search. Practically speaking, with dozens or hundreds of searchers, the Poisson results produce accurate enough estimates.
The best advantage of the random method is that it allows people to participate completely anonymously, as there is nothing to report save the Eureka!, and that can be done through a remailer anyway. When the challenge is solved, everyone can stop cracking.
A very good point! Anonymous cracking has many 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."