Re: Problems with bit-twiddlers

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

I feel that we should include the results of this discussion in the 
requirements section, because I feel that many others will raise the same 
issues.

The design of MixMinion as it is protects the anonymity of the messages in 
transit. It does not protect its confidentiality or intergity, but only to 
the degree that any of these could compromise anonimity. It also does not 
guarantee that the applications that are going to use it are going to use 
it properly to guarantee the anonymity at a higher level. So MixMinion is 
simply (and it is already not simple at all) an anonymous channel.

On 28 Mar 2002, Nick Mathewson wrote:
> A danger with our current design stems from the fact that (when using
> counter mode) a flipped bit in M results in a flipped bit in E_K(M).
> [...]
> 
> A) In the SURB design I proposed earlier, where the 'To: bob@bob.com'
> portion of the payload is included, an attacker might flip the
> nth-from-last byte of the payload, resulting in a possibility of a
> message sent to 'bib@bob.com'.  That's no good: the attacker could then
> deduce that the SURB was one of Bob's.
> 

Yes it is true that the payload can be hit by an "attack in depth", and 
the modules that implement real systems (like SMTP( on top of MixMinion 
should keep that in mind. Maybe adding a hash to the message, or a MAC 
would do, it depends on how we implement SMPT services.

> B) An adversary controls M1, and M9.  She receives a message at M1 which
> she needs to relay to M2; She suspects that M9 may be the next
> destination.  To confirm this, she flips the 129th byte and forwards the
> message.  If M9 later receives a message whose first byte can be altered
> to give a real header, then the adversary had confirmed her suspicions. 
> No good. 

That is a good one! I will be thinking of this... 

> 
> C) Mallory thinks that a message Alice just sent is heading for Bob.  To
> confirm this, she dances a happy fandango on the probable payload
> portions of Alice's message.  If Mallory can read Bob's mail, she checks
> to see whether Bob is receiving gobbledegook that -- when modified to
> her specifications -- makes sense.  If so, Mallory's won.
> 

This is good too. It does not work for SURBs because they will never be in 
a form that the attacker can distinguish from random noise, but it works 
for the forward path. In particular if the adversary controls the last 
node he can check for tagged messages. This is a fatal flaw that might 
require re-enginnering!

> We thought of a few solutions:
> 
> 1) Every header contains a hash of all of the rest of the message.  This
> won't work for SURBs.
> 

It was in the very original design and got rejected for this reason.

> 1') Same as 1, except that SURB MH just have a hash of the rest of the
> message, up to the last header.  This would allow SURBs to function, but
> make them readily distinguishable from forward delivery.
> 

It will also give away the number of headers that there are. No good.

> 2) Every header contains a hash of the next header.  The last header has
> a hash of the payload.  This won't work for SURBs either.
> 
> 3) Every header contains a hash of the next header.  The last header has
> a hash of the "header portion" of the payload.  The payload's header has
> a hash of the payload.
> 
> This would entail another kind of type specification, where a message
> would be of the form:
>        MH1 MH2 MH3 MH4 E_{K1..4}(CH1 (CH2 (CH3 Content)))
> 
> 4) We discover a magical, efficient, symmetric whitening process, such
> that changes to X have no predictable effect on W(X), and so that
> W(W(X))=X.  This would solve all our problems, but seems unlikely to
> turn up. ;)
> 
> 5) We use something other than counter mode.  This does us no good at
> all, but only ups the block size from 1 byte to something larger.  If
> errors recover in a matter of a block or two, or if they only propagate
> forward, then the attacks above could still be made to work.
> 
I agree that if we do not use chaining (which will make it a nightmare to 
keep the state necessary to decode return addresses) this does not good.

> 
> **Clearly, (3) is the one I liked best. :)
> 


> 
> Can anybody think of any other solutions?  The restrictions are:
>         I. Mallory shouldn't be able to learn anything by modifying
>            messages that he couldn't learn by dropping them.  [One way
>            to achieve this is to somehow ensure that honest nodes drop
>            modified messages.]
>        II. SURBS still need to work.
>       III. It should not be possible for those other than the sender and
>            receiver to distinguish a message sent with a SURB from a
>            message sent via a forward path.
> 

IV. Intermediate mixes should not know their position on the path, neither 
the total length of the path.

> Yours,
> 

I am off to a cafe to spend my day thinking of these quite depressing 
tagging attacks. Some major re-engineering might result from this, but it 
is only for the better. Well done Roger and Nick for the attacks.

Yours,

George