[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

*To*: or-dev@xxxxxxxxxxxxx*Subject*: Re: Master's Thesis: Performance-Improved Onion Routing*From*: Nick Mathewson <nickm@xxxxxxxxxxxxx>*Date*: Sat, 29 Sep 2007 12:43:02 -0400*Delivered-to*: archiver@xxxxxxxx*Delivered-to*: or-dev-outgoing@xxxxxxxx*Delivered-to*: or-dev@xxxxxxxx*Delivery-date*: Sat, 29 Sep 2007 12:43:11 -0400*In-reply-to*: <46FD2444.60703@xxxxxx>*Mail-followup-to*: Nick Mathewson <nickm@xxxxxxxxxxxxx>, or-dev@xxxxxxxxxxxxx*References*: <46FBCF1C.90503@xxxxxx> <20070928142421.GL3927@xxxxxxxxxxxxxxxxxx> <46FD2444.60703@xxxxxx>*Reply-to*: or-dev@xxxxxxxxxxxxx*Sender*: owner-or-dev@xxxxxxxxxxxxx*User-agent*: Mutt/1.4.2.1i

On Fri, Sep 28, 2007 at 05:56:52PM +0200, Johannes Renner wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 > > Nick Mathewson wrote: > >> proposed techniques is presented. Included evaluations cover the > >> performance that is reached on average, but also the degree of > >> anonymity that is achieved when employing different methods of > >> path selection. > > > > What are you using as your anonymity measure? > > [Answering here since it seems to be interesting] > > To measure a "degree of anonymity", a certain method of path > selection can provide, I do the following: > > I generate a (preferably big) amount of paths, without actually > creating any circuit. This list of paths can then be evaluated > regarding the occurrences of specific nodes on the single > positions of the paths. So, as a first metric I simply count the > total number of different nodes that is chosen on the single > positions of the paths. The higher the single numbers for > entry/middle/exit positions, the more anonymity there is. This seems pretty weird; it implies that an adversary can increase people's anonymity by signing up more nodes. (Since the more nodes on the network, the more possible nodes will appear in entry/middle/exit positions.) > I know, this metric does not consider that some methods choose > some nodes with a higher probability (means more often) than > others. Therefore, I work towards the conditional probability > that a specific entry node is chosen, given the IP of an exit > node and vice-versa (according to an advice from Mike Perry). This is a bit more reasonable, though it probably makes more sense to look at conditional entropy of entry node given exit node and/or target IP... or perhaps additional information gained about entry nodes given knowledge of the exit node or destination? (If entry nodes are chosen dependent on the client's current location, we want to look at additional info gained about client location too.) [I see below that you *do* go for entropy. Cool.] Also, if we're worried about the attacker being the exit, we need to look at additional info gained given knowledge of the exit _and_ middle nodes: if you're the exit node, you not only know where you are, but you also know the previous node in the circuit. In any case, that's a decent measure of the attack where the adversary observes some nodes in the circuit and tries to infer the rest. But there are other attacks, and so there there are other measures that count too! These include: - Given a fraction of nodes compromised by an adversary, what is the probability that a given path will have first and last node compromised? - Given a fraction of nodes compromised by an adversary, and assuming guard nodes are in use, what is the probability that adversary can be first and last node for a sample of paths? (This is important if what you're worried about is statistical sampling.) > This means, instead of counting the occurrences of single nodes, > I count the total number of different combinations of entry and > exit nodes (EE-combinations). Intuitively, the more different > EE-combinations there are in a sample of n paths, the better the > achieved anonymity. This doesn't take into account knowledge of the middle node that the attacker gets by being the exit. > Further, I calculate the entropy regarding the probabilities of > the different EE-combinations, and from this, a bounded degree > of anonymity 'd'. This is done using the maximum entropy that is > calculated from a sample of size n, where no two paths have the > same EE-combination (which means d=1, iff all of the generated > paths show different EE-combinations). This way it is easy to > compare different methods of path selection regarding the > achieved anonymity by generating samples of the same size. From > these samples, 'd' is calculated and the results can be compared. > For my thesis I generated samples of 100.000 paths (only), so it > will be interesting to increase n to maybe 1.000.000 and repeat > the experiment. [THis looks interesting; I think I should read the relevant bits of the thesis for details and think about it more.] > Note, that I only had limited time for writing my thesis, and > the anonymity evaluation was not the most important aspect in > it (even if it is maybe the most interesting). So, all of this > surely offers room for improvements, please send me your ideas! My main idea is this: too many papers decide to characterize some measure as "anonymity" when that measure only reflects the difficulty of one possible attack among many. This is indeed a valuable contribution to research, since resisting more attacks is quite worthwhile... but it's possible to resist one attack at the expense of becoming weaker to another. Thus, it's important to look at many different measures and consider the effects of design choices on all the significant attacks that effect your system. For all I know, you do this in your thesis; I should check it out in more detail. anyways, thanks again for your work! I have the copy of your thesis that you sent, and I look forward to reading it. yrs, -- Nick Mathewson

**Attachment:
pgpHD801O9gsM.pgp**

**References**:**Master's Thesis: Performance-Improved Onion Routing***From:*Johannes Renner

**Re: Master's Thesis: Performance-Improved Onion Routing***From:*Nick Mathewson

**Re: Master's Thesis: Performance-Improved Onion Routing***From:*Johannes Renner

- Prev by Author:
**Re: Tor crash** - Next by Author:
**Re: Exit guards?** - Previous by thread:
**Re: Master's Thesis: Performance-Improved Onion Routing** - Next by thread:
**Tor crash** - Index(es):