GuardedGossip: Secure and Anonymous Node Discovery in Untrustworthy Networks

Abstract

Node discovery is a fundamental service for any overlay network. It is a particular challenge to provide unbiased discovery in untrustworthy environments, e.g., anonymization networks. Although a major line of research focused on solving this problem, proposed methods have been shown to be vulnerable either to active attacks or to leak routing information, both threatening the anonymity of users. In response, we propose GuardedGossip—a novel gossip-based node discovery protocol—that achieves an unbiased random node discovery in a fully-decentralized and highly-scalable fashion. It is built on top of a Chord distributed hash table (DHT) and relies on witness nodes and bound checks to resist active attacks. To limit routing information leakages, GuardedGossip uses gossi** to create uncertainty in the process of node discovery. By incorporating the principles of DHTs with the unstructured nature of gossi** in a subtle way, we profit from the strengths of both techniques while carefully mitigating their shortcomings. We show that GuardedGossip provides a sufficient level of security for users even if 20% of the participating nodes are malicious. Concurrently, our system scales gracefully and provides an adequate overhead for its security and privacy benefits.

Appendices

A Bound Checking

Given a FT, bound checking is performed as follows: Initially, the node density d is computed. Ideally, this can be done by deriving $d=\frac{N}{n}$, where N is the ID space size of the DHT and n is the number of active nodes. However, n is usually not known. Thus, each peer computes means of the distance between the actual IDs in its FT and optimal IDs (as if all IDs would exist). The mean distance is then multiplied with a finger table tolerance factor $\gamma > 0$. Finally, to verify the plausibility of a given FT g the GuardedGossip node applies the following constraint $d_{g} < \gamma d$ to check whether the FT g is manipulated. In our work, we use $\gamma = \sqrt{\frac{1}{f}}$, where f is the (supposed) fraction of colluding malicious nodes. As the actual fraction of colluding malicious nodes is not known by the users, $\gamma$ corresponds to the estimated maximum fraction of malicious nodes that is supposed to be tolerated by our approach.

To assess the optimal value of $\gamma$, we rely on the approach used to detect routing failures in [7]. As the value of $\gamma$ depends on the false positives rate $\alpha$ (i.e., a correct FT is falsely detected as manipulated) and the false negatives rate $\beta$ (i.e., a manipulated FT is detected as correct), here we aim to minimize both, $\alpha$ and $\beta$, simultaneously. To this end, we deal with the total number n of all uniformly sampled active nodes within the ID space N. According to [7], the distances between consecutive node IDs within a FT can be modeled by independent exponentially distributed random variables with a mean of $\frac{N}{n}$. Similarly, the distance between consecutive malicious nodes can be modeled using exponential distribution with a mean of $\frac{N}{f \cdot n}$, where f is the fraction of malicious nodes. We construct a new random variable by summing up the distances between nodes in the FT of the verifying node (denoted as $S_{o}$) and the distances between nodes in the retrieved FT to be verified by that node (denoted as $S_{v}$). Given that k denotes the FT size, the values of $\frac{1}{k} \cdot S_{o}$ and $\frac{1}{k} \cdot S_{v}$ measure the mean distances between node IDs in the FT of the verifying node and the retrieved FT to be verified by that node using bound checking. Now, the false positive rate $\alpha$ can be expressed by the probability $\alpha (k, \gamma , f) = Pr \left( \frac{1}{k} \cdot S_{v} > \gamma \frac{1}{k} \cdot S_{o} \right)$. Similarly, the false negative rate $\beta$ is computed as follows: $\beta (k, \gamma , f) = Pr \left( \frac{1}{k} \cdot S_{v} < \gamma \frac{1}{k} \cdot S_{o} \right) .$ According to [7], the false positives and false negatives get minimized if $\alpha = \beta$. Thus, we obtain the following equation: $\alpha (k, \gamma , f) = \beta (k, \gamma , f)$, from which $\gamma$ can be computed. Moreover, $S_{o}$ and $S_{v}$, are $\gamma$-distributed with a shape parameter k and scale parameters $\frac{n}{N}$ and $\frac{f \cdot n}{N}$, correspondingly. The use of the gamma distribution and solving the equation by $\gamma$ finally yields $\gamma = \sqrt{\frac{1}{f}}$.

Fig. 8.

Bounds checking false positive rate $\alpha$, false negative rate $\beta$, and objective function for optimization $\alpha + \beta$ over the FT tolerance factor $\gamma$ for $f = 0.2$.

We performed experiments to check these theoretical results. Figure 8 shows the bounds checking false positive rate $\alpha$, the false negative rate $\beta$ and the objective function for the optimization of $\alpha + \beta$, which is intended for minimization over the threshold $\gamma > 0$. As suggested in [7], the minimal cumulated error is achieved in case of $\alpha = \beta$, which justifies our computation of $\gamma$.

B Completeness of Node Discovery

To achieve a sufficient level of anonymity, GuardedGossip should deliver random nodes from the set of all active nodes in the network. Thus, the attacker cannot influence the selection of nodes for anonymized user connections except by injecting more peers in the network. As the list of guarded nodes is the only source in our approach providing nodes for building user connections, we analyze its content with respect to its completeness. Figure 9 shows the fraction of nodes collected in individual lists of guarded nodes during the operation of GuardedGossip over time. For an increasing number of iterations, the fraction of nodes observed in guarded lists (measured by 95% quantiles) converges to 100%. Already after 1000 iterations, almost all GuardedGossip nodes have seen other active nodes forming the half of the network. This also confirms the expectation that staying longer in the network increases the coverage of discovered nodes. Every node also gets a chance to be discovered by all network participants.

Fig. 9.

Fraction of nodes in guarded lists measured by 95% quantiles for a network of size 2,000 nodes.

Fig. 10.

Average number of nodes in gossiped and guarded lists for different network sizes with 10% adversarial nodes.

C Number of Nodes in Gossiped and Guarded Lists

We also explore the average number of nodes contained in both the gossiped list and the guarded list. Figure 10 shows that the size of the guarded list rapidly increases already in the beginning of operation of our approach, i.e., after 20 iterations. On the other hand, the number of nodes in the gossiped list increases slower, i.e., after 100 iterations it becomes stable. The guarded list grows faster as it gets filled by the whole FTs whereas the gossiped list only by single entries. We observe that the size of the network does not influence the bootstrap** process of the guarded list and has only a moderate impact on the size of gossiped list. Naturally, for an increasing network size the steady state of the gossiped list is reached earlier as more nodes participate in the gossi** process. However, even for small networks with 1000 nodes we achieve a sufficient number of nodes after approximately 150 iterations. This ensures fluctuations within the lists (once both lists are completely filled, some nodes are discarded in favor of new nodes) so that it becomes more difficult for an attacker to promote favorable nodes due to the constant rotation of nodes in the gossiped list.