owned this note
owned this note
Published
Linked with GitHub
# "Hashing it out in public"
###### tags: `Tag(HashCloak - Validator Privacy)`
Author(s): Andrew Tran, Nicholas Hopper, Yongdae Kim
Paper: https://www-users.cs.umn.edu/~hoppernj/hashing\_it\_out.pdf
### Table of Contents
[toc]
:::info
>Abstract: We examine peer-to-peer anonymous communication systems that use Distributed Hash Table algorithms for relay selection. We show that common design flaws in these schemes lead to highly effective attacks against the anonymity provided by the schemes. These attacks stem from attacks on DHT routing, and are not mitigated by the well-known DHT security mechanisms due to a fundamental mismatch between the security requirements of DHT routing’s putget functionality and anonymous routing’s relay selection functionality. Our attacks essentially allow an adversary that controls only a small fraction of the relays to function as a global active adversary. We apply these attacks in more detail to two schemes: Salsa and Cashmere. In the case of Salsa, we show that an attacker that controls 10% of the relays in a network of size 10,000 can compromise more than 80% of all completed circuits; and in the case of Cashmere, we show that an attacker that controls 20% of the relays in a network of size 64000 can compromise 42% of the circuits.
:::
## 1. INTRODUCTION
One natural alternative to using a global list of relays is to organize routers into a distributed hash table (DHT).
* A DHT is a decentralized, distributed system that assigns a logical identifier to a set of $N$ nodes and provides algorithms to efficiently locate the node responsible for an arbitrary identifier, typically given knowledge of $O(log N)$ other nodes.
* Typically this “routing” layer is used to implement a hash table put/get interface allowing peers to store a value associated to a key at several “replica” nodes with identifiers closest to the key. In principle such schemes would present a scalable method to find relays for building tunnels.
* Unfortunately, schemes based on DHTs have proven hard to secure.
Our attacks target two common “failure modes” of such schemes that allow an adversary who controls a fraction $f$ of the nodes to compromise a fraction larger than $f$ of the circuits (compared with fraction $f^2$ of circuits in case every node knows all other nodes).
* The common theme between these failure modes is that a DHT lookup necessarily involves $O(log n)$ nodes, so that with very high probability the results of any lookup can be influenced by some adversarial node.
* In essence, while previous attacks show how a particular routing mechanism can give a local attacker some of the capabilities of a global passive adversary, our attacks show that essentially every DHT-based anonymity scheme promotes a local attacker to a global *active* adversary.
The central question in designing DHT-based anonymous overlays then becomes whether DHTs can be adapted to support these requirements.
## 2. BACKGROUND
### 2.1 Relay-based anonymity
All of the anonymity schemes we consider in this paper are based on a “circuit” model inherited from Onion Routing and Tor and are intended to provide “low-latency” connections for interactive applications such as web browsing and file sharing.
### 2.2 Distributed Hash Table Overview
A distributed hash table (DHT) is a distributed system that provides efficient lookup of key-value pairs. Each node in a DHT is assigned a unique identifier, called its $nodeID$, uniformly distributed in a large *key* space. Application specific data are also assigned identifiers, called keys, from the same ID space. The overlay designates ownership of a set of keys to a single unique live node. If a node owns a key, then the node is said to be the *root* of that key.
Queries can proceed either iteratively or recursively.
In recursive routing the source will delegate control of its query to a node in its routing table closer to the target. The node, who receives a query, passes control of the query to another node with a longer prefix match with the key. Nodes repeat this process until a node decides if it is the root of the key and passes the answer back (either by reversing the route from the source or by directly sending the answer to the source).
For example in **Figure 1 (a)**, the source $S$ wants to recursively find the root of the key $K$.
* First, $S$ contacts $A$ and control of the look up passes to $A$.
* Second, $A$ contacts $B$ and control of the look up passes to $B$.
* $B$ contacts $R$.
* Then, $R$ decides that it is the root of $K$ and notifies $B$ that it is the root of $K$.
* $B$ tells $A$ that $R$ is root of $K$.
* Finally, $A$ tells $S$ that $R$ is the root of $K$.
* In some cases, $R$ sends the message directly to $S$.
![](https://i.imgur.com/BZ8hUt5.png)
Iterative routing starts with the source asking the node in its routing table with the greatest prefix match to the target for a node with an even longer prefix match. The source repeatedly queries the results for nodes with longer prefix matches until the source cannot find any node closer to the key.
For example, in **Figure 1 (b)**:
* The source $S$ wants to iteratively find the root $R$.
* First, $S$ contacts $A$ and $A$ responds with $B$.
* Second, $S$ contacts $B$ and $B$ responds with $R$.
* Finally, $S$ contacts $R$ and decides $R$ is the answer.
### 2.3 Attacks on Distributed Hash Tables
#### 2.3.1 Query Capture
DHT routing has two main security problems: the first is that the chance of a query passing through a malicious node is very high, and the second is that it is very hard to determine whether the result of a query is correct.
Suppose a query uses on average $p$ hops to traverse the DHT. If any of the $p$ hops are controlled by the attacker, then the query is considered captured. Thus, the probability that a query is captured is $1 − (1 − f) p$ , where $p$ is $O(log n)$ in most DHTs and $n$ is the size of the network. > This is an overestimate since it assumes every query takes $O(log n)$ hops every time.
**Figure 2** 2 shows the fractions of queries captured by at least one malicious node by plotting eq. (1) for varying values of $f$ and $p$. Significantly more queries will be captured as $f$ and $p$ grow.
* In particular when $p = Ω(log \space n)$ then the probability of query capture is $1 − O(n ^{−f})$.
![](https://i.imgur.com/mpUynsa.png)
The second attack involves a malicious node forwarding queries to other malicious nodes or even non-existent nodes.
* For instance, upon receiving a request for a key $K$ the adversary simply returns the IP address of a malicious node.
* Unless the victim has detailed knowledge of the neighborhood of the destination ID space, it is difficult for the victim to verify whether or not the returned result is correct.
#### 2.3.2 Mitigating Attacks on Routing
One way to prevent attackers from claiming an arbitrary portion of the ID space is to make nodeIDs verifiable. For example, a node’s ID could be defined as the hash of its IP address.
One way to reduce the chance of query failure is to send queries through multiple routes simultaneously. The chance of a query failing may be reduced from the probability that the attacker controls any of the nodes on a given path to probability that the attacker controls a node on every path.
The “density check” method can be used to partially mitigate a node’s lack of detailed knowledge about different regions of the ID space. The checks are made on the assumption that malicious nodes are less dense in the ID space versus honest nodes [34]. The density check tests whether the distance between a result node and the key is consistent with the distribution of node IDs near the initiator; if the distance is greater than some multiple (e.g. 1.5×) of the average distance between nodeIDs (near the initiator) the result is rejected.
## 3. GENERIC FAILURE MODES OF DHT-BASED RELAY SELECTION
In this section, we discuss two related failure modes of DHT-based anonymous overlays: *insecure relay selection* and *overlay circuit extension*.
Recall that in a generic relay-based anonymity scheme a circuit is established by iteratively extending the circuit to a series of $\ell$ randomly chosen relays; essentially the “algorithm” for such a scheme is:
![](https://i.imgur.com/LEsu3Cw.png)
The “relay selection problem” is to efficiently and privately choose an unbiased relay for the next hop of a circuit.
In particular, a “generic” DHT-based anonymity scheme implements step 2a by uniformly choosing a key $k$, using the DHT to look up the root of $k$, and selecting $R_{i+1} = root(k)$.
* In expectation, when all nodes follow the protocol, this results in an unbiased relay selection.
* However, the “randomness” (lack of bias) of the query depends critically on the correctness of the query result:
* If lookups are susceptible to attacks that return incorrect or nonexistent results, the relay selection may be biased towards adversarial nodes.
* Additionally, if a DHT queries can be linked to its initiator, then the privacy of the relay selection may be undermined, allowing an adversary who controls the final relay of the circuit to determine the initiator without controlling the initial relay.
### 3.1 Insecure Relay Selection
In particular, consider the following selective denial of service attack on a generic anonymous peer to peer system’s circuit construction using recursive routing for random node selection.
* Source $S$ wants to build a tunnel out of the roots of the keys $K_1, K_2, and K_3$.
* First, $S$ does a lookup for $K_1$.
* With probability $q$ the attacker can capture $S$’s query.
Suppose the attacker captures the query.
* If the attacker controls malicious node $M_1$ close enough to $K_1$, an event with probability at least $f$, the attacker returns $M_1$ and otherwise the attacker drops the request.
* Now $S$ requests $M_1$ to lookup the root of $K_2$.
* $M_1$ returns this node, $N$, whether it is malicious or not.
* Finally, $N$ queries the DHT for $K_3$.
* With probability $q$ this query is captured as well, and if the attacker controls a nodes $M_3$ close enough to $K_3$ then $M_3$ is returned and otherwise the query is dropped.
* If $N$ extends a circuit to $M_3$ the circuit is compromised;
* If it does not, then $M_1$ drops the circuit.
* Adversarial nodes always drop circuit requests that come from relays that are not part of circuits that begin at adversarial nodes.
![](https://i.imgur.com/y04XBoH.png)
Under this scenario, a circuit can only be built successfully in two cases.
1. In the first case, none of the nodes $root(K_1), root(K_2), root(K_3)$ are adversarially controlled and none of the queries for these nodes is captured;
* The probability of this event is $(1−q)^3 (1−f)^3$.
2. Second, the adversary controls nodes sufficiently close to $K_1$ and $K_3$ to be accepted as the roots of these keys.
* In this case (whether or not the queries are captured) the circuit is compromised, and the event has probability at least $f^2$.
Thus, conditioned on successfully building a circuit, the probability of compromise is $f^2 \over f^2+(1−q)^3(1−f)^3$. Generalizing to circuits of length $\ell$ gives a fraction $f^{\lfloor \ell \ 2 \rfloor + 1} \over ((1−q)(1−f))^{\ell}+f^{\lfloor \ell /2 \rfloor +1}$ of compromised circuits. **Figure 3** shows how the probability of compromise grows as a function of $q$ when $f = 0.1$.
**Remark:** In recursive routing, it is difficult to attribute query failure to the responsible node, since the source can not see each step of the recursive query.
* If a node fails somewhere along the path from the source’s perspective only the next node has failed.
* Suppose source $S$ has a recursive query that uses nodes $A, B, C$.
* $S$ can not distinguish between failures at $A, B$, and $C$, because from $S$’s perspective it only appears that $A$ has failed.
* As a consequence, malicious nodes can be selectively uncooperative without being blacklisted.
Iterative routing has the property that it is easier for the source to recover from node failure. The source can see all of the nodes in an iterative query because it talks to them directly.
* If a node fails, the source can just timeout on that node, and ask other node.
* Since the source talks to all of the nodes in the query directly the source can decide not to use poorly performing nodes.
* However, use of iterative routing leads to passive attacks on anonymity similar to those discussed by Mittal and Borisov [25].
* Combined with selective DoS at the relay level these attacks (on iterative routing) are similar in effectiveness to the one described above.
### 3.2 Overlay Circuit Extension
Many DHT-based anonymous overlays make additional use of the DHT overlay: rather than simply looking up relays over the DHT and then connecting directly to the roots, the actual traffic carried by the overlay is delivered over the DHT by recursive routing. Unfortunately this opens the door to potentially more powerful attacks, since adversarial nodes gain the ability to conditionally allow circuits to be constructed and then close these circuits (by dropping all messages sent over the DHT to a particular ID) when additional information becomes available.
**Figure 4** shows how the fraction of compromised circuits (conditioned on successful completion) varies with $f, N$, and $\ell$.
![](https://i.imgur.com/p6SZIma.png)
## 4. SALSA
### 4.1 Overview of Salsa
Salsa [29] is a DHT-based layered circuit anonymity scheme.
* Salsa relays are organized into a Chord-like recursive DHT for node selection, where each node’s ID is determined by applying a cryptographic hash function to its IP address.
* Salsa is explicitly designed to resist attacks on its DHT functionality, assuming a fraction $f < 0.2$ of malicious nodes, through the aforementioned use of verifiable IDs, bounds checking and redundant lookup.
In addition to bounds checking, Salsa uses a binary tree structure that ensures that nodes share very few global contacts on average.
Salsa’s circuit construction process is shown in **Figure 5**.
![](https://i.imgur.com/T5zbHGf.png)
Circuits are built in $\ell$ stages, using redundancy parameter $r$.
* In the first stage, the initiator $I$ asks $r$ nodes (including itself) in its local DHT neighborhood to perform recursive lookups for $r$ keys $k_1, . . . , k_r$, and receives public keys and IP addresses for $r$ relays $A_1, . . . , A_r$.
* $I$ establishes a single-hop circuit with each of these nodes, and the next stage begins.
* At each subsequent stage, $I$ asks each of these $r$ circuit endpoints to recursively lookup $r$ additional keys $k_1^{'}, . . . , k_r^{'}$, to learn the IP addresses and keys of $r$ additional relays $B_1, . . . , B_r$.
* $I$ extends circuits from each $A_i$ to each $B_j , 1 ≤ i, j ≤ r$, and then randomly chooses one of the successfully extended circuits to each $B_j$ , discarding the rest.
* This process continues until the final stage, in which each of the $r$ circuit endpoints is asked to recursively lookup a single key $k^{''}$, obtaining the IP address and public key of a single relay $T$.
* $I$ extends each circuit from $B_i$ to $T$ and randomly picks one of the successfully extended circuits for its anonymous session.
Salsa nodes resolve conflicting lookup results as follows: the initiator uses the public cryptographic hash function to compute the ID for each IP address returned. The ID that is closest to the target key is selected, and the other results are discarded. Finally, this ID is subjected to the density test and if it passes the lookup succeeds.
### 4.2 Attack on Salsa
Our attack is a variant of the generic selective DoS attack of Section 3.1. It relies on three shortcomings of Salsa’s lookup defense mechanisms.
1. First, the bounds check is ineffective in case the adversary controls the closest live node to a key.
2. Second, Salsa’s “closest ID” conflict resolution means that an adversary can cause a redundant lookup to fail by being capturing *one* of the redundant queries and returning the IP address of the non-participating node with the closest hash to a given key (If fraction $c$ of all IP addresses participate in Salsa, the probability that one of the nonparticipating IP addresses is closest to a given key is greater than $1 − e^{−1/c}.$)
3. Finally, Salsa has no mechanism to verify the binding between a public key and IP address; if a first-stage node is malicious it can masquerade as any nonparticipating node simply by returning a public key of its choosing for that node.
Our attack uses a dictionary of IP address and hash pairs to defeat Salsa’s ID is hash of IP check. The attacker generates the dictionary by hashing all of the IP addresses. The storage required for a dictionary of 2$^32$ hashes is only 16 GB. (It is only necessary to remember which 4-byte IP address produces the closest hash to any 32-bit ID prefix).
The attack proceeds as follows:
* The adversary attacks all DHT lookup requests.
* Upon capturing a query for key $k$, malicious node $M$ first determines whether the correct response to the query is another malicious node $M'$ and if so, $M$ immediately returns $M'$ as the recursive lookup result.
* If not, $M$ identifies the IP address $N$ with the hash closest to $k$ and returns $N$ as the recursive lookup result.
* Since with overwhelming probability $N$ is not a participant, the initiator will fail to extend a circuit to $N$ and choose a different key instead.
* This heavily biases the choice of first-stage relays towards malicious nodes.
### 4.3 Salsa Simulation
To demonstrate the effectiveness of our attack, we simulated Salsa networks of varying size using a 64-bit hash space, neighborhoods of size 128, fraction $f = 0.1$ of malicious nodes and circuits of length $\ell = 3$. For each network size, and redundancy level $r ∈ \{3, 5, 7\}$, we simulated the creation of 100000 circuits and recorded the fraction of completed circuits compromised. The results appear in **Figure 6**.
![](https://i.imgur.com/LxL1BmF.png)
An alternative to Salsa’s “closest node” strategy for resolving conflicting redundant lookups is to take the relay (that passes the bounds check) returned by the majority of lookups. In this case, the best strategy for the adversary is to “stack the vote” towards a malicious node that can pass the bounds check for a key if one exists, and “drop” the query otherwise by returning an offline node that can pass the bounds check. Since asymptotically the majority of redundant lookups will be captured this increases the probability of having a malicious first-stage relay by a factor of the bounds check multiplier.
**Figure 7** shows the result of simulations using this conflict resolution method.
![](https://i.imgur.com/jP0JLjB.png)
## 5. CASHMERE
### 5.1 Overview of Cashmere
Cashmere is a recursive DHT-based anonymous communications overlay built on top of the Pastry DHT [34].
* Cashmere uses *virtual relays* composed of sets of nodes (or *relay groups*) for resilience.
* A Cashmere node with a $k$-bit nodeID has an $m$-bit groupID for every $1 ≤ m ≤ k$.
* A node belongs to relay group if the groupID is a prefix of the nodeID.
* Every relay group must have a public/private key pair, and every member of the relay group has the public/private key pair for that group.
* Cashmere assumes all of the keys are both generated and distributed by a trusted offline CA.
* When a user bootstraps into Cashmere, the user obtains a signed $k$-bit nodeID and the set of $k$ keys associated with prefixes of that nodeID.
* The user must also obtain a public key for all other prefixes.
![](https://i.imgur.com/tQPfGIH.png)
Circuits consist of $\ell$ stages.
* Suppose peer $S$ wants to forward a message to peer $T$.
* $S$ chooses a path consisting of $\ell$ relay groups $G_1, . . . , G_{\ell}$, such that $T$ is in relay group $G_d$ for a randomly chosen $1 ≤ d ≤ \ell$.
* $S$ then encrypts the forwarding path in layers using each relay group’s public key.
Cashmere decouples a message’s payload from the forwarding path and encrypts each separately. This allows a source to reuse a forwarding path reducing the computational overhead of multiple encryption. By caching the forwarding path the source is able to send multiple messages to the destination at the cost of a single public key encryption per key.
### 5.2 Attack on Cashmere
The attack on Cashmere is similar to the generic attack on overlay circuit extension described in section 3.2 with some small modifications. As in that section, the adversary attempts to discover the entire path by either being on the forwarding path to a relay group or being a member of the previous group.
Compared to the generic attack, the use of relay groups increases the probability of learning the next group by being a member of the previous group.
* If the adversary sees message $m_1$ delivered to group $G_1$ and then sees $m_2$ delivered to $G_2$, it can test whether $G_1$ and $G_2$ are neighbors on the same path by constructing its own path message including $G_1$ and $G_2$ and forwarding this message from the point it observed $m_1$.
* If it sees its message at the same point it observed $m_2$, the amount of path diversity in the Pastry overlay gives us high confidence that $m_2$ came from $G_1$.
If the adversary observes the construction of a chain of $\ell$ relay groups then malicious nodes are instructed to deliver subsequent messages using the same path only if the initiator can be determined. Due to Pastry’s “wide” routing table, with probability $15 \over 16$ a query’s first hop is to a node with a single-digit prefix match. Thus when a malicious node receives a recursive query with a one-digit prefix match it knows that the forwarding node is the query initiator; if the target of the query is the first relay group in an observed chain of $\ell$ then the query initiator is also the circuit initiator.
Thus, a circuit can only successfully deliver subsequent (nonreply block) payloads if the adversary learns the initiator and all of the relay groups or if none of the DHT paths between the initiator and the recipient are captured.
> $ρ$ is the size of a relay groupp; the recommended parameters of $\ell$ = 4 and ρ = 5 mean that when a circuit is compromised the initiator can be linked to a list of 20 possible recipients.
![](https://i.imgur.com/51pgd7C.png)
**Figure 9** shows how the success rate of this attack varies with $n$ and $f$, when $\ell = 3$ and $ρ = 5$.
![](https://i.imgur.com/dl3Ij7j.png)
**Figure 10** shows how the fraction of completely compromised circuits varies with $f$ and $N$.
## 7. CONCLUSION
> The critical question for future work in this line of research is whether a “DHT-like” algorithm can be designed to meet the specific requirements – in terms of privacy, availability, and correctness – of an anonymity scheme.