Reply blocks and tagging protection: a third variant

[Roger Dingledine <arma@mit.edu>]

Ok. I've looked at Zooko's proposal, and I think it will work, but it
wastes half the space. I've looked at George's proposal, and I also
think it will work. A variant of George's proposal follows which is a
bit simpler and I think provides similar properties.

Basically, you have a single integrity-protected header, and for the
most part you don't check the integrity of the payload.

At each step, the mix decrypts the whole thing, verifies the
hash-of-header, generates appropriate junk via the master secret and
sticks the junk at the end of the header. But the trick is that there's
another operation that a mix can do: "strip N". This instructs the mix
to strip N hops from the bottom of the header; it then repopulates the
space it stripped via new junk.

So let's say a header can hold 16 hops. Alice writes a reply block
which uses 6 hops. So the first hop in her reply block has a "strip
10" directive, which at that point pulls off the bottom of the header
(everything but the reply block) and repads it with known junk. That way
the checksums inside the reply block will match at each step, but Bob
(using the reply block) can use whatever hops are unused to ensure his
own anonymity.

We can do George's trick of using the hash of the payload to decrypt
the header at the strip point, to do some integrity checking of the
payload. But note that if we make this hash-of-payload-decrypts-header
step always go along with the 'strip N' operation, then we couldn't
put decoy 'strip N' operations inside a reply block -- because we can't
anticipate the payload. Basically the presence of the strip operation
is a good indicator that a reply block is just starting. But even so,
only one mix gets to know there was a strip.

So say Bob's message to Alice goes through two phases: phase one is the
part where it goes through Bob's anonymizing hops, and phase two is the
part where it follows Alice's reply block hops. An adversary (possibly
working with Alice) could try to learn that Bob is sending to Alice's
reply block (ie, tag his message in phase one). But if he tags the header
at any point, it will get dropped; and if he tags the payload then it
can't decrypt at the strip point. An adversary (possibly working with Bob)
could try to learn where Alice's reply block points (ie, tag the message
in phase two). But since it's a reply block and it encrypts at each hop,
then a tagged message will only be discernable by Alice.

Which leads to the issue of putting destination information in the payload
vs the header. I'm still not convinced by George's statement that it
should go in the payload. First off, it seems hard to put destination
info in the payload of a reply block: I just don't know how it could work
with our encryption system. The guy using your reply block should not be
able to learn (parts of) your delivery info, eg by keeping transport_type
but changing email_address, in order to learn transport_type. Second,
in order for tagged (and thus random) messages to not be recognizable,
some messages must be plausibly all-random. These messages are the ones
that are encrypted to somebody, either a forward message encrypted to
the recipient or a reply message which has been multiply-encrypted. If
the destination info is in plaintext, then these payloads aren't
all-random. So tagged messages are discernable.

Can you clarify your reasoning for putting delivery info in the payload,
George? Do you agree that the above approach is simpler but along the
same lines? Does it lose any properties from yours?

Ugh. It's 7am. I reserve the right to deny this when I wake up. :)
--Roger