From: Hal <hfinney@shell.portal.com>
Date: Mon, 31 Jan 94 17:50:27 PST
To: cypherpunks@toad.com
Subject: Re: 2-way anonymous via SASE
Message-ID: <199402010131.RAA05280@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


From: "Jon 'Iain' Boone" <boone@psc.edu>

>   So, you use a chain of anonymous-id's to set up your return-path?

Unfortunately, return-paths are not exactly the strong point of the
current cypherpunks remailers :-).  That is what much of the discussion
in this thread has discussed: how to best allow for convenient but secure
return paths.

>   What if you have a remailer that only assigns you an id for that message
>   so that your id is equivalent to (say) the Message-ID (or some portion
>   thereof)?  How do you return-path without specifying?

Your syntax is a bit hard to follow here, but I'm guessing that you are
proposing such a remailer as a way of providing for return paths.  The
remailer would remember the message-id's of outgoing messages, and would
remember where those messages came from.  Then if a reply came back for
one of those message-id's it could send it to that remembered address.

There were some proposals along these lines made last year, or maybe back
in 1992.  This scheme doesn't seem to generalize well to multi-remailer
paths.  Also, I think people would be nervous about having remailers keep
this kind of out-to-in mapping information.

>  Jon Boone | PSC Networking | boone@psc.edu | (412) 268-6959
>  finger boone@psc.edu for PGP public key block #B75699

It is interesting that it is theoretically easy to make a fake PGP
key which matches someone else's "displayed keyID", the low-order
24 bits of the RSA modulus.  If someone did this they could make a
fake PGP key for you with ID B75699, then fake finger and they would
be able to substitute their own key for yours.  Rather than displaying
your key ID it would be better to display your key fingerprint, visible
with "pgp -kvc", although it is 128 bits rather than 24 bits so may be
a bit cumbersome for a signature.

Here is how you make a key which matches a given low-order 24 bits.
Pick a random prime p.  Take the low order 24 bits of p and divide into
the given 24-bit "displayed keyID", mod 2^24, to get qx.  Now you
simply need to find a prime q whose low order 24 bits are qx.  This
can be done by picking a random q = qx + rand()<<24 (e.g. a random number
whose low-order 24 bits are qx), and repeat q += 1<<24 testing each
q for randomness.  This can even be sieved for a very fast test similar
to what PGP does.  It would be an interesting exercise to write such
a routine.

I understand there is already at least one 24-bit collision on the
public key servers, not unexpected given a few thousand keys.

Hal