Crowds: Anonymity for Web Transactions
`
`Michael K. Reiter
`
`and
`
`Aviel D. Rubin
`
`AT&T Labs—Research
`
`In this paper we introduce a system called Crowds for protecting users’ anonymity on the world-
`wide-web. Crowds, named for the notion of “blending into a crowd”, operates by grouping users
`into a large and geographically diverse group (crowd) that collectively issues requests on behalf of
`its members. Web servers are unable to learn the true source of a request because it is equally likely
`to have originated from any member of the crowd, and even collaborating crowd members cannot
`distinguish the originator of a request from a member who is merely forwarding the request on
`behalf of another. We describe the design, implementation, security, performance, and scalability
`of our system. Our security analysis introduces degrees of anonymity as an important tool for
`describing and proving anonymity properties.
`
`Categories and Subject Descriptors: C.2.0 [Computer-Communication Networks]: General—
`security and protection; C.2.2 [Computer-Communication Networks]: Network Protocols—
`applications; K.4.1 [Computers and Society]: Public Policy Issues—privacy; K.4.4 [Comput-
`ers and Society]: Electronic Commerce—security
`
`General Terms: Security
`
`Additional Key Words and Phrases: anonymous communication, world-wide-web
`
`1. INTRODUCTION
`
`Every man should know that his conversations, his correspondence, and
`his personal life are private. — Lyndon B. Johnson, president of the
`United States, 1963–69
`
`The lack of privacy for transactions on the world-wide-web, or the Internet in
`general, is a well-documented fact [Brier 1997; Miller 1997]. While encrypting com-
`munication to and from web servers (e.g., using SSL [Hickman and Elgamal 1995])
`can hide the content of the transaction from an eavesdropper (e.g., an Internet
`service provider, or a local system administrator), the eavesdropper can still learn
`the IP addresses of the client and server computers, the length of the data being
`exchanged, and the time and frequency of exchanges. Encryption also does little
`to protect the privacy of the client from the server. A web server can record the
`Internet addresses at which its clients reside, the servers that referred the clients to
`it, and the times and frequencies of accesses by its clients. With additional effort,
`this information can be combined with other data to invade the privacy of clients
`even further. For example, by automatically fingering the client computer shortly
`after an access and comparing the idle time for each user of the client computer
`with the server access time, the server administrator can often deduce the exact
`user with high likelihood. Some consequences of such privacy abuses are described
`in [Miller 1997].
`In this paper we introduce a new approach for increasing the privacy of web
`
`BLUE COAT SYSTEMS - Exhibit 1079 Page 1
`
`

`
`2
`
`·
`
`transactions and a system, called Crowds, that implements it. Our approach is
`based on the idea of “blending into a crowd”, i.e., hiding one’s actions within the
`actions of many others. To execute web transactions in our model, a user first joins
`a “crowd” of other users. The user’s request to a web server is first passed to a
`random member of the crowd. That member can either submit the request directly
`to the end server or forward it to another randomly chosen member, and in the
`latter case the next member chooses to submit or forward independently. When
`the request is eventually submitted, it is submitted by a random member, thus
`preventing the end server from identifying its true initiator. Even crowd members
`cannot identify the initiator of the request, since the initiator is indistinguishable
`from a member that simply forwards a request from another.
`In studying the anonymity properties provided by this simple mechanism, we in-
`troduce the notion of degrees of anonymity. We argue that the degree of anonymity
`provided against an attacker can be viewed as a continuum, ranging from no
`anonymity to complete anonymity and having several interesting points in between.
`We informally define these intermediate points, and for our Crowds mechanism
`described above, we refine these definitions and prove anonymity properties for
`our system. We expect these definitions and proofs to yield insights into proving
`anonymity properties for other approaches, as well.
`An intriguing property of Crowds is that a member of a crowd may submit
`requests initiated by other users. This has both negative and positive consequences.
`On the negative side, the user may be incorrectly suspected of originating that
`request. On the positive side, this property suggests that the mere availability
`of Crowds offers the user some degree of deniability for her observed browsing
`behavior, if it is possible that she was using Crowds. Moreover, if Crowds becomes
`widely adopted, then the presumption that the computer from which a request is
`received is the computer that originated the request will become decreasingly valid
`(and thus decreasingly utilized).
`The anonymity provided by Crowds is subject to some caveats. For example,
`Crowds obviously cannot protect a user’s anonymity if the content of her web trans-
`actions reveals her identity to the web server (e.g., if the user submits her name and
`credit card number in a web form). More subtley, Crowds can be undermined by
`executable web content that, if downloaded into the user’s browser, can open net-
`work connections directly from the browser to web servers, thus bypassing Crowds
`altogether and exposing the user to the end server. In today’s browsers, such ex-
`ecutable content takes the form of Java applets and ActiveX controls. Therefore,
`when using Crowds, it is recommended that Java and ActiveX be disabled in the
`browser, which can typically be done via a simple preferences menu in the browser.
`The rest of this paper is structured as follows. In Section 2, we more precisely
`state the anonymity goals of our system and introduce the notion of degrees of
`anonymity. This gives us sufficient groundwork to compare our approach to other
`approaches to anonymity in Section 3. We describe the basic Crowds mechanism
`in Section 4 and analyze its security in Section 5. We describe the performance
`and scalability of our system in Sections 6 and 7, respectively. We discuss crowd
`membership in Section 8, the system’s user interface in Section 9, and the obstacles
`that firewalls present to wide scale adoption of Crowds in Section 10. We conclude
`in Section 11.
`
`BLUE COAT SYSTEMS - Exhibit 1079 Page 2
`
`

`
`·
`
`3
`
`
`
`absolute
`privacy
`
`beyond
`suspicion
`
`probable
`innocence
`
`possible
`innocence
`
`exposed
`
`provably
`exposed
`
`Fig. 1. Degrees of anonymity: Degrees range from absolute privacy, where the attacker cannot
`perceive the presence of communication, to provably exposed, where the attacker can prove the
`sender, receiver, or their relationship to others.
`
`2. GOALS
`
`2.1 Anonymity
`
`As discussed in [Pfitzmann and Waidner 1987], there are three types of anony-
`mous communication properties that can be provided: sender anonymity, receiver
`anonymity, and unlinkability of sender and receiver. Sender anonymity means that
`the identity of the party who sent a message is hidden, while its receiver (and the
`message itself) might not be. Receiver anonymity similarly means that the identity
`of the receiver is hidden. Unlinkability of sender and receiver means that though the
`sender and receiver can each be identified as participating in some communication,
`they cannot be identified as communicating with each other.
`A second aspect of anonymous communication is the attackers against which
`these properties are achieved. The attacker might be an eavesdropper that can
`observe some or all messages sent and received, collaborations consisting of some
`senders, receivers, and other parties, or variations of these [Pfitzmann and Waidner
`1987].
`To these two aspects of anonymous communication, we add a third: the degree
`of anonymity. As shown in Figure 1, the degree of anonymity can be viewed as an
`informal continuum. For simplicity, below we describe this continuum with respect
`to sender anonymity, but it can naturally be extended to receiver anonymity and
`unlinkability as well. On one end of the spectrum is absolute privacy: absolute
`sender privacy against an attacker means that the attacker can in no way distinguish
`the situations in which a potential sender actually sent communication and those
`in which it did not. That is, sending a message results in no observable effects for
`the attacker. On the other end of the spectrum is provably exposed: the identity
`of a sender is provably exposed if the attacker cannot only identify the sender of a
`message, but can also prove the identity of the sender to others.
`For the purposes of this paper, the following three intermediate points of this
`spectrum are of interest, listed from strongest to weakest.
`
`—Beyond suspicion: A sender’s anonymity is beyond suspicion if though the
`attacker can see evidence of a sent message, the sender appears no more likely to
`be the originator of that message than any other potential sender in the system.
`
`—Probable innocence: A sender is probably innocent if, from the attacker’s
`point of view, the sender appears no more likely to be the originator than to not
`be the originator. This is weaker than beyond suspicion in that the attacker may
`have reason to expect that the sender is more likely to be responsible than any
`other potential sender, but it still appears at least as likely that the sender is not
`
`BLUE COAT SYSTEMS - Exhibit 1079 Page 3
`
`

`
`4
`
`·
`
`responsible.
`—Possible innocence: A sender is possibly innocent if, from the attacker’s point
`of view, there is a nontrivial probability that the real sender is someone else.
`
`It is possible to describe these intermediate points for receiver anonymity and
`sender/receiver unlinkability, as well. When necessary, we define these interme-
`diate points more precisely.
`Which degree of anonymity suffices for a user obviously depends on the user and
`her circumstances. Probable innocence sender anonymity should prevent many
`types of attackers from acting on their suspicions (therefore avoiding many abuses,
`e.g., cited in [Miller 1997]) due to the high probability that those suspicions are
`incorrect. However, if the user wishes to avoid any suspicion whatsoever—including
`even suspicions not sufficiently certain for the attacker to act upon—then she should
`insist on beyond suspicion sender anonymity.
`The default degree of anonymity on the web for most information and attackers
`is exposed, as described in Section 1. All recent versions of Netscape Navigator and
`Internet Explorer are configured to automatically identify the client computer to
`web servers, by passing information including the IP address and the host platform
`in request headers.
`
`2.2 What Crowds achieves
`
`As described in Section 1, our system consists of a dynamic collection of users,
`called a crowd. These users initiate web requests to various web servers (and receive
`replies from them), and thus the users are the “senders” and the servers are the
`“receivers”. We consider the anonymity properties provided to an individual user
`against three distinct types of attackers:
`
`—A local eavesdropper is an attacker who can observe all (and only) communi-
`cation to and from the user’s computer.
`—Collaborating crowd members are other crowd members that can pool their
`information and even deviate from the prescribed protocol.
`—The end server is the web server to which the web transaction is directed.
`
`The above descriptions are intended to capture the full capabilities of each at-
`tacker. For example, collaborating members and the end server cannot eavesdrop
`on communication between other members. Similarly, a local eavesdropper cannot
`eavesdrop on messages other than those sent or received by the user’s computer.
`A local eavesdropper is intended to model, e.g., an eavesdropper on the local area
`network of the user, such as an administrator monitoring web usage at a local fire-
`wall. However, if the same LAN also serves the end server, then the eavesdropper
`is effectively global, and we provide no protections against it.
`The security offered against each of these types of attackers is summarized in
`Table 1 and justified in the remainder of the paper. As indicated by the omission of
`an “unlinkability of sender and receiver” column from this table, our system serves
`primarily to hide the sender or receiver from the attacker. In this table, n denotes
`the number of members in the crowd (for the moment we treat this as static) and
`pf > 1/2 denotes the probability of forwarding, i.e., when a crowd member receives
`a request, the probability that it forwards the request to another member, rather
`
`BLUE COAT SYSTEMS - Exhibit 1079 Page 4
`
`

`
`·
`
`5
`
`Table 1. Anonymity properties provided by Crowds
`
`Attacker
`
`Sender anonymity
`
`Receiver anonymity
`
`local eavesdropper
`
`exposed
`
`n ≥
`
`c collaborating members,
`pf
`pf −1/2 (c + 1)
`end server
`
`probable innocence
`
`P (absolute privacy) −→
`n→∞
`beyond suspicion
`
`1
`
`P (beyond suspicion) −→
`n→∞
`P (absolute privacy) −→
`n→∞
`
`1
`
`1
`
`N/A
`
`than submitting it to the end server. (pf is explained more fully in Section 4.) The
`boldface claims in the table—i.e., probable innocence sender anonymity against
`collaborating members and beyond suspicion sender anonymity against the end
`server—are guarantees. The probability of beyond suspicion receiver anonymity
`against a local eavesdropper, on the other hand, only increases to one asymptotically
`as the crowd size increases to infinity. Put another way, if the local eavesdropper is
`sufficiently lucky, then it observes events that expose the receiver of a web request,
`and otherwise the receiver is beyond suspicion. However, the probability that it
`views these events decreases as a function of the size of the crowd. Similarly, a
`sender’s assurance of absolute privacy against collaborating members also holds
`asymptotically with probability one as crowd size grows to infinity (for a constant
`number of collaborators). Thus, if the collaborators are unlucky, users achieve
`absolute privacy. We provide a more careful treatment of these notions in Section 5.
`Of course, against an attacker that is comprised of two or more of the attackers
`described above, our system yields degrees of sender and receiver anonymity that
`are the minimum among those provided against the attackers present. For example,
`if a local eavesdropper and the end server to which the user’s request is destined
`collaborate in an attack, then our techniques achieve neither sender anonymity nor
`receiver anonymity. Another caveat is that all of the claims of sender and receiver
`anonymity in this section, and their justifications in the remainder of this paper,
`require that neither message contents themselves nor a priori knowledge of sender
`behavior give clues to the sender’s or receiver’s identity.
`
`2.3 What Crowds does not achieve
`
`Crowds makes no effort to defend against denial-of-service attacks by rogue crowd
`members. A crowd member could, e.g., accept messages from other crowd mem-
`bers and refuse to pass them along. In our system, such denial-of-service can result
`from malicious behavior, but typically does not result if (the process representing)
`a crowd member fails benignly or leaves the crowd. As a result, these attacks
`are detectable. More difficult to detect are active attacks where crowd members
`substitute wrong information in response to web requests that they receive from
`other crowd members. Such attacks are inherent in any system that uses interme-
`diaries to forward unprotected information, but fortunately they cannot be utilized
`to compromise anonymity directly.
`
`3. RELATED WORK
`
`There are two basic approaches previously proposed for achieving anonymous web
`transactions. The first approach is to interpose an additional party (a proxy) be-
`
`BLUE COAT SYSTEMS - Exhibit 1079 Page 5
`
`

`
`6
`
`·
`
`tween the sender and receiver to hide the sender’s identity from the receiver. Exam-
`ples of such proxies include the Anonymizer (http://www.anonymizer.com/) and
`the Lucent Personalized Web Assistant [Gabber et al. 1997] (http://lpwa.com).
`Crowds provides protection against a wider range of attackers than proxies do.
`In particular, proxy-based systems are entirely vulnerable to a passive attacker in
`control of the proxy, since the attacker can monitor and record the senders and
`receivers of all communication. Our system presents no single point at which a
`passive attack can cripple all users’ anonymity. In addition, a proxy is typically
`a single point of failure; i.e., if the proxy fails, then anonymous browsing cannot
`continue. In Crowds, no single failure discontinues all ongoing web transactions.
`A second approach to achieving anonymous web transactions is to use a mix
`[Chaum 1981]. A mix is actually an enhanced proxy that, in addition to hiding
`the sender from the receiver, also takes measures to provide sender and receiver
`unlinkability against a global eavesdropper.
`It does so by collecting messages of
`equal length from senders, cryptographically altering them (typically by decrypt-
`ing them with its private key), and forwarding the messages to their recipients in a
`different order. These techniques make it difficult for an eavesdropper to determine
`which output messages correspond to which input messages. A natural extension
`is to interpose a sequence of mixes between the sender and receiver [Chaum 1981].
`A sequence of mixes can tolerate colluding mixes, as any single correctly-behaving
`mix server in the sequence prevents an eavesdropper from linking the sender and
`receiver. Mixes have been implemented to support many types of communication,
`for example electronic mail (e.g., [Gulcu and Tsudik 1996]), ISDN service [Pfitz-
`mann et al. 1991], and general synchronous communication (including web brows-
`ing) [Syverson et al. 1997].
`The properties offered by Crowds is different from those offered by mixes. As
`described above, Crowds provide (probable innocence) sender anonymity against
`collaborating crowd members. In contrast, in the closest analog to this attack in
`typical mix systems—i.e., a group of collaborating mix servers—mixes do not pro-
`vide sender anonymity but do ensure sender and receiver unlinkability [Pfitzmann
`and Waidner 1987]. Another difference is that mixes provide sender and receiver
`unlinkability against a global eavesdropper. Crowds does not provide anonymity
`against global eavesdroppers. However, our intention is for a crowd to span mul-
`tiple administrative domains, where the existence of a global eavesdropper is un-
`likely. Another difference is that mixes typically rely on public key encryption,
`the algebraic properties of which have been exploited to break some implementa-
`tions [Pfitzmann and Pfitzmann 1990].
`Crowds’ unique properties admit very efficient implementations in comparison to
`mixes. With mixes, the length of a message routed through a mix network grows
`proportionally to the number of mixes through which it is routed, and the mix net-
`work must pad messages to fixed lengths and generate decoy messages to foil traffic
`analysis. Moreover, in a typical mix implementation, routing a message through
`a sequence of n mixes incurs a cost of n public key encryptions and n private key
`decryptions on the critical path of the message, which are comparatively expensive
`operations. Thus, since the unlinkability provided by mixes is tolerant of up to n−1
`mixes colluding, increasing n improves anonymity but hurts performance. Privacy
`in Crowds can similarly be enhanced by increasing the average number of times a
`
`BLUE COAT SYSTEMS - Exhibit 1079 Page 6
`
`

`
`·
`
`7
`
`request is forwarded among members before being submitted to the end server, but
`this should impact performance less because there are no public/private key oper-
`ations, no inflation of message transmission lengths (beyond a small, constant-size
`header), and no decoy messages needed.
`Another performance advantage of Crowds is that since each user actively partic-
`ipates in the function of the crowd, the throughput of a crowd grows as a function
`of the number of users. In fact, we show in Section 7 that a crowd can scale al-
`most limitlessly (in theory), in the sense that the load on each user’s computer is
`expected to remain roughly constant as new users join the crowd. With a fixed
`network of mixes, the load of each server increases proportionally to the number of
`users, with a resulting linear decrease in throughput.
`
`4. CROWD OVERVIEW
`
`As discussed previously, a crowd can be thought of as a collection of users. A user
`is represented in a crowd by a process on her computer called a jondo (pronounced
`“John Doe” and meant to convey the image of a faceless participant). The user (or
`a local administrator) starts the jondo on the user’s computer. When the jondo is
`started, it contacts a server called the blender to request admittance to the crowd.
`If admitted, the blender reports to this jondo the current membership of the crowd
`and information that enables this jondo to participate in the crowd. We defer
`further discussion of the blender and crowd membership maintenance to Section 8.
`The user selects this jondo as her web proxy by specifying its host name and
`port number in her web browser as the proxy for all services. Thus, any request
`coming from the browser is sent directly to the jondo.1 Upon receiving the first user
`request from the browser, the jondo initiates the establishment of a random path of
`jondos that carries its users’ transactions to and from their intended web servers.
`More precisely, the jondo picks a jondo from the crowd (possibly itself) at random,
`and forwards the request to it. When this jondo receives the request, it flips a
`biased coin to determine whether or not to forward the request to another jondo;
`the coin indicates to forward with probability pf . If the result is to forward, then
`the jondo selects a random jondo and forwards the request to it, and otherwise the
`jondo submits the request to the end server for which the request was destined. So,
`each request travels from the user’s browser, through some number of jondos, and
`finally to the end server. A possible set of such paths is shown in Figure 2. In this
`figure, the paths are 1 → 5 → server; 2 → 6 → 2 → server; 3 → 1 → 6 → server;
`4 → 4 → server; 5 → 4 → 6 → server; and 6 → 3 → server. Subsequent requests
`initiated at the same jondo follow the same path (except perhaps going to a different
`end server), and server replies traverse the same path as the requests, only in reverse.
`A pseudocode description of a jondo is presented in Figure 3. This figure describes
`a thread of execution that is executed per received request. This description uses
`client-server terminology, where one jondo is a client of its successor on the path.
`
`1The services that must be proxied include Gopher, FTP, HTTP and SSL. Otherwise, e.g., FTP
`requests triggered by downloading a web page would not go through the crowd, and would thus
`reveal the user’s IP address to the end server. Java and ActiveX should be disabled in the browser
`as well, because a Java applet or ActiveX control embedded in a retrieved web page could connect
`back to its server directly and reveal the user’s IP address to that server.
`
`BLUE COAT SYSTEMS - Exhibit 1079 Page 7
`
`

`
`8
`
`·
`
`
`
`2
`
`1
`
`3
`
`Crowd
`
`Web Servers
`
`6
`
`4
`
`5
`
`3
`
`1
`
`2
`
`5
`
`6
`
`4
`
`Fig. 2. Paths in a crowd (the initiator and web server of each path are labeled the same)
`
`For each path, indicated by a path id, the value next[path id] is the next jondo on
`the path. To assign next jondos for paths, each jondo maintains a set Jondos of
`jondos that it believes to be active (itself included). When it chooses to direct the
`path to another jondo, it selects the next jondo uniformly at random from this set
`(lines 6, 16, and 26); i.e., “←R S” denotes selection from the set S uniformly at
`random. Subsequent sections shed greater light on the operation of a jondo and
`the pseudocode description of Figure 3.
`For technical reasons, it is convenient for the jondo at each position in a path to
`hold a different path identifier for the path. That is, if a jondo receives a request
`marked with path id from its predecessor in a path, then it replaces path id with a
`different path identifier stored in translate[path id] before forwarding the request to
`its successor (if a jondo). This enables a jondo that occupies multiple positions on a
`path to act independently in each position: if the path id remained the same along
`the path, then the jondo would behave identically each time it received a message
`on the path, resulting in an infinite loop. Path identifiers should be unique; in our
`present implementation, new path id() (lines 5 and 15) returns a random 128-bit
`value.
`Omitted from the description in Figure 3 is that fact that all communication
`between any two jondos is encrypted using a key known only to the two of them.
`Encryption keys are established as jondos join the crowd, as is discussed in Section 8.
`
`5. SECURITY ANALYSIS
`
`In this section we consider the question of what information an attacker can learn
`about the senders and receivers of web transactions, given the mechanisms we de-
`scribed in Section 4. The types of attackers we consider were described in Section 2.
`Our analysis begins with the two attackers for which analysis is more straightfor-
`
`BLUE COAT SYSTEMS - Exhibit 1079 Page 8
`
`

`
`client,request ← receive request()
`if (client = browser)
`sanitize(request)
`if (my path id = ⊥)
`my path id ← new path id()
`next[my path id] ←R Jondos
`forward request(my path id)
`
`else
`
`path id ← remove path id(request)
`if (translate[path id] = ⊥)
`coin ← coin flip(pf )
`if (coin = heads)
`translate[path id] ← ‘submit’
`
`else
`
`translate[path id] ← new path id()
`next[translate[path id]] ←R Jondos
`if (translate[path id] = ‘submit’)
`submit request()
`
`else
`
`forward request(translate[path id])
`
`subroutine forward request(out path id)
`send out path id||request to next[out path id]
`reply ← await reply(∞)
`if (reply = ‘jondo failed’)
`Jondos ← Jondos \ {next[out path id]}
`next[out path id] ←R Jondos
`forward request(out path id)
`
`else
`
`send reply to client
`
`·
`
`9
`
`/* strip cookies and identifying headers */
`/* if my path id is not initialized ... */
`
`/* client is a jondo */
`/* remove “incoming” path id */
`/* “incoming” path id is new */
`/* tails with probability pf */
`
`/* set “outgoing” path id */
`/* select next jondo at random */
`
`/* wait for reply or recognizable jondo failure */
`/* jondo failed */
`/* remove the jondo */
`/* assign a new random jondo for this path */
`/* try again */
`/* received reply from jondo */
`
`subroutine submit request ()
`send request to destination(request)
`reply ← await reply(timeout)
`send reply to client
`
`/* send to destination web server */
`/* wait for reply, timeout, or server failure */
`/* send reply or error message to client */
`
`(1)
`(2)
`(3)
`(4)
`(5)
`(6)
`(7)
`(8)
`(9)
`(10)
`(11)
`(12)
`(13)
`(14)
`(15)
`(16)
`(17)
`(18)
`(19)
`(20)
`
`(21)
`(22)
`(23)
`(24)
`(25)
`(26)
`(27)
`(28)
`(29)
`
`(30)
`(31)
`(32)
`(33)
`
`Fig. 3. Pseudocode description of a jondo
`
`ward, namely a local eavesdropper and the end server. This is followed by an
`analysis of crowd security versus collaborating jondos.
`
`5.1 Local eavesdropper
`
`Recall that a local eavesdropper is an attacker that can observe all (and only)
`communication emanating from an individual user’s computer. When this user
`initiates a request, the fact that she did so is exposed to the local eavesdropper,
`since we make no effort to hide correlations between inputs to and outputs from
`the initiating computer. That is, the local eavesdropper observes that a request
`output by the user’s computer did not result from a corresponding input. Thus, we
`offer no sender anonymity against a local eavesdropper.
`The mechanisms we described do, however, typically prevent a local eavesdropper
`from learning the intended receiver of a request, because every message forwarded
`on a path, except for the final request to the end server, is encrypted. Thus, while
`the eavesdropper is able to view any message emanating from the user’s computer,
`it only views a message submitted to the end server (or equivalently a plaintext
`message containing the end server’s address) if the user’s jondo ultimately submits
`the user’s request itself. Since the probability that the user’s jondo ultimately sub-
`mits the request is 1/n where n is the size of the crowd when the path was created,
`the probability that the eavesdropper learns the identity of the receiver decreases
`
`BLUE COAT SYSTEMS - Exhibit 1079 Page 9
`
`

`
`10
`
`·
`
`as a function of crowd size. Moreover, when the user’s jondo does not ultimately
`submit the request, the local eavesdropper sees only the encrypted address of the
`end server, which we suggest yields receiver anonymity that is (informally) beyond
`suspicion. Thus, P (beyond suspicion) −→
`1 for receiver anonymity.
`n→∞
`
`5.2 End servers
`
`We now consider the security of our system against an attack by the end server only.
`Because the web server is the receiver, obviously receiver anonymity is not possible
`against this attacker. However, the anonymity for the path initiator is quite strong.
`In particular, since the path initiator first forwards to another jondo when creating
`its path (see Section 4), the end server is equally likely to receive the initiator’s
`requests from any crowd member. That is, from the end server’s perspective, all
`crowd members are equally likely to have initiated the request, and so the actual
`initiator’s sender anonymity is beyond suspicion. It is interesting to note that this
`result, as opposed to that for collaborating jondos below, does not depend on pf
`(the probability of forwarding; see Section 4).
`Indeed, increasing expected path
`length offers no additional assurance of anonymity against an end server.
`
`5.3 Collaborating jondos
`
`Consider a set of collaborating (corrupted) jondos in the crowd. A single malicious
`jondo is simply a special case of this attacker, and our analysis applies to this case as
`well. Because each jondo can observe plaintext traffic on a path routed through it,
`any such traffic, including the address of the end server, is exposed to this attacker.
`The question we consider here is if the attacker can determine who initiated the
`path.
`To be precise, consider any path that is initiated by a non-collaborating member
`and on which a collaborator occupies a position. The goal of the collaborators is
`to determine the member that initiated the path. Assuming that the contents of
`the communication do not suggest an initiator, the collaborators have no reason
`to suspect any member other than the one from which they immediately received
`it, i.e., the member immediately preceding the first collaborator on the path. All
`other noncollaborating members are each equally likely to be the initiator, but
`are also obviously less likely to be the initiator than the collaborators’ immediate
`predecessor. We now analyze how confident the collaborators can be that their
`immediate predecessor is in fact the path initiator.
`Let Hk, k ≥ 1, denote the event that the first collaborator on the path occupies
`the kth position on the path, where the initiator itself occupies the 0th position
`(and possibly others), and define Hk+ = Hk ∨ Hk+1 ∨ Hk+2 ∨ . . . Let I denote the
`event that the first collaborator on the path is immediately preceded on the path
`by the path initiator. Note that H1 ⇒ I, but the converse is not true, because the
`initiating jondo might appear on the path multiple times. Given this notation, the
`collaborators now hope to determine P (I|H1+), i.e., given that a collaborator is on
`the path, what is the probability that the path initiator is the first collaborator’s
`immediate predecessor? Refining our intuition from Section 2, we say that the path
`initiator has probable innocence if this probability is at most 1/2.
`
`Definition 5.1. The path initiator has probable innocence (with respect to sender
`
`BLUE COAT SYSTEMS - Exhibit 1079 Page 10
`
`

`
`·
`
`11
`
`anonymity) if P (I|H1+) ≤ 1/2.
`
`In order to yield probable innocence for the path initiator, certain conditions
`must be met in our system.
`In particular, let pf > 1/2 be the probability of
`forwarding in the system (see Section 4), let c denote the number of collaborators
`in the crowd, and let n denote the total number of crowd members when the path
`is formed. The theorem below gives a sufficient condition on pf , c, and n to ensure
`probable innocence for the path initiator.
`Theorem 5.2. If n ≥ pf
`pf −1/2(c + 1), then the path initiator has probable inno-
`cence against c collaborators.
`Proof. We want to show that P (I|H1+) ≤ 1/2 if n ≥ pf
`pf −1/2(c + 1). First note
`that
`
`P (Hi) = (cid:18) pf (n − c)
`
`n
`