Re: On reply blocks and tagging attacks (was Re: Problems withbit-twiddlers)

[George Danezis <gd@theory.lcs.mit.edu>]

On Tue, 2 Apr 2002, Roger Dingledine wrote:

> Ok. I'm going to try to summarize the problem here, to make sure I've
> got it right.
>
> []

ok, we are in sync up to here.

> 
> Because there aren't any hashes to ensure payload integrity, the adversary
> can stomp on it whenever he likes. However, assuming it stays encrypted
> all the way to Bob, the adversary can never detect stomping downstream of
> an honest mix. This assumption is quite strong: we assume we're encrypting
> to Bob, and we assume the message has *no* predictable parts (we can allow
> the final mix in the chain to put useful things like "Mimetype PGP" and
> "Dear Bob, this is a MixMinion message" in). 

This is assuming that the payload is encoded using a stream cipher and 
XOR. In order to avoid this attack we can use a variable length block 
cipher like BEAR. The high level property of BEAR is that Encryption and 
decryption ARE symmetric (and equally secure) as we need, but if any bit of 
the input is changed then the output is random (for someone that does not 
know they key). That means that at the end, when the message should be "in 
plain" only 1 bit of information is leaked: is the message is plain or 
does it look random? Therefore an adversary can extract very little 
information from this kind of tagging.

> Even then, bad-guy Bob could
> be working with the adversary to discover Alice's identity. In any case,
> plaintext messages will be vulnerable to tagging attacks, but only if
> the adversary can observe the message going to Bob (simply having two
> nodes somewhere in the path and bridging the mixes in between won't
> work anymore).
> 
> (If we want to allow people to use the reply block anonymously, we
> might declare that only the first 8 of the 16 hops can be pre-filled;
> thus the sender can add up to 8 more before he sends it. Intermediate
> hops can still add a single bonus hop a la Babel, but not more than one.)
> 

This is very difficult to do since the creators of the two headers cannot 
know the secrets inside the others in order to compute the hashes. 
Suddenly the only architecture to bridge between normal and reply modes are 
special modules.

> It really does seem like we simply need better crypto here. One approach
> is the all-or-nothing transform George is investigating, to transform
> the payload at each hop in a way that will totally destroy it if it's
> modified (thus looking for the tag later on will be fruitless). Let us
> know how that goes, George. :)
> 

[the answer is above, sorry]

> Another would be to use trapdoor/chameleon hashes -- basically we
> deliver some secrets along with the reply block that will allow the
> responder to fill in the correct numbers in the headers even though
> he doesn't really know what he's doing. This seems fundamentally hard
> to get right because Bob might be an agent of the adversary. (This
> whole 'agent of the adversary' thing is what keeps us from having Bob
> include a payload-secret, specify payload-hashes, and thus ensure payload
> integrity at each hop.) But perhaps some encrypted functions would still
> do the trick.
> 
> Hard problem. I'm becoming more convinced that the correct solution is
> to strengthen our notion of 'encrypt' until the problem goes away.
> 

I agree and I will try to write something up by tomorow evening (UK time)

Yours,

George