[messaging] Mixmaster Protocol Design

[Trevor Perrin]

On Wed, Jul 16, 2014 at 12:20 PM, Tom Ritter <tom at ritter.vg> wrote:
> 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.)

The message won't be discarded if a later header is tagged.


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

The "random header added at the end" should be
deterministic-but-random-looking so it can be MAC'd yet can't be
distinguished from a real header.  That's what I was trying to
describe in my last mail.


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

Was bookkeeping complexity and brittleness-in-case-of-network-changes
the main problem with reply-block nymservers, or was it security
issues like:

http://archives.seul.org/mixminion/dev/Oct-2007/msg00010.html

?


>> 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 agree, I'm just pointing out it's a complex, costly, and
probably-needs-to-be-centralized infrastructure to setup *in addition*
to setting up a high-latency mix net.


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

I guess, but this still means everyone has to agree to use the same
distributor nodes, or else user choice of their distributors will
partition users into potentially-small anonymity sets.  So I think
this implies Pynchon Gate would need to be a centralized
infrastructure, which brings a bunch of downsides.


Trevor