[messaging] Mixmaster Protocol Design

[Tom Ritter]

On 15 July 2014 21:14, Trevor Perrin <trevp at trevp.net> wrote:
> The rest of the changes seem like a failed attempt to prevent tagging
> attacks via integrity protection.

Why do you say it fails?  If each Mix Header authenticates the next
(as opposed to each header authenticating every single header), when a
message transits an attacker-uncontrolled node, it will be discarded
as the next header was corrupted. (Each header also needs to
authenticate the body.)

What's more, I think if you authenticate every header in every header,
you disclose the path length. You can't authenticate a random header
added at the end in the next hop, so when you receive a message that
only authenticates 17 of the headers, you know where you are in the
chain.

> (For context: a "tagging" attack means a message is marked somehow
> prior to entering a "mix" which will unwrap a layer of encryption from
> the message and hold it a random time before forwarding it.  If the
> mark can be detected afterwards, such as by a failed integrity check,
> then an attacker could learn that an output message corresponds to a
> particular input message).

More Context: https://crypto.is/blog/tagging_attack_on_mixmaster


>>  Pynchon Gate is
>> also state of the art in nymservers, but is undeveloped.
>
> Unclear to me whether multi-server PIR (like Pynchon Gate) is
> practical for a "nymserver", or even whether nymservers are that
> useful.
>
> The original idea for nymservers, I think, is that they would store
> "reply blocks" associated to a user's email address, where each reply
> block is a set of mix-headers for routing a message to Alice.  When
> the nymserver receives a message for "alice at nymserver.whatever" it
> would attach a reply-block to the message and forward it through the
> mix net.  Because of the onion-like nature of each reply block,
> Alice's identity would be hidden even from her nymserver.

Yes, this is Type I or GHIO nymservers.  The Reply Blocks became
extraordinarily complex, with latency commands and duplication
commands, etc.  They're brittle, and intolerant to the removal of
nodes from the remailer network.  (Contrasted with Tor, where if a new
node comes up or goes down, the consensus is updated every hour.)

> If the nymserver use a multi-server PIR system to deliver messages to
> Alice (Pynchon Gate), instead of reply blocks, then Alice's identity
> is hidden from the system as long as one of the PIR servers is not
> colluding with the others.  But this requires an additional
> infrastructure besides the mix net, consisting of PIR servers that are
> coordinating but are run by different parties to ensure trust.
> Moreover, Alice's anonymity set is only those users who are
> communicating with the same PIR system, so you may want this to be a
> centralized system that everyone uses.
>
> So that's a hard thing to setup.  How useful is it?

I agree it's hard to setup, but if you want an anonymous system, I
think it needs to have a network of mutually distrusting nodes working
in concert. If you choose colluding nodes, your anonymity is broken,
but if not you achieve it.

I'm not too familiar with Bitcoin mining, but as I understand it, you
can mine blocks on multiple blockchains at once.  Imagine two Tor
networks, one run by Tor Project, and the second run by CCC.de.  A
node could run on both networks, and it'd not be apparent which
network you were using if you talked to it.  Similarly, the
distributors in Pynchon Gate could be distributors for multiple
nymservers.


> For "relationship-hiding", nymservers aren't needed:  Alice and Bob
> just need to send "forward" messages through the mix net to each
> other's mailbox servers.

Agreed.

> For "identity-hiding", if the anonymous party has some initial way to
> deliver a reply-block to the other party, they can bootstrap from that
> and exchange reply blocks directly, so nymservers are also not needed.

Barring the brittleness of Reply Blocks, agreed.  Although if one
wanted to be anonymous, having a SMTP-based mailserver is not as good
as having a .onion-backed mailserver or Pynchon Gate-backed address.

> To be sure, it would be nice to have anonymous pseudonyms that anyone
> could send messages to - this is sort of the high-latency messaging
> analogue of a Tor hidden service - but in light of how hard this seems
> to build, it's worth noting we can do a lot without it.

We can do a lot without it, but if we had it, we could do all those
things and more.

>> There's also an unpublicized twitter-based remailer system using
>> Sphinx I believe.  I can't recall which academic published it in the
>> last 2 years, but I swore it was a fairly well known person who had
>> put it on the back burner before developing it more...
>
> I think you mean Ibis, which I don't think has been officially presented yet -
>
> https://crypto.stanford.edu/seclab/sem-12-13/goldberg.html
> https://ibis.uwaterloo.ca/

That was it!

-tom