[messaging] Panoramix decryption mixnet messaging spec and design documents

[Michael Rogers]

On 06/11/17 13:29, Ximin Luo wrote:
> https://www.cs.rice.edu/~dwallach/pub/osdi2002.pdf
> 
> This paper's description of the eclipse attack is as follows:
> 
> "More precisely, routing updates from correct nodes point to a faulty node with
> probability at least f whereas this probability can be as high as one for
> routing updates from faulty nodes. Correct nodes receive updates from other
> correct nodes with probability at most 1 − f and from faulty nodes with
> probability at least f. Therefore, the probability that a routing table entry
> is faulty after an update is at least (1 − f) × f + f × 1, which is greater
> than f. This effect cascades with each subsequent update, causing the fraction
> of faulty entries to tend towards one."
> 
> This argument assumes that nodes have a (very) simple algorithm for selecting
> their neighbours, one that is uniformly random over all offered neighbours. It
> assumes that nodes are unable to use any other information to distinguish
> between faulty vs good neighbours. Indeed, the paper you linked proposes
> various more sophisticated algorithms to defend against the basic attack.
> 
> I actually can't think of a selection algorithm that is less sophisticated than
> "uniform random" and I think it's a bit unfair (and incorrect) to "write off"
> all decentralised systems just because the simplest example one can think of,
> has problems.

I don't think the attack in general depends on uniform random selection.
That's just the easiest case to quantify. The attack applies to any
system with the following properties:

* The potential victim discovers nodes by asking some nodes she already
knows about for other nodes they know about
* The potential victim repeats the discovery process, so the outputs of
one discovery round become the inputs to another
* There are some dishonest nodes
* Dishonest nodes are disproportionately likely to return other
dishonest nodes when asked

The attack also applies if we replace "ask" with "tell", i.e. if nodes
proactively gossip.

Under these conditions, the proportion of nodes the victim knows about
that are dishonest will tend to increase with each discovery round,
unless there's some countervailing tendency for honest nodes to return
other honest nodes.

So if we're asking whether a system may be vulnerable to the attack, and
it has the properties above, then we need to ask whether the system is
doing something to produce that countervailing tendency. In other words,
is it actively preventing the attack?

> Going back to the original issue (epistemic attacks against mixnets), the key
> point AFAIU is to ensure that n ~= N. Whether this is achieved in a centralised
> or decentralised way seems immaterial to me.

The question isn't really the size of the view, but how much overlap
there is between the views of different users. Even if a user has some
way to know the value of N in a decentralised system (which is a hard
problem in its own right), how does she know whether the n ~= N nodes in
her own view are also in other users' views?

In a centralised system, only trusted parties are allowed to contribute
to a user's view of the network (we ensure this by checking signatures
on a consensus document, for example). So it's easy to be sure that all
views are substantially the same.

In a decentralised system, untrusted parties can also contribute to a
user's view of the network (by responding to discovery queries, for
example). Clearly this introduces the potential for the view to be
manipulated. How does the system ensure that doesn't happen?

I'm not interested in writing off decentralised systems any more than
you are, but there's a burden of proof here. Given the existence of a
pretty broad class of attacks that only apply to decentralised systems,
a decentralised system needs to show it's not vulnerable to those attacks.

Cheers,
Michael
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0x9FC527CC.asc
Type: application/pgp-keys
Size: 4660 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20171110/5fbf2d98/attachment.key>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 473 bytes
Desc: OpenPGP digital signature
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20171110/5fbf2d98/attachment.sig>