Unlabelled PGP messages

[Hal Finney]

Peter Shipley points out that PGP messages are labelled with an
identifier of the person they are sent to.  This hurts the anonymity
of the messages somewhat.

What PGP actually puts in the cleartext message header is the "Key ID"
of the recipient.  This is the low-order 64 bits of the RSA modulus
"n" of his key.  (PGP displays only the low-order 24 bits when it
shows key ID's, but it keeps 64 bits internally.)

I understand that there was some discussion during the development of
PGP 2.0 of having a mode where this wouldn't be done.  One possibility
would be to output a key ID of all zeros for a message which wanted to
hide who it was for.  Then, as Peter suggests, it would either be
trial-decrypted by all of the secret keys you have, or, more simply,
it would just try your "default" secret key.  Most people only have
one secret key so both methods would be the same in most cases.  Doing
it the second way would be a pretty easy patch to PGP.

I'm not so sure now that this feature is that helpful.  First, you
don't have to put your real name in the "user name" field.  You could
use a pseudonym.  So you really don't have to give much information
away about yourself the way it is now.

Also, if someone is sending a message to you using encrypting
remailers, they would encrypt it using your key, add remailing
instructions for the last remailer in the chain, encrypt that using
that remailer's keys, add remailing instructions for the next-to-last
remailer, encrypt it again, and so on.  (This would be done
automatically by some future software - you wouldn't want to do this
by hand!)  The result is that the mail you send does not expose the
key ID of your recipient.  That information is only revealed when it
comes out of the last remailer in the chain.  And by that time, it's
no secret, since that last remailer is using the true email address of
the recipient anyway.  So it's not giving anything away.

For the other kind of anonymous messaging, where you just post to a
newsgroup or use some other kind of "broadcast" system, the key ID is
revealed and for this case it might be better to hide it.  But, the
key ID can be useful in this application by letting you know which
messages you should decrypt.  No one has to know that a particular key
ID is "you".  You can still download 1000 messages and only read yours
without anyone knowing which ones you read.  But with key ID hidden
you would have to decrypt them all to see which are yours.  Do you
want to decrypt all 1000?  This will take minutes, hours, or days,
depending on your key size and computer speed.  (Most of the decrypt
time is spent doing the RSA step, at least for most messages, and you
can't tell if it's for you without doing that step.)

This still might be a good idea, but I'm not sure...

Hal Finney
74076.1041 at compuserve.com