[messaging] Panoramix decryption mixnet messaging spec and design documents

[Ximin Luo]

Michael Rogers:
> On 01/11/17 01:40, Ximin Luo wrote:
>> After a quick web search on "epistemic attacks", the main paper I can find [1] has the result that attacks are very strong if each node only knows about a small fraction (n nodes) of the whole network (N nodes).
>>
>> They lay the motivation for this assumption (n << N), by describing a discovery-based p2p network where each node "samples" (i.e. directly contacts) a small fraction of the network. This is equating with mere "knowledge" of a node, so that the act of "sampling" an attacker-controlled node, gives them (or a GPA) the ability to know exactly which nodes "know" the target node.
>>
>> The paper does not seem to consider the possibility that nodes could discover more of the network without directly sampling every node, e.g. via gossip with their neighbours on "which other nodes exist".
> 
> The eclipse attack is relevant here. Briefly, if you discover nodes by
> asking each node you know about which other nodes it knows about, an
> attacker who controls some fraction d/n of the nodes can control a
> larger fraction of your view, because honest nodes return a sample with
> d/n dishonest nodes on average, whereas dishonest nodes can return a set
> containing only dishonest nodes.
> 
> If node discovery is ongoing - for example, if you replace nodes in your
> view that have gone offline by discovering more nodes - then the
> attacker can eventually control your whole view.
> 
> (This is from memory and may be inaccurate, it's been a long time since
> I read the paper.)
> 
> https://www.eecs.harvard.edu/~mema/courses/cs264/papers/eclipse-infocom06.pdf
> 

The paper above does not describe a specific eclipse attack, but it does
reference this paper for its definition of "eclipse attack":

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.

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.

X

-- 
GPG: ed25519/56034877E1F87C35
GPG: rsa4096/1318EFAC5FBBDBCE
https://github.com/infinity0/pubkeys.git