stream ciphers and mutability

[Marc Rennhard]

> 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?

Definitely. At least it's somewhat cleaner. Even if you use block
ciphers (see below) where one flipped bit in the cphertext means 
complete garbage when decrypting the plaintext, it seems 'cleaner'
to solve that by the protocol itself than to relay on a 'higher level
garbage detector' that sees that the payload dose not really look
like, e.g. an IP-address/port.

If you are conserned about space requirements for the hash, then I argue
that you don't even need to include the whole hash; some bytes of it
are fine; because even using only the first 4 bytes of the has means
that flipped bits are recognized with probability 1 - 0.5^32. Since
you cannot offer perfect anonymity anyway, one could live with that.
And also, the hash costs some cycles, but that's not really a problem
because the performance of an or is usually bounded by its bandwidth
anyway.

In MorphMix, my headers (between two nodes and end-to-end) are 16 bytes
and include a 10-byte checksum. The checksum is built by concatenating
the left 10 bytes and the right 10 bytes of a sha1 hash over the header
and the payload. Yes, 10 bytes is a lot, but since I'm using AES, I work
on 16-byte blocks, and since my packets are 512 bytes long, I can live 
with 32 bytes total overhead per packet.

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

I have come to the conclusion that stream ciphers are not a good idea
for or-style protocols, simply because you can so easily flip bits
through the disguise. In the Anonymity Network, I used RC4, mainly
for speed reasons (with 128-bit keys, it's about the fastest cipher 
out there), but I'll switch to AES in MorphMix. Despite speed, you
lose a bit of flexibility because your header/packet lengths should
be a multiple of the block size, which is often 8 bytes (16 with AES).
Using the block cipher in CBC mode is a good idea, too, since this
beats reply attacks (re-sending a packet into a mix and looking where it
goes) without having to employ sequence numbers or having to store the
n least recently seen packets. 

--Marc