[1398] in cryptography@c2.net mail archive
Re: Checking for cheaters in distributed challenges
daemon@ATHENA.MIT.EDU (Black Unicorn)
Mon Sep 1 10:15:19 1997
Date: Sun, 31 Aug 1997 21:01:16 -0500
To: Steve Reid <sreid@sea-to-sky.net>
From: Black Unicorn <unicorn@schloss.li>
Cc: cryptography@c2.net
In-Reply-To: <Pine.LNX.3.95.970831123813.5103A-100000@alpha.sea-to-sky.n
et>
At 01:09 PM 8/31/97 -0700, you wrote:
>> 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?
>
>The checking would be done on the individual keyspaces that are handed out
>to each person, not just on the whole search.
>
>Suppose each person takes 2^24 keys at a time. A "near miss" would be a
>key that decrypts the ciphertext such that the first, say, 20 bits of the
>resulting plaintext match the first 20 bits of the known correct plaintext
>(or some other fixed value, maybe all zeros). If the cipher has no
>statistical biases then the odds of finding a 20-bit match are one in
>2^20. Each person searching a 2^24 keyspace should find, on average,
>2^(24-20) or 16 near misses per block of keyspace.
>
>Each time the key server receives a report of a searched block of keys, it
>should also receive a list of keys that resulted in near misses. It would
>take just one decrypt operation per near miss to verify each near miss. If
>someone reports keyspace searched but reports bogus near misses, the
>person is untrustworthy. The key server should ignore people deemed
>untrustworthy.
>
>If the number of near misses is unusually low, it may be that the person
>hasn't really searched the keyspace, or it may just be that they were
>unlucky. The keyspace should be searched again by a trusted participant.
>If near misses are found that were not reported, the person in question
>probably didn't search their whole block of keyspace and should be
>considered untrustworthy.
But an attacker could still refrain from reporting all near misses, or
design a process to search only for a few near misses and report a fraction
of them (both to skew the stats and to hide under the cloak of
reliability). Can the number of near misses in a given subset of the
entire keyspace be determined with any accuracy? If not, then we still
have the same problem- i.e. relying on statistics to compare the reported
near misses of a small fraction of keyspace to the expected average for the
whole keyspace. How is the expected average obtained? We hope, of course,
that the keyspace is linear enough that a reasonably accurate number on
near misses can be arrived at by simple permutation math, but
cryptographically random and statistically random output are not the same
thing and it is entirely possible (even likely) that some near misses might
be precluded by the nature of the keyspace, the cipher, or key setup.
Determining a number for near misses in that context is a difficult
prospect, and ironically, more difficult with ciphers which have weaker
keyspace or key setup processes. Now you're in a position where the
political side of distributed cryptanalysis (showing the world that a
cipher is weak) is more difficult for those ciphers which are weak because
of nonlinear key space.
Statistical anomolies in output for a small keyspace could result in
ignoring valued submitters who have been saddled with a strange behaving
block of keyspace.
