stream ciphers and mutability

[Roger Dingledine <arma@mit.edu>]

This issue is a variant of the tagging attack, as brought
up during the Bandwidth Throttling (threat model) thread on
http://archives.seul.org/or/dev/Jul-2002/threads.html. The fundamental
problem is that there's no integrity-checking on the data in the cells.

The issue I brought up before is that an adversary could squash a byte
at one end of the circuit, and then look for a squashed byte coming out
of the onion routing network somewhere else. That's a pretty weak attack
compared to, eg, packet counting or timing attacks.

But since the layered symmetric crypts are just xor'ed into the plaintext,
and indeed even the link encryption is currently OFB, there's a much
stronger attack (thanks to Nick for pointing this one out).

Imagine a node (*or even observer*) early in Alice's path guesses what
website Alice is going to. The first data cell down the circuit is a
'topic begin' cell, which includes "address,port" of the destination
website. Since all the encryption is just by xor, our adversary simply
xors out the guessed website, xors in the replacement website, and wham,
Alice is going somewhere else. This helps both to confirm a guess,
and also to give Alice the wrong pages (possibly subtly wrong pages).

Now, the attack is a bit more difficult with topics, since an observer
won't be able to tell which data cells are topic begins; but it's a good
guess that the first one is. (Topics actually help quite a bit, because
one of the best ways to guess what Alice is websurfing is by watching
successive queries, and doing website fingerprinting by size, timing,
etc -- by merging all requests into one data stream that becomes a bit
trickier.) It's also more difficult with zlib compression, because you
have to replace the address with one that compresses similarly; but I
don't think that's impossible.

Would it be worthwhile to include some randomness plus a sha1 hash,
in topic begins, to resolve this particular attack, recognizing that it
doesn't resolve it in general?

Since connections between ORs and OPs speak cells, they always communicate
in 128 byte chunks. We could switch our link encryption cipher from a
stream cipher to something that requires n-bit chunks and breaks if a
byte is flipped. That way an observer couldn't do this attack (or other
tagging attacks) so easily.

There's a bigger issue here, which is that the exit node can lie to you,
give you a subtly modified page, etc. I'm not sure how to resolve that
without a wider integrity-oriented infrastructure. How do people handle
that who use public (or country-wide) web proxies? What about Akamai?
There are some solutions that have come out of the p2p space for ensuring
integrity from an untrusted delivery agent. The simple example there is
that you name a file by its sha1 hash, and then it's clear if somebody
handed you a modified/wrong file.

--Roger