Problems with bit-twiddlers

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

[From a conversation with Roger.]

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).

I've got to pack to leave for Connecticut for the weekend, so I won't be
able to discuss this at length, but here are a few messy scenarios:

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.

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. 

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.

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.

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.

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.


**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.

Yours,
-- 
Nick