[tor-bugs] #6460 [Analysis]: Devise metrics to measure the safety of the Tor network

[Tor Bug Tracker & Wiki]

#6460: Devise metrics to measure the safety of the Tor network
----------------------+-----------------------------------------------------
 Reporter:  asn       |          Owner:     
     Type:  task      |         Status:  new
 Priority:  normal    |      Milestone:     
Component:  Analysis  |        Version:     
 Keywords:            |         Parent:     
   Points:            |   Actualpoints:     
----------------------+-----------------------------------------------------
Changes (by asn):

 * cc: robgjansen (added)


Comment:

 Some papers on measuring anonymity:

 - ''Towards an Information Theoretic Metric for Anonymity'' by Danezis et
 al. which uses the concept of information theoretic entropy to measure the
 anonymity of mix networks. Done in #6232 wrt the bandwidth weights of the
 consensus.

 - ''Towards measuring anonymity'' by Diaz et al. which comes up with the
 concept of ''degree of anonymity''. Graphs of the ''degree of anonymity''
 of the Tor network were created in #6232.

 - ''Measuring Anonymity Revisited'' by Tóth et al. which gives examples on
 why entropy and ''degree of entropy'' are not the best ways of measuring
 anonymity and proposes ''local anonymity measure'' as a more correct way.

 They said that entropy as a measurement is flawed because two anonymous
 networks with the same number of users but completely different anonymity
 properties can have the same entropy. Also, there are anonymous networks
 with ''degree of anonymity'' *very* close to 1 that are completely broken.

 They also said that entropy as a measurement describes the amount of
 information that an adversary needs to completely and deterministically
 deanonymize a user. They argue that an adversary is also successful if his
 attack has a big '''chance''' of deanonymizing the user. They believe that
 entropy can't handle the probability that an attacker's attack will
 succeed and their ''local anonymity measure'' measurement tries to provide
 that.

 I'm not sure how useful it would be for us to use ''local anonymity
 measure'' as a network security measurement.

 - ''A Combinatorial Approach to Measuring Anonymity'' by Edman et al.
 which provides a different model of measuring anonymity.

 They quantify anonymity by modeling all possible communications and
 input/output of nodes of an anonymity system as a bipartite graph and then
 use some graph theory to get a single value that characterizes the
 system's anonymity.

 It seems like a fun approach but the paper is concentrated on mixnets and
 I'm not sure how it can be generalized to onion routing.

 What other anonymity-measuring research have I missed or forgot?

-- 
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/6460#comment:3>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online