Anonymous address problems

[ghsvax!hal@uunet.UU.NET (Hal Finney)]

We've had some discussion of anonymous addressing, which allows
someone to post an address at which mail can be sent to them without
people being able to find out exactly who they are.

I showed how the current remailers could, somewhat clumsily, allow
anonymous addresses.  The problem is, with a single-remailer anonymous
address that remailer sees whom each anonymous address corresponds to,
so you have to trust it.  Now that other encrypting remailers are up
it's possible to have anonymous addresses which go through more than
one remailer before going to the final destination.  This, I thought,
would provide a more secure address since a whole group of remailers
would have to be "broken" in order for someone to find out where a
given anonymous address leads.

However, with the current implementation, there is a security
weakness.  Whomever owns the last remailer in the chain for your
anonymous address can find out who you are.  They do this simply by
sending an anonymous message with known contents, like "test number
1598293".  They then watch all messages going through their remailer,
looking for one whose contents match what they sent.  If they are the
last remailer in the chain, when they see this message go through
them, they can look at whom it is being sent to, and so they then know
your true name.  So, a multi-remailer anonymous address is really no
more secure than a single-remailer one.

Chaum, in his "mix" paper, avoided this problem by having the
anonymous addresses include a random number which each remailer sees
as it decrypts the incoming message.  (There is always such a number,
it turns out, for the RSA encryption to be secure.)  He had the mix,
as it passes the message through, encrypt the contents with a
single-key algorithm (like DES) using this random number as the key.
This way the message is transformed at each step and so if it later
comes back through the same mix, it won't be recognizeable as the one
it sent earlier.  So the attack above fails.

For this to work, the user has to save the random numbers that were
used to construct his anonymous address, and decrypt the message using
DES with these as keys before going on to read it or public-key decrypt
it as usual.  This would be quite a bit less convenient.

Chaum goes on to say that these return addresses can only be used
once.  I was a little puzzled by the exact attack that he is trying to
defend against in applying this rule.  Chaum doesn't always make the
attacks clear, leaving that as an exercise for the reader.  I believe
the problem is that, say, the last remailer in the chain could send 100
messages to a given anonymous address (all would have different
contents).  Then, after working its way through the remailer chain, it
would see 100 messages going to the same final destination.  It could
guess that those 100 were the 100 it sent, especially if it repeats this
test every few days with different numbers.

Chaum's rule of allowing each anonymous address to be used only once
makes them much less useful.

These complications just go to show that real security doesn't come
easy or cheap.  There is still work to be done before we achieve the
goal of crypto anonymity.

Hal
74076.1041@compuserve.com