[1396] in cryptography@c2.net mail archive
Re: Checking for cheaters in distributed challenges
daemon@ATHENA.MIT.EDU (Black Unicorn)
Sun Aug 31 13:07:05 1997
Date: Sat, 30 Aug 1997 21:36:33 -0500
To: cryptography@c2.net
From: Black Unicorn <unicorn@schloss.li>
In-Reply-To: <af0c28eba223b7c950588613c403251a@squirrel>
At 08:56 PM 8/30/97 -0000, you wrote:
>One problem with DES challenges is that someone could grab some key
>space and claim to have searched it, but they actually didn't. Here is a
>solution.
>
>Make searchers not just report when they are done, but also to report
>"near misses". These could be cases when the ciphertext and encrypted
>plaintext match in the first n bits. n can be chosen so that a typical
>batch produces some reasonable number of hits - enough so that it will
>be clear when the number of hits is statistically plausible, but few
>enough that the amount of data uploaded to report a batch completion
>is not too big.
>
>The server can store (and perhaps check) the reported near misses, to
>make sure that they are correct. The only way to generate enough near
>misses is essentially to search (almost) the whole key space. So this can
>confirm that searchers are at least doing what they claim to.
>
>This doesn't solve the problem of the person who finds the key and then
>claims that it was not present in his search range. Such a person may have
>an interest in seeing the challenge fail (he invests in technology which
>would be threatened by success) or he may want to pass the key on to
>a confederate who will claim to have discovered it on his own, and who
>then seeks to acquire the whole prize for himself.
But when you think about it, this is the same thing. Statistically there
should be (at least) one "direct hit" in every search of the entire
keyspace. If you don't get one (first RC4-40 attempt for example) you know
you have a problem. What, however, can be done but restart the search or
continue?
This, I think, highlights the limited scope of the solution, namely that it
may tell you if there are cheaters, but does not identify them or suggest a
solution. I love the method, it's quite elegant, but what about the utility?
What will be the action after the cheating is exposed? If, as I suspect,
the "near misses" are based on statistics which are in turn based on a
large sample of data (if not one might question their accuracy) then how
can an individual searcher's "near miss" results be informative? How much
keyspace are we willing to say is enough to determine if the searching is
statistically accurate? 10% 25%? 50%? (Certainly there is a wealth of
data sitting around to answer this as it is basically an election returns
problem- ENIAC anyone?) I'm not sure that checking for near misses could
be useful until a substantial portion of the keyspace was examined, and I
doubt that a figure on near misses for a given subset of keyspace could be
arrived at quicker than scanning the entire keyspace subset.
Ok- let's assume that after searching 10% of the key space, we have an
indication that there is a cheater. What's the next course of action?
Stop the search? This would allow a single attacker, provided he did
enough searching to skew the statistics, to sabatoge the entire project
without searching the subset that contained the key. (A distinct advantage
to the attacker). All an attacker has to do is skew the statistics and the
search grinds to a halt. It's a particularly insidious attack because it
is bound to reduce the number of participants as users (who have endured
who knows how many hastles to get a client running) throw up their hands
after the Nth restart.
My suspicion is that you might have to take a U.S. customs approach.
Perhaps check 10% of the submissions on the assumption that the cheater
might be detered by the 1 in 10 chance of detection. Obviously there is an
increase in processing time, but this is the price you pay. Clearly this
is no solution at all unless you have some kind of name matches submitters
claimed name authentication.
