[messaging] Mixmaster Protocol Design

Steve Crook steve at mixmin.net
Sun Jul 20 03:14:45 PDT 2014

On Fri, Jul 18, 2014 at 08:55:06AM -0500, Tom Ritter wrote:
> On 16 July 2014 20:38, Trevor Perrin <trevp at trevp.net> wrote:
> > On Wed, Jul 16, 2014 at 4:08 PM, Tom Ritter <tom at ritter.vg> wrote:
> >> If I tag Header 5, I can't recognize the tag unless I'm the recipient
> >> for Header 5.  If I'm not the recipient for Header 4, the recipient at
> >> Header 4 will discard it because it was modified.
> >
> > I.e. the recipient for Header 4 can recognize that the message was
> > tagged.  Which is a tagging attack.
> True. If you tag one past where you think you're going to be the
> recipient, you can detect a bad MAC. Lower layer checksums make it
> pretty unlikely kit's anything but a tag.

I agree, although I'm not sure there is a practical solution.  If
Remailer 1 tags (or corrupts) an outbound message then another remailer
somewhere in the chain must detect that action, that's the very purpose
of the anti-tag hash.  The hash serves to ensure that the final-hop
remailer cannot receive a message tagged by the first hop, thus ensuring
source, recipient and content are not known to a common party (assuming
more than 2 hops per chain).

> Sorry, you're right - it seems safe to say that if a tag isn't
> detected at the very next hop, it will always be vulnerable.
> >> We may be talking past each other.  This is what I'm seeing the problem is:
> >>
> >> Client Constructs twenty headers (let's say 5 of them are real, 15
> >> fake) and computes a MAC for each of them and enclose these MACs in
> >> the first 5 headers.
> >
> > I understand what you're saying, but it's solvable.
> >
> >> Remailer 1 verifies the MACs on Headers 1-20, then tacks on a random
> >> header at the end, and sends it off
> >
> > Instead of doing that, Remailer 1 should tack on a
> > deterministic-but-random-looking header at the end, with contents that
> > are predictable by the initial client so that it matches the MACs for
> > later remailers, but later remailers can't tell whether it's a real or
> > fake header.
> >
> > E.g. in Mixminion, I think Remailer 1 pretends the new header has a
> > ciphertext of zeros and "decrypts" it to come up with the new last
> > header which is sent to Remailer 2.  Remailer 2 does the same thing,
> > etc.
> >
> > See Mixminion paper, section 4.1:
> > http://mixminion.net/minion-design.pdf
> I think I've got this now.  I had to go read the source - according to
> [0] and [1] I think this is actually random data with the output of a
> seed that the client gives to the remailer.
> [0] https://github.com/mixminion/mixminion/blob/master/lib/mixminion/BuildMessage.py#L601
> [1] https://github.com/mixminion/mixminion/blob/master/lib/mixminion/server/PacketHandler.py#L169
> >> Well, AIUI, issues with people actually using it were the brittleness
> >> of remailers going up and down. And I know that the complexity of the
> >> system let to lots of user errors on AAM.  The security issues like
> >> intersection attacks are great reasons it's not a good idea - not
> >> reasons it failed in deployment and use.
> >
> > Good to know, thanks.  I'd love to hear more overview / history of the
> > remailer networks and what the obstacles are to wider deployment, if
> > you or Zax have more thoughts.
> I've always thought it was a PITA to set up and run your own
> mailserver - but Mixminion middle-nodes don't require that, and we
> still don't see more of them =/

I think the Mixminion network is completely dead at the moment.  The
last server node with exit capabilities shutdown a few months ago.  I'd
love to see it resurrected but there's a significant amount of work
required by a competent programmer with anonymity skills.  The number
of people who fit that criteria is less than those capable of
maintaining and enhancing Mixmaster, and so it lives on.


More information about the Messaging mailing list