Re: Fwd: [DES-ANNOUNCE] New clients and 'spamming'

Justin Dolske (dolske@cis.ohio-state.edu)
Mon, 5 May 1997 14:09:03 -0400 (EDT)


On Mon, 5 May 1997, Nelson Minar wrote:

> There are some serious, realistic threat models on a distributed
> attack like deschall. On a discussion on coderpunks a few months ago
> the consensus was that the only really safe solution was a completely
> uncoordinated one - every client pick random blocks.

Would that have been Peter Trei saying that, per chance? He's been a
proponent of the uncoordinated approach for awhile...

Assuming that the percentage of malicious clients is fairly low, you can
achieve a rather high degree of certainty that blocks are being searched.
The easiest way is to compute a checksum of the decoded results. You then
hand out the same keyspace to another host (or more, if you're paranoid),
and make sure both checksums match. This obviously cuts the search rate at
least in half, so you can optimize it a bit by only spot checking. The
most you spot check a host, the less chance it has of cheating.

There are also a couple variations on this which require the client to
find a known result within its key block. This requires a small amount of
work on the server, but ensures the clients are checking at least 50% (on
average) of their assigned work.

The one "flaw" in spot checking is that a malicious client that lies
*only* if it finds the key is hard to detect, unless another host is asked
to spot check that exact range.

Justin Dolske <URL:http://www.cis.ohio-state.edu/~dolske/>
(dolske@cis.ohio-state.edu)
Graduate Fellow / Research Associate at The Ohio State University, CIS Dept.
-=-=-=-=-=-=-=-=-=-=-=-=-=- Random Sig-o-Matic (tm) -=-=-=-=-=-=-=-=-=-=-=-=-
"Don't turn your back on a baby and a bucket."
-- heard on a TV commercial for the Plastic Shipping Container Industry Group