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

[Nick Mathewson <nickm@alum.mit.edu>]

On Tue, 2002-04-02 at 13:24, George Danezis wrote:
 [...]
> > 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.

First off, your example of BEAR might be suboptimal.  From
http://citeseer.nj.nec.com/124166.html : 
    The original contribution of this paper is to point out deficiencies
    in BEAR and LION which allow an adversary with knowledge of only
    half the key bits to recover part of the plaintext.  It is also
    shown how a meet-in-the-middle attack can be used as a key recovery
    attack on both BEAR and LION given only one plaintext/ciphertext
    pair.

Second, your claim "that an adversary can extract very little
information" seems superficially false:  If I control nodes 1 and 4 in a
cascade, and I tag an incoming mail at node 1, won't I discover the
recipient when it comes out as bit salad at node 4?  In this
configuration, you only need one per message to link senders and
recipients.
 
 [...]
> > 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)

I half-agree, but am looking forward to see what we get. I think that,
unless we can detect altered messages at each hop, tagging attacks like
the above -- even if they only leak 1 bit per message -- are sufficient
for an attacker to break anonymity.

-- 
Nick