1、Wheres Wally? Precise User Discovery Attacks in Location Proximity Services Iasonas PolakisGeorge Argyros Theofi los Petsios Suphannee SivakornAngelos D. Keromytis Network Security Lab, Computer Science Dept. Columbia University, New York, NY, USA polakis, argyros, theofi los, suphannee, angeloscs.c
2、olumbia.edu Abstract Location proximity schemes have been adopted by social networks and other smartphone apps as a means of balanc- ing user privacy with utility. However, misconceptions about the privacy off ered by proximity services have rendered users vulnerable to trilateration attacks that ca
3、n expose their lo- cation. Such attacks have received major publicity and, as a result, popular service providers have deployed countermea- sures for preventing user discovery attacks. In this paper, we systematically assess the eff ectiveness of the defenses that proximity services have deployed ag
4、ainst adversaries attempting to identify a users location. We pro- vide the theoretical foundation for formalizing the problem under diff erent proximity models, design practical attacks for each case, and prove tight bounds on the number of queries required for carrying out the attacks. To evaluate
5、 the completeness of our approach, we conduct extensive experi- ments against popular services. While we identify a diverse set of defense techniques that prevent trilateration attacks, we demonstrate their ineffi ciency against more elaborate at- tacks. In fact, we pinpoint Facebook users within 5
6、meters of their exact location, and 90% of Foursquare users within 15 meters. Our attacks are extremely effi cient and complete within 3-7 seconds. The severity of our attacks was acknowl- edged by Facebook and Foursquare, both of which have fol- lowed our recommendations and adopted spatial cloakin
7、g to protect their users. Furthermore, our fi ndings have wide implications as numerous popular apps with a massive user base remain vulnerable to this signifi cant threat. 1.INTRODUCTION Location-based services (LBS) have become an integral part of everyday life. However, accessibility to fi ne-gra
8、ined location information has raised signifi cant privacy concerns, as users are exposed to various threats, ranging from the inference of sensitive data 33 (e.g., medical issues, politi- cal inclination and religious beliefs) to physical threats such as stalking 10. Furthermore, apart from the reve
9、lations re- garding mass user surveillance by government agencies, arti- cles have revealed that law enforcement agencies also follow more targeted, and unorthodox, tactics. Fake profi les are used to befriend users and gain access to personal data, as well as track their whereabouts by monitoring t
10、heir check- in behavior 6,8. Therefore, the information accessible by users contacts is a signifi cant aspect of their privacy. Revealing a users location is considered a signifi cant pri- vacy breach 46, and services are adopting the more privacy- preserving approach of location proximity: notifyin
11、g users about who is nearby, and at what distance. However, when the exact distance to a user is revealed by the service, trilat- eration attacks become feasible, with several examples being presented in the media recently. Articles have also reported that the Egyptian government used trilateration
12、to locate and imprison users of gay dating apps 7,9. While the use of trilateration has not been confi rmed, such reports highlight the potential severity of such attacks, and the importance of preserving the locational privacy of users. Naturally, these reports have caught the attention of popular
13、services, which in turn have deployed defense mechanisms to prevent local- ization attacks 2. In this paper, we explore the privacy guarantees of 10 popular social networks and LBS. We audit the services and identify the mechanisms deployed to protect the location privacy of their users. To evaluate
14、 the defenses that have been adopted by the industry, we formalize the problem of locating users as a search problem in the discrete Euclidean plane. To our knowledge, this is the fi rst formal treatment of user discovery attacks in proximity services. We prove tight bounds on the number of queries
15、required to attack a service under diff erent proximity models, and devise optimal algo- rithms that realize those attacks. The lower bounds on the query complexity of our techniques provide useful insight on the eff ectiveness of mitigations against localization attacks, such as rate limiting the n
16、umber of queries. We evaluate our attacks against four of the audited ser- vices that employ a diverse set of countermeasures. We show that user discovery attacks against proximity services may require complex techniques; our attacks include geometric algorithms that gradually reduce the candidate b
17、ounding area where a user resides, the employment of colluding ac- counts for obtaining side channel information on the distance between users, and the utilization of statistical algorithms for coping with the randomization used by services as a de- fense mechanism. Our results demonstrate that, des
18、pite the defense mechanisms in place, our attacks are still very ef- fective and time-effi cient, and practical for use at scale and on a continuous basis (real-time tracking).In particular, using a single account, we pinpoint Facebook users within 5 meters of their actual location in 3 seconds, and
19、 90% of Foursquares Swarm users within 15m in 7 seconds.We even stress-test our attacks and demonstrate the feasibility of tracking moving targets in real time. Due to the recent events 9, Grindr hides the distance information for citizens of oppressive regimes. Even without any distance informa- ti
20、on disclosed, we are able to carry out successful attacks by 1 inferring the distance to our target. Using a pair of collud- ing accounts, and the distance-based ordering of users by Grindr, we pinpoint 67% of the users within 10m of their exact location, and 98% within 19m. Similarly, even though S
21、kout implements a sophisticated randomization defense, we are able to pinpoint its users within 37.4m on average. Our fi ndings reveal that there is no industry standard for ensuring the locational privacy of users; attempts are based on ad-hoc approaches that often exhibit a lack of under- standing
22、 of the technical intricacies of localization attacks. Despite the active eff ort to prevent such threats, every ser- vice we audited was vulnerable to, at least, one of our at- tacks. To provide a robust solution, we revisit an obfuscation mechanism from the literature, namely spatial cloaking 19,
23、and apply it to the domain of distance-based proximity ser- vices. By quantizing the plane and mapping users to points on a grid, the service can prevent adversaries from pinpoint- ing users to a fi ner precision than that of a grid cell. To in- centivize services to adopt this defense, we provide a
24、 precise characterization of both the privacy obtained (under certain assumptions), and the tradeoff between privacy and usabil- ity. After our disclosure, Facebook and Foursquare acknowl- edged the severity of our attacks and, following our guide- lines, adopted spatial cloaking for protecting thei
25、r users. The main contributions of this paper are: We present a formal treatment of user discovery attacks within a proximity service. We model the problem, prove the lower bounds on the query complexity, and design algorithms that match the corresponding lower bounds. We evaluate the privacy of pop
26、ular proximity services through extensive experimentation, and reveal the short- comings of existing proximity models and defenses. The disclosure of our fi ndings to the services resulted in Face- book and Foursquare adopting spatial cloaking. We analyze the practical aspects of our attacks, and id
27、en- tify key characteristics that aff ect their performance and accuracy. We provide guidelines for impairing the attacks and ensuring a minimum level of privacy without incur- ring a signifi cant deterioration of the quality of service. We release an open-source auditing framework for assist- ing d
28、evelopers and researchers in assessing the privacy of proximity services. Our framework has already been used by Facebook for evaluating their newly-adopted spatial cloaking mechanism. 2.MODELLING DISCOVERY ATTACKS In this section we provide the theoretical modelling of our user discovery attacks. F
29、or simplicity, we refer to the adver- sary as Mallory and the target user as Wally. Threat Model. The adversary can be any entity inter- ested in determining a users location; a government or law enforcement agency conducting user surveillance ( 6,8), a third party (e.g., insurance company) interest
30、ed in inferring private data or a malicious individual (e.g., stalker) 10. To highlight the ineffi ciency for existing designs and counter- measures, we adopt a weak adversarial model: the adversary uses only the distance information revealed by the service. Our attacks do not require prior knowledg
31、e of the users whereabouts, and the only requirement is to have an account in the service so as to obtain some type of information about the distance to the user. In Section 5 we demonstrate that we can identify a users location with high precision, and also track a moving target in real time. Probl
32、em Formulation. We formulate our problem as a search problem in the discrete Euclidean plane. This is justifi ed by the fact that both services and protocols (e.g., GPS) cannot provide arbitrary accuracy. By modelling it as a discrete problem, we can adapt the size of the input to match the accuracy
33、 provided by the service. We consider a target user u residing at a point puof the discrete Euclidean plane. The attacker can request proxim- ity information regarding the location of the user u. This is obtained through an oracle, which we refer to as a proximity oracle P. Since the attacker can fa
34、ke her own location, she can query the proximity oracle from any point within the Euclidean plane. Thus, the proximity oracle accepts a point p and returns proximity information for the point p and the location puof the target user. We denote by Pu() the proximity oracle which, for an input of a poi
35、nt p, outputs some function of p,pu . Also, we defi ne as dist(p1,p2) the Euclidean distance between two points p1,p2. We proceed to defi ne the user discovery problem, our main algorithmic problem, in the context of location proximity services. Definition 1. User Discovery Problem (UDP): Let pube a
36、 point in the discrete Euclidean plane and A an area containing pu. In the User Discovery Problem the goal is to identify the point pu, given as input the area A and black box access to a proximity oracle Pu. In the following sections we will describe three diff erent implementations of the proximit
37、y oracle that capture the protocols used by real services. For each of these oracles, we describe how to solve UDP given access to the respective oracle. 2.1Disk User Discovery Problem We start by giving the defi nition of the fi rst oracle. Definition 2. Disk Proximity Oracle: A disk proxim- ity or
38、acle Pr,u(p) with radius r, accepts as input a point p in the discrete Euclidean plane and is defi ned as: Pr,u(p) = ( 1if dist(p,pu) r 0otherwise This model captures services and protocols that inform the user whether another user is within a certain distance of his current location; otherwise the
39、user is not in proximity and no further information is given. We defi ne the Disk User Discovery Problem (DUDP) to be the UDP given black box access to a Disk Proximity Oracle.We solve DUDP by partitioning the problem into two subproblems, which require a diff erent approach in order to be solved: f
40、i rst, we wish to restrict the user within a single disk of radius r and, second, to search that disk for the target point pu. In the former subproblem, the user is given a, possibly large, area A which she wants to cover with disks of radius r in order to restrict the search area within a single di
41、sk. We call this problem the Disk Coverage Problem. To achieve an effi cient attack, we wish to cover the area with the minimum number of disks. Definition 3. In the Disk Coverage Problem, the in- put is an area A in the discrete Euclidean plane and a num- ber r 0. The goal is to cover the area A wi
42、th the minimum number of disks of radius r. 2 After the target users location is restricted within a single disk of radius r, one has to use the proximity oracle to fur- ther refi ne the users location up to a single point. We call this subproblem the Disk Search Problem. Definition 4. In the Disk S
43、earch Problem the input is a single disk of radius r along with a proximity oracle Pr,u(). The goal is to uniquely pinpoint the point puwithin the input disk. Notice that the Disk Search Problem is exactly the DUDP when the input area is restricted to a disk of radius r. Be- cause the two cases are
44、handled in a diff erent manner, we address them separately. Next, we examine each subprob- lem and describe algorithms for solving them. Solving Disk Coverage. To generalize our attack, we assume that the only information the attacker has is a very coarse-grained approximation of the location of the
45、 targeted user; for example Mallory might know which state Wally lives in. Given a total area in which the user might reside, our fi rst goal is to to pinpoint the user within a disk of radius r, as provided by the proximity oracle. A problem that corresponds precisely to the Disk Cover- age Problem
46、 is the Minimum Dominating Set (MDS) prob- lem in a special class of graphs called Unit Disk Graphs (UDG). In the MDS problem, one is given as input a graph G = (V,E) and the goal is to fi nd a set D V such that for every v V there exists a u D for which (u,v) E. UDG are a special class of geometric graphs; even though a number of equivalent defi nitions exist, we will use what is referred to as the proximity model 15: Definition 5. (Prox
