[messaging] Mixmaster Protocol Design

[Tom Ritter]

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.

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 =/

-tom