From: b44729@achilles.ctd.anl.gov (Samuel Pigg)
Date: Fri, 27 Aug 93 03:55:54 PDT
To: hfinney@shell.portal.com
Subject: Re: Attacks on remailers (LONG)
In-Reply-To: <9308270511.AA25630@jobe.shell.portal.com>
Message-ID: <9308271052.AA07922@achilles.ctd.anl.gov>
MIME-Version: 1.0
Content-Type: text/plain



>>>>> On Thu, 26 Aug 93 22:11:20 PDT, hfinney@shell.portal.com said:

>>>>> On Wed, 25 Aug 93 11:39:11 EDT, J_G_Thomas%CAASD1@mwmgate1.mitre.org said:
	[...]

	hfinney> As I indicated in my long posting, it is not
	hfinney> necessary to send out the same message that was
	hfinney> received.  Chaum proposed encrypting the message (the
	hfinney> non-address-block portion) with a secret key at each
	hfinney> stage, a key which would be revealed to the remailer
	hfinney> (along with the address of the next address in the
	hfinney> chain) when it peeled off its own layer of
	hfinney> encryption.

	[...]

	hfinney> If no encryption is done on the message body, there
	hfinney> is another attack for this case that I didn't
	hfinney> mention.  It is:

	hfinney> Run a remailer.  For every anonymous address floating
	hfinney> around on the net, try sending a message to it.  Look
	hfinney> at the messages which pass through your own remailer
	hfinney> and look for matches to the message you sent.  Any
	hfinney> anonymous address which includes your remailer as one
	hfinney> of the elements will pass through you.  You have then
	hfinney> defeated all of the stages of the chain before
	hfinney> yourself.  In particular, if you happen to be the
	hfinney> last remailer of the chain, you have broken the
	hfinney> anonymity of the anonymous address.

	hfinney> This attack, while not the most powerful on the list,
	hfinney> defeats many of the principles of remailer chains,
	hfinney> such as that the chain is as strong as its strongest
	hfinney> link.  It requires you to strongly trust at least one
	hfinney> remailer in the chain (the last one), whereas without
	hfinney> this attack you would not have to especially trust
	hfinney> any single remailer.  So it is significant.

Correct me if I'm wrong, but as I see it, there are two goals
for the remailers:

(1) 	Anonymous addresses to which mail can be sent, but the recipient
	is unknown and cannot be determined (receiving anonymous mail).

(2)	The ability to send mail to someone without anyone (including
	the recipient) determing that you did so (sending anonymous mail).


Number 2 can be mostly taken care of with nested encryption of mail headers.

Using the method you mentioned above of including a key to encrypt the
body of the message nested inside each level of nested encryption
would take care of the above problem (having to completely trust the
last remailer) and restore the "chain is as strong as its strongest
link" principle.

This would complicate slightly complicate the final decryption for the
anonymous recipient (having to decrypt the body of the message with each
key in turn.) New software tools could need to be written for
the recipients as well as the sender to handle this easier.

A "anonymous address block" similar to the pgp signature blocks
would be helpful for automating the sending of mail to anonymous
addresses.

To construct an anonymous address block might be something like:

	Anonymous Anne wants an anonymous address.
	First she generates a set of N keys (IDEA, DES or RSA, doesn't
	matter except RSA would disallow a remailer to decrypt what it 
	encrypted using it.) She would then choose a path through
	the remailers and encrypt her address (and perhaps one of 
	the random keys) with the last remailer's key.

	The result of this she would pair with the address of the 
	next remailer closer to her (in the remailing path) and
	one of the random keys, and encrypt this with the 
	next-to-the-last remailer's key
		.
		. (for all hops)
		.
		|
		v
	She would then encrypt the result of the previous operation
	with the key of the intended first remailer in the chain.

	Then she would add the address of the first remailer
	(in cleartext).

	This (largish nested encrypted address chain + cleartext
	first remailer address) she would encrypt (or sign) with the
	secret key of her anonymous persona.

The appropriate software tools would allow someone to reply
to an anonymous address using this "anonymous address block".

	[...]
	hfinney> This lack-of-TCP problem also impacts the proposal to
	hfinney> use a public telnet port for message communication.
	hfinney> Another problem with that proposal is that it would
	hfinney> need the remailers to run as background processes.
	hfinney> With the current software they can run as mail
	hfinney> filters, which makes them much less conspicuous to
	hfinney> system managers.

True, but it would also protect against attack 2 in your "Attacks on
remailers" post -- the mail log problem.

I think it would be fairly simple to include in the next-remailer-address
whether or not to use normal mail channels (for uucp remailers)
or to use socket nnnn connection to the remailer (for the ones
that are capable.)

	hfinney> The suggestion for remailers to send messages by
	hfinney> telnet connection to port 25 of some other machine
	hfinney> (rather than by piping to sendmail as they currently
	hfinney> do) is perhaps reasonable (for those systems with TCP
	hfinney> access), although it makes the remailer somewhat
	hfinney> harder to set up since you have to find some other
	hfinney> machine which will let you connect to their port.
	hfinney> Also, I think some machines may log incoming or
	hfinney> outgoing telnet connections to this port, since it is
	hfinney> a common technique for mail forgeries.  I have heard
	hfinney> that most systems will actually not allow public
	hfinney> telnet connections to this port.

The socket connections to other remailers would use a special port
number. For the last connection (to the recipient) could be either
by socket 25 connection or normal mail, whichever works (preferrably
socket 25.)

	hfinney> I don't know that much about how widely available
	hfinney> telnet and other TCP/IP services are on the net, so
	hfinney> if these techniques are more usable than I am
	hfinney> suggesting I'd like to hear about it.

I haven't seen a machine that doesn't allow just anyone to
connect to port 25. (is there some new authentication protocol
for this that I missed?)


So the attacks and defenses as outlined by hal (with some additions):

(1) Reading the "request-remailing-to" lines in the message to determine
where it is going.

Defeats remailer goal #2.

Defense: can be defeated by nesting the remailer encryption.

(2) Reading mail logs to plot the path of a message.

Defeats remailer goals 1 and 2.

Defense: bypass mail systems on remailer hosts, using special
port socket connection communication wherever possible; run remailers
only on systems that do not keep mail logs.

(3) Monitor messages in real time flowing in and out of remailers,
	correlating the input messages with output.

This is a variation of attack 2, and can defeat both remailer goals.

Defense: Batch remailing messages in a manner which frustrates analysis;
	send fake messages to other remailers in such a manner as
	to maintain a constant flow, removing flow rate cues.

(4) Read header info and check message size for remailer input/output
	correlation cues.

Variation of attack 2, and can defeat both remailer goals.

Defense: Do not preserve any header information; pad messages to remove size
	cues.

(5) Inject a clone of a message into the remailer stream, and look for
	two identical messages to come out of a remailer to track the
	message.

Another variation of attack 2.

Defense: Check for duplicate messages in the remailer and remove all
	but one copy of each duplicate.

(6) Insert duplicate messages in the input stream in seperate batches,
	checking the outgoing batches for copies to track the message.

Same problem as (5) really.

Defense: Timestamp the messages so they are only good for a number of days,
	thus reducing the number of messages to check against for duplicates.

I don't like this defense.
Who would make the timestamp?
Where would you put the timestamp?
How would you prevent spoofing?

	If you added an element of randomness to the procedure that
padded/altered the message before sending on to the next remailer, it
would defend against this line of attack -- so two identical messages
going into a remailer would come out differently. This is where DH key
exchange could be fruitful (with random session keys for each
message.)  (Assuming that the remailers don't know each other's RSA
keys. If they did, then they could simply encrypt a random session key
with the other's key and encrypt the message with the key also, and
ship them both over to the next remailer.)


(7): Look at all messages coming out of the first remailer, and
follow them into their 2nd remailers; take all messages from those and
follow them on, and so on.  This will eventually lead to a number of
destinations, one of which must have been the destination of the original
message.  Over a period of time, look for correlations between destinations
and sources.

Defense: Use large remailer chains of popular remailers.  With enough
mixing at each stage of the chain, the number of possible destinations
will become astronomically large, making correlations statistically
impossible; use of dummy messages to pad flow rate to constant
would increase the difficulty of such an attack (would hide the signal
deeper in the noise.); such an attack (PROLONGED monitoring of all
remailers) would be very difficult to perform, esp. with use of
remailer-remailer socket connections.

(8): Correlate messages being sent from person A with messages being
received a certain time later by person B.  Even without the ability to
track messages through the remailers this can show a communication pattern.

Defense: Send dummy messages at regular intervals, which bounce through
the remailer network and then die.  When you have a real message to send,
replace one of the dummies with this.  The sender's traffic pattern is
then constant and no information can be gained from it.

(9): Bribe or coerce one or more remailer operators into revealing
their keys, or into decrypting the desired messages.  Alternatively, run
many remailers, pretending to be dedicated to privacy, while secretly
gathering information on the messages.

Defense: Use many remailers in a variety of geographical locations, so
that it is unlikely that all of them can be corrupted in this way.


There is another attack scenario, a variation of (9) that
has not really been discussed.

(10)The problem begins with the fact that anonymous addresses are
essentially timeless. While you are safe as long as one remailer is
not compromised ("chain being as strong as its strongest link"), your
anonymous address block is "eternal" in that it lasts as long as the
remailers themselves. 
	Suppose some "determined power" wanted to know who was at the
other end of an anonymous address.  This "determined power" could
coerce each remailer to in turn strip its encryption from the
anonymous address block, and TAKE AS LONG AS IT NEEDED with each
remailer to do this.
	To defend against this, I think remailer secret keys should
expire and BE DESTROYED after a set period of time. When it's time to
expire the old key pair, a remailer could generate a new key pair, and
sign the new public key with the old secret key (assuring it came from
the remailer) and then destroy the old secret key completely. All
remailers would have to do this fairly synchronized, in order for anon
addresses to be useable. (Can't have one key in the chain expiring
unexpectedly).
	Anonymous addresses would then have to be re-generated with the
new remailer keys (and hopefully a new remailer path as well!).

	Hopefully if such a situation ever arose, the keys would
expire and be deleted before the "determined power" could manage to coerce
ALL the remailers in the anonymous address block's remailer chain to
strip off their respective encryption layers.  (coercion/key
theft/whatever..)
(ie "Sorry.. can't decrypt this for you.. the key was automatically
destroyed 6 days ago...")

	This would also help defend against attack #7 by forcing 
the re-generation of anonymous address blocks, with (hopefully)
new remailer chains attached to them.


Other possibilities for increasing the security and the difficulty of
attacks:

(1)	Allow for encrypted header blocks (either in the anonymous
address block or in the sender's encrypted header block) to contain
commands to remailers to split the message into pieces (either just
cutting it up, or ripping it into 2 or more pieces connected by XOR's
or whatever) and send out via different paths (path "forking") to be
reassembled at the end.
	This would make attacks 3,4, and 7 more difficult, and would
not be too bad to reassemble for the anonymous address blocks, but
would be hard to deal with for the sender-anonymity version (at the
receiver end.)


(2) 	Implement a remailer web that is constantly connected via
sockets, with a near-constant-volume encrypted byte stream, with rapidly
changing keys and mixing of fake data and real data.
	This would eliminate the need to pad or batch messages and
would defeat attacks 2,3,4,5,6, and would make attack 7 harder.

	This would also be pretty tough to do, and could put a serious
drain on the computational and bandwidth resources of the remailer
hosts. (student accts would be out.)

Ideas/Comments/Criticisms?

Sorry, this was longer than I thought it would be (trying to be as complete
as I can.)
-Sam