[rc5] Suggestion for protocol

Seth D. Schoen sigma at ishmael.nmh.northfield.ma.us
Tue Jun 24 01:29:32 EDT 1997

Checksums don't really work as authentication against spamming.  A
user could still compute and return checksums faster than actually
doing the work, while not really testing keys.

True, in my proposal about test keys, the user could potentially do
all the work to see whether the key was one of the test keys (if
source is available or the user is really proficient in assembly),
but two major differences are that doing the full decryption is
_required_ (so a spammer would still have to do precisely as much
work as everyone else, and at least wouldn't attain a falsely higher
keyrate), and actually bypassing the security scheme requires an
active modification to the program to classify keys as test keys
or non-test keys (requiring _at least_ source and decompilation),
rather than simple determination to "break" the program by having it
compute checksums and no decryptions.  To use _even more_ C pseudocode
(sorry, everybody: it comes from having a weak knowledge of C, and
from writing about completely hypothetical protocols and authentication
schemes), the "checksum" scheme is basically

if apparent_match(decryption=decrypt(rsaciphertext,assignedkey))

and can be circumvented by doing simply


in every circumstance!

If the checksum is or is dependent upon the actual decryption itself and
not merely simpler aspects of the key, there is still a fairly automatic
means of getting around the authentication scheme!

If the real client is known to do

if apparent_match(decryption=decrypt(rsaciphertext,assignedkey))

a malicious client can easily be written to do


in every circumstance.  My objection, then, the the checksum schemes
is that even if they guarantee that spammers and spoofers will not
attain unrealistic keyrates (which I'm not convinced of anyway, since
there may be very real shortcuts to computing whatever checksum is
demanded), there is a particularly straightforward way to modify the
client into a malicious client _solely on the basis of knowledge of the
protocol and the checksum_.  True, if the checksum is chosen ideally
(in which case it will significantly slow down the server, which will
have to perform one decryption per thousand blocks!) to slow down
malicious clients, 

In my "test keys" scheme for authentication, load on the servers is
decreased (since they can use predetermined known test keys and only
look for the presence of an affirmative response, rather than doing
the math to verify a checksum), and there is, first of all, no
"straightforward" way to make an undetectable malicious client (since
doing so requires specific knowledge of client internals, only to
be obtained from source or disassembly, and which can never be obtained
by watching network traffic, since _the decryptions of the test keys
are never transmitted over the network_ but are instead held inside
the client, just like Unix passwords, as I explained earlier).
Second of all, any undetectable malicious client is guaranteed, if
RC5 is secure against a cryptanalytic attack, to be necessarily at
least as slow as a genuine client!  It is never possible for an
undetectable malicious client which authenticates via test keys
to run faster than a genuine client.  (At least, this is true of
a malicious client which spams or spoofs by returning false reports;
it is not true of a client which would hide the true key if it found
it.  Against such a client, which could still only be produced
by decompiling the program or by running a second client as a
wrapper so that the overall process was twice as slow, I have not
yet found a defense, unless you can create a true-key detection
algorithm and a test-key reporting algorithm which are indistinguishable
from one another, an interesting prospect.  This might still be doable:
if you can find a few test keys which decrypt into all-printable
strings, and then the client tests for a decryption containing only
printable characters, you'd be safe against some, but not all, attacks
from casual decompilation of the client, although not against someone who
ran a wrapper program which tested every key by a separate and more
sophisticated check -- or who modified a decompiled client to behave
this way!)

Good checksums will severely load the servers in verifying them, and
have no more reliability (in fact, potentially less) than test keys.
Bad checksums provide easy ways to falsify them and create
undetectable malicious clients which may still run significantly faster
than genuine clients, and this can be done solely on the basis of
reverse-engineering the protocol and the checksum algorithm, without
any knowledge whatsoever of the specifics of the client internals.
For these reasons, I still maintain that checksums are not a good
solution, and test keys ("F" keys, as I called them earlier) are a
relatively good solution to the problem of authentication.

To elaborate an analogy as to the benefits of test keys over checksums,
let's imagine that you have sent a spy into some country.  You wish
to determine whether the spy is still active and whether he has
not been captured.  Although it is possible to send intelligible
requests for the spy to do specific things, you wouldn't be able to tell
this way whether or not the spy had been captured; his captors could force
him to give the responses you had asked for.  A much better means of
answering your question is to establish beforehand certain responses to
certain innocuous, undetectable signals -- if the spy _has not_ been
captured, he will perform a certain behavior in response to observing
a particular event, but if he has been captured, he will not do so.
His potential captors have no way to know what constitutes a signal
to the spy, so they cannot force him to fake a response to one; only
the spy himself can determine whether a prearranged secret signal has
been given.  The spy's own response to your pre-arranged condition
provides a very natural way to distinguish his voluntary behaviors
from the behaviors he makes as a result of coersion and the
interception of explicit and obvious communcations to him.

Nothing is more dangerous for man's private morality than the habit of
commanding.  The best man, the most intelligent, disinterested, generous,
pure, will infallibly and always be spoiled at this trade.
            -- Mikhail A. Bakunin (thanks to Rabbi Albert Axelrad)
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.

More information about the rc5 mailing list