[RC5] newbie question

Bruce Wilson bwilson at distributed.net
Mon Aug 25 07:45:38 EDT 2003

| -----Original Message-----
| 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).

What you're suggesting is called a "residual".  Whether it is obtained
from an XOR of the top N bits, or a CRC of the bottom N bits, or (in
the case of OGR) a count of the number of nodes found in the stub, the
idea is to capture some information which cannot easily be computed
without actually doing the work.  Since the start of OGR, we have been
looking at ways to capture residuals on each of our projects.  We're
working on one or two new projects now, and working out how to come up
with a reasonable residual.

One dimension which has in the past made it difficult to compute a
residual is the fact that clients could work with different size
workunits.  The proxy has the ability to accept superblocks and split
it into appropriate sized blocks for each dnetc request.  Some
recombining is performed upstream as well, when possible, to reduce
bandwidth.  (Not all work comes back to the same proxy which provided
it, and not all work comes back in the same amount of time.)  A good
residual for RC5 would need to survive splitting/recombining, and
still be computationally infeasible without doing the work.  I'm not
sure, but an XOR solution may be a bit too simple.

Another factor is that tracking the running XOR/CRC/whatever may have
a greater impact on performance on register-starved architectures
(X86).  Either the new value occupies a register, or it must be
swapped in and out of registers through the core of the loop.  This
change of flow may have a very significant impact on performance.
Clearly, if that is what we have to do to protect against people, then
that's what we may have to do.

It's arguable that a residual need not be perfect to achieve its
purpose.  By making it harder to figure out where to insert a JMP, we
may discourage most of those who try to "find the solution in 20
minutes after work."

Bruce Wilson <bwilson at distributed.net>
PGP KeyID: 5430B995, http://www.toomuchblue.com/ 

"I want to move to Theory. Everything works in Theory."
    --John Cash, id Software

More information about the rc5 mailing list