[messaging] Mixmaster Protocol Design

[Steve Crook]

On Sun, Jul 20, 2014 at 08:32:37AM -0500, Tom Ritter wrote:
> On 20 July 2014 05:14, Steve Crook <steve at mixmin.net> wrote:
> > 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).
> 
> I'd make these statements more generic in a few ways.
> 
> > "another remailer somewhere in the chain must detect that action"
> 
> Not just 'somewhere in the chain' - it's got to be the very next hop
> _and all subsequent hops_ after the attacker-hop.
> 
> If the N-th hop is controlled by the attacker, and N+1 is not - N+1
> must detect the tag and drop the message.
> 
> If the N-th and N+1 hops are both controlled by the attacker - there
> is no need to tag, it can track the message trivially. But if it did
> tag at N, recognize the tag at N+1 but not drop it - then if the tag
> is still propogating N+2 (not attacker controlled) must detect and
> drop.
> 
> > "The hash serves to ensure that the final-hop remailer cannot receive a message tagged by the first hop"
> 
> Anti-tagging defenses should ensure that any N+Mth server (M>=1) can
> detect a message tagged by the Nth server.  Focusing on the 'first'
> and 'final' hops was my mistake. While it's less useful to tag an
> inner route (say, if you're hop 2 of 5 and you're trying to figure out
> if you're 4 of 5 also) - but it's still a valid attack we should
> defend against.

Hi Tom,

Thinking about that in Mixmaster terms, the original spec calls for each
hop to individually encrypt each subsequent 512 Byte header and the
Payload.  If an alternative approach was used and the headers were all
encrypted as one, we could ensure that any tagging resulted in complete
corruption of the remaining headers (using AES-IGE mode).

Each remailer appends a fake header to the bottom of the message which
would corrupt decryption from that point on.  I don't believe this
matters as no real headers exist beyond the fake.  The payload is
encrypted as a separate (10240 Byte) operation, thus immune from
corruption from the fake headers.

This has an added benefit that the Encrypted Header component doesn't
need to store 19 IVs.  Instead, only 2 are required: Payload and Header.
If AES is used, that saves 17 * 16 Bytes per header.

> > 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.
> 
> I disgaree that competent programmers with anonymity skills are not
> required to maintain Mixmaster - as evidenced by the tagging attack
> Trevor found on the proposed anti-tagging defense.
Sorry, I wasn't meaning to imply that Mixmaster doesn't require
anonymity skills.  Rather that implementation of the specification is
much simpler than in Mixminion or Sphinx.  Producing a secure
specification remains of paramount importance.

> Maybe it's the clients? Mixmaster has Windows GUI clients - Mixminion
> does not?
That is indeed a significant difference.  It's also very hard to gauge
the number of Mixmaster users (without spying on incoming connections).
It could be a small number of very vocal contributors.

Steve