# SSID Oracle Attack on Undisclosed Wi-Fi Preferred Network Lists

Authors: Ante Dagelić; Toni Perković; Bojan Vujatović; Mario Čagalj
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

User’s location privacy concerns have been further raised by today’s Wi-Fi technology omnipresence. Preferred Network Lists (PNLs) are a particularly interesting source of private location information, as devices are storing a list of previously used hotspots. Privacy implications of a disclosed PNL have been covered by numerous papers, mostly focusing on passive monitoring attacks. Nowadays, however, more and more devices no longer transmit their PNL in clear, thus mitigating passive attacks. Hidden PNLs are still vulnerable against active attacks whereby an attacker mounts a fake SSID hotspot set to one likely contained within targeted PNL. If the targeted device has this SSID in the corresponding PNL, it will automatically initiate a connection with the fake hotspot thus disclosing this information to the attacker. By iterating through different SSIDs (from a predefined dictionary) the attacker can eventually reveal a big part of the hidden PNL. Considering user mobility, executing active attacks usually has to be done within a short opportunity window, while targeting nontrivial SSIDs from user’s PNL. The existing work on active attacks against hidden PNLs often neglects both of these challenges. In this paper we propose a simple mathematical model for analyzing active SSID dictionary attacks, allowing us to optimize the effectiveness of the attack under the above constraints (limited window of opportunity and targeting nontrivial SSIDs). Additionally, we showcase an example method for building an effective SSID dictionary using top-N recommender algorithm and validate our model through simulations and extensive real-life tests.


---

## Body

## 1. Introduction

Location privacy presents one of the most challenging problems in today’s mobile era. Modern mobile devices such as smartphones, tablets, or smart watches collect information from surrounding devices that can be used for Wi-Fi-based positioning systems [1]. In a similar fashion, these devices emit radio signals that can be used for localization and tracking by using, for example, cell tower trilateration [2]. Furthermore, Wi-Fi information transmitted from mobile devices can be used for indoor tracking and targeted services [3–6]. Many of these solutions base their services upon collecting a number of management frames (e.g., beacon, probe request, and probe response frames,) that are transmitted by devices, whose main purpose is to establish a fast and efficient connection during the authentication process.A number of papers discuss various threats to user’s privacy based upon collected probe requests containing an Access Point’s (AP) Service Set Identifier-SSID [7–13]. Wi-Fi-enabled devices using Active Service Discovery broadcast these probe request frames aimed at the set of preferred APs to increase the connection speed. Such probe request packet contains an SSID of a previously associated AP stored in the device’s preferred network list-PNL (a complete list of previously associated APs), the MAC address of the mobile device, and some other information. Simply by observing these probe request packets, a potential attacker can learn a complete PNL, which raises serious privacy threats. As an example, we highlight SSID=Shelbourne Medical Clinic from a large amount of Wi-Fi traffic that we passively collected during a festival that attracts 50 000 people. This problem is highlighted by the fact that SSIDs can also be geolocated (e.g., by using a WIGLE service [14]) thus violating user’s location privacy.To mitigate these privacy breaches made possible by active scanning (AS), the devices could use passive scanning (PS) technique whereby devices transmit no probe request packets but instead listen to beacon packets emitted from the APs. Unfortunately, compared to active scanning, this technique accomplishes slower connection times [15]. Besides direct probe mode, active scan also supports a broadcast probe mode where probe request packets hold an empty SSID field. All neighboring APs (including the ones in the device’s PNL) will answer the broadcast probe request. This mode is widely used in most of today’s Android-based mobile devices (Although a recent discovery showed that some Android devices transmit their PNL while being in low-power state with their screen turned off, it seems that Google was unaware of such vulnerability [16, 17]). Using this mode of operation, the attacker cannot learn more information about the user’s location history by simply observing broadcast probe request packets.However, the mentioned broadcast probe mode does not protect the user from an active attack. One of the simplest methods to verify whether a user was connected to an AP in a specific location includes the creation of a rogue AP with that specific name (SSID) and identifier, i.e., by mounting a so-called Karma attack [18], verifying if the victim initiates a connection to it. In the recent work where Karma attack was performed, only a fraction of different SSIDs were considered, by using a dictionary containing a small number of the most popular APs that are found in the surrounding area (a popular café bar or a restaurant, etc.) [19]. Similarly, faking an AP has also been used in [20] by performing a simple dictionary attack on hidden SSID networks, using a Phyton library Scapy. However, as opposed to static environments in which users are at their homes and offices with laptops and desktop PCs, users with smartphones are usually mobile with their devices; hence the opportunity window for the attack can be very time limited. In contrast to existing work, in this paper we focus on greatly improving the attack’s performances. We want to find methods and techniques that will allow the attacker to query every SSID from as large as possible dictionary within the given opportunity window against a victim’s device. Moreover, we are interested in discoveringnontrivial SSIDs, thus increasing the importance of disclosed SSIDs from user’s PNL.Such form of a dictionary attack is universal to all devices that implement IEEE 802.11 standard, regardless of the active or passive scanning technique. The following contributions have been made:(i)
We developed an analytical model for the SSID dictionary attack;(ii)
We created a probing strategy that minimizes probing time of the complete SSID dictionary;(iii)
We carried out extensive real-life tests and simulations to validate our model.Additionally, an example SSID dictionary building algorithm is provided using a modified top-N recommendation algorithm [21] to reflect victim’s PNL.The rest of the paper is organized as follows: in Section2 we are defining the general attack setup and describing device behavior. Section 3 provides a comprehensive mathematical model for the attack strategy followed by Section 4, which provides an overview of the practical tests carried out on multiple devices alongside performed simulation and an example algorithm for building the dictionary. Finally, we cover related work and conclude in Sections 5 and 6.


## 2. System and Attacker Model

Regardless of the type of scanning technique (Active Service Discovery with or without an empty probe or Passive Service Discovery), in our model we assume that devices are periodically scanning for available APs as shown in Figure1, whereby the scanning period is significantly shorter than the idle period when the device is not scanning for the available networks. The scan period depends on the device model, OS, settings controlled by the user, such as keeping Wi-Fi on/off during sleep mode [22], location services, and also general sensors’ activity (accelerometer, gyroscope), which might change the state of the device. Other features that can affect the periodic scanning behavior of Wi-Fi devices are determined by the activity of various services, such as if cellular data is turned on, or if the smartphone is in maintenance mode, or if the user is extensively using Internet. A comprehensive overview of measured scanning periods depending on the mentioned settings and scenarios can be found in [23].Figure 1
SSID Oracle attack basic setup.


### 2.1. Periodic Wi-Fi Scan Intervals

Scanning periods in practice do change in length, either in fixed increases or exponentially. However, the scanning period tends towards repetition in the same length intervals, as can be seen from [23, 24]. The authors have tested various Apple and Android devices and the results have shown that all the devices end up scanning for Wi-Fi networks in fixed intervals. Periodic behavior was observed in various use cases for the victim (Wi-Fi settings screen, other screens, and display off). The authors in [23] have also concluded that these are fixed times depending on the victim’s device and operating system, which has also been observed in our tests. Furthermore, the periodical behavior can be actively provoked, and the required scanning/idle time durations can be measured by the attacker, as it will be described in the following subsection. Increasing the scanning frequency also increases the success rate of various Wi-Fi attacks/data analysis and has been noted by others before [25].


### 2.2. Increasing the Scanning Frequency

Although the model presented in this paper optimizes the performances for any given periodic scanning frequency, there are ways for the attacker to actively control the periodic behavior of Wi-Fi scanning intervals. For example, in our tests with smartphone devices, we showed that if the device is in sleep mode having cellular data enabled (e.g., withEDGE/3G/4G), simply by sending push notification to the victim (a WhatsApp/Viber message) we can induce the device to wake up and initiate a Wi-Fi scan. We have noticed that the device typically initiates the scan within 5s from waking up. If cellular data is not enabled, we can also send anSMS to force the device to wake up from the sleep state.We have observed that some devices, prior to going to sleep mode, scan for the neighboring APs with time periods that increase exponentially. Our initial brief analysis on iPhone 6s plus has shown another method to minimize the scan intervals for a device while being in sleep mode. By assuming that the device is connected to a known AP and continuously enabling iPhone to connect/force disconnect from the AP (e.g., by jamming a Wi-Fi channel), we can keep the device in a60s scan period, as opposed to double or triple values otherwise.


### 2.3. Threat Model

As depicted in Figure1, two different timelines are present during the attack. The configuration of the device timeline is unknown to the attacker, and the attacker timeline is limited in length (the attack can be performed only within the Wi-Fi vicinity of the victim). The attacker is constantly faking APs using different SSIDs. The goal is to test as many unique SSIDs within the available time, using as much as possible of thematch opportunity time during the device scan period. If the attacker gets a connection attempt from the device, for a fake AP, the attack is considered a success.Although the basic idea seems quite straightforward, the attack presents a lot of different challenges. How does the attacker know when thematch opportunity occurs? What is the scanning and idle period length? How good is the Wi-Fi communication channel? Which SSIDs should be tested? How do we maximize the number of unique SSIDs we can test?In the following section, we will answer these questions and describe the SSID Oracle attack.


## 2.1. Periodic Wi-Fi Scan Intervals

Scanning periods in practice do change in length, either in fixed increases or exponentially. However, the scanning period tends towards repetition in the same length intervals, as can be seen from [23, 24]. The authors have tested various Apple and Android devices and the results have shown that all the devices end up scanning for Wi-Fi networks in fixed intervals. Periodic behavior was observed in various use cases for the victim (Wi-Fi settings screen, other screens, and display off). The authors in [23] have also concluded that these are fixed times depending on the victim’s device and operating system, which has also been observed in our tests. Furthermore, the periodical behavior can be actively provoked, and the required scanning/idle time durations can be measured by the attacker, as it will be described in the following subsection. Increasing the scanning frequency also increases the success rate of various Wi-Fi attacks/data analysis and has been noted by others before [25].


## 2.2. Increasing the Scanning Frequency

Although the model presented in this paper optimizes the performances for any given periodic scanning frequency, there are ways for the attacker to actively control the periodic behavior of Wi-Fi scanning intervals. For example, in our tests with smartphone devices, we showed that if the device is in sleep mode having cellular data enabled (e.g., withEDGE/3G/4G), simply by sending push notification to the victim (a WhatsApp/Viber message) we can induce the device to wake up and initiate a Wi-Fi scan. We have noticed that the device typically initiates the scan within 5s from waking up. If cellular data is not enabled, we can also send anSMS to force the device to wake up from the sleep state.We have observed that some devices, prior to going to sleep mode, scan for the neighboring APs with time periods that increase exponentially. Our initial brief analysis on iPhone 6s plus has shown another method to minimize the scan intervals for a device while being in sleep mode. By assuming that the device is connected to a known AP and continuously enabling iPhone to connect/force disconnect from the AP (e.g., by jamming a Wi-Fi channel), we can keep the device in a60s scan period, as opposed to double or triple values otherwise.


## 2.3. Threat Model

As depicted in Figure1, two different timelines are present during the attack. The configuration of the device timeline is unknown to the attacker, and the attacker timeline is limited in length (the attack can be performed only within the Wi-Fi vicinity of the victim). The attacker is constantly faking APs using different SSIDs. The goal is to test as many unique SSIDs within the available time, using as much as possible of thematch opportunity time during the device scan period. If the attacker gets a connection attempt from the device, for a fake AP, the attack is considered a success.Although the basic idea seems quite straightforward, the attack presents a lot of different challenges. How does the attacker know when thematch opportunity occurs? What is the scanning and idle period length? How good is the Wi-Fi communication channel? Which SSIDs should be tested? How do we maximize the number of unique SSIDs we can test?In the following section, we will answer these questions and describe the SSID Oracle attack.


## 3. Modeling the Problem

This section introduces a comprehensive mathematical model that depicts a general SSID attack. We begin with modeling the problem, after which we introduce the SSID Oracle attack accompanied by various attack variations and optimization techniques.The proposed general model depicts a simple question: how can an adversary recover (at least one) SSID from the user’s PNL and thus his previous whereabouts. The theoretical model comprises various SSID attacks scenarios, ranging from well-known passive sniffing to active attacks in which an adversary performs the attack with rogue access point or even advanced brute force attacks to user’s PNL.Before we pursue the detailed description of the attack, let us denote the following notation used to describe the location privacygame. First, we denote a targeted user’spreferred network list (PNL) with P, unknown by the adversary A prior to the attack. D denotes a dictionary list of (nontrivial) SSIDs prepared by A to be tested. A has a limited time period to execute the attack, so D needs to contain SSIDs which are highly likely to be present in P. A confirmation that an SSID from D is successfully tested to be present in P is denoted with a hit. A has a goal of achieving a hit, under assumption that P∩D≠∅ holds.Definition 1.
We definesuccess probability  PsuccL-priv(A) as the probability that the adversary A performs a successful location privacy attack L-priv and learns at least one SSID from P:(1)PsuccL-privA≜PP∩D≠∅,hit=PP∩D≠∅·Phit∣P∩D≠∅As can be seen, the success probabilityPsuccL-priv of the attacker A can be denoted as a product of two probabilities. Conditional probability Phit∣P∩D≠∅ denotes the probability in which A observes a hit (a successful query), meaning that condition P∩D≠∅ holds. Probability P[P∩D≠∅] is responsible for building a good quality dictionary for the targeted victim such that the condition P∩D≠∅ holds. Since the available opportunity window for A is time limited, potential attack’s performances need to be optimized alongside having a quality dictionary.There is a wide range of different strategies for revealing user’s PNL (e.g., ranging from blind guessing to even physically readingP off the user’s screen). Some devices in Active Service Discovery mode are transmitting the complete unencrypted PNL list to quickly establish a connection to a previously associated APs [17]. For A gathering unencrypted probe request packets represents a trivial problem for revealing P and will not be discussed any further in our work. Our model assumes that devices are periodically broadcasting empty probe requests or are passively scanning for APs. As we describe further in this paper, all Wi-Fi devices using active or passive service discovery are vulnerable to our attack.


### 3.1. Defining SSID Oracle

Recall, to verify that the victim’s device holds anSSID within its preferred network list P, that the adversary A can mount a rogue access point holding that specific SSID (i.e., by using the Karma tool [18].). If A confirms that the user initiated a connection, he concludes that the SSID is a part of the victim’s PNL list (SSID∈P).Definition 2 (SSID Oracle).
We denote victim as a binary response SSID OracleO. When A fakes an SSID, he is querying O for a binary outcome. If SSID∈P, then O returns a positive outcome; otherwise O does not respond. We denote the following notation:(2)OSSID=1,ifSSID∈P0,ifSSID∉PIn our attackO responds to queries only during the scanning period (Figure 1,match opportunity) and will respond with a positive outcome only in the case that the queried SSID is within its P. No response is considered to be a negative outcome. However, the success rate of querying O is subject to channel quality, which can potentially cause false negatives. In case of a low channel quality, the attacker cannot tell whether the cause for no response is SSID∉P or the victim did not receive the query.IfO would respond to every query and thematch opportunity would span during the entire attack time uninterrupted, our work would be much simpler, as we would only have to manage the problem of building a good quality SSID dictionary and test every SSID from that list one by one. A similar approach has already been covered by many papers describing dictionary or brute force attempts on password cracking [19, 26].Since in our model the attacker does not actually know when that match opportunity period occurs (we assume the worst case scenario in our model with passive scan, as measured for iOS 10) and is subject to channel quality, it is necessary to create a model/algorithm that will allow the attacker to test every SSID at least once with as high probability as possible, within the match opportunity window.


### 3.2. SSID Oracle Attack

Independently of the type of scanning technique (Active Service Discovery with or without an empty probe request or Passive Service Discovery) in our model the Wi-Fi scan occurs periodically everyTI seconds (idle period in between scans) and lasts only for a short scanning period of TS, such that TS≪TI.Figure2 describes the general trade-offs that we face when executing SSID Oracle attack. As mentioned at the beginning of this section, to succeed in the location privacy game the adversary A would have to create a dictionary of (nontrivial) SSIDs that hold at least one SSID from P. A simplest solution would be to increase the dictionary size so that the probability P[P∩D≠∅] of finding at least one SSID approaches 1. This can be clearly seen from Figure 2, where the shape of the curve depends on different approaches to building D. Our goal is to test SSIDs having a higher chance of being in P first, so P[P∩D≠∅] will grow faster for small D with tendency of becoming linear for large D. One such example approach on building dictionaries based on recommendation algorithm is described in Section 3.5. However, dictionary size depends on the opportunity window TA, the time available for the attacker to execute the attack (Figure 1). If we take into account the fact that adversary A sends SSIDs (e.g., beacons) at maximum rate r, we can denote withslot a discrete time period in which one SSID from D is sent to the Oracle O (victim’s device) within TS period. Since TS is the only valuable time period for A to conduct the attack, the maximum available number of time slots for the attacker within opportunity window TA equals TA·TS/TS+TI·r. For this reason, the dictionary size tested on O satisfies the following condition: D≤TA·TS/TS+TI·r. As the dictionary size increases, the required time for the attacker A to test all SSIDs increases, so the conditional probability Phit∣P∩D≠∅ drastically decreases.Figure 2
Conditionalhit chance Phit∣P∩D≠∅ and dictionary quality P[P∩D≠∅] in comparison to the size of dictionary D.Another observation shows just how big of an impactTI has on the attack. If we assume that idle time is zero (TI=0), the victim’s device would be constantly scanning the Wi-Fi channel. A can then create D such that the dictionary size equals the maximum number of timeslots available in TA (D¯=TA·r). A could easily test many more SSIDs from the dictionary against the victim’s device within TA (by taking into account the fact that all queries arrive to the Oracle O (there are no collisions in Wi-Fi channel) and that there are no retransmissions.).In our model, we do not know whenTS or TI occurs, just a measurement of their lengths. To be able to execute the attack, despite not knowing when a new scanning period starts, a logical solution (intuition) would be to create smallchunks of size L testable slots, fill them with SSIDs from D, and retransmit chunks for the duration of time period T until we are convinced that O received all L queries from the chunk at least once. After the chunk retransmission time T, A sends the following chunk containing another L slots. The proposed method is described in detail in Figure 3.Figure 3
Attacker and victim timelines.The attacker strategys can be described by using the following triplet D, L, and T:(3)s=D,L,TOur goal is to find the optimal strategys∗ which will result, given the available time period TA (opportunity window), in the best SSID Oracle attack execution:(4)s∗=arg⁡maxD,L,T⁡Phit∣P∩D≠∅·PP∩D≠∅The following sections focus on definings∗. We start by discussing and defining L and T parameters which affect the efficiency of attack execution. Later in Section 3.5 an example method for defining and building a good quality D is presented.


### 3.3. Finding Optimal ParametersL∗ and T∗

As we mentioned in the previous section, chances of making OracleO respond to a query with a positive answer depend on multiple parameters, out of which some are predetermined by the Oracle (smartphone) implementation (i.e., periods TI, TS), while some are controlled by the adversary A (i.e., dictionaries D, L, and T). In this section, our goal is to find the optimal parameters for the chunk size L∗ and chunk retransmission time period T∗. Recall from Figure 3 that it is necessary to find a strategy that guarantees (with high probability) that every slot from the chunk of size L hits the scanning interval TS.Let us consider the scenario in which the attackerA is omniscient; i.e., A knows the exact moment at which O initiates the search for neighboring SSIDs. Since A knows when scan initiates and also its duration TS, he can adapt the attack transmission start time Tstart towards O at maximum rate r, as can be seen in Figure 4-I. Now we can easily conclude that the maximum number of unique slots that can fit into TS equals to r·TS (recall that r denotes a rate at which chunks are transmitted). Due to the fact that during the period TI the Oracle O cannot receive any query from A, we can denote r·TS as a single chunk Li, i.e., Li=Li=r·TS. Now, referring back to our attacking model (Section 2), A is not omniscient and cannot actually know when TS starts; therefore it is necessary to find such a strategy that the complete L finds TS period.Figure 4
Choosing optimal chunk transmission time T.Please observe from Figure4 that since the TS+TI intervals are periodically repeating, the easiest solution for A would be to retransmit chunks Li towards left and right (Figure 4-II) and expand them until it reaches the expansion of chunk Li-1 on the left and chunk Li+1 on the right (Figure 4-III). How does this help the attacker? Figure 4-IV shows that since chunk retransmission period equals T=TS+TI and L=r·TS, regardless of when Tstart period actually occurs, the complete chunk is still going to hit the appropriate scanning period TS, with Tstart∈[0,TS+TI]. The zoomed sections in Figure 4, A (in case of all-knowing O scenario) and B (in case of any other scenario), show that the same unique SSIDs contained in L chunk will overlap the scanning period TS in both cases.For this reason the optimal chunk size equals the number of slots that can fit in the scanning periodTS:(5)L∗=r·TS,whereas the optimal time interval to retransmiti-th chunk equals the sum of TI and TS:(6)T∗=TS+TI.Given the attacker’s opportunity windowTA, we can calculate the maximum number of unique testable slots Nslot for our strategy s∗:(7)Nslot=TATS+TI·L,We have shown that by using optimalT∗ we can achieve the same number of slots Nslot compared to the omniscient A we started this discussion from, although the actual attacker A cannot tell the exact moment at which O initiates TS.The following conclusion sums up our observations so far: when definings∗, execution of SSID Oracle attack with parameters L∗ (5) and T∗ (6) willmaximize the available number of unique slots  Nmax.However, in low channel quality conditions there is always a chance that query sent fromA does not get to O. If we have a hit (O responds to a query with positive outcome), there is a chance that the response does not get to A, so we are introducing a new parameter-probability p that SSID Oracle successfully receives and responds to a query.For this reason it may not be optimal to fill all the slots with unique SSIDs; thus the size of the dictionary might have to decrease even further.(8)D¯max≤Nslot.


### 3.4. Matching Dictionary to Slots

In previous sections we carried out the analysis of proposed model in good quality channel environments (p≈1). We have shown that the optimal chunk retransmission time is the period T∗=TS+TI, while the chunk size equals the number of queries that can fit the scan interval L=L∗=r·TS. In this scenario, D was equal to the maximum number of testable slots D=Nslot within TA.However, what can be done in scenarios of low quality channelp<1? In such scenarios, not all slots that attacker A sends within scan period TS will be received by O, the same way the responses sent by O (in case we have a hit) will not be received by A (all these parameters depend on attacker’s Wi-Fi card quality, victim’s Wi-Fi card quality, channel quality, distance from the attacker and the victim, etc.). To be more precise, in low quality channel conditions it could be better to retransmit SSIDs that have a larger probability of occurrence in the victim’s PNL list, rather than to transmit Nslot different SSIDs for a given TA.Let us useD′ to denote the set of all SSIDs known by A, whereas not all SSIDs from D′ have the same probability of being part of the victim’s PNL list P. Our goal is to maximize PsuccL-priv thus finding the optimal D⊂D′ to be tested within window of opportunity TA. The event of a successful O test, with a positive result, is denoted by hi,∀i∈D′. To find the best D, A has to use different tools (such as the example recommender system found in Section 3.5) to assign a chance that an SSID contained in D′ is also contained in the victim’s PNL. For this purpose, we are introducing a new subjective probability parameter pi assigned to every SSID in D′ and calculated by A.(9)pi∈0,1∀i∈D′Recall that we denote withslot a discrete time period in which one SSID is sent to the victim’s device within TS period. It is our goal to determine the number of slots every SSID in D′ should take:(10)ni∈0,Nslot∀i∈D′In order to characterizeni, we proceed as follows:(11)PsuccL-priv=PP∩D′≠∅·Ph∣P∩D′≠∅=PP∩D′≠∅·Ph1∨⋯∨hD′∣P∩D′≠∅The dictionary quality equation part of (11) resolves to(12)PP∩D′≠∅≜∑i∈D′Pi∈P∣P∩D′≠∅=∑i∈D′pi≤1,Attack execution equation part of (11) resolves to(13)P∨ihi∣P∩D′≠∅≤∑i∈D′Phi∣P∩D′≠∅=1∑i∈D′Phi,i∈P∣P∩D′≠∅=∑i∈D′Phi∣i∈P,P∩D′≠∅·Pi∈P∣P∩D′≠∅=2∑i∈D′1-1-pnipiwhere (1) follows fromPA∣B=PA,C∣B+PA,¬C∣B, whereas latter part of the equation in our case is equal to 0 (i∉P) and (2) comes the under assumption that Oracle queries are mutually independent of each other (sum of probabilities). Please note that due to burst effects in Wi-Fi channel [27] we may not always face such scenario, since there is a chance that consecutive Wi-Fi packets are more likely to fail to transmit if previous packets also failed. Given the premises Nslot≫L and T≫TS we can see that different L slots are being tested couple of seconds apart, meaning that different chunks are not subject to the same error burst. In case of retransmitting SSIDs, we use interleaving to tackle the error burstiness.We are now ready to set the optimization problem, whose solution will giveA the required parameters ni. Please note that the SSID Oracle attack requires ni∈N0, but we are using linear optimization to solve the optimization problem. To execute an attack, it is required to round ni calculated from our model, as will be shown in simulations later.(14)maxn1,…,nD′∑i∈D′pi-pi1-pnis.t.∑ini≤TATSTS+TI·r=Nslotni≥0pi∈0,1∑ipi≤1p∈0,1We approach the optimization problem (14) using Lagrange multipliers method. Objective function has unique solutions based on its concave nature.Lemma 3.
The relation between SSID subjective correctness probabilitypi, channel quality p, and number of testing attempts ni for every SSID is(15)ni∗-nj∗=log⁡pj/pilog⁡1-pAs can be seen from (15) and Figure 5, for good channel (p>0.95), the attacker does not significantly increase his hit chance by retransmitting SSIDs with higher probability of occurrence. On the other hand, a bad channel (p<0.5) brings up the importance of having a good SSID dictionary generator algorithm.Figure 5
Transmission attempts differenceni-nj as a function of channel and SSID quality (based on Lemma 3).Theorem 4.
SSID Oracle attack execution strategys∗ should be achieved by picking L∗=r·TS and T∗=TS+TI parameters. The optimal execution strategy s∗ maximizes the number of unique testable slots Nslot. When matching D to Nslot, the condition ni-nj=log⁡pj/pi/log⁡1-p,∀i,j∈D′ must be fulfilled to achieve the best attack performance in case of a poor quality channel p.In the next subsection, we will introduce an example dictionary creation method, based on top-N recommendation algorithm, which can provide us with the required SSID importance parameterspi.


### 3.5. Building a Dictionary

In this subsection we introduce an example dictionary generation algorithm, based on a recommendation algorithm. We will only briefly cover the approach and later provide the experimental results in Section4.3. Please note that there can be multiple different dictionary creation approaches, depending on the information the attacker has on the potential victim. One goal could be to gather as many pairs of Wi-Fi MAC address and SSID to do statistical analysis of a crowd (similar work to many papers mentioned in our related work). In that case, having a more general dictionary is the best approach. Another goal could be the deanonymization of a specific person or a group by linking the victim to his MAC address. In that case, the dictionary should be prepared for that specific scenario, containing related SSIDs from victims neighborhood. Nevertheless, our SSID Oracle attack strategy will maximize the potential successful outcome for any provided dictionary.In order for the attack to be successful, the dictionary has to be(i)
compact: the size of the dictionaryD should be small enough so that performing the attack is feasible in reasonable time(ii)
precise: the dictionary should reflect victim’s PNL as much as possible (contain as many SSIDs that are in the user’s PNL as possible)The method we used for building a dictionary for the attack is based on collaborative filtering, namely, a modified version of Item-based top-N recommendation algorithm as seen in [21, 28]. It outputs a list of N recommended items that user might prefer/consume/buy/visit based on the current knowledge of user’s preferences/history and the knowledge of preferences/history of other users (training dataset). Cosine based similarity has shown to produce the best results.After building a list ofN recommended SSIDs for each test user, it is compared with the original PNL and the hit-rate (HR) is calculated: (16)HR=#ofSSIDsrecommendedthatareinusersPNLs#ofSSIDsinusersPNLsAn HR value of1.0 indicates that the algorithm was always able to recommend the hidden item, whereas an HR value of 0.0 indicates that the algorithm was not able to recommend any of the hidden items [21].Our algorithm uses two parameters which affect the effectiveness of the modified recommender system. The number of similar SSIDs we want to store for each SSID in the learning process is denoted byk∈N. The growth of the exponential equation used for calculating the importance of SSID repetition in the training set data is controlled by parameter A∈R.In the next section we will perform various SSID Oracle attacks using our setup.


## 3.1. Defining SSID Oracle

Recall, to verify that the victim’s device holds anSSID within its preferred network list P, that the adversary A can mount a rogue access point holding that specific SSID (i.e., by using the Karma tool [18].). If A confirms that the user initiated a connection, he concludes that the SSID is a part of the victim’s PNL list (SSID∈P).Definition 2 (SSID Oracle).
We denote victim as a binary response SSID OracleO. When A fakes an SSID, he is querying O for a binary outcome. If SSID∈P, then O returns a positive outcome; otherwise O does not respond. We denote the following notation:(2)OSSID=1,ifSSID∈P0,ifSSID∉PIn our attackO responds to queries only during the scanning period (Figure 1,match opportunity) and will respond with a positive outcome only in the case that the queried SSID is within its P. No response is considered to be a negative outcome. However, the success rate of querying O is subject to channel quality, which can potentially cause false negatives. In case of a low channel quality, the attacker cannot tell whether the cause for no response is SSID∉P or the victim did not receive the query.IfO would respond to every query and thematch opportunity would span during the entire attack time uninterrupted, our work would be much simpler, as we would only have to manage the problem of building a good quality SSID dictionary and test every SSID from that list one by one. A similar approach has already been covered by many papers describing dictionary or brute force attempts on password cracking [19, 26].Since in our model the attacker does not actually know when that match opportunity period occurs (we assume the worst case scenario in our model with passive scan, as measured for iOS 10) and is subject to channel quality, it is necessary to create a model/algorithm that will allow the attacker to test every SSID at least once with as high probability as possible, within the match opportunity window.


## 3.2. SSID Oracle Attack

Independently of the type of scanning technique (Active Service Discovery with or without an empty probe request or Passive Service Discovery) in our model the Wi-Fi scan occurs periodically everyTI seconds (idle period in between scans) and lasts only for a short scanning period of TS, such that TS≪TI.Figure2 describes the general trade-offs that we face when executing SSID Oracle attack. As mentioned at the beginning of this section, to succeed in the location privacy game the adversary A would have to create a dictionary of (nontrivial) SSIDs that hold at least one SSID from P. A simplest solution would be to increase the dictionary size so that the probability P[P∩D≠∅] of finding at least one SSID approaches 1. This can be clearly seen from Figure 2, where the shape of the curve depends on different approaches to building D. Our goal is to test SSIDs having a higher chance of being in P first, so P[P∩D≠∅] will grow faster for small D with tendency of becoming linear for large D. One such example approach on building dictionaries based on recommendation algorithm is described in Section 3.5. However, dictionary size depends on the opportunity window TA, the time available for the attacker to execute the attack (Figure 1). If we take into account the fact that adversary A sends SSIDs (e.g., beacons) at maximum rate r, we can denote withslot a discrete time period in which one SSID from D is sent to the Oracle O (victim’s device) within TS period. Since TS is the only valuable time period for A to conduct the attack, the maximum available number of time slots for the attacker within opportunity window TA equals TA·TS/TS+TI·r. For this reason, the dictionary size tested on O satisfies the following condition: D≤TA·TS/TS+TI·r. As the dictionary size increases, the required time for the attacker A to test all SSIDs increases, so the conditional probability Phit∣P∩D≠∅ drastically decreases.Figure 2
Conditionalhit chance Phit∣P∩D≠∅ and dictionary quality P[P∩D≠∅] in comparison to the size of dictionary D.Another observation shows just how big of an impactTI has on the attack. If we assume that idle time is zero (TI=0), the victim’s device would be constantly scanning the Wi-Fi channel. A can then create D such that the dictionary size equals the maximum number of timeslots available in TA (D¯=TA·r). A could easily test many more SSIDs from the dictionary against the victim’s device within TA (by taking into account the fact that all queries arrive to the Oracle O (there are no collisions in Wi-Fi channel) and that there are no retransmissions.).In our model, we do not know whenTS or TI occurs, just a measurement of their lengths. To be able to execute the attack, despite not knowing when a new scanning period starts, a logical solution (intuition) would be to create smallchunks of size L testable slots, fill them with SSIDs from D, and retransmit chunks for the duration of time period T until we are convinced that O received all L queries from the chunk at least once. After the chunk retransmission time T, A sends the following chunk containing another L slots. The proposed method is described in detail in Figure 3.Figure 3
Attacker and victim timelines.The attacker strategys can be described by using the following triplet D, L, and T:(3)s=D,L,TOur goal is to find the optimal strategys∗ which will result, given the available time period TA (opportunity window), in the best SSID Oracle attack execution:(4)s∗=arg⁡maxD,L,T⁡Phit∣P∩D≠∅·PP∩D≠∅The following sections focus on definings∗. We start by discussing and defining L and T parameters which affect the efficiency of attack execution. Later in Section 3.5 an example method for defining and building a good quality D is presented.


## 3.3. Finding Optimal ParametersL∗ and T∗

As we mentioned in the previous section, chances of making OracleO respond to a query with a positive answer depend on multiple parameters, out of which some are predetermined by the Oracle (smartphone) implementation (i.e., periods TI, TS), while some are controlled by the adversary A (i.e., dictionaries D, L, and T). In this section, our goal is to find the optimal parameters for the chunk size L∗ and chunk retransmission time period T∗. Recall from Figure 3 that it is necessary to find a strategy that guarantees (with high probability) that every slot from the chunk of size L hits the scanning interval TS.Let us consider the scenario in which the attackerA is omniscient; i.e., A knows the exact moment at which O initiates the search for neighboring SSIDs. Since A knows when scan initiates and also its duration TS, he can adapt the attack transmission start time Tstart towards O at maximum rate r, as can be seen in Figure 4-I. Now we can easily conclude that the maximum number of unique slots that can fit into TS equals to r·TS (recall that r denotes a rate at which chunks are transmitted). Due to the fact that during the period TI the Oracle O cannot receive any query from A, we can denote r·TS as a single chunk Li, i.e., Li=Li=r·TS. Now, referring back to our attacking model (Section 2), A is not omniscient and cannot actually know when TS starts; therefore it is necessary to find such a strategy that the complete L finds TS period.Figure 4
Choosing optimal chunk transmission time T.Please observe from Figure4 that since the TS+TI intervals are periodically repeating, the easiest solution for A would be to retransmit chunks Li towards left and right (Figure 4-II) and expand them until it reaches the expansion of chunk Li-1 on the left and chunk Li+1 on the right (Figure 4-III). How does this help the attacker? Figure 4-IV shows that since chunk retransmission period equals T=TS+TI and L=r·TS, regardless of when Tstart period actually occurs, the complete chunk is still going to hit the appropriate scanning period TS, with Tstart∈[0,TS+TI]. The zoomed sections in Figure 4, A (in case of all-knowing O scenario) and B (in case of any other scenario), show that the same unique SSIDs contained in L chunk will overlap the scanning period TS in both cases.For this reason the optimal chunk size equals the number of slots that can fit in the scanning periodTS:(5)L∗=r·TS,whereas the optimal time interval to retransmiti-th chunk equals the sum of TI and TS:(6)T∗=TS+TI.Given the attacker’s opportunity windowTA, we can calculate the maximum number of unique testable slots Nslot for our strategy s∗:(7)Nslot=TATS+TI·L,We have shown that by using optimalT∗ we can achieve the same number of slots Nslot compared to the omniscient A we started this discussion from, although the actual attacker A cannot tell the exact moment at which O initiates TS.The following conclusion sums up our observations so far: when definings∗, execution of SSID Oracle attack with parameters L∗ (5) and T∗ (6) willmaximize the available number of unique slots  Nmax.However, in low channel quality conditions there is always a chance that query sent fromA does not get to O. If we have a hit (O responds to a query with positive outcome), there is a chance that the response does not get to A, so we are introducing a new parameter-probability p that SSID Oracle successfully receives and responds to a query.For this reason it may not be optimal to fill all the slots with unique SSIDs; thus the size of the dictionary might have to decrease even further.(8)D¯max≤Nslot.


## 3.4. Matching Dictionary to Slots

In previous sections we carried out the analysis of proposed model in good quality channel environments (p≈1). We have shown that the optimal chunk retransmission time is the period T∗=TS+TI, while the chunk size equals the number of queries that can fit the scan interval L=L∗=r·TS. In this scenario, D was equal to the maximum number of testable slots D=Nslot within TA.However, what can be done in scenarios of low quality channelp<1? In such scenarios, not all slots that attacker A sends within scan period TS will be received by O, the same way the responses sent by O (in case we have a hit) will not be received by A (all these parameters depend on attacker’s Wi-Fi card quality, victim’s Wi-Fi card quality, channel quality, distance from the attacker and the victim, etc.). To be more precise, in low quality channel conditions it could be better to retransmit SSIDs that have a larger probability of occurrence in the victim’s PNL list, rather than to transmit Nslot different SSIDs for a given TA.Let us useD′ to denote the set of all SSIDs known by A, whereas not all SSIDs from D′ have the same probability of being part of the victim’s PNL list P. Our goal is to maximize PsuccL-priv thus finding the optimal D⊂D′ to be tested within window of opportunity TA. The event of a successful O test, with a positive result, is denoted by hi,∀i∈D′. To find the best D, A has to use different tools (such as the example recommender system found in Section 3.5) to assign a chance that an SSID contained in D′ is also contained in the victim’s PNL. For this purpose, we are introducing a new subjective probability parameter pi assigned to every SSID in D′ and calculated by A.(9)pi∈0,1∀i∈D′Recall that we denote withslot a discrete time period in which one SSID is sent to the victim’s device within TS period. It is our goal to determine the number of slots every SSID in D′ should take:(10)ni∈0,Nslot∀i∈D′In order to characterizeni, we proceed as follows:(11)PsuccL-priv=PP∩D′≠∅·Ph∣P∩D′≠∅=PP∩D′≠∅·Ph1∨⋯∨hD′∣P∩D′≠∅The dictionary quality equation part of (11) resolves to(12)PP∩D′≠∅≜∑i∈D′Pi∈P∣P∩D′≠∅=∑i∈D′pi≤1,Attack execution equation part of (11) resolves to(13)P∨ihi∣P∩D′≠∅≤∑i∈D′Phi∣P∩D′≠∅=1∑i∈D′Phi,i∈P∣P∩D′≠∅=∑i∈D′Phi∣i∈P,P∩D′≠∅·Pi∈P∣P∩D′≠∅=2∑i∈D′1-1-pnipiwhere (1) follows fromPA∣B=PA,C∣B+PA,¬C∣B, whereas latter part of the equation in our case is equal to 0 (i∉P) and (2) comes the under assumption that Oracle queries are mutually independent of each other (sum of probabilities). Please note that due to burst effects in Wi-Fi channel [27] we may not always face such scenario, since there is a chance that consecutive Wi-Fi packets are more likely to fail to transmit if previous packets also failed. Given the premises Nslot≫L and T≫TS we can see that different L slots are being tested couple of seconds apart, meaning that different chunks are not subject to the same error burst. In case of retransmitting SSIDs, we use interleaving to tackle the error burstiness.We are now ready to set the optimization problem, whose solution will giveA the required parameters ni. Please note that the SSID Oracle attack requires ni∈N0, but we are using linear optimization to solve the optimization problem. To execute an attack, it is required to round ni calculated from our model, as will be shown in simulations later.(14)maxn1,…,nD′∑i∈D′pi-pi1-pnis.t.∑ini≤TATSTS+TI·r=Nslotni≥0pi∈0,1∑ipi≤1p∈0,1We approach the optimization problem (14) using Lagrange multipliers method. Objective function has unique solutions based on its concave nature.Lemma 3.
The relation between SSID subjective correctness probabilitypi, channel quality p, and number of testing attempts ni for every SSID is(15)ni∗-nj∗=log⁡pj/pilog⁡1-pAs can be seen from (15) and Figure 5, for good channel (p>0.95), the attacker does not significantly increase his hit chance by retransmitting SSIDs with higher probability of occurrence. On the other hand, a bad channel (p<0.5) brings up the importance of having a good SSID dictionary generator algorithm.Figure 5
Transmission attempts differenceni-nj as a function of channel and SSID quality (based on Lemma 3).Theorem 4.
SSID Oracle attack execution strategys∗ should be achieved by picking L∗=r·TS and T∗=TS+TI parameters. The optimal execution strategy s∗ maximizes the number of unique testable slots Nslot. When matching D to Nslot, the condition ni-nj=log⁡pj/pi/log⁡1-p,∀i,j∈D′ must be fulfilled to achieve the best attack performance in case of a poor quality channel p.In the next subsection, we will introduce an example dictionary creation method, based on top-N recommendation algorithm, which can provide us with the required SSID importance parameterspi.


## 3.5. Building a Dictionary

In this subsection we introduce an example dictionary generation algorithm, based on a recommendation algorithm. We will only briefly cover the approach and later provide the experimental results in Section4.3. Please note that there can be multiple different dictionary creation approaches, depending on the information the attacker has on the potential victim. One goal could be to gather as many pairs of Wi-Fi MAC address and SSID to do statistical analysis of a crowd (similar work to many papers mentioned in our related work). In that case, having a more general dictionary is the best approach. Another goal could be the deanonymization of a specific person or a group by linking the victim to his MAC address. In that case, the dictionary should be prepared for that specific scenario, containing related SSIDs from victims neighborhood. Nevertheless, our SSID Oracle attack strategy will maximize the potential successful outcome for any provided dictionary.In order for the attack to be successful, the dictionary has to be(i)
compact: the size of the dictionaryD should be small enough so that performing the attack is feasible in reasonable time(ii)
precise: the dictionary should reflect victim’s PNL as much as possible (contain as many SSIDs that are in the user’s PNL as possible)The method we used for building a dictionary for the attack is based on collaborative filtering, namely, a modified version of Item-based top-N recommendation algorithm as seen in [21, 28]. It outputs a list of N recommended items that user might prefer/consume/buy/visit based on the current knowledge of user’s preferences/history and the knowledge of preferences/history of other users (training dataset). Cosine based similarity has shown to produce the best results.After building a list ofN recommended SSIDs for each test user, it is compared with the original PNL and the hit-rate (HR) is calculated: (16)HR=#ofSSIDsrecommendedthatareinusersPNLs#ofSSIDsinusersPNLsAn HR value of1.0 indicates that the algorithm was always able to recommend the hidden item, whereas an HR value of 0.0 indicates that the algorithm was not able to recommend any of the hidden items [21].Our algorithm uses two parameters which affect the effectiveness of the modified recommender system. The number of similar SSIDs we want to store for each SSID in the learning process is denoted byk∈N. The growth of the exponential equation used for calculating the importance of SSID repetition in the training set data is controlled by parameter A∈R.In the next section we will perform various SSID Oracle attacks using our setup.


## 4. Practical Tests and Simulations

In this section we present the performed practical tests, simulations, and an example dictionary creation algorithm based on top-N recommendation algorithm. The achieved results have been compared with the appropriate parts of our model.


### 4.1. Experimental Analysis of Chunk SizeL and Retransmission Time T

Extensive tests have been carried out to show the effectiveness of SSID Oracle attack and correctness of chunk sizeL∗ and retransmission time period T∗ optimal parameters on tests with real devices and in real-world scenarios. To be more precise, our tests were based on a modifiedAirbase-ng tool on Ubuntu machine equipped with D-Link DWA-556 Wireless N PCI-E Desktop Adapter placed in monitoring mode used to “… encourage clients to associate with the fake AP”[29]. We slightly modified Airbase-ng in a way that sends beacon packets from a predefined chunk of fixed size L, while it does not reply to any authentication request packets (nor probe request packets). Beacon packets were sent only on a single Wi-Fi channel (Wi-Fi channel 1 on 2.4GHz in our scenario). To accomplish focusing on a specific Wi-Fi channel, in parallel with Airbase-ng we used Airodump-ng tool. On the other hand, to capture authentication requests, we also rantshark, filtering out sought authentication request packets. Every test chunk L holds one SSID from P, i.e., L∩P=1. For different chunk sizes L (L∈50,60,80,100) performed in our tests we transmit beacon packets from chunk L for T consecutive seconds (T∈2,3,4,…,10). Interestingly, a similar test with multiple APs was implemented using Airbase-ng tool in [19], but the authors had problems with handling large number of SSIDs, so they limited their attack to a smaller number of SSIDs, i.e., 5 SSIDs, which is significantly smaller than our SSID Oracle attack with chunk sizes up to 100 APs (and even more). We repeated this test 100 times for each fixed period T and chunk size L. It is also important to note that since Tstart can appear uniformly at random within TI+TS (Figure 3), a random delay between two consecutive tests was induced. To enable shorter periodic scanning behavior (periods TS+TI), smartphone’s screen is powered ON and the default Wi-Fi finder program is opened in every test. This was done solely for practical reasons since running experiments for higher scanning intervals, e.g., “Display off" as mentioned in Section 2.1, would take too long (Figure 7 experiments alone had been running for a month).Figure6 shows the test results were carried out at Samsung Galaxy 3, Sony Xperia X8, LG P350, and Samsung S5 Mini devices. The dotted lines present success rate of response reception to query for various parameters of chunk retransmission period T and a fixed chunk size L. It is interesting to observe that for small transmission periods T there is a small chance that the Oracle responds with a success (a hit). Since idle period TI is larger than T and given that the start of transmission period Tstart starts uniformly at random within [0,…,TS+TI], for small T there is a high probability that attacker transmits a query within idle period. By increasing the chunk retransmission period T the success rate increases rapidly up to a point TS+TI. Note that this period is not equal for all devices; i.e., for Samsung Galaxy 3 it was 7s and for Sony Xperia X8 it was approximately 6s, while LG P350 was 7s. Indeed, in an additional study the time period between two consecutive probe packets corresponded to these intervals (in Active Service Discovery, when devices initiate the scan for neighboring APs on a specific Wi-Fi channel, they send a burst of probe request packets [30]). Moreover, it is important to note that chunks L were sent on a single Wi-Fi channel (Wi-Fi channel 1 in our case). Therefore, the effective scanning interval TS corresponds to the scanning interval of a single channel (if we eliminate the possibility of capturing communication on non-overlapping channels), which approximates to 0.1-0.12s. Interestingly, we can see in Figure 6 that the best results for success rate were indeed achieved for chunks sizes of L≤60. Please note that since in our tests every beacon packet was sent approximately every 2ms (r≈500s-1), sending the complete chunk L will take the exact amount of time that corresponds to the scan interval of TS≈0.12s of a smartphone device (L/r≈0.12s). We can also observe the impact of imperfect Wi-Fi channel where Oracle does not reply to all queries successfully, although TS=L/r and T=TS+TI; i.e., the success rate is not 1 but instead approximates to p≈0.98. In Table 1 we give detailed results for periods TS, TI+TS, and the probability p for every tested device.Table 1
Scanning and idle intervals for test devices.
Device T S T I + TS p 1. Samsung Galaxy 3 150 ms 7 s 0.97 2. Sony Xperia X8 120 ms 6.2 s 0.95 3. LG 120 ms 7 s 0.95 4. Samsung S5 Mini 180 ms 10 s 0.95 5. Sony Xperia Miro 100 ms 10.1 s 0.95Figure 6
Model comparison with test results for different devices and chunk sizes, usingr=500SSIDs/sec.Figure 7
Comparison of our model with experimental results on Sony Xperia miro forL=60.To verify the correctness of experimental results we also developed a mathematical model depicting the hitting probabilityP[hit] for SSID Oracle attack—the probability that the attacker A observes a hit, given that the observed chunk holds at least one SSID from P (Li∩P≠∅). We evaluate this probability as a function of parameters T and L and rate r controlled by the A, and parameters TS and TI given by Oracle’s specification, as well as the channel quality p. Our model also assumes that the chunk transmission time Tstart starts uniformly at random within the period [0,…,TS+TI] and that the sought SSID is also placed uniformly at random within the observed chunk L. In our analysis (see Appendix A) we obtain the expression for probability P[hit] which is solved numerically.The experimental results, along with the numerical ones, are shown in Figure6. As we can see from the figure, the model quite accurately predicts the probability for parameters given in Table 1. We also carried out extensive tests with Sony Xperia miro device and presented them with 95% confidence interval. For every chunk transmission period T we carried out 10000 tests, while the chunk size was L=60. The experiments give us the values for TS=100ms, while TS+TI≈10.01s. By plugging these values into our model (Appendix) we can see that our model quite accurately predicts the probability P[hit] (Figure 7).As mentioned before, our experiments were conducted in an area where other Wi-Fi devices were also transmitting, so there has been some interference present. To try to get almost perfect Wi-Fi conditions (p=1) we did another test in a controlled and clean environment with no other devices transmitting in Wi-Fi band. The success rate of almost a 100% has been achieved on the device for TI+TS=10s, as can be seen from Figure 8.Figure 8
Achieved results for channel qualityp≈1.


### 4.2. Retransmission Simulations for Low Quality Channel Conditions (p<1)

In order to show the effectiveness of SSID Oracle attack in low quality channel conditions (p<1), we implemented a simulator in MATLAB. The simulator gives us a good understanding about SSID retransmissions (testings) under low quality channel conditions, thus allowing us to manipulate various parameters, from the quality of the dictionary (the probability of every SSID being part of victim’s PNL list), up to the number of testings ni of a single SSID (SSID retransmissions in different chunks). For the purpose of our simulator we used the following variables: TA=1212s, TI=10s, TS=100ms, L=50, and r=500-1s. Every point in the results was simulated 200 000 times.Example 5.
In this example we verify the effect of retransmitting (testing) SSIDs multiple times. By retesting an SSID multiple times,i-th SSID from D fits more than one slot (has more than one chance of a hit) within the Oracle’s TA period. Since the number of available Nslot is limited in TA, this also means that testing one SSID more than once results in not having available slots intended to test all SSIDs in D. Simulator test dictionary D contains SSIDs assigned with corresponding probabilities contained within user’s PNL list pi=Pi∈P∣P∩D≠∅,∀i∈D (normalized to [0,1]). Please note that SSIDs in D are ordered according to the descending probabilities (pi≥pi+1,∀i), such that SSID with higher probability will be tested first. In our example, dictionary contains 6000 SSIDs. Figure 9 shows the cumulative probability distribution of SSIDs within D. We can observe that ∑i=11000‍pi=0.62, whereas if we observe the complete dictionary of 6000 SSID we will have ∑i=16000‍pi=0.8. Therefore, with a quality dictionary, in scenarios with low channel quality, an attacker A will test those SSIDs having a higher probability of occurrence in P at the cost of not testing SSIDs having a lower probability of occurrence.Figure 9
Cumulative probability distribution in test dictionary.Figure10 presents the achieved test success rate for various channel qualities p. The available transmission time TA=1212s allows us to attempt tests for 6000 slots (Nslot=6000). Simulation will test the first Nrepeat SSIDs twice (ni=2,∀i∈1,…,D-Nrepeat,s.t.pi≥pi+1), which have a higher probability of occurrence in P, at the cost of not testing the least significant Nrepeat SSIDs. The goal is to observe how this exchange affects the overall hit success rate for different channel qualities. The following holds:(17)ni=2,∀i∈1,Nrepeat0,∀i∈D-Nrepeat,D1,∀i∈Nrepeat,D-NrepeatFigure 10
Success rate for different channel qualityp when swapping SSIDs in test dictionary.The importance of finding a method/algorithm for building a quality dictionary for targeted users was pointed out in Figure10 and Table 2, especially in the scenarios with low channel quality. More precisely, by reducing the dictionary by Nrepeat=500 and giving the opportunity to (re)test first Nrepeat SSIDs twice (ni=2), we achieve an overall increase in probability of hit of up to 35.07% and 20.29% for channel qualities p=0.5 and p=0.7, respectively. On the other hand, by incrementing Nrepeat for good quality channels, the overall success rate decreases, since the actual dictionary to be tested now decreases to the size of D-Nrepeat, thus not giving an opportunity to test SSIDs with lower probability within the initial dictionary D.Table 2
Achieved increases in Simulation 1.
p Nrepeat succ. rate increase to  Nrepeat=0 0.5 500 0.5426 35.07% 0.7 500 0.6742 20.29% 0.9 250 0.7602 5.49% 0.98 125 0.7868 2.8%Example 6.
In the following example we verify, both through simulations and theoretically, the optimal number of slots assigned to the firstNrepeat SSIDs in scenarios with different channel quality p that would maximize the probability of hit. We use the following properties for our model: D=6000, Nrepeat=125, ∑‍pi=0.8, and pi\pj=30,∀i∈1,2,…,125,∀j∈D∖i. Simulation is performed for ni∈1,…,11 values.The results can be found in Figure11 and Table 3. Indeed, from the results we can see that the estimated maximum number of slots assigned to the first Nrepeat SSIDs corresponds to the ones obtained through simulations. We also show that it pays off for A to re-test SSIDs with high probability of occurrence at the expense of not testing the ones with low probability of occurrence. As expected, the highest increase in the hit probability will be obtained during the lowest channel quality p.Table 3
Optimaln values for Simulation 2.
p n 1 - 125 o p t  test n 1 - 125 o p t  model increase to  n1-125=1 0.5 5 4.9069 32.15% 0.7 3 2.8250 12.9% 0.9 2 1.4771 2.63% 0.98 1 0.8694 0%Figure 11
Success rate for different channel qualityp and SSID repetitions n.In the next section, we approach the problem of building a good quality dictionary for the targeted user, i.e., a dictionary in which a probability of occurrence of the firstNrepeat SSIDs within victim’s PNL list will be high.


### 4.3. Dictionary Creation Results

In this section we will present the achieved results based on the top-N recommender system algorithm we discussed in Section3.5. For testing the performance of the system we collected users’ PNLs from Apple devices, mainly from the visitors of a big music festival in our country. 4426 users (different MAC addresses) were collected and 15095 SSIDs, with total of 23701 MAC-SSID pairs (average PNL size of 5.35). Another interesting starting dataset is also provided by the authors of [31] where SSIDs were gathered on multiple locations in Rome, Italy.To get more accurate and statistically valid results, instead of doing one test experiment, a 10-fold cross-validation method is used where the dataset is divided into10 partitions and in each of 10 folds (reruns of the experiment) one partition is used as test set and the rest as training set. The final hit-rate (HR) is calculated as the average of hit-rates for all folds.It is also possible to optimize the performance of the system by running cross-validation with different parameters of the system and pick the set of parameters which produce the best result [32]. Different similarity functions are also tested (cosine based or conditional probability based). The results are shown in Table 4.Table 4
Cross-validation hit-rate for different parameters forN=1000.
Cosine based Conditional probability based k = 10 k = 20 k = 40 k = 60 k = 10 k = 20 k = 40 k = 60 A = 5 32.69% 32.43% 32.40% 32.37% 32.74% 32.50% 32.55% 32.57% A = 10 32.65% 32.47% 32.41% 32.34% 32.68% 32.74% 32.77% 32.64% A = 20 32.62% 32.43% 32.37% 32.37% 32.75% 32.80% 32.73% 32.84% A = 100 32.75% 32.72% 32.69% 32.67% 32.73% 32.89 % 32.86% 32.76%We see that the best results can be obtained by settingA=100 and k=20, even though the system is quite stable on parameters variations. To show how well the system performs on our dataset in comparison with other (benchmark) datasets, we have compared the results of our experiments with the ones done in [21] (which are modified to fit the classical recommender scenario), and showed the results in Table 5.Table 5
Performance comparison with other datasets.
Dataset n m # of records Density Average #items/user HR for experiment ctlg1 58565 502 209715 0.71% 3.58 41.5% ctlg2 23480 55879 1924122 0.15% 81.95 15.4% ctlg3 58565 39080 453219 0.02% 7.74 54.0% ccard 42629 68793 398619 0.01% 9.35 17.6% ecmrc 6667 17491 91222 0.08% 13.68 17.4% em 8002 1648 769311 5.83% 96.14 40.5% ml 943 1682 100000 6.31% 106.04 27.2% skill 4374 2125 82612 0.89% 18.89 37.3% ssids 4426 15095 23701 0.04 % 5.35 32.7 % ∗Clearly the performance is comparable with datasets from the classical scenario of recommender system usage (despite the fact that the density of our dataset is quite low), which justifies its application here as well. There are other possibilities of making and improving dictionary which can be taken into consideration in future work, like including human knowledge, categorizing people by their preferences/life habits, or applying additional rules for specific scenarios.


## 4.1. Experimental Analysis of Chunk SizeL and Retransmission Time T

Extensive tests have been carried out to show the effectiveness of SSID Oracle attack and correctness of chunk sizeL∗ and retransmission time period T∗ optimal parameters on tests with real devices and in real-world scenarios. To be more precise, our tests were based on a modifiedAirbase-ng tool on Ubuntu machine equipped with D-Link DWA-556 Wireless N PCI-E Desktop Adapter placed in monitoring mode used to “… encourage clients to associate with the fake AP”[29]. We slightly modified Airbase-ng in a way that sends beacon packets from a predefined chunk of fixed size L, while it does not reply to any authentication request packets (nor probe request packets). Beacon packets were sent only on a single Wi-Fi channel (Wi-Fi channel 1 on 2.4GHz in our scenario). To accomplish focusing on a specific Wi-Fi channel, in parallel with Airbase-ng we used Airodump-ng tool. On the other hand, to capture authentication requests, we also rantshark, filtering out sought authentication request packets. Every test chunk L holds one SSID from P, i.e., L∩P=1. For different chunk sizes L (L∈50,60,80,100) performed in our tests we transmit beacon packets from chunk L for T consecutive seconds (T∈2,3,4,…,10). Interestingly, a similar test with multiple APs was implemented using Airbase-ng tool in [19], but the authors had problems with handling large number of SSIDs, so they limited their attack to a smaller number of SSIDs, i.e., 5 SSIDs, which is significantly smaller than our SSID Oracle attack with chunk sizes up to 100 APs (and even more). We repeated this test 100 times for each fixed period T and chunk size L. It is also important to note that since Tstart can appear uniformly at random within TI+TS (Figure 3), a random delay between two consecutive tests was induced. To enable shorter periodic scanning behavior (periods TS+TI), smartphone’s screen is powered ON and the default Wi-Fi finder program is opened in every test. This was done solely for practical reasons since running experiments for higher scanning intervals, e.g., “Display off" as mentioned in Section 2.1, would take too long (Figure 7 experiments alone had been running for a month).Figure6 shows the test results were carried out at Samsung Galaxy 3, Sony Xperia X8, LG P350, and Samsung S5 Mini devices. The dotted lines present success rate of response reception to query for various parameters of chunk retransmission period T and a fixed chunk size L. It is interesting to observe that for small transmission periods T there is a small chance that the Oracle responds with a success (a hit). Since idle period TI is larger than T and given that the start of transmission period Tstart starts uniformly at random within [0,…,TS+TI], for small T there is a high probability that attacker transmits a query within idle period. By increasing the chunk retransmission period T the success rate increases rapidly up to a point TS+TI. Note that this period is not equal for all devices; i.e., for Samsung Galaxy 3 it was 7s and for Sony Xperia X8 it was approximately 6s, while LG P350 was 7s. Indeed, in an additional study the time period between two consecutive probe packets corresponded to these intervals (in Active Service Discovery, when devices initiate the scan for neighboring APs on a specific Wi-Fi channel, they send a burst of probe request packets [30]). Moreover, it is important to note that chunks L were sent on a single Wi-Fi channel (Wi-Fi channel 1 in our case). Therefore, the effective scanning interval TS corresponds to the scanning interval of a single channel (if we eliminate the possibility of capturing communication on non-overlapping channels), which approximates to 0.1-0.12s. Interestingly, we can see in Figure 6 that the best results for success rate were indeed achieved for chunks sizes of L≤60. Please note that since in our tests every beacon packet was sent approximately every 2ms (r≈500s-1), sending the complete chunk L will take the exact amount of time that corresponds to the scan interval of TS≈0.12s of a smartphone device (L/r≈0.12s). We can also observe the impact of imperfect Wi-Fi channel where Oracle does not reply to all queries successfully, although TS=L/r and T=TS+TI; i.e., the success rate is not 1 but instead approximates to p≈0.98. In Table 1 we give detailed results for periods TS, TI+TS, and the probability p for every tested device.Table 1
Scanning and idle intervals for test devices.
Device T S T I + TS p 1. Samsung Galaxy 3 150 ms 7 s 0.97 2. Sony Xperia X8 120 ms 6.2 s 0.95 3. LG 120 ms 7 s 0.95 4. Samsung S5 Mini 180 ms 10 s 0.95 5. Sony Xperia Miro 100 ms 10.1 s 0.95Figure 6
Model comparison with test results for different devices and chunk sizes, usingr=500SSIDs/sec.Figure 7
Comparison of our model with experimental results on Sony Xperia miro forL=60.To verify the correctness of experimental results we also developed a mathematical model depicting the hitting probabilityP[hit] for SSID Oracle attack—the probability that the attacker A observes a hit, given that the observed chunk holds at least one SSID from P (Li∩P≠∅). We evaluate this probability as a function of parameters T and L and rate r controlled by the A, and parameters TS and TI given by Oracle’s specification, as well as the channel quality p. Our model also assumes that the chunk transmission time Tstart starts uniformly at random within the period [0,…,TS+TI] and that the sought SSID is also placed uniformly at random within the observed chunk L. In our analysis (see Appendix A) we obtain the expression for probability P[hit] which is solved numerically.The experimental results, along with the numerical ones, are shown in Figure6. As we can see from the figure, the model quite accurately predicts the probability for parameters given in Table 1. We also carried out extensive tests with Sony Xperia miro device and presented them with 95% confidence interval. For every chunk transmission period T we carried out 10000 tests, while the chunk size was L=60. The experiments give us the values for TS=100ms, while TS+TI≈10.01s. By plugging these values into our model (Appendix) we can see that our model quite accurately predicts the probability P[hit] (Figure 7).As mentioned before, our experiments were conducted in an area where other Wi-Fi devices were also transmitting, so there has been some interference present. To try to get almost perfect Wi-Fi conditions (p=1) we did another test in a controlled and clean environment with no other devices transmitting in Wi-Fi band. The success rate of almost a 100% has been achieved on the device for TI+TS=10s, as can be seen from Figure 8.Figure 8
Achieved results for channel qualityp≈1.


## 4.2. Retransmission Simulations for Low Quality Channel Conditions (p<1)

In order to show the effectiveness of SSID Oracle attack in low quality channel conditions (p<1), we implemented a simulator in MATLAB. The simulator gives us a good understanding about SSID retransmissions (testings) under low quality channel conditions, thus allowing us to manipulate various parameters, from the quality of the dictionary (the probability of every SSID being part of victim’s PNL list), up to the number of testings ni of a single SSID (SSID retransmissions in different chunks). For the purpose of our simulator we used the following variables: TA=1212s, TI=10s, TS=100ms, L=50, and r=500-1s. Every point in the results was simulated 200 000 times.Example 5.
In this example we verify the effect of retransmitting (testing) SSIDs multiple times. By retesting an SSID multiple times,i-th SSID from D fits more than one slot (has more than one chance of a hit) within the Oracle’s TA period. Since the number of available Nslot is limited in TA, this also means that testing one SSID more than once results in not having available slots intended to test all SSIDs in D. Simulator test dictionary D contains SSIDs assigned with corresponding probabilities contained within user’s PNL list pi=Pi∈P∣P∩D≠∅,∀i∈D (normalized to [0,1]). Please note that SSIDs in D are ordered according to the descending probabilities (pi≥pi+1,∀i), such that SSID with higher probability will be tested first. In our example, dictionary contains 6000 SSIDs. Figure 9 shows the cumulative probability distribution of SSIDs within D. We can observe that ∑i=11000‍pi=0.62, whereas if we observe the complete dictionary of 6000 SSID we will have ∑i=16000‍pi=0.8. Therefore, with a quality dictionary, in scenarios with low channel quality, an attacker A will test those SSIDs having a higher probability of occurrence in P at the cost of not testing SSIDs having a lower probability of occurrence.Figure 9
Cumulative probability distribution in test dictionary.Figure10 presents the achieved test success rate for various channel qualities p. The available transmission time TA=1212s allows us to attempt tests for 6000 slots (Nslot=6000). Simulation will test the first Nrepeat SSIDs twice (ni=2,∀i∈1,…,D-Nrepeat,s.t.pi≥pi+1), which have a higher probability of occurrence in P, at the cost of not testing the least significant Nrepeat SSIDs. The goal is to observe how this exchange affects the overall hit success rate for different channel qualities. The following holds:(17)ni=2,∀i∈1,Nrepeat0,∀i∈D-Nrepeat,D1,∀i∈Nrepeat,D-NrepeatFigure 10
Success rate for different channel qualityp when swapping SSIDs in test dictionary.The importance of finding a method/algorithm for building a quality dictionary for targeted users was pointed out in Figure10 and Table 2, especially in the scenarios with low channel quality. More precisely, by reducing the dictionary by Nrepeat=500 and giving the opportunity to (re)test first Nrepeat SSIDs twice (ni=2), we achieve an overall increase in probability of hit of up to 35.07% and 20.29% for channel qualities p=0.5 and p=0.7, respectively. On the other hand, by incrementing Nrepeat for good quality channels, the overall success rate decreases, since the actual dictionary to be tested now decreases to the size of D-Nrepeat, thus not giving an opportunity to test SSIDs with lower probability within the initial dictionary D.Table 2
Achieved increases in Simulation 1.
p Nrepeat succ. rate increase to  Nrepeat=0 0.5 500 0.5426 35.07% 0.7 500 0.6742 20.29% 0.9 250 0.7602 5.49% 0.98 125 0.7868 2.8%Example 6.
In the following example we verify, both through simulations and theoretically, the optimal number of slots assigned to the firstNrepeat SSIDs in scenarios with different channel quality p that would maximize the probability of hit. We use the following properties for our model: D=6000, Nrepeat=125, ∑‍pi=0.8, and pi\pj=30,∀i∈1,2,…,125,∀j∈D∖i. Simulation is performed for ni∈1,…,11 values.The results can be found in Figure11 and Table 3. Indeed, from the results we can see that the estimated maximum number of slots assigned to the first Nrepeat SSIDs corresponds to the ones obtained through simulations. We also show that it pays off for A to re-test SSIDs with high probability of occurrence at the expense of not testing the ones with low probability of occurrence. As expected, the highest increase in the hit probability will be obtained during the lowest channel quality p.Table 3
Optimaln values for Simulation 2.
p n 1 - 125 o p t  test n 1 - 125 o p t  model increase to  n1-125=1 0.5 5 4.9069 32.15% 0.7 3 2.8250 12.9% 0.9 2 1.4771 2.63% 0.98 1 0.8694 0%Figure 11
Success rate for different channel qualityp and SSID repetitions n.In the next section, we approach the problem of building a good quality dictionary for the targeted user, i.e., a dictionary in which a probability of occurrence of the firstNrepeat SSIDs within victim’s PNL list will be high.


## 4.3. Dictionary Creation Results

In this section we will present the achieved results based on the top-N recommender system algorithm we discussed in Section3.5. For testing the performance of the system we collected users’ PNLs from Apple devices, mainly from the visitors of a big music festival in our country. 4426 users (different MAC addresses) were collected and 15095 SSIDs, with total of 23701 MAC-SSID pairs (average PNL size of 5.35). Another interesting starting dataset is also provided by the authors of [31] where SSIDs were gathered on multiple locations in Rome, Italy.To get more accurate and statistically valid results, instead of doing one test experiment, a 10-fold cross-validation method is used where the dataset is divided into10 partitions and in each of 10 folds (reruns of the experiment) one partition is used as test set and the rest as training set. The final hit-rate (HR) is calculated as the average of hit-rates for all folds.It is also possible to optimize the performance of the system by running cross-validation with different parameters of the system and pick the set of parameters which produce the best result [32]. Different similarity functions are also tested (cosine based or conditional probability based). The results are shown in Table 4.Table 4
Cross-validation hit-rate for different parameters forN=1000.
Cosine based Conditional probability based k = 10 k = 20 k = 40 k = 60 k = 10 k = 20 k = 40 k = 60 A = 5 32.69% 32.43% 32.40% 32.37% 32.74% 32.50% 32.55% 32.57% A = 10 32.65% 32.47% 32.41% 32.34% 32.68% 32.74% 32.77% 32.64% A = 20 32.62% 32.43% 32.37% 32.37% 32.75% 32.80% 32.73% 32.84% A = 100 32.75% 32.72% 32.69% 32.67% 32.73% 32.89 % 32.86% 32.76%We see that the best results can be obtained by settingA=100 and k=20, even though the system is quite stable on parameters variations. To show how well the system performs on our dataset in comparison with other (benchmark) datasets, we have compared the results of our experiments with the ones done in [21] (which are modified to fit the classical recommender scenario), and showed the results in Table 5.Table 5
Performance comparison with other datasets.
Dataset n m # of records Density Average #items/user HR for experiment ctlg1 58565 502 209715 0.71% 3.58 41.5% ctlg2 23480 55879 1924122 0.15% 81.95 15.4% ctlg3 58565 39080 453219 0.02% 7.74 54.0% ccard 42629 68793 398619 0.01% 9.35 17.6% ecmrc 6667 17491 91222 0.08% 13.68 17.4% em 8002 1648 769311 5.83% 96.14 40.5% ml 943 1682 100000 6.31% 106.04 27.2% skill 4374 2125 82612 0.89% 18.89 37.3% ssids 4426 15095 23701 0.04 % 5.35 32.7 % ∗Clearly the performance is comparable with datasets from the classical scenario of recommender system usage (despite the fact that the density of our dataset is quite low), which justifies its application here as well. There are other possibilities of making and improving dictionary which can be taken into consideration in future work, like including human knowledge, categorizing people by their preferences/life habits, or applying additional rules for specific scenarios.


## 5. Related Work

A lot of work covers the location privacy problem for devices disclosing their PNL. Numerous papers focus on the IEEE 802.11 connection scanning and initialization protocols: AS, AS with broadcast, or PS [16, 24, 33, 34]. Those papers are relevant for our research as it covers scanning and idle times and showcases the tendency for the periodical Wi-Fi scans. LAPWiN proposes a location based protection mechanism to protect one from privacy leaks [30]. Such protection mechanism would directly mitigate the kind of privacy attack we are attempting; however that standard has not been implemented by the Wi-Fi card manufacturers yet. The authors in [23] are using Wi-Fi behavior to do aerial search and rescue operations. The authors are monitoring probe request packets using equipment mounted on drones in order to detect the location of a user during the search and rescue operation.Others focus on making conclusions about a user from their PNL. Signals from the crowd [7] uses gathered SSIDs to discover user’s country of origin, device manufacturer, and other, as is [8, 9, 35]. SSIDs in the Wild [36] are mapping SSIDs to real-world locations, and [10] finds social relation between users by matching PNL. WiFiPi [11] tracks user movement at mass events using a combination of MAC address and SSIDs, using a deployed sensor network.Linking a MAC address gathered from a Wi-Fi packet to an actual person (MAC de-anonymization) appears to be challenging. Reference [26] uses beacon reply attack and fakes user’s known SSIDs to trigger his phone to connect, thus doing a MAC address matching. Beam me up, Scotty [37] has an interesting approach to Wi-Fi assisted geo location where they fake an AP from another location causing services like Twitter to display the fake location as the origin of a tweet. The authors in [38, 39] showcase an entire network of sensors doing location privacy attack in the city of London gathering data on users movements and whereabouts.To complicate tracking and privacy leaks, user equipment manufacturers have started using MAC address randomization. However, the authors in [19, 40, 41] showed that randomizing MAC address does not increase privacy, as the devices are sending probe requests that contain APs from the PNL, proving that privacy protection is indeed a considerate issue for the manufacturers.The related work mentioned in this section so far focuses on passive monitoring of probe requests and various conclusions one can deduce from gathered PNLs. The devices using active scanning with broadcast packets or passive scanning are not vulnerable to passive monitoring, so an active attack is needed.The attempt at actively faking an AP and thus revealing user’s PNL has not been researched in detail, to the best of our knowledge. Active attacks on user’s PNL have been mentioned in some previous work [19, 26] where the authors are mounting fake APs containing user’s known SSID in order to provoke connection initiation from the victim with the goal of revealing their real MAC address. Considering that such active attack was not the main focus of their work, the authors have concluded from their experiments that in practice one can test only a small number of different SSIDs. Our work however was focused on optimizing the active attack, where we have shown that depending on scanning and idle periods of the Wi-Fi enabled device and the size of the opportunity window, it is possible to test dictionaries more than 10 times bigger in size.


## 6. Conclusion

In this paper we propose an attacking strategy to extract victim’s preferred network list from a mobile device while the device is in Active Service Discovery mode with broadcast scan, or passive scan mode. We introduced the SSID Oracle attack that queries a set of SSIDs from a dictionary against the victim’s device by faking APs. We calculated the optimal parameters for the attack execution and proposed a detailed mathematical model depicting the attack.The model has been confirmed by running extensive tests on different smartphone devices. Furthermore, we also created a simulator to cover more complex attack scenarios with low Wi-Fi channel quality.Since users are mobile with their devices, the attacker’s opportunity window is quite small and the attack depends on having SSIDs which are highly likely to be present in victim’s PNL. For that reason we also proposed an example recommender system based algorithm for building a high quality dictionary. We have concluded that by choosing the right dictionary and by executing the attack using our model, it is possible to achieve high probability of success when attempting to disclose an SSID from victim’s PNL.For future work we plan to work on finding solutions that can protect against SSID Oracle attacks. One solution would be to use Geofencing technique in which the device will only respond to probes for APs which are both known and geographically nearby. We plan to further research dynamic tracking and other aspects of Wi-Fi network traffic.



---

*Source: 5153265-2018-07-22.xml*