[messaging] Mixmaster Protocol Design

[Tom Ritter]

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.

> 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.

Maybe it's the clients? Mixmaster has Windows GUI clients - Mixminion does not?

-tom