The Traffic Analysis of Continuous-Time MixesGeorge DanezisUniversity of Cambridge, Computer Laboratory,15 JJ Thomson Avenue, Cambridge CB3 0FD, United [email protected]. We apply the information-theoretic anonymity metrics tocontinuous-time mixes, that individually delay messages instead of batch-ing them. The anonymity of such mixes is measured based on their delaycharacteristics, and as an example the exponential mix (sg-mix) is anal-ysed, simulated and shown to use the optimal strategy. We also describea practical and powerful traffic analysis attack against connection basedcontinuous-time mix networks, despite the presence of some cover traf-fic. Assuming a passive observer, the conditions are calculated that maketracing messages through the network possible.1 IntroductionBuilding blocks for anonymous communication operating by batching input mes-sages in rounds, such as threshold or pool mixes, have recently been the subjectof extensive study [15, 16, 6, 17]. The same is not true for mixes that operatein continuous-time, by individually delaying messages. An example of these isthe sg-mix construction presented by Kesdogan et al [10]. Its inventors presentan analysis of its anonymity, but this cannot easily be generalised to other mixstrategies.We will present a new framework for analysing the anonymity provided bymix strategies that individually delay messages. In order to make the analysiseasier, we assume that the rate of arrival of messages to the mixes is Poissondistributed. Using the work presented here, different mix strategies can be anal-ysed but we choose to illustrate our method with an analysis of the exponentialmix (sg-mix), both because it is relatively simple and because it has been exten-sively mentioned in the literature. Furthermore, a section is devoted to showingthat given some latency constraints the exponential mix is the mixing strategyproviding maximal anonymity.We then present a powerful attack that given enough packets, can break theanonymity provided by connection-based mix networks functioning in continuous-time. The attack relies on detecting an input traffic pattern, at the outputs ofthe mixes or network, using signal detection techniques. A detailed descriptionis given on how to perform this attack, and confidence intervals are provided toassess the reliability of the results. The attack can be used effectively againstmany proposed anonymous communications systems such as Onion Routing [13],Freedom [4], TARZAN [7] or MorphMix [14].2 Delay characteristic and anonymityThe main aim of a mix, as introduced by Chaum [5], is to hide the correspon-dence between the input and output messages it relays. First it makes its inputsand outputs bitwise unlinkable, which means that a third party cannot linkthem by observing their bit patterns without knowledge of the cryptographickeys used to perform the transform. Secondly it blurs the timing correlationsbetween inputs and outputs by batching, introducing appropriate random de-lays and reordering messages. Continuous-time mixes achieve this by delayingeach message individually and independently of the others.We can say that a particular mix strategy is described by its delay character-istic. This is a function f(β|α) that represents the probability a message injectedin the mix at time α leaves the mix at time β, where α ≤ β. Since f(β|α) is aconditional probability distribution, it is normalised.∀α.Z+∞αf(β|α) dβ = 1 . (1)The inverse delay characteristic, f0(α|β), of the same mix strategy is a proba-bility distribution that describes the likelihood a message being ejected at time βwas injected at time α. Again because it is a conditional probability distributionit is normalised.∀β.Zβ−∞f0(α|β) dα = 1 . (2)The two characteristics are related, since the second f0can be calculatedusing Bayes theorem from f. Some knowledge of the probability of arrivals atparticular times is necessary to perform this conversion. To simplify things, wewill consider that arrivals are Poisson distributed with a rate λα. In a Poissonprocess, the probability of an arrival is independent from other arrivals or thetime α.f0(α|β) =f(β|α)Pr[Arrival at α]Rβ−∞f(β|α)Pr[Arrival at α] dα(3)=f(β|α)Rβ−∞f(β|α) dα(4)Therefore, given the delay characteristics and some assumptions about thetraffic in the network we can calculate the inverse delay characteristic. Thesewill allow us to measure the effective sender and receiver anonymity for this mixstrategy.We will use the metric introduced in [15] to calculate the sender anonymityprovided by a mixing strategy. This metric is based on defining a random variablethat describes the possible senders of a message and calculating the entropy ofits underlying probability distribution. The entropy is then a measure of theanonymity provided, and can be interpreted as the amount of information anattacker is missing to deterministically link the messages to a sender.We assume that in a time interval (β − T, β), K messages arrive at the mix,where K is distributed according to a Poisson distribution with parameter λα.These messages arrive at times X1...Keach distributed according to a uniformdistribution U(t) over the time interval of length T (as required by the Poissondistribution).Given the inverse delay characteristic of the mix f0(α|β), the sender anonymity Aprovided by the mix can be calculated. It represents the entropy of the proba-bility distribution describing how likely each of the inputs Xiis to be output ata particular time β.A =KXi=1f0(Xi|β)PKj=1f0(Xj|β)logf0(Xi|β)PKj=1f0(Xj|β)= (5)=1PKj=1f0(Xj|β) KXi=1f0(Xi|β) log f0(Xi|β)!− logKXj=1f0(Xj|β) (6)From the Law of Large Numbers1we know that the sums converge to:KXj=1f0(Xj|β) →KT→ λα(7)KXi=1f0(Xi|β) log f0(Xi|β) →KTZββ−Tf0(t|β) log f0(t|β)dt → λαE[f0(α|β)] (8)Thus the fraction K/T converges to λα, which is the rate of arrival of mes-sages to the mix and the integral (8) reduces to the entropy of the inverse delaycharacteristic function E[f0(α|β)]. Therefore the sender anonymity of a continu-ous mix with delay characteristic f0and a rate of arrival λαcan be expressed.A → E[f0(α|β)] − log λα(9)Putting this into words, the effective sender anonymity set size of the mixingstrategy will converge towards the relative entropy of the inverse delay charac-teristic, as defined by Shannon [19], minus the logarithm of the
View Full Document
Unlocking...