Admin: Created page with "In anonymity networks (e.g., Tor, Crowds, Mixmaster, I2P, etc.), it is important to be able to measure quantitatively the guar..."

2019-03-27T06:43:03Z

Created page with "In anonymity networks (e.g., Tor, Crowds, Mixmaster, I2P, etc.), it is important to be able to measure quantitatively the guar..."

New page

In [[anonymity network]]s (e.g., [[Tor]], [[Crowds]], [[Mixmaster anonymous remailer|Mixmaster]], [[I2P]], etc.), it is important to be able to measure quantitatively the guarantee that is given to the system. The '''degree of anonymity''' <math>d</math> is a device that was proposed at the 2002 Privacy Enhancing Technology (PET) conference. There were two papers that put forth the idea of using [[entropy]] as the basis for formally measuring anonymity: "Towards an Information Theoretic Metric for Anonymity", and "Towards Measuring Anonymity". The ideas presented are very similar with minor differences in the final definition of <math>d</math>.

__TOC__

==Background==
Anonymity networks have been developed and many have introduced methods of proving the anonymity guarantees that are possible, originally with simple [[Mix network|Chaum Mixes]] and Pool Mixes the size of the set of users was seen as the security that the system could provide to a user. This had a number of problems; intuitively if the network is international then it is unlikely that a message that contains only Urdu came from the United States, and vice versa. Information like this and via methods like the [[Onion Routing|predecessor attack]] and [[Onion Routing|intersection attack]] helps an attacker increase the probability that a user sent the message.

===Example With Pool Mixes===
As an example consider the network shown above, in here <math>A, B, C</math> and <math>D</math> are users (senders), <math>Q, R, S</math>, and <math>T</math> are servers (receivers), the boxes are mixes, and <math>\{A, B\} \in T</math>, <math>\{A, B, C\} \in S</math> and <math>\{A, B, C, D\} \in Q, R</math> where <math>\in</math> denotes the anonymity set. Now as there are [[pool mix]]es let the cap on the number of incoming messages to wait before sending be <math>2</math>; as such if <math>A, B</math>, or <math>C</math> is communicating with <math>R</math> and <math>S</math> receives a message then <math>S</math> knows that it must have come from ??<math>E</math>?? (as the links between the mixes can only have <math>1</math> message at a time). This is in no way reflected in <math>S</math>'s anonymity set, but should be taken into account in the analysis of the network.

==Degree of Anonymity==
The degree of anonymity takes into account the probability associated with each user, it begins by defining the [[entropy]] of the system (here is where the papers differ slightly but only with notation, we will use the notation from .): <br>
<math>H(X) := \sum_{i=1}^{N} \left[p_i \cdot \lg\left(\frac{1}{p_i}\right)\right]</math>,
where <math>H(X)</math> is the entropy of the network, <math>N</math> is the number of nodes in the network, and <math>p_i</math> is the probability associated with node <math>i</math>.
Now the maximal [[entropy]] of a network occurs when there is uniform probability associated with each node <math>\left(\frac{1}{N}\right)</math> and this yields <math>H_M := H(X) \gets \lg(N)</math>.
The degree of anonymity (now the papers differ slightly in the definition here, defines a bounded degree where it is compared to <math>H_M</math> and gives an unbounded definition—using the entropy directly, we will consider only the bounded case here) is defined as <br>
<math>d := 1 - \frac{H_M - H(X)}{H_M} = \frac{H(X)}{H_M}</math>.
Using this anonymity systems can be compared and evaluated using a quantitatively analysis.

===Definition of Attacker===
These papers also served to give concise definitions of an attacker:
; Internal/External : an '''internal''' attacker controls nodes in the network, whereas an '''external''' can only compromise communication channels between nodes.
; Passive/Active : an '''active''' attacker can add, remove, and modify any messages, whereas a '''passive''' attacker can only listen to the messages.
; Local/Global : a '''local''' attacker has access to only part of the network, whereas a '''global''' can access the entire network.

==Example <math>d</math>==
In the papers there are a number of example calculations of <math>d</math>; we will walk through some of them here.

===Crowds===
In [[Crowds]] there is a global probability of forwarding (<math>p_f</math>), which is the probability a node will forward the message internally instead of routing it to the final destination. Let there be <math>C</math> corrupt nodes and <math>N</math> total nodes. In [[Crowds]] the attacker is internal, passive, and local. Trivially <math>H_M \gets \lg (N - C)</math>, and overall the entropy is <math>H(x) \gets \frac{N - p_f \cdot (N - C - 1) }{N} \cdot \lg\left[\frac{N}{N - p_f \cdot (N - C - 1)}\right] + p_f \cdot \frac{N - C - 1}{N} \cdot \lg\left[N/p_f\right]</math>, <math>d</math> is this value divided by <math>H_M</math>.

===Onion routing===
In [[onion routing]] let's assume the attacker can exclude a subset of the nodes from the network, then the entropy would easily be <math>H(X) \gets \lg(S)</math>, where <math>S</math> is the size of the subset of non-excluded nodes. Under an attack model where a node can both globally listen to message passing and is a node on the path this ''decreases'' to <math>H(X) \gets \lg(L)</math>, where <math>L</math> is the length of the onion route (this could be larger or smaller than <math>S</math>), as there is no attempt in onion routing to remove the correlation between the incoming and outgoing messages.

===Applications of this metric===
In 2004, Diaz, [[Len Sassaman|Sassaman]], and DeWitte presented an analysis of two anonymous [[remailers]] using the Serjantov and Danezis metric, showing one of them to provide zero anonymity under certain realistic conditions.

==See also==
* [[Onion routing]]
* [[Tor]]
* [[Crowds]]

==Source==
[http://wikipedia.org/ http://wikipedia.org/]

[[Category:Anonymity and security]]

Degree of anonymity - Revision history

Admin: Created page with "In anonymity networks (e.g., Tor, Crowds, Mixmaster, I2P, etc.), it is important to be able to measure quantitatively the guar..."