[1403] in cryptography@c2.net mail archive
Re: Checking for cheaters in distributed challenges
daemon@ATHENA.MIT.EDU (Peter Trei)
Tue Sep 2 13:55:10 1997
From: "Peter Trei" <trei@process.com>
To: Secret Squirrel <nobody@secret.squirrel.owl.de>, cryptography@c2.net
Date: Tue, 2 Sep 1997 10:33:08 -6
Reply-to: trei@process.com
CC: trei@process.com
> Date: 30 Aug 1997 20:56:01 -0000
> From: Secret Squirrel <nobody@secret.squirrel.owl.de>
> Subject: Checking for cheaters in distributed challenges
> To: cryptography@c2.net
> 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.
>
> Prize issuers could also demand to see some minimum number of near
> misses in order to award the prize, in order to determine that searchers
> really did the work. Of course the searchers could claim to have just
> gotten lucky and found the key far sooner than expected, but this would
> be awfully suspicious, to say the least.
There was very extensive discussion of these issues in the period
leading up to the DES challenge last winter. The upshot was that while
it was possible to prove that a searcher had searched most of his or
her allotted keyspace, it was impossible to prevent a 'bad actor'
from finding the key, yet reporting that chunk of keyspace empty.
Issues affecting 'cheating' rate.
1. Prize money.
I asked RSA to structure the prize in a way to maximize the chance
that a successful search would be reported; the prize was given to
the first person who reported the key; regardless of how they
obtained it. The size of the prize (US $10,000) was large enough that
relatively few individuals would turn it down. If a 'bad actor'
organization found the key with no intention of reporting it, I hoped
that some individual in that organization would defect and claim they
(or some acquaintence) had found it independently using an uncoordinated
search.
2. Coordinated vs uncoordinated searches:
In an uncoordinated search, every searcher is on his/her own; they
pick a random point within the keyspace to start searching, and
work forward from there. My DESKR and Mikkelsen's BRYDDES used this
approach. This technique is immune to cheaters, as the same space
may be searched by different people. Rivest calculated that on
average, this approach takes twice as long as a coordinated search.
Many (all?) of the coordinated searches kept their client source
code secret, along with the format of data passed between the
keyspace server and the client, in a effort to prevent false reports
of searched space. At least one (and possibly two) clients and
protocols were hacked by bad actors during the DES Challenge.
The coordinated searches gave the person who found the key
only a fraction of the prize money, if any. Thus the 'loss of
opportunity' cost of a cheater in a coordinated search was
relatively low.
The remaining techniques prove that a member of a coordinated
search searched the keyspace alloted, but not that they found
or did not find the key.
3. 'Checksums'
If a running XOR of some unpredictable internal variable of the
key testing engine is maintained, this serves as a 'checksum',
a value which cannot be generated except by doing the work. DESKR
kept a running xor of the output of the last complete DES round.
This technique works, but checking requires the same level of
effort as was used to generate it. I proposed that servers randomly
re-issue 1% of the keyspace searched by each client, as a spot-check.
4. 'Half-matches'
DES breaks the block it is working on in half, and deals with each
half-block alternately. Thus, it was possible to find a keys which
decrypted one half-block correctly, but not the other. These
'half-match' keys seem to be distributed more or less randomly.
DESKR reported these in it's output file.
In a coordinated search, these 'half-matches' can be checked by
a server very quickly, but there is no proof that there would
be any particular number of half-matches in a given chunk of
keyspace, other than statistical.
5. 'Salting the data'
This was the best proof-of-work-expended method proposed. In
this, the server, for each block of keyspace is issues, randomly
picks one or more keys within the block and tests them. The output
of these tests (salts) are passed along to the client, and as the client
searches, it checks for matches not only to the prize-winning target
message, but also for the particular salts generated by the
server. The client passes back not only whether it found the
magic key, but also the keys that generated the ask-for salts.
This can be checked for quickly, and proves that the client expended
at least enough effort to find all of the salts. It does require that
the server keep state about which salts have been provided for which
client.
Thus, while techniques were discovered which would effectively
prevent a 'cheater' from reported a chunk of keyspace as searched
when they had not done so, no technique was found that would
prevent an individual or organization willing to forgo the prize
money from falsely reporting a chunk as 'empty' in a coordinated
search.
Keeping the client and it's protocols secret, while not foolproof,
provided some protection against unsophisticated attackers.
The existance of software for uncoordinated searches provided a
plausible mechanism for defectors from 'bad actor' organizations
to claim to have found the key.
Peter Trei
trei@process.com
