Re: Lurkers: First draft: call for comments (was Re: Paper deadlines)

[Roger Dingledine <arma@mit.edu>]

On Mon, May 06, 2002 at 04:19:19PM +0200, Wouter Slegers wrote:
> Overal: The document is hard to read "standalone", i.e. without prior
> knowledge of the current discussions about remailers security and

Our audience for this paper is people who have read and understood
chaum81, babel, and remailer-essay. I'd like to also include a short
overview of mixes, but I don't think we've got space for it at this
point. Perhaps it should go as a separate document; but I think
familiarity with the literature is a good thing to expect at this point.

> functionality on this list and mixmaster-devel. Besides making it hard
> for an interested reader to get up to speed, it also makes for a shakey
> foundation as the consensus of the discussions on the mailinglists will
> have changed by the time this paper is published. I particularly miss a
> discussion on the reasons for developing a new(er) protocol (i.e. what
> is currently missing in mixmaster) and a short write-up of the

That's a good point. I'll think some more on that.

> protocol-parts that are re-used from mixmaster I/II designs. In
> particular paragraph 3.1 "Indistinguishable replies" is hard to read
> without it.

Hopefully section 3 has changed a bit since you last looked at it.

But the reason we don't currently have much discussion about the details
of mixmaster is because they're not documented anywhere and we don't know
them. So we have no idea what we specifics we're reusing from mixmaster.
Hopefully the paper will spark more discussion about that, and we can
include it in the (longer) spec, which is still to come.

> Section 1 "Introduction": I suggest adding to the argument for
> "seperating the core mixing architecture from these higher-level
> modules, we can limit their influence on the anonymity properties of the
> system", "and allow usage of the Mixminion remailer network for other
> uses then anonymous email exchange" or something similiar to describe
> the idea that the network may be used for other goals.

Done

> Section 2 "Related work" should probably be moved to the end of the
> document. It doesn't add to the understanding of mixminion as such, only
> to differentiate it (but this is only apparent after you understand
> mixminion).

Hrm. This is a tricky one. The related work section is growing to provide
a bit of the background that you were looking for above. Putting it
at the end would have implications, e.g. we'd no longer have defined
\emph{cascade} for the reader. It's a good thing to consider for the
preproceedings revision; remind us about it then. :)

> Section 3 "A MIX-net with Secure Replies":
> As I said, some recap of the working of mixmaster as reused by mixminion
> is nice here, even if only as a picture of the structure.
> I prefer reading the attacks prior to the description of the solution,
> more in a "this is the problem, and this is the solutions we came up
> with"-structure.

i've added a bit more intuition about the need to make forwards and
replies indistinguishable.

> The split-leg-description needs some work, I don't think people are
> going to understand what you are doing without going to the
> mailarchives.

it's true. hopefully we've gotten closer to having it make sense,
with the last day's revisions.

> The cover-trash _is_ dummy traffic?

well, it would be dummy traffic that explicitly looks like a tagged
message (random payload, unreadable second header).

> Section 4 "Related design decisions":
> I suggest adding "of past traffic" after "decryption notices" as some
> countries also have decryption notices that mandate decryption of
> current and future traffic which this rekeying cannot guard against.

done

> Paragraph 4.4 "Message expiration, replay prevention and key rotation":
> I do not understand why the rekeying frequency and the timeperiod over
> which hashes of headers of messages are kept are set equal. It seems to
> me that this links the security of a single node against (legal/hack)
> compromise of its identity to the security of (partial) information on
> the past traffic through that node. Ofcourse t_rekey >= t_hashflush, but I
> can imagine flushing the hashes much frequently then longliving identity
> keys.

I can imagine flushes hash more frequently than longlived identity keys,
but we must take care to never ever allow a replay of a message.

The reason for this is that a replayed message will come out the other
end exactly like it did the previous time. So somebody watching the
links can replay messages once their hashes have expired from a mix,
and break anonymity of past messages. Link encryption helps because it's
not blindingly clear which message is which; but intersection attacks
are still very viable.

So we thought rather than introducing timestamps inside messages to
specify when they're valid, we would instead make a message unusable
after a certain point (in this case, we do a key rotation to enforce it),
and take care to remember hashes of *all* messages we've seen up until
the key rotation.

It's not a perfect solution. I'd like to hear one that's more robust
against the various attacks.

> I think we also need to look at the information that these lists of
> hashes contains, in particular from the point of defense against legal
> attacks (sue for logs).

Interesting point. Well, the presence of a hash in the replay db means
that the MIX encountered a message whose headers hashed to that value,
sometime since the last key rotation. This information is useful to
somebody only via guess-and-check ("did you see this message? what about
this one?"), so if they can't show up with the target message, they can't
learn anything. And if they can show up with the target message, then
by definition they're doing it before the key rotation (else the replay
db will be erased), so the mix is able to decrypt the message for them.

So it sounds like the main attack is to show up with a message, and
confirm ("prove") via the replay db that the mix did in fact preciously
see the message. But note that I'm saying "see" and "encountered", not
"processed and sent out the other side". Eg, the message might have
decrypted to a broken message and been dropped.

Of course, if you've got the message, you can force him to show that it
decrypts to a valid message. But the mix might simply have decided to be
mean and drop it. Here we get into reputation system issues, where the
fact that somebody has a good reputation implies that he probably *did*
process the message in question.

Ok. I should sleep soon. Did I take that in the direction you intended,
or a different one? :)

> With kind regards,
> Wouter

--Roger