Portal de Periódicos da CAPES

Energy‐efficient replica detection for resource‐limited mobile devices in the internet of things

2013; Institution of Engineering and Technology; Volume: 7; Issue: 18 Linguagem: Inglês

10.1049/iet-com.2013.0283

1751-8636

Kwantae Cho, Byung‐Gil Lee, Kyungho Lee, Dong Hoon Lee,

Caching and Content Delivery

IET CommunicationsVolume 7, Issue 18 p. 2141-2150 ArticleFree Access Energy-efficient replica detection for resource-limited mobile devices in the internet of things Kwantae Cho, Corresponding Author Kwantae Cho kwantaecho@etri.re.kr Cyber Security Research Laboratory, Electronics and Telecommunications Research Institute (ETRI), 161 Gajeong-dong, Yuseong-gu, Daejeon, 305-700 Republic of KoreaSearch for more papers by this authorByung-Gil Lee, Byung-Gil Lee Cyber Security Research Laboratory, Electronics and Telecommunications Research Institute (ETRI), 161 Gajeong-dong, Yuseong-gu, Daejeon, 305-700 Republic of KoreaSearch for more papers by this authorKyungho Lee, Kyungho Lee Center for Information Security Technologies (CIST), Graduate School of Information Security, Korea University, Anam-dong, Seongbuk-gu, Seoul, 136-713 Republic of KoreaSearch for more papers by this authorDong Hoon Lee, Dong Hoon Lee Center for Information Security Technologies (CIST), Graduate School of Information Security, Korea University, Anam-dong, Seongbuk-gu, Seoul, 136-713 Republic of KoreaSearch for more papers by this author Kwantae Cho, Corresponding Author Kwantae Cho kwantaecho@etri.re.kr Cyber Security Research Laboratory, Electronics and Telecommunications Research Institute (ETRI), 161 Gajeong-dong, Yuseong-gu, Daejeon, 305-700 Republic of KoreaSearch for more papers by this authorByung-Gil Lee, Byung-Gil Lee Cyber Security Research Laboratory, Electronics and Telecommunications Research Institute (ETRI), 161 Gajeong-dong, Yuseong-gu, Daejeon, 305-700 Republic of KoreaSearch for more papers by this authorKyungho Lee, Kyungho Lee Center for Information Security Technologies (CIST), Graduate School of Information Security, Korea University, Anam-dong, Seongbuk-gu, Seoul, 136-713 Republic of KoreaSearch for more papers by this authorDong Hoon Lee, Dong Hoon Lee Center for Information Security Technologies (CIST), Graduate School of Information Security, Korea University, Anam-dong, Seongbuk-gu, Seoul, 136-713 Republic of KoreaSearch for more papers by this author First published: 01 December 2013 https://doi.org/10.1049/iet-com.2013.0283Citations: 5AboutSectionsPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinkedInRedditWechat Abstract The forthcoming Internet of Things – an intelligent collaboration of resource-limited static/mobile devices that are embedded in the daily lives of users – poses new challenges to security and end-user privacy. One of the most challenging problems is how to thwart replica attacks. Once a device is captured physically by an attacker or contaminated by malicious code, it can be reprogrammed and the secret information inside can be duplicated into a large number of replicas that maliciously occupy the network and collect users private information without authorisation. In this study, the authors focus on studying the detection of replicas in mobile applications; which can consist of resource-limited static devices attached to mobile entities. Most existing solutions for detecting replicas have been designed for static devices, and cannot be immediately applied to mobile devices because of their unique properties, in particular, their node mobility. The authors present two efficient methods for detecting replicas in mobile devices. Through performance evaluations, they find that the proposed methods provide highly accurate replica detection with nearly zero detection errors. Furthermore, the distributed and cooperative strategy of the methods significantly reduces the energy required to detect replicas while providing faster replica detection than the existing solutions. 1 Introduction Generally, people use the Internet for their desired services, for example, sending/receiving emails, monitoring health-care processes, accessing multimedia contents, playing online games and using the other social networking applications. In the near future, the number of Internet users is expected to reach two billion, while the interconnection of natural and human-made systems spreads rapidly around the globe. Thus, it is predictable that the Internet will exist as a seamless fabric of interconnectivity and interoperability related to the desired services, which will be all around us and readily available. This vision is now being pursued with the development of technologies. More specifically, the technologies facilitate the Internet of Things (IoT) by dealing with resource-limited devices such as wireless sensor nodes and radio frequency identification. The technologies are slowly but inexorably becoming part of our everyday lives. However, at the same time, the IoT also opens up a whole new class of security problems [1-3]. Each resource-limited device (e.g. a sensor) is potentially a point of vulnerability to people who upload malicious code for fun, profit or other advancement of personal goals. Replica attacks are some of the most challenging security problems. Such attacks can make complete nonsense of existing defence systems such as secure communication and entity authentication by using inside secret credentials. An attacker may be able to either physically compromise devices (or so-called nodes) or insert malicious code in them via the Internet. The attacker then obtains private information or credentials that allow him/her to pass through the existing defence systems in order to inject fake data, disrupt network operations and eavesdrop on network communications. A far more harmful consequence of a node compromise attack is that the attacker can fabricate replicas with the credentials and surreptitiously insert them at selected target positions (or place them in/on selected target objects) in the network. These replicas can then be used to launch various stealth attacks depending on the aim of the attacker (e.g. to control the target areas). This type of attack, first referred to as a 'replica attack' by Parno et al. [4], is considered the most fatal type of attack that must be resolved [5-18]. 1.1 Motivation and overview None of the current approaches [9, 11, 13, 14, 16] in mobile applications are suitable for immediate deployment, mainly because of two drawbacks: high communication costs caused by the inefficient way of updating information in each node, and high detection errors. In the proposed approach, each node is assigned randomly chosen target nodes to observe. A node maintains a location claim consisting of the ID and location of a target node, along with the time when the node was positioned in that location. To detect a replica, a location claim is used, as in Ho et al. [9]. That is, given the time interval between two positions of a node and its maximum speed, only a genuine node can move within the expected distance. The novelty of the proposed approach is in its way of updating the location claims of target nodes. When two nodes meet while moving, they share location claims only on their common target nodes. This simple and efficient way of updating the claims turns out to reduce communication costs greatly. We note that in previous protocols, either a base station collects the location claims of all nodes, which leads to high communication costs, or two neighbouring nodes exchange entire records. Our method of sharing location claims also enables our approach to update the location claims without direct contact with the target nodes, which in turn significantly reduces communication costs. Another notable feature of our approach is that the number of target nodes assigned to each node are fixed. When the memory of a node is full, the existing methods [11, 13, 14] delete the oldest record, which may cause high detection errors. Our approach does not require any records to be deleted because the number of target nodes to be stored in a node is fixed. This way of fixing target nodes also allows two neighbouring nodes to exchange a small amount of information in their transactions, resulting in reduced communication costs. 1.2 Our contributions In this paper, we propose efficient distributed detection methods of replicas (EDDRs) for large-scale mobile networks. According to the number of communication rounds, EDDRs are divided into two-round EDDR and three-round EDDR. In three-round EDDR, a node and its neighbouring node share the location claims of the common target nodes through exchange of their records (called 'mutual sharing'). On the other hand, in two-round EDDR, only one party can obtain the location claims of the common target nodes through one-sided delivery of the record (called 'unilateral sharing'). The mutual sharing strategy enables three-round EDDR to provide a higher detection ratio and shorter detection time, whereas the unilateral sharing strategy enables two-round EDDR to provide lower energy consumption. In this paper, we describe an improved version of our previous three-round EDDR method [5]. Compared with the previous work, in this paper, we additionally introduce two-round EDDR and provide security analyses as well as simulation results. In comparison with the related literatures, we have identified the following unique contributions of this paper: Useful design for replica detection: EDDRs characterise target nodes while supporting unilateral and mutual sharing of records. This leads to the following benefits: ○ Efficient information update: To share information on common target nodes, EDDRs exchange records concerning only common target nodes, whereas time-domain detection (TDD) and space-domain detection (SDD) [11] exchange entire records with a counterpart node. As a result, EDDRs can reduce communication costs considerably. ○ Low detection errors: When the memory of a node is full, eXtremely efficient detection (XED) [13], TDD and SDD [11] delete the oldest record to store the record of the most recently encountered node. Unfortunately, this deletion may cause high detection errors. In contrast to these methods, EDDRs restrict target nodes to a fixed number, so there is no need for record deletion. ○ Small-sized records: In EDDRs, a record is only 14 bytes in size, and consists of a node ID, a meeting time and a location. ○ Scalable design: Unlike TDD and SDD [11], EDDRs do not require any additional overheads in order to achieve the addition of nodes. Acceptable simulation results: We implemented EDDRs, XED [13] and Ho's protocol [9] by using a simulation tool. Here, we note that the measured values should be used only for comparative analysis because they are obtained from simulation results. Consequently, we demonstrate that EDDRs have several advantages: ○ High replica detection ratio: EDDRs show an almost perfect replica detection ratio of 0.97, whereas XED and Ho's protocol show average ratios of 0.76 and 0.38, respectively. ○ Low detection errors: Detection errors can be measured with false-positive and false-negative ratios. EDDRs hardly generate any detection errors, that is, the error values are close to zero. Conversely, XED generates the ratios of 0.87 and 0.24, respectively, and Ho's protocol generates a value of 0.16 on average for both ratios. In critical mission tasks such as military surveillance, maintaining extremely low detection errors is vital. ○ Energy-efficient replica detection: Two-round EDDR is the most energy-efficient protocol, in which 2547.70 mJ of energy is consumed by a node on average. In three-round EDDR, XED and Ho's protocol, the averages are 6364.41, 5273.55 and 26 511.18 mJ, respectively. We note that energy efficiency is important when we consider that nodes in a hostile environment are often non-rechargeable, and hence, their availability depends on their energy efficiency. ○ Speedy replica detection: Three-round EDDR detects all replicas within the shortest time; it requires 86.11 s on average. In contrast, the average times for two-round EDDR, XED and Ho's protocol are 103.39, 244.66 and 726.87 s, respectively. 1.3 Organisation of the paper The paper is organised as follows. In Section 2, we introduce related works. In Section 3, we explain our assumptions and the attack model. Subsequently, we describe the EDDRs in Section 4, and show analyses of the security, performance and statistical scalability in Section 5. Lastly, we draw our conclusions in Section 6. 2 Related work Although mobile devices are more advanced than static ones, most replica detection methods [4, 6-8, 10, 12, 15, 16, 18] deal with static ad hoc networks, mainly by using a fixed node location as proof of the identification of a replica and a digital signature as the authentication mechanism. Recently, several solutions [5, 9, 11, 13, 14, 16] have been proposed for mobile applications. Yu et al. [13] designed a distributed protocol, XED, by using a random number exchange that requires a far lower computational cost than a digital signature. Whenever a node meets another node during movement, both nodes exchange and record a random number. When the two nodes meet again, they confirm the previously exchanged random number. If the exchanged random number matches with the record, they exchange a new random number. Otherwise, a revocation message that includes the ID of the node transmitting the unmatched random number is broadcast over the entire network. Although this protocol has the advantage of requiring neither location information [i.e. no need for a global positioning system (GPS)] nor a signature algorithm, it causes high detection errors in large-scale mobile applications owing to memory limitation in the nodes. The authors also introduced another distributed protocol [14] that uses a (predefined) maximum possible number, ϕ, of encounters with genuine nodes. For example, if the number of encounters with a node is more than the predefined parameter ϕ, the node is regarded as a replica. However, determining a reasonable value for ϕ is difficult because the movements of all nodes are unpredictable. Ho et al. [9] proposed a centralised protocol (hereafter Ho's protocol) that uses the maximum node speed and a digital signature. After the base station has collected a location claim (including a node ID, the current time and its location) for each node in an authenticated way, it computes the speed of each node and then determines a replica by comparing the computed speed with a predefined maximum speed. This solution involves high communication costs, because the location claims of all nodes, even from distant locations, must be periodically reported to the base station. Furthermore, the nodes closest to the base station tend to have heavier routing loads than other nodes, resulting in considerable performance degradation. Cho et al. [5] also proposed an effective distributed detection protocol (here, we call the protocol 'three-round EDDR') using the location claim exchange with neighbouring nodes. Unfortunately, the three-round EDDR requires more energy than 'two-round EDDR', which is newly proposed in this paper. As this paper is an improved version of the work [5], we introduce more energy-efficient replica detection protocol in two-round EDDR. In addition, we show that the proposed protocols have good performance through simulation experiments. Although Conti et al. [16] also proposed a replica detection protocol based on the location claim exchange, the work did not provide high replica detection ratio because of memory limitation. Recently, Xing and Cheng [11] presented two replica-detection protocols. Their protocols are appropriate combinations of a one-way hash chain technique [19] and the abovementioned techniques of information exchange with neighbouring nodes [5, 13], limited maximum number of encounters [14] and limited maximum speed [9]. However, one of the protocols causes excessive routing traffic during the delivery of location in mobile applications, possibly resulting in high communication overheads. Furthermore, another protocol requires large-sized records. Unfortunately, large-sized records are unsuitable for memory-limited devices such as sensor motes because the number of records that can be stored in a node is limited. 3 Assumptions and attack model 3.1 Assumptions We assume that a node does not require any tamper-proof hardware, which in general is not a plausible solution in a node because of its limited cost. This implies that an attacker with a captured node can easily extract the credentials of the node and reproduce replicas. Here, we also assume that the replicas are commodity nodes that anybody can easily purchase. Hence, we assume that the replicas and genuine nodes have the same capabilities in terms of processing capacity, radio-channel number, communication range and storage. We also assume that an attacker cannot readily generate a new ID for a replica. Newsome et al. [20] describe several techniques to prevent an attacker from deploying nodes with arbitrary IDs. For instance, we can bind each node ID to the unique knowledge it possesses. In the ID-based cryptosystems of [21-23], a node ID could correspond to its secret key, which is generated by a trusted authority. In this way, an attacker gains little advantage by claiming the possession of an ID without actually having the appropriate keys. We assume that each node can obtain its own geographical positions. Numerous researchers have proposed methods to calculate node location [24, 25], or to detect replicas by using node location [4, 6-11, 15], in which they assume that each node can measure its position by using specific hardware such as a GPS receiver. A replica is not supposed to generate any report for the purpose of revoking genuine nodes. The principal goal of a replica attack is to deceive the genuine nodes to obtain any information from them. If all the genuine nodes are revoked, only replicas will exist. This situation will not benefit the attacker. The clocks of all nodes are loosely synchronised with a maximum error of ε. Existing protocols [9, 11] have been designed by using loose time synchronisation. In addition, maintaining loose time synchronisation between all the nodes in the network is easy because nodes equipped with a GPS receiver can obtain the global time at any time. 3.2 Attack model A replica attack is one in which the attacker injects more than one replica into a network by using the same ID as another node, that is, a captured node [4] to compromise a large fraction of the network with minimal effort. With regard to this type of attack, an attacker is assumed to capture only a tiny fraction of nodes in the network. The reason is because capturing a large fraction may not require replicas at all and it also would be much more costly and detectable. Therefore a reasonable assumption is that an attacker captures only a small number of nodes, and makes replicas by duplicating the captured nodes to inject them back into the network. Subsequently, the attacker achieves adversarial goals such as the fabrication of messages to mislead the header nodes or the injection of bogus data to cause network failure (see Fig. 1). Fig. 1Open in figure viewerPowerPoint σ-round EDDR protocol (code of node a, σ ∈ {2, 3}) In addition, replicas travel extensively in the network while communicating with a number of genuine nodes in order to gather a large amount of information in as short a time as possible before being detected. Furthermore, replicas do not move around in groups because their limited movements cannot greatly benefit the attacker in the short term. 4 EDDR protocols EDDRs can run in two or three rounds with regard to resource efficiency and detection time. We describe EDDRs from the standpoint of node a in Algorithm 1 (see Fig. 1), which consists of 'setting' and 'processing' phases. In the setting phase, which is preparatory to the processing phase, each node initialises all the parameters. In the processing phase, the nodes detect replicas by exchanging information during their movements. The setting and processing phases are described in greater detail in Sections 4.1 and 4.2, respectively. Table 1 lists the nomenclature used in our description of the protocols. Table 1. Nomenclature used to describe our protocol Notation Description σ number of protocol rounds performed in EDDR, that is, σ = 2 or 3 IDa ID of node a IDlow lowest node ID in the network IDhigh highest node ID in the network Ta set of target node IDs for node a, or simply node a's target set |T| number of nodes in the target set. This is defined by a trusted authority such as the base station params environmental parameters suitable for each message, for example a flag variable La location of node a time instant that a message is generated by sender node a 4.1 Setting phase In the setting phase, in Algorithm 1 (see Fig. 1), node a computes its target set Ta by using the public function SelectTarget(·): Ta ← SelectTarget(IDa, IDlow, IDhigh, |T |), where low is the lowest index and high is the highest index of all the nodes. This means that each node (here, node a) uniformly and randomly selects its target set Ta of a predefined size |T| among {IDlow, …, IDhigh}. For example, we assume that, given IDlow = IDa, IDhigh = IDx, and |T | = 3, node a obtains its target set Ta = {IDc, IDg, IDv} ← SelectTarget(IDa, IDa, IDx, 3), that is, node a has its target nodes c, g and v. In the case of node addition, that results from node failure such as battery exhaustion or node compromise, each node can easily update its target set by receiving new values of IDlow', IDhigh' and |T | from the base station in an authenticated way. Assume that new nodes y and z are inserted in the network, and node a receives a node addition message containing IDlow′ = IDa, IDhigh′ = IDz and |T | = 4 from the base station. On receiving the node addition message, node a can renew Ta ← SelectTarget(IDa, IDa, IDz, 4). In addition, node a resets system parameters such as its timer in the setting phase. These settings can be configured before or immediately after node deployment. 4.2 Processing phase Fig. 2 displays the processing phase of Algorithm 1 (see Fig. 1) in diagram form. The phase consists of four stages: (i) broadcast of claim request, (ii) ID validation, (iii) claim request handling and (iv) ReplyList message handling. We describe the four stages below. (1) Broadcast of claim request [line 1 in Algorithm 1 (see Fig. 1)]: Here, a node periodically transmits a claim request message in order to inform neighbouring nodes of its existence. This operation allows its neighbouring nodes to reply. Node a first starts a timer and broadcasts a claim request message periodically after a fixed interval Δ. Whenever the timer reaches interval Δ, node a broadcasts a claim request message 〈params, IDa〉 consisting of related parameters and IDa. (2) ID validation [line 2 in Algorithm 1(see Fig. 1)]: When a node receives a message (a claim request or ReplyList), it first validates the sender ID by checking whether or not the sender is a replica based on a revocation list and an ID check. The details are as follows: when node a receives a message from another node, say node b, it checks if IDb is in its revocation list. If so, the request is ignored. If the ID of the sender is equal to IDa (i.e. IDa = IDb), node a concludes that it has been replicated. Node a then broadcasts a revocation message and falls into disuse itself. Consequently, all nodes having IDa are isolated from the network. When any node in the network receives the revocation message of node a, it registers IDa in its revocation list after validating the message. Fig. 2Open in figure viewerPowerPoint Outline of processing phase in a node *in three-round EDDR, a claim request message is transmitted together with the ReplyList message (3) Claim request handling [lines 3–10in Algorithm 1(see Fig. 1)]: This stage handles a claim request message. Upon receiving a claim request message, a node generates a reply message, ReplyList, which is used to identify replicas, and then transmits it to the sender. In the case of three-round EDDR, the node also transmits a claim request message to the sender. This additional operation leads the node to receive the ReplyList from the sender. The details are as follows: when node a receives a claim request (line 3), it first derives b's target set Tb via SelectTarget(IDb, IDlow, IDhigh, |T|) and resets its ReplyList. If node a finds itself in Tb (line 4), it generates a ReplyList consisting of its ID, location and current time (line 5). Node a also searches for all the target nodes common to Ta and Tb (line 6), and inserts the information on the common target nodes into the ReplyList (line 7). If the ReplyList is not empty, node a sends it to node b (line 8). In Algorithm 1 (see Fig. 1), 'a → b(*):M ' indicates that node a transmits message M to node b, via broadcast rather than unicast, while expecting node b to receive message M. Note that in fact, node b may not receive message M. In our simulation experiments, this message-transmission strategy makes message routing easier, and thus contributes greatly to improving the performance of EDDRs. In contrast to two-round EDDR, a claim request message is also transmitted (lines 9 and 10) in three-round EDDR so that the receiver node (node a) also collects the information of its counterpart node (node b). Accordingly, in three-round EDDR, the claim request handling stage (lines 3–10) is conducted in node a as well as in node b. Although the difference between two-round and three-round EDDRs is apparently small, it leads to obvious differences in terms of performance measures such as detection time and consumed energy. We will show this difference from the simulation results in Section 5.2. (4) ReplyList message handling [lines 11–16 in Algorithm 1 (see Fig. 1)]: A node determines whether or not its target nodes are replicas on the basis of the ReplyList message. The details are as follows: when node a receives the location information of its target nodes (line 11), it first validates their signature. The information, ReplyList, contains the locations and recent times of node a's target nodes and/or the common nodes between Ta and Tb. For each target node in the ReplyList (line 12), node a then checks if its location in the information is reasonably bounded, considering the received time and its recorded time (line 13). Node a computes the distance by using a Euclidean distance algorithm and the maximum speed of the node, and determines whether the distance is within the maximum bound. If not, node a decides that the target node is cloned and broadcasts a message that revokes its ID (line 14). Otherwise, node a checks the freshness of the received information. If the information is newer than its own (line 15), node a updates its own record (line 16). 5 Analysis For a clear analysis of EDDRs, we define the notations in Table 2. Table 2. Nomenclature used to analyse our protocol Notation Description Ng number of all genuine nodes Ngc number of genuine nodes that are captured and replicated by an attacker, that is, the number of captured nodes Nrc number of replicas for each captured node. For example, if Nrc = 2, two replicas are generated for one captured node. To simplify the analysis, we assume that the same number of replicas are generated for each captured node Nr number of all replicas, that is, Nr = Ngc × Nrc N number of all nodes including replicas in the network, that is, N = Ng + Nr PT Proportion of |T| among N, that is, (|T|/N) d average number of neighbouring nodes n number of moves, that is, how many times neighbouring nodes are changed 5.1 Security analysis In some cases, a replica may not be detected at all. We identify these cases, and show that in fact, the likelihood of these cases occurring is negligible. 5.1.1 Four cases with replica undetected Case 1: Replicas do not abide by the rules of EDDRs and may collude under an attacker's control. In this case, we assume that even when a replica (a′) discovers another replica (b′\where a′ ∈ Tb'), the replica b′ does not broadcast the existence of replica a′. We do not include the case where a replica refuses to exchange information or intentionally exchanges fabricated information with a genuine node. Such behaviours enable the genuine node to recognise the replica and do not help obfuscate replica detection. Case 2: A genuine node may not meet any target nodes in its target set. In this case, no watcher node can collect any evidence to identify the replicas. Case 3: A genuine node may not meet any other genuine nodes with common target nodes. Case 4: The common target nodes exchanged with neighbouring nodes may not be replicas or nodes captured to make the replicas, so the genuine nodes do not obtain any useful information to detect the replicas. The first case accounts for attacks that replicas might launch, whereas the other three cases account for all situations in which no useful information for replica detection is available. We define the event probabilities of the four cases as P1, P2, P3 and P4, respectively, and determine them for each case. For a mathematical analysis of security, we assume that each node meets d neighbouring nodes in each time window. We also assume that two replicas are generated for e