Bandwidth throttling (was Re: Padding)

[Roger Dingledine]

On Fri, Jul 05, 2002 at 07:57:54PM -0400, Roger Dingledine wrote:
> Since there are no checksums on the payloads, another attack is to modify
> the payloads on data cells Alice sends, or even to simply fabricate a
> huge pile of data cells and send them downstream. Bob will suddenly start
> getting garbage text.

I suppose now's a fine time to introduce the notion of \emph{tagging
attacks} as developed in the Mixminion design document:

|A {\em tagging attack} is an active attack in which a message is
|modified by altering part of it (for example by flipping bits), so
|that it can be recognized later in the path.  A later MIX controlled by
|the attacker can recognize tagged messages because the header does
|not conform to the expected format when decrypted.  Also, the final
|recipient can recognize a tagged message for which the payload has
|been altered.

Specifically, it looks like most stream ciphers we might use will
introduce a really nasty vulnerability: even though a given node can't
read the payload of a data cell, he can tweak a byte and watch for a
single tweaked byte coming out of some exit node. Worse, he can xor a
portion of a data cell payload with some string he knows, then watch for
anomalous bytes of that length coming out of an exit node which, when
xored with the string, look normal again. (I say 'most stream ciphers'
because we may be able to find a stream cipher that produces total
garbage at every point after the first tagged byte. This is comparable
to Mixminion's use of Lioness, an all-or-nothing variable-length block
cipher. But even then, we simply reduce the drama of the attack; a
slightly weaker variant is still possible.)

Drawing from Mixminion, here's the beginnings of a solution:

* Introduce hashes in forward cells to verify integrity. Since we're not
pulling off pieces off the payload and replacing them with deterministic
garbage (like we are in remailers), then we just have a "hashes"
section in each cell. At 2 bytes per hash, this is maybe 22 bytes (I
don't remember what the max number of hops is). This is obnoxious, but
not devastating. At each hop, you decrypt the hash section, decrypt the
length, decrypt the payload, and then hash the payload and verify that
the first two bytes of the hash match the first two bytes of the hashes
section. (If not, drop the packet.) Now remove the top two bytes of the
hash section (move it all up by two bytes), and put two bytes of garbage
at the bottom. The hashes section is not integrity-checked, but since
the adversary doesn't know the keys at each hop, he can't craft *any*
payload and hashes section that match unless he's quite lucky. (Thus he
is also prevented from creating new data cells and inserting them into
the stream.)

* Cells in the backward direction cannot include hashes, because the exit
node doesn't know the appropriate keys. But since we can distinguish
forward from backward streams [1], we simply don't require hashes on
backward streams. This lack of integrity is acceptable because we're
*encrypting* the payloads at each point -- so only the sender will be
able to recognize tagging.

* Reply onions are a bit harder, but they may well be salvageable too.
We'll tackle that one down the road.


[1] Speaking of which, this allows a node anywhere in the circuit to
watch patterns of forward vs backward cells, and get a good idea of
what protocol is being spoken on that circuit. Yet another thing to keep
in mind.

--Roger