A survey of security issues in wireless sensor networks <s> Deterministic Approaches <s> It is sometimes required that user pairs in a network share secret information to be used for mutual identification or as a key in a cipher system. If the network is large it becomes impractical or even impossible to store all keys securely at the users. A natural solution then is to supply each user with a relatively small amount of secret data from which he can derive all his keys. A scheme for this purpose will be presented and we call such a scheme a symmetric key generation system (SKGS). However, as all keys will be generated from a small amount of data, dependencies between keys will exist. Therefore by cooperation, users in the system might be able to decrease their uncertainty about keys they should not have access to.The objective of this paper is to present a class of SKGS for which the amount of secret information needed by each user to generate his keys is the least possible while at the same time a certain minimum number of users have to cooperate to resolve the uncertainty of unknown keys. <s> BIB001 </s> A survey of security issues in wireless sensor networks <s> Deterministic Approaches <s> A key distribution scheme for dynamic conferences is a method by which initially an (off-line) trusted server distributes private individual pieces of information to a set of users. Later any group of users of a given size (a dynamic conference) is able to compute a common secure key. In this paper we study the theory and applications of such perfectly secure systems. In this setting, any group of t users can compute a common key by each user computing using only his private piece of information and the identities of the other t - 1 group users. Keys are secure against coalitions of up to k users, that is, even if k users pool together their pieces they cannot compute anything about a key of any t-size conference comprised of other users.First we consider a non-interactive model where users compute the common key without any interaction. We prove a lower hound on the size of the user's piece of information of (k+t-1 t-1) times the size of the common key. We then establish the optimality of this bound, by describing and analyzing a scheme which exactly meets this limitation (the construction extends the one in [2]). Then, we consider the model where interaction is allowed in the common key computation phase, and show a gap between the models by exhibiting an interactive scheme in which the user's information is only k + t - 1 times the size of the common key. We further show various applications and useful modifications of our basic scheme. Finally, we present its adaptation to network topologies with neighborhood constraints. <s> BIB002 </s> A survey of security issues in wireless sensor networks <s> Deterministic Approaches <s> The security of sensor network s is ever more important nowadays. In this paper we propose a new protocol BROSK to construct link dependent keys by broadcasting key negotiation messages. The link-dependent key will be negotiated in an ad-hoc scheme. Most of the proposed security protocols in sensor networks are based on point-to-point handshaking procedures to negotiate link -dependent keys, but this will influence the scalability of the network. The simulation shows that the scalability of BROSK is better than two other security protocols of sensor network, SPINS and SNAKE, and is reasonably secure. This new protocol consumes less energy by reducing the number of transmissions used for key negotiation among sensor nodes. <s> BIB003 </s> A survey of security issues in wireless sensor networks <s> Deterministic Approaches <s> Distributed Sensor Networks (DSNs) are ad-hoc mobile networks that include sensor nodes with limited computation and communication capabilities. DSNs are dynamic in the sense that they allow addition and deletion of sensor nodes after deployment to grow the network or replace failing and unreliable nodes. DSNs may be deployed in hostile areas where communication is monitored and nodes are subject to capture and surreptitious use by an adversary. Hence DSNs require cryptographic protection of communications, sensor-capture detection, key revocation and sensor disabling. In this paper, we present a key-management scheme designed to satisfy both operational and security requirements of DSNs. The scheme includes selective distribution and revocation of keys to sensor nodes as well as node re-keying without substantial computation and communication capabilities. It relies on probabilistic key sharing among the nodes of a random graph and uses simple protocols for shared-key discovery and path-key establishment, and for key revocation, re-keying, and incremental addition of nodes. The security and network connectivity characteristics supported by the key-management scheme are discussed and simulation experiments presented. <s> BIB004 </s> A survey of security issues in wireless sensor networks <s> Deterministic Approaches <s> Key establishment in sensor networks is a challenging problem because asymmetric key cryptosystems are unsuitable for use in resource constrained sensor nodes, and also because the nodes could be physically compromised by an adversary. We present three new mechanisms for key establishment using the framework of pre-distributing a random set of keys to each node. First, in the q-composite keys scheme, we trade off the unlikeliness of a large-scale network attack in order to significantly strengthen random key predistribution's strength against smaller-scale attacks. Second, in the multipath-reinforcement scheme, we show how to strengthen the security between any two nodes by leveraging the security of other links. Finally, we present the random-pairwise keys scheme, which perfectly preserves the secrecy of the rest of the network when any node is captured, and also enables node-to-node authentication and quorum-based revocation. <s> BIB005 </s> A survey of security issues in wireless sensor networks <s> Deterministic Approaches <s> A distributed Wireless Sensor Network (WSN) is a collection of n sensors with limited hardware resources. Sensors can exchange messages via Radio Frequency (RF), whose range usually covers only a limited number of other sensors. An interesting problem is how to implement secure pair-wise communications among any pair of sensors in a WSN. A WSN requires completely distributed solutions which are particularly challenging due to the limited resources and the size of the network. Moreover, WSNs can be subject to several security threats, including the physical compromising of a sensor. Hence, any solution for secure pairwise communications should tolerate the collusion of a set of corrupted sensors. This paper describes a probabilistic model and two protocols to establish a secure pair-wise communication channel between any pair of sensors in the WSN, by assigning a small set of random keys to each sensor. We build, based on the first Direct Protocol, a second Co-operative Protocol. The Co-operative Protocol is adaptive: its security properties can be dynamically changed during the life-time of the WSN. Both protocols also guarantee implicit and probabilistic mutual authentication without any additional overhead and without the presence of a base station. The performance of the Direct Protocol is analytically characterized while, for the Co-operative Protocol, we provide both analytical evaluations and extensive simulations. For example, the results show that, assuming each sensor stores 120 keys, in a WSN composed of 1024 sensors with 32 corrupted sensors the probability of a channel corruption is negligible in the case of the Co-operative Protocol. <s> BIB006 </s> A survey of security issues in wireless sensor networks <s> Deterministic Approaches <s> Sensor networks are ideal candidates for applications such as target tracking and environment monitoring. Security in sensor networks is critical when there are potential adversaries. Establishment of pairwise keys is a fundamental security service, which forms the basis of other security services such as authentication and encryption. However, establishing pairwise keys in sensor networks is not a trivial task, particularly due to the resource constraints on sensors. This paper presents several techniques for establishing pairwise keys in static sensor networks. These techniques take advantage of the observation that in static sensor networks, although it is difficult to precisely pinpoint sensors' positions, it is often possible to approximately determine their locations. This paper presents a simple location-aware deployment model, and develops two pairwise key predistribution schemes, a closest pairwise keys predistribution scheme and a location-based pairwise keys scheme using bivariate polynomials, by taking advantage of sensors' expected locations. The analysis in this paper indicates that these schemes can achieve better performance if such location information is available and that the smaller the deployment error (i.e., the difference between a sensor's actual location and its expected location) is, the better performance they can achieve. <s> BIB007 </s> A survey of security issues in wireless sensor networks <s> Deterministic Approaches <s> It is an important issue to establish pairwise keys in distributed sensor networks (DSNs). In this paper, we present two key predistribution schemes (KPSs) for DSNs, ID-based one-way function scheme (IOS) and deterministic multiple space Blom's scheme (DMBS). Our schemes are deterministic, while most existing schemes are based on randomized approach. We show that the performance of our schemes is better than other existing schemes in terms of resiliency against coalition attack. In addition we obtain perfectly resilient KPSs such that the maximum supportable network size is larger than random pairwise keys schemes. <s> BIB008 </s> A survey of security issues in wireless sensor networks <s> Deterministic Approaches <s> To achieve security in wireless sensor networks, it is important to he able to encrypt messages sent among sensor nodes. Keys for encryption purposes must he agreed upon by communicating nodes. Due to resource constraints, achieving such key agreement in wireless sensor networks is nontrivial. Many key agreement schemes used in general networks, such as Diffie-Hellman and public-key based schemes, are not suitable for wireless sensor networks. Pre-distribution of secret keys for all pairs of nodes is not viable due to the large amount of memory used when the network size is large. Recently, a random key pre-distribution scheme and its improvements have been proposed. A common assumption made by these random key pre-distribution schemes is that no deployment knowledge is available. Noticing that in many practical scenarios, certain deployment knowledge may be available a priori, we propose a novel random key pre-distribution scheme that exploits deployment knowledge and avoids unnecessary key assignments. We show that the performance (including connectivity, memory usage, and network resilience against node capture) of sensor networks can he substantially improved with the use of our proposed scheme. The scheme and its detailed performance evaluation are presented in this paper. <s> BIB009 </s> A survey of security issues in wireless sensor networks <s> Deterministic Approaches <s> We discuss the use of combinatorial set systems in the design of deterministic key predistribution schemes for distributed sensor networks. We concentrate on analyzing combinatorial properties of the set systems that relate to the connectivity and resilience of the resulting distributed sensor networks. <s> BIB010 </s> A survey of security issues in wireless sensor networks <s> Deterministic Approaches <s> To achieve security in wireless sensor networks, it is important to be able to encrypt and authenticate messages sent between sensor nodes. Before doing so, keys for performing encryption and authentication must be agreed upon by the communicating parties. Due to resource constraints, however, achieving key agreement in wireless sensor networks is nontrivial. Many key agreement schemes used in general networks, such as Diffie-Hellman and other public-key based schemes, are not suitable for wireless sensor networks due to the limited computational abilities of the sensor nodes. Predistribution of secret keys for all pairs of nodes is not viable due to the large amount of memory this requires when the network size is large.In this paper, we provide a framework in which to study the security of key predistribution schemes, propose a new key predistribution scheme which substantially improves the resilience of the network compared to previous schemes, and give an in-depth analysis of our scheme in terms of network resilience and associated overhead. Our scheme exhibits a nice threshold property: when the number of compromised nodes is less than the threshold, the probability that communications between any additional nodes are compromised is close to zero. This desirable property lowers the initial payoff of smaller-scale network breaches to an adversary, and makes it necessary for the adversary to attack a large fraction of the network before it can achieve any significant gain. <s> BIB011
LEAP uses unicast for key exchange. Notice that most of the proposed security protocols were based on point-to-point handshaking procedures to negotiate session keys. Lai et al. have proposed a BROadcast Session Key (BROSK) negotiation protocol BIB003 . BROSK assumes a master key is shared by all nodes in the network. To establish a session key K with its neighbors, such as node B, a sensor node A broadcasts a key negotiation message: A and B will receive the broadcast message. They can verify the message using the master key K and both A and B can calculate the shared session key: BROSK therefore establishes pairwise session keys between every two neighboring nodes. It is both scalable and energy efficient. Camtepe and Yener have proposed a deterministic key distribution schemes for WSNs using Combinatorial Design Theory  . The combinatorial design theory based pairwise key predistribution (CDTKeying) scheme is based on block design techniques in combinatorial design theory. It employs symmetric and generalized quadrangle design techniques. The scheme uses a finite projective plane of order n (for prime power n) to generate a symmetric design with parameters n 2 + n + 1, n + 1, 1. The design supports n 2 + n + 1 nodes, and uses a key-pool of size n 2 + n + 1. It generates n 2 + n + 1 key chains of size n + 1 where every pair of key chains has exactly one key in common, and every key appears in exactly n + 1 key chains. After the deployment, every pair of nodes finds exactly one common key. Thus, the probability of key sharing among a pair of sensor nodes is 1. The disadvantage of this solution is that the parameter n has to be a prime power, thus indicating that not all network sizes can be supported for a fixed key-chain size. Lee and Stinson have proposed two combinatorial design theory based deterministic schemes: the ID-based one-way function scheme (IOS) and the deterministic multiple space Blom's scheme (DMBS) BIB008 . They further discussed the use of combinatorial set systems in the design of deterministic key predistribution schemes for WSNs in BIB010 . Probabilistic Approaches -Most proposed key management schemes in WSNs are probabilistic and distributed schemes. Eschenauer and Gligor introduced a key predistribution scheme for sensor networks which relies on probabilistic key sharing among the nodes of a random graph in BIB004 . This scheme consists of three phases: key predistribution, sharedkey discovery, and path key establishment. In the key predistribution phase, each sensor is equipped with a key ring held in the memory. The key ring consists of k keys which are randomly drawn from a large pool of P keys. The association information of the key identifiers in the key ring and sensor identifier is also stored at the base station. Further, the authors assumed that each sensor shares a pairwise key with the base station. In the shared key discovery phase, each sensor discovers its neighbors within the wireless communication range with which it shares keys. Two methods to accomplish this are suggested in BIB004 . The simplest method is for each node to broadcast a list of identifiers of the keys in their key ring in plain text, thus allowing neighboring nodes to check whether they share a key. However, an adversary may observe the key-sharing patterns among sensors in this way. The second method uses the challenge-response technique to hide key-sharing patterns among nodes from an adversary. For every K i on a key ring, each node could broadcast a list α, E Ki (α), i = 1, …, k where α is a challenge. The decryption of E K i (α) with the proper key by a recipient would reveal the challenge and establish a shared key with the broadcasting node. This method requires that the challenge α be well known in the sensor network, thus allowing the recipient with the proper key to discover the challenge. Finally, in the path-key establishment phase, a path-key is assigned for those sensor nodes within wireless communication range and not sharing a key, but connected by two or more links at the end of the second phase. If a node is compromised, the base station can send a message to all other sensors to revoke the compromised node's key ring. Rekeying follows the same procedure as revocation. The messages from the base station are signed by the pairwise key shared by the base station and sensor nodes, and thus it is ensured that no adversary can forge a base station. If a node is compromised, the attacker has a probability of approximately k/P to be able to successfully attack any link. Because k << P, it only affects a small number of sensor nodes. Inspired by the work in BIB004 , which we call the basic random key scheme in the following section, additional random key predistribution schemes have been proposed in BIB005  BIB006 BIB011 BIB009  . In the basic random key scheme, any two neighboring nodes need to find a single common key from their key rings in order to establish a secure link in the key setup phase. However, Chan et al. observed that increasing the amount of key overlap in the key ring can increase the resilience of the network against node capture BIB005 . Thus, they proposed a qcomposite keying scheme, in which it is required that at least q common keys be shared in the key setup phase in order to build a secure link between any two neighboring nodes. Further, a key update phase was introduced to enhance the basic random key scheme. Suppose A has a secure link to B after the key setup phase and the secure key k is from the key pool P. Because k may be residing in the key-ring memory of some other nodes in the network, the security of the link between A and B is jeopardized if any of those nodes are captured. Thus, it is better to update the communication key between A and B instead of using a key in the key pool. To address this problem, they presented a multipath key reinforcement for the key update. Assume there are j disjoint paths between A and B. A generates j random values v 1 , v 2 , …, v j and then routes each random value along a different path to B. When B has received all j keys, the new link key can be computed by both A and B as follows: The adversary has to eavesdrop on all j paths if he/she wants to reconstruct the communication key. This security enhancement comes at the cost of more communication overhead needed to find multiple disjoint paths. Further, Chan et al. also developed a random-pairwise keys scheme for nodeto-node authentication. Blundo et al. presented a polynomial-based key predistribution protocol for group key predistribution BIB002 which can also be adapted to sensor networks. The key setup server randomly generates a bivariate t-degree polynomial f(x, y) = Σ i t , j=0 a ij x i y j over a finite field F q where q is a prime number that is large enough to accommodate a cryptographic key such that it has the property of f(x, y) = f(y, x). For each sensor i, the setup server computes a polynomial share of f(x, y), that is, f(i, y). For any two sensor nodes i and j, node i can compute the common key f(i, j) by evaluating f(i, y) at point j, and node j can compute the same key f(j, i) = f(i, j) by evaluating f(j, y) at point i. In this approach, each sensor node i needs to store a t-degree polynomial f(i, x), which occupies (t + 1) log q storage space. This scheme is unconditionally secure and tcollusion resistant. However, the storage cost for a polynomial share is exponential in terms of the group size, making it prohibitive in sensor networks. Inspired by the work of BIB004 BIB005 BIB002 , Liu and Ning proposed a polynomial pool-based key predistribution scheme in  , which also includes three phases: setup, direct key establishment, and path key establishment. In the setup phase, the setup server randomly generates a set F of bivariate t-degree polynomials over the finite field F q . For each sensor node, the setup server picks a subset of polynomials F i ⊆ F and assigns the polynomial shares of these polynomials to node i. In the direct key establishment stage, the sensor nodes find a shared polynomial with other sensor nodes and then establish a pairwise key using the polynomial-based key predistribution scheme discussed in BIB002 . The path key establishment phase is similar to that in the basic random key scheme. Further, the proposed framework allows for the study of multiple instantiations of possible pairwise key establishment schemes. Two of the possible instantiations, the key predistribution scheme based on random subset assignment and the grid-based key predistribution scheme, are also presented and analyzed in the article. Similar to  , Du et al. presented another pairwise key predistribution scheme in BIB011 which uses Blom's method BIB001 . The key difference between  and BIB011 is that the scheme in  is based on a set of bivariate t-degree polynomials while Du's scheme is based on Blom's method. The proposed scheme allows any pair of nodes in a network to be able to find a pairwise secret key. As long as no more than λ nodes are compromised, the network is perfectly secure (which is called the λ-secure property). To use Blom's method, during the predeployment phase, the base station first constructs a (λ + 1) × N matrix G over a finite field GF(q) where N is the size of the network and G is considered to be public information. Then the base station creates a random (λ + 1) × (λ + 1) symmetric matrix D over GF(q), and computes a N × (λ + 1) matrix A = (D ⋅ G) T where (D ⋅ G) T is the transpose of D ⋅ G. Matrix D needs to be kept secret, and should not be disclosed to adversaries. It is easy to verify that A ⋅ G is a symmetric matrix. Thus, we know that K ij = K ji . The idea is to use K ij (or K ji ) as the pairwise key between nodes i and j. To carry out the above computation, in the predistribution phase, for any sensor k = 1, …, N: • Store the k th row of matrix A at node k • Store the k th column of matrix G at node k Therefore, when nodes i and j need to find the pairwise key between them, they first exchange their columns of G, and then respectively compute K ij and K ji using their private rows of A. In the proposed scheme in BIB011 , each sensor node is loaded with G and τ distinct D matrices drawn from a large pool of ω symmetric matrices D 1 , …, D ω of size (λ + 1) × (λ + 1). For each D i , calculate the matrix A i = (D i ⋅ G) T and store the j th row of A i at this node. After deployment, each node needs to discover whether it shares any space with neighbors. If they find out that they have a common space, the nodes can follow Blom's method to build a pairwise key. The scheme in BIB011 is scalable and flexible. Moreover, it is substantially more resilient against node capture as compared to  . Hwang et al. extended the basic random key scheme and proposed a cluster key grouping scheme  . They further analyzed the tradeoffs involved between energy, memory, and security robustness. Notice that location information helps to avoid unnecessary key assignments and thus improve the performance of sensor networks, for example, connectivity, memory usage, and network resilience against node capture. Taking this into account, two random key predistribution schemes were proposed in BIB009 BIB007 . Although the presented schemes show improved performance, the deployment information (e.g., location) is required when sensors are deployed. The abovementioned schemes are classified and compared in Note: Category I denotes deterministic approaches and category II denotes probabilistic approaches. Master key is the key shared by all the nodes in the network. Pairwise key is the key shared between two neighboring nodes. Path key denotes the key shared between any two nodes which need exchange data but does not share a pairwise key. Cluster key denotes the common key shared by all cluster members.