[RC5] newbie question

Slawek sgp at telsatgp.com.pl
Sun Aug 24 13:45:03 EDT 2003

Bruce Wilson wrote:

> Regarding the security issues, bovine has an in depth
> discussion of why security is so complicated for
> distributed projects at
> http://www.distributed.net/source/specs/opcodeauth.html.
> In the distributed computing realm, we are faced with the reality
> of untrusted participants (they're out there) who would want to
> send back forged work.  If we release the source code to the
> networking/transport-crypto portions of our client, these people
> could generate packets with a false "found it" flag on RC5
> projects as a denial of service, or just pump up their stats by
> sending back packets as finished without doing the work.

Nethertheless there _IS_ a highly universal way to detect
such attacks.

I'm talking about RC5 now (in case of OGR it's even easier).

My solution would have following impact on performance
of the system:
- 1 to 2% slow-down on keyrate
- only neglible effect on CPU operatios of keyserver
- a little increase on disc space requirement of keyserver
  (I haven't taken a look of what's tracked so far, so I can't
  be more accurate, for example is it tracked which block
  were submitted by which user?)
- 4 bytes per workunit more to send on the net

I'm not sure if slow down of total keyrate is acceptable.

The idea is very simple.

Just modify the clients to make some simple operation on
each of decripted texts. For example ADD or XOR high
4 bytes of each (8 bytes on 64 bit processors may be faster,
in order to be compatible we may discard lower bytes after
processing each workunit).

I think XOR is better here because on some processors
it may be beneficial to have decripted texts generated
splitted against some registers. In such case doing an
ADD might be somewhat expensive.

Now require clients to send whose "checksum" to the
proxies and to the keyservers.

Keyserver would need to choose which workunits should
be checked. Checking would mean reissuing the same
workunit to the other client so of course we're not going
to check all of them.

I would suggest checking about 1 per 100 if we're dealing
with new user and decrease checking rate as user submits
more data.

Of course the method of choosing which workunits to check
has to be unpredictable but having a large userbase it may be
enough to base on number of keys submitted in total
(variations possible in case of parallelism and so on).

This method naturally would not catch cheaters at the moment
they're starting cheating, so we need a way of rolling back
keys submitted by offending client once he's proven to cheat.

We can for example remember the checksum of each submitted
workunit for some time and delete it after a while (after checking
it or not). This way whenether we catch somebody's cheating
we can check his previous blocks also.

We other idea would be to remember checksums only for
block selected to checking. This way after catching
somebody's cheating we can't easily check how often had
he cheated, but we still can reissue all of his lastly submitted
(or all - depending on the policy) blocks.

We don't have to remember the checksums permanently.
It's enough to remember them as long as it takes to recheck
them and/or for some predefined time period. This means
we don't need much additional disc space on the keyserver.

We may have a problem with defects in the processors
or RAM or so. Those would mean false positives,
but I think accepting work from clients which -
even unintentionally - submit flawed results is something
that should avoided.

Ok, so what do you think about this?

Slawek Piotrowski

ps. I'm _NOT_ volunteering to write the code ;)

More information about the rc5 mailing list