Re: tagging attacks and forward-message/reply-message distinction

[Roger Dingledine <arma@mit.edu>]

On Wed, Apr 03, 2002 at 06:51:48AM -0800, Zooko wrote:
>  --- proposed improvement
> 
> At a cost of two times message expansion, we can combine both kinds of messages 
> in such a way that each node in the chain cannot tell whether it is processing a 
> forward-travelling or reply message.

We want this property, but we also want another property: we want to
prevent the person using the reply block from learning where it leads.
That's where the below design breaks down.

> When the message is a forward-travelling message, then the actual message (and 
> reply block) are hidden inside the encrypted A-payload.  When the message is 
> a reply message, then the message is hidden inside the encrypted B-payload.  But 
> what is the contents of the A-payload when the message is actually a reply?  It 
> is dummy garbage which looks like an encrypted payload, and which matches the 
> MACs that the original sender included in the reply block!
> 
> Where did the replier gets this dummy A-payload?  It is generated 
> deterministically by the replier from a secret that the original sender included 
> along with the reply block in the original A-payload.

It seems very hard for the person using the reply block to come up with
the dummy A-payload without being able to recognize it down the road.

One approach: the author of the reply block could ship a valid A-payload
along with the reply block. But the problem there is that we can't
package MixMinion packets within MixMinion packets. That is, there's
no way to get the reply block to the other guy in a single packet. I
guess we could do more than one, but that means people can't talk have a
conversation where they're both anonymous to each other because it would
be too hard to get reply blocks back and forth. It's like talking with
one-time pads and exchanging the pads too.

Another approach (the one above): the author of the reply block gives
some hints along with the reply block, to help the guy using it come up
with a valid A-payload. If this hint is in the form of symmetric keys,
hashes that are supposed to match at each hop, and a random seed to
generate the initial payload before encryptions, then the person using
the reply block can generate a valid A-payload, but he can also recognize
it at each layer: collaborating with some nodes in the mix-net, he may
be able to trace its path.

There may possibly be a neat encrypted-function approach whereby the
user of the reply block can generate an A-payload such that upon each
decryption it hashes correctly but he does not know any of the hashes
or any other identifying features of any version of decrypted text. But
that sounds really hard -- effectively you need to take a seed, use
it to generate a payload-sized hunk of text, multiply encrypt it,
and then find some seed which characterizes the encrypted text. So
basically it's like approach one above, except you're compressing the
random-and-thus-uncompressable payload which otherwise you'd have to
transmit in full.

Did you have something in mind here? I might be wrong; I haven't
gone through and proved it impossible based on common crypto hardness
assumptions. But it seems amenable to such a proof.

--Roger