From: wcs@anchor.ho.att.com (Bill Stewart)
Date: Mon, 30 Nov 92 14:47:10 PST
To: cypherpunks@toad.com
Subject: Re: Unlabelled PGP messages
Message-ID: <9211302245.AA04980@anchor.ho.att.com>
MIME-Version: 1.0
Content-Type: text


Hal Finney points out some problems with unlabelled messages,
where the headers don't identify the public key by keyid -
remailers include your email address, while newsgroups / broadcasts
might have a LOT of articles, such that decrypting them to see if they're
for you would be impractically slow.  Some techniques that may help:
- a remailer-to-newsgroup anonymous poster, which lets you
	send the remailer articles (presumably with unlabelled keys)
	to be posted to the alt.whatever group -- should be an easy combination
	of existing tools.
- include an optional non-address label along with the unlabelled message.
	If you're having an ongoing secret conversation with somebody,
	you can secretly tell them the label to include, 
		Subject: Unlabelled PGP message label: fnord
	If you don't see the fnords, you don't have to decrypt them.

	You don't want to use anything that can be traced to you,
	and you probably don't want to use labels in a sequence,
	or use the same label throughout a conversation, but it could help.

	You could also, if you're only mildly paranoid, use something
	like a 4-bit checksum of the PGP key or the key length as a label 
	- it's not enough to identify which key it is, but it's enough
	to cut down on your decryption by a factor of 16.
	A longer checksum is too revealing - even 8 bits identifies 
	1/256th of the crypto community, which isn't very anonymous.

	With all these methods, if you're concerned about traffic analysis,
	you've still got to download the messages you don't care about
	to your machine before discarding them.

- The Conventional Data Encryption (DEK) packet includes a checksum,
	which lets you know if you've successfully decrypted it
	using the RSA key, so you can tell quickly enough whether a message
	is for you, without decrypting the message itself.
	The RSA step probably takes most of the time for short messages,
	but it's still a win.

	(PGP does lose some security this way, since the Bad Guys can also tell
	if their exhaustive search of PGP keys has gotten the right one,
	and now they can go beat up the Key-Certifier to find out
	who the key really belongs to, but it's a start.
	If you want heavier anonymity, you have to do without the checksum.
	There's also an extremely small chance of an incorrect PGP key
	producing a correct checksum, but it's about 2**-26, and 
	it still gives an incorrect session key.)

				Bill Stewart, somewhere in New Jersey