On reply blocks and tagging attacks (was Re: Problems with bit-twiddlers)

[Roger Dingledine <arma@mit.edu>]

Ok. I'm going to try to summarize the problem here, to make sure I've
got it right.

Our goal is to do reply blocks without losing anonymity.

First a description of simple forward-only messages, to make sure I have
them straight. (Do I?)

Alice wants to send a message M through 1 and 2 to Bob. So she constructs
a blob.

When 1 gets the blob, he decrypts the outer header (it's the top 128
bytes; it is encrypted to his public key). Inside, he learns the next
hop and shared secret (shared between Alice and 1; we call it the master
secret). There's also a hash which he can use to verify that what he
got has not been tampered with. (Alice creates this hash by taking the
message 1 should be looking at, zeroing out the entry where the hash
will go, hashing the overall thing, and then putting the hash in.)

1 then strips off the header he was just reading; decrypts the
remaining blob with a symmetric key that's a function of the master
secret (say, hash it with a constant string) so its appearance
changes; and adds padding to the bottom of the message. This padding
is similarly deterministic based on the master secret (say, he
symmetric-encrypts a block of 128 zeroes with a key that comes from
H(master-secret,"for padding")).

Because all of the operations 1 does are deterministic, Alice can
work through them backwards herself to make all the hashes correct,
etc. Once 2 does its payload-decrypt, it's got a message that it can
send to Bob. Any mix that detects a tampered message must drop it:
tagging attacks are stopped. So far so good.

(There's also stuff like replay detection; I don't need to get into that
here though.)

However, it's hard to extend this design to reply blocks -- the author
of the reply block does not know the payload, so he can't guess valid
hashes. Without hashes to ensure integrity, we're open to the message
tagging attacks we described earlier.

A variant of the above which allows reply blocks and is mostly resistant
to message tagging attacks involves separating the header from the payload
somewhat. Basically we set a fixed-size header block (with room for, say,
16 header structs). Each header then has the master secrets/etc as above,
but the hashes are not over the payload, just the header block. When
a header is stripped, 128 new predictable-but-random-looking bytes
are placed at the bottom of the header block. So while the payload is
decrypted at each hop (by a function of the master secret), it basically
just goes along for the ride.

Because there aren't any hashes to ensure payload integrity, the adversary
can stomp on it whenever he likes. However, assuming it stays encrypted
all the way to Bob, the adversary can never detect stomping downstream of
an honest mix. This assumption is quite strong: we assume we're encrypting
to Bob, and we assume the message has *no* predictable parts (we can allow
the final mix in the chain to put useful things like "Mimetype PGP" and
"Dear Bob, this is a MixMinion message" in). Even then, bad-guy Bob could
be working with the adversary to discover Alice's identity. In any case,
plaintext messages will be vulnerable to tagging attacks, but only if
the adversary can observe the message going to Bob (simply having two
nodes somewhere in the path and bridging the mixes in between won't
work anymore).

(If we want to allow people to use the reply block anonymously, we
might declare that only the first 8 of the 16 hops can be pre-filled;
thus the sender can add up to 8 more before he sends it. Intermediate
hops can still add a single bonus hop a la Babel, but not more than one.)

It really does seem like we simply need better crypto here. One approach
is the all-or-nothing transform George is investigating, to transform
the payload at each hop in a way that will totally destroy it if it's
modified (thus looking for the tag later on will be fruitless). Let us
know how that goes, George. :)

Another would be to use trapdoor/chameleon hashes -- basically we
deliver some secrets along with the reply block that will allow the
responder to fill in the correct numbers in the headers even though
he doesn't really know what he's doing. This seems fundamentally hard
to get right because Bob might be an agent of the adversary. (This
whole 'agent of the adversary' thing is what keeps us from having Bob
include a payload-secret, specify payload-hashes, and thus ensure payload
integrity at each hop.) But perhaps some encrypted functions would still
do the trick.

Hard problem. I'm becoming more convinced that the correct solution is
to strengthen our notion of 'encrypt' until the problem goes away.

--Roger