From: b44729@achilles.ctd.anl.gov (Samuel Pigg)
Date: Sat, 28 Aug 93 03:03:02 PDT
To: cypherpunks@toad.com
Subject: Re: REMAIL: Attacks on remailers (LONG (again))
In-Reply-To: <9308271714.AA11676@ah.com>
Message-ID: <9308280959.AA15615@achilles.ctd.anl.gov>
MIME-Version: 1.0
Content-Type: text/plain


>>>>> On Fri, 27 Aug 93 10:14:19 -0700, hughes@ah.com (Eric Hughes) said:

	Eric> Attack (7) is made by an opponent who monitors all
	Eric> network traffic, but has no access to the insides of the
	Eric> remailer nodes.

	Eric> The defense is more subtle, however, than proposed.

>(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.

	[...]

>making correlations statistically impossible

	Eric> What is the nature of the remailer path, however, for
	Eric> which we have an assurance that the correlations are too
	Eric> difficult to carry out?  Or to ask a simpler question
	Eric> for a simpler environment where we assume all remailers
	Eric> are equal, just how long does the path have to be?

	Eric> We know that by making the paths "long enough" that we
	Eric> can prevent correlations from becoming significant.  The
	Eric> question is how do we find out what is long enough?

>such an attack (PROLONGED monitoring of all
>remailers) would be very difficult to perform, esp. with use of
>remailer-remailer socket connections.

	Eric> The fact that it would be difficult is not the issue for
	Eric> the theory, but for the practice.  The extremely high
	Eric> cost, however, could be justified for 'national
	Eric> security' reasons against a few targets, or to break the
	Eric> system completely open looking for 'tax evaders.'

	Eric> If our theory is good against an arbitrarily strong
	Eric> opponent, then the system can withstand sustained
	Eric> attack.  If the existence of the system is seen as
	Eric> sufficiently threatening, for any number of different
	Eric> threats, we should plan for a sustained attack.  We need
	Eric> to know what the limits of the capability are and not
	Eric> just guess.

	[.. lots of good stuff about privacy diffusion deleted..]

	You are right of course, we can't just hope that it's "good
enough", but I want to ask if this problem of defending against attack
(7) should be considered a problem for the remailer web to handle at
all. I think this should be a problem for the authors of anonymous address
blocks and sender-anonymous headers blocks, and the software used to
do such.
	NOT that this should not be addressed, but it should not be an
impediment to implementing a remailer web. If we delegate resolution
of that problem (as complex a defense as you want) to software to
create encrypted headers, then people can have as good a defense to
this attack as they deem reasonable. (ie protection against this is
responsibility of remail users rather than the remail net.)

	To delegate this responsibility to the remail users, one could
implement the remailers with the ability to process simple commands
that are revealed when the remailer strips off its layer of encryption
of the encrypted header (or anonymous address block).

	The most important command (for anonymous address blocks)
would be instructions to encrypt the message body with with a supplied
key.  This is to defeat the previously discussed problem of trusting
the remailers themselves (run your own remailer and send mail to anon
address, and look for a copy of your message to pass through.)

	A delay function would be useful also. (ie delay(15000) to
tell the remailer to hold the message 15 minutes before sending on.)

	A command that would make analysis more difficult would be a
random function that could be used to randomize aspects of the
message's path, layered encryption, or time delay.

Ex1:

	After removing its layer of encryption from the message header,
	the remailer gets something like (pseudo header with comment
	lines begin with a #):

	random(3,7463)
#     3 choices^    ^seed
	{
	header-block 1
	header-block 2
	header-block 3
	}
#the header blocks would contain the next remailer to use, the
#encrypted header to send along with the message, and the key to encrypt
#the message with (if this is an anonymous address block we are talking about)

Ex2:

	delay(random(20000,9842))

#this would tell the remailer to wait between some minimum and
#20000 seconds to send the message along (along with the seed of 9842 for 
#the random function.



The randomness should be seeded by both the message and the remailer,
and if using randomly selectly keys to encrypt with (from a list),
some indication of which one was used (1, 2, or 3 etc) should be
included with the message, perhaps tacked onto the end of the message
after encryption (in a remailer->recipient data block ?), possibly
encrypted to the anonymous recipient using their key (included in this
layer.)

Commands could of course be nested, to create as complex a routing
specification as desired.

While this may seem overly complicated, most of it could be
handled fairly transparently by the user software.

	This approach ("smart messages") would have the possible
drawback of very large anonymous address blocks (containing multiply
encrypted, command driven headers, path branches etc.)

	A response to this could consist of "anonymous address
servers" which which the user software could, when mailing to an anon
address (ie "anon7462849") query to get the associated anonymous
address block (which being signed by the anonymous recipient would
assure its authenticity) and connect to the first remailer in the
chain as specified by the anon address block, all handled
transparently, possibly including handling sender-anonymity header
work as well.
	This would have several added advantages. The first would be
the simplification of handling anonymous address block- all the user
would need to know is the name and public key of the anonymous persona.
	It would also assist in the remailer key-expiration defense I
proposed previously. The anonymous address server could be synched
with the remailers to erase all the anonymous addresses when the
remailer keys are replaced.

	Anonymous address creation software could be written to grab
the new public keys to all the remailers from somewhere (maybe even
the anon address server itself ?) which were signed with the old
secret keys to assure their authenticity, and construct a new
anonymous address block, which would then be encrypted with the
anonymous address server's key, and submitted to the server via
sender-anonymous mail.
	Anonymous recipients could then also alter their anon address
header as often as they wanted (although being forced to when the
remailer keys expire), changing the path specification to frustrate
statistical path analysis.

	As ideas progress regarding how to defend against statistical
analysis of the message traffic, software to create anonymous address
blocks and construct sender-anonymous headers could be correspondingly
improved, without having to rewrite the remailer software.



I know this appears to be quite a bit of software work, but if and when
we get the protocols agreed upon, *I* will work on it as much as I can,
and I hope others would work on it also (whatever system is accepted/agreed
upon -- be it this or something else.)

The software system I've proposed includes (so far):

Remailers:
	Socket connections for talking to other remailers;
	Encrypt using other remailers keys to insure that
		two identical messages going into a remailer come out
		differently (random session key).
	Ability to handle simple command language and perform operations
		on the message and header. (picking one of several paths etc.)
	Ability to handle all the necessary decryptions- header encryption
		using its pubkey and random session key based encryption
		from previous remailer.
	Message batching (to be combined with "delay" function somehow?)
	Message padding (to be handled inside of encryption-to-next-remailer?)


Mailer:
	Ability to handle construction of sender-anonymous
		nested encrypted headers possibly using command language.
	Ability to communicate with and verify output of anonymous
		address block servers.

Anonymous Address Creation Software:

	Ability to obtain current remailer keys.
	Generate set of random keys for remailers to use.
	Intelligent creation of "smart header" and random anonymous
		mail path(s).

Anonymous Mail Reader:

	Ability to parse message and determine which keys were used
		by the remailers and decrypt layers to get message.


	Such a system would not have to be implemented all at once.  I
think the first steps would be remailer socket communication, and
simple anonymous address and sender-anonymity header construction
software.


Comments/Suggestions/Improvements/Criticisms necessary and welcome.

(yeah I know.. it's easy to "propose" something -- but I'm willing to
actually invest significant effort and time in it also, for what it's worth.)

Sam Pigg                                  "UnAmused" by the USGovCo.
b44729@achilles.ctd.anl.gov     <or>     dt1acaca@cfraix.cfr.usf.edu
PGP Key Fingerprint: ED A7 49 33 65 90 9A BD A4 E4 C5 92 5A 00 BC 6C