[messaging] Mixmaster Protocol Design

[Trevor Perrin]

On Tue, Jul 15, 2014 at 12:27 PM, Tom Ritter <tom at ritter.vg> wrote:
> On 15 July 2014 14:19, Trevor Perrin <trevp at trevp.net> wrote:
>> Side question, for you or anyone:  Is this really the
>> "state-of-the-art" in real-world remailers?  Is no-one working on
>> anything better?
>
> Good lord no.  This is a hack to make Mixmaster still run with some
> semblance of security.

I guess raising the RSA keysize from 1024 is an improvement, but with
4096-bit keys the headers would take ~30x the space of a curve25519
Sphinx, and probably have a worse compute ratio.  You want this to
scale to large volumes of traffic to get a large anonymity set, so I'd
worry about the inefficiency.

The rest of the changes seem like a failed attempt to prevent tagging
attacks via integrity protection.

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

Tagging can be prevented by integrity-protecting all the headers and
message body, so that a tagged message gets dropped instead of
forwarded.  There's a good solution to integrity-protecting headers in
Sphinx, Mixminion, and [1], which any new format should probably
adopt:

The message contains a list of headers, one for each mix that will
process the message, followed by a bunch of dummy headers padding the
list to a constant size.  Each header contains a MAC and also data for
the receiving mix to derive a secret key used for MAC-then-decrypt of
subsequent headers.  A receiving mix processes the first header, then
shifts the headers down one (replacing the first with the old second,
the second with the old third, etc.).  Then it adds a
deterministic-but-random-looking dummy header to the end, so
subsequent mixes can verify their MAC (deterministic) but can't tell
whether it's a real header (random-looking).

(For protecting the body, Sphinx and Mixminion get weird because they
try to make forward messages and reply-block messages
indistinguishable, so they can't do the obvious thing of just MAC'ing
the body.  I've argued that's overcomplex and could be avoided [2]).

> IMO: 'State of the art' in deployed or close-to-deployed would be
> Mixminion replaced with Sphinx as a packet format.

I'd vote for a simpler format than Sphinx, e.g. without the
large-block cipher stuff.


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

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?

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.

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.

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.


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


Trevor


[1] https://eprint.iacr.org/2002/119
[2] https://moderncrypto.org/mail-archive/messaging/2014/000471.html