[rc5] Suggestion for protocol

Seth D. Schoen sigma at ishmael.nmh.northfield.ma.us
Mon Jun 23 03:07:25 EDT 1997

>On Sun, 22 Jun 1997, Fedor Kouranov wrote:
>> solution. This way we can determine the fake clients. On the other hand, a
>> smart hacker will be able to tell 'the' solution from 'a' solution by some
>> very simple heuristic analysis.
>Can you elaborate on that?

I can think of one very specific way to do this: if the client receives
the encrypted message to check along with the keyspace (which I'd imagine
it must under the new protocol, if there is to be a way to "send out
blocks which will appear as solutions"), then the client need only do
something like

if (ciphertext == original_rsa_ciphertext)
	falsely_report_as_checked()	/* a genuine block */ 
	actually_check_block();		/* a fake block just there to
					   test us */

If, on the other hand, sending out blocks which appear as solutions only
means satisfying whatever heuristic algorithm is presently built into
the client (which the web page or FAQ indicates is not completely
reliable), it's quite possible that the organizers would be able to test
the reliability of clients by issuing blocks which would satisfy the
known existing not-completely-reliable heuristic.  For instance, suppose
that key "F" is known to produce a decryption of the RSA ciphertext
which is "close enough" for the solution-detecting algorithm built into the
genuine client to report a match.  This could _certainly_ be the case
if the algorithm in the code is explicitly kludged to "accept as a solution"
the (incorrect) decryption resulting from a preselected particular key F.
That's much like Unix password encryption, in fact, if you think about

In this case, it's still conceivably possible for a malicious user to
attempt to write code to determine whether a false-match-producing key
was being assigned or not.  This would be done by operating a genuine
client for a long period of time and determining which particular key
or key(s) were

- repeatedly issued by the keyservers, and
- produced false matches

It's not possible in my scenario above to determine what the key F is
by simply inspecting the code, any more than it is possible to determine
what a Unix password is by inspecting its hash.  In my scenario, the
designers of the client have essentially included an encrypted "password"
in the client (the decryption of the RSA ciphertext by means of the
preselected "password" key F), and if it matches, a client is expected,
as a test of its reliability, to report the match.

In other words, to use more C pseudocode, the client hypothetically
contains this authentication mechanism:

if (begins_with_The_unknown_message_is(decrypt(rsaciphertext,assignedkey)) ||
    decryption == decrypt(rsaciphertext,F))

But as I described above, by observing the client's response to assigned
blocks and identifying a particular block or small set of blocks which
are repeatedly assigned and which are always reported as being
potential solutions, a malicious user can write a "wrapper" which will

if (assignedkey == F)

There is very little which can be done about such an attack, or worse,
an attack like

if (assignedkey == F)

Here's my overly-complicated and difficult-to-implement suggestion to
the code maintainers, if they're concerned about making reliable such
an authentication scheme: include in the released clients a mechanism
whereby a very large number (say fifty to one hundred) particular
keys, stored _as the decryptions which they produce_, will automatically
trigger a deliberate false positive report.  Then have every 100 blocks
(as suggested earlier) be a block containing a randomly-chosen one of
these particular "F" keys.

A note on the practicability of this: it might be horribly inefficient
as a general requirement, on the assumption that STO will work and
nobody can reverse-engineer the protocol, but it might work _very_
well as a means of maintaining a version of v1 protocol which would
be accepted: require everybody who wants source to run a client which
contains this false-positive authentication mechanism.  It might be
worth the extra overhead (for the project) and slightly slower
genuine keyrate (for the v1 client users) in order to maintain
contributions from the relatively tiny minority of people who, very
reasonably, will always insist on source.

In this case, a relatively reliable v1.1 to v2 translating proxy
could be created!  Or, more accurately, a trustable proxy which could
translate the output of untrusted clients to a trusted protocol!
(Completely destroying all my previous arguments to the contrary... :-)

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