[messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

> Hi David,

Hi Trevor,

> Hope you don't mind belated comments:

That's a very thoughtful message you have written and I really appreciate it.
I'm hoping my mixnet design collegues will join this discussion because they
have lots of ideas on the subject and our specs are filled with many tradeoffs
that we made for the constraints of this particular project.

> This is an ambitious protocol stack!  I think the different layers and
> choices are something like:
> 
> Mix packet format = Sphinx
> Mix strategy = Poisson Mix (a simplified "Stop-and-Go Mix")
> Mixnet topology = Stratified
> Dummy traffic strategy = Loopix
> Reliability/retransmission = Stop-and-Wait ARQ
> Congestion control = "Source Quench" from mixes to providers
> Link protocol = TCP/Noise_XX
> End-to-end protocol = Email/Noise_X

yeeup that's right. I would also mention that our noise-based wire protocol
uses the NewHope_Simple handhshake (which we should later upgrade to Kyber).
I added the "rekey" feature to the go noise library.

In Yawning's noise fork he added the NewHope_Simple handshake here:

https://github.com/Katzenpost/noise

> It's interesting to see everything needed for a full mixnet architecture.
> I imagine these decisions might be different for different applications, so
> I hope you're building modularity between components.

Indeed we are building modular components, it's really the only way to
write decent code. For instance here's our wire protocol:

https://github.com/Katzenpost/core/tree/master/wire

and here's Yawning Sphinx implementation:

https://github.com/Katzenpost/core/tree/master/sphinx

The client is still in a very rough draft state here in the develop branch:

https://github.com/Katzenpost/client/tree/develop

> "Sphinx" and "Stop-and-Go mixes" seem particularly reusable within
> different architectures.  High-quality specs and code for them would be one
> great outcome here.

Yes we are striving for high-quality specs and code. So many years after the Sphinx
paper was written we finally have a Sphinx spec:

https://github.com/Katzenpost/docs/blob/master/specs/sphinx.txt

I think our other specs are pretty good too. Although we did not yet specify
decoy traffic because we plan to do that in another research and dev cycle
based on traffic statistics of legit traffic within the closed group of "Providers".

> (Though there's room for debate even within those components.  For example,
> SURB support in Sphinx adds complexity and requires an unusual
> "large-block" cipher.  SURBs don't seem necessary for Loopix, and I've
> wondered whether dropping SURB support would make things simpler [1])

Yes! I have discussed this subject extensively with many people. Our
design can *easily* be adapted to a totally different application
that will NOT require SURBs even if reliability of message transmission is
required e.g. "send zcash transaction to the blockchain over the mixnet".

In the case of this zcash mixnet transport, the client sends a zcash transaction
and then after the total Poisson mix route delay checks the blockchain for their
transaction. If the transaction is not present, retransmit!

This is essentially a Stop and Wait ARQ that uses a broadcast mechanism instead
of ACKnowledgement control messages.

I agree, in the Loopix design SURBs are not needed. Even the "decoy loops"
do not need SURBs:

1. clients send decoy loops to their Provider, the message is
routed through a series of mixes, one mix in each layer of strata and then to
the same Provider and finally back to the client.

2. mix decoy loops also do not need SURBs: the mix sends the message and it
gets routed through each layer of strata until it reaches a Provider which
subsequently routes the message back into the mix layers until it reaches
it's origin mix.

On the other hand the Loopix design as described in the paper does not
include any message reliability mechanism at all. In our design we do
not use the SURBs to achieve any identity-hiding property like
Mixminion does. Instead we only use SURBs to send ACKnowledgements in
our Stop and Wait ARQ protocol from Client to Provider.

> Anyways, the hardest decisions are probably around "mixnet topology" and
> "dummy traffic", since this is where real-world economic and deployability
> concerns come in:
>  * Who is going to run mixes?

For this particular project the Providers will be LEAP e-mail providers
who will also operate one or more mixes. (we are not even trying to make a
Tor-like volunteer run mixnet)

>  * How tolerable are latency and dummy-traffic requirements for real users?

Good question! I have a link to a paper which is relevant:

Obstacles to the Adoption of Secure Communication Tools
https://www.ieee-security.org/TC/SP2017/papers/84.pdf

This paper seems to indicate that the primary obstacles are lack of
interoperability and low quality of service. In the case of mixnets I
strongly believe that unreliable message delivery contributes just as
much to low quality of service as does high latency. We hope to
address all of these obstacles in our design, especially the
unreliable message delivery which I think is totally unacceptable in
a cryptographic messaging system.

> The Loopix paper [2] presents examples with:
>  * Several independent mix nodes
>  * A server acting as "provider" for each few hundred users
>  * Each user sending a dummy message every few seconds (or faster!)
>  * Each user downloading messages or dummy traffic from their provider at a
> constant rate
> 
> Those all seem like difficult requirements for real systems, so I'm
> wondering about your thoughts on near-term deployment.

The specifics for how to do decoy traffic will depend on the amount of
legit traffic and desired mix anonymity set size... Also this subject
would be best discussed by my design collegues such as Ania
Piotrowska, Claudia Diaz and George Danezis.

Once we've deployed a mixnet without decoy traffic, we can take messurements
and perform experiments to determine optimal decoy traffic profiles.

> In general, the security vs. practicality tradeoffs seem pretty brutal for
> mixnets.  Most papers (like Loopix) push the slider towards the security
> end so they can achieve their security goal, but with parameters unlikely
> to be deployed at any scale.  I'd be more interested in the opposite sort
> of analysis: how much security can be eked out of "minimum viable"
> deployments.
> 
> Anyways, those are scattered thoughts.  It's great to see people working in
> this area, keep us posted!

Yes, however unpopular compared to Tor, I think it's important because we at
least have a powerful threat model such that a sufficiently global adversary
that can easily break Tor doesn't get to easily break our mixnet. Well, that's
the idea anyway. Our design is not fully baked and isn't yet fully implemented,
has no decoy traffic etc.

Additionally, I think this points us towards the fact that often times the decision
to work on a given crypto project is not an intellectual decision but rather the
result of a popularity contest.

I think it would be great if there was much more diversity in practical deployed
anonymity networks (aka location-hiding networks), instead of our current situation
where the world's very best is only Tor and nothing else even comes close.
(to be clear i'm a huge fan of Tor and i have been very inspired by both Nick and Roger)

> Trevor
> 
> [1]
> https://moderncrypto.org/mail-archive/messaging/2014/000456.html

Replying to Brian Warner's comment on SURBs:

Actually SURBs *do* have an expiration. The mix routing key rotation causes a SURB to expire.

> https://moderncrypto.org/mail-archive/messaging/2014/000471.html
> 
> [2] https://arxiv.org/pdf/1703.00536.pdf
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20170916/b758be63/attachment.sig>