[messaging] Mixmaster Protocol Design

[Steve Crook]

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.

Steve