Establishing Pairwise Keys in Distributed Sensor Networks Donggang Liu Peng Ning Jason Buckingham CSCI 7143 Secure Sensor Networks October 12 2004 Motivation Authentication and key management are essential to a secure network Due to resource constraints public key cryptography and key distribution center KDC are not feasible Prior Schemes Probabilistic key predistribution with key ring article we read last week A Key Management Scheme for Distributed Sensor Networks q composite key predistribution Increases capture the resilience of the network against node Random pairwise keys scheme Random pairs of nodes are assigned pairwise keys Adds authentication if each node stores the ID of the other node that shares the associated pairwise key Problems with existing schemes For basic probabilistic and q composite schemes as the number of compromised nodes increases the fraction of affected pairwise keys rapidly increases For random pairwise keys scheme network size is limited by the desired probability of two nodes sharing a link Polynomial Based Key Predistribution The key setup server randomly generates a bivariate tdegree polynomial over a finite field Fq where q is a prime number and f x y f y x Each sensor i has a unique ID and the server computes a polynomial share of f x y by computing f i y Two nodes i j can computer the same key node i can compute f i j by evaluating f i y at point j and vice versa Problems with Polynomial Based Key Predistribution Tolerates only the compromise of t nodes t is the degree of the polynomial To support additional nodes with the same security the size of the polynomial must increase and thus the memory requirements increase Polynomial Pool Based Key Predistribution Uses a pool of randomly generated bivariate polynomials to establish pairwise keys Two special cases When the polynomial pool has only one polynomial this is the same as Polynomial Based Key Predistribution When the polynomials are all of degree 0 this is the same as the basic key pool predistribution Setup The key setup server generates a set of polynomials assigning each polynomial a unique ID Each sensor node is randomly assigned a subset of these polynomials Key Establishment Done through direct key or path key establishment Secure Link two nodes can establish a pairwise key through direct key establishment Polynomial share discovery is done through predistribution or real time discovery Predistribution requires additional memory makes it difficult for nodes to join the network on the fly and may provide additional information to an attacker Real time discovery is done through the exchange of a list of polynomial IDs or with a challenge This adds additional communication overhead Path Key Establishment through real time discovery Two nodes that do not share a direct link that need to communicate with each other must establish a pairwise key This is done by finding a path between the two nodes via nodes that do share a pairwise key directly This path discovery problem introduces substantial communication overhead Differences from Basic Key Pool Predistribution Chooses a polynomial from a polynomial pool instead of a key from a key pool In Basic Key Pool Predistribution several nodes share the same key With polynomial pools there is a unique key between each pair of sensors each node gets a unique polynomial share based on its unique node ID If no more that t shares on the same polynomial are discovered then no pairwise keys from noncompromised nodes can be discovered Network Connectivity The probability of two sensors sharing the same polynomial can directly connect is s is the number of polynomials pool size and s is the number of polynomial shares stored on each node The probability that two nodes can establish a pairwise key directly or indirectly is Ps 1 1 p 1 p2 d where d is the average number of neighbors each node has Vulnerability of Polynomial Pool Predistribution If an attacker compromises t 1 nodes that have the same polynomial he is able to compromise all links that use that polynomial Solution don t allow a polynomial to be used in more than t 1 nodes Given this constraint the total number of sensors cannot exceed t 1 s s Comparison with Previous Schemes Fraction of compromised links between non compromised sensors vs number of compromised sensor nodes Grid Based Key Predistribution For a sensor network with at most N nodes We construct an m x m grid with a set of 2m polynomials Each node is assigned a unique row column intersection in the grid A node at coordinate i j stores the polynomial shares for and Pairwise Key Establishment To directly establish a pairwise key with a node j node i must either be in the same column or same row as node j If not path discovery is performed Either node ci rj or cj ri can establish a pairwise key with both nodes What if both nodes ci rj and cj ri are compromised or out of range Path Discovery There are still many alternative paths In fact there are up to 2 m 2 pairs of such nodes in the grid Grid Based Analysis Each node can potentially establish a pairwise key with 2 m 1 other nodes directly The percent of nodes that a node can establish a link with directly is In fact if there are no compromised nodes it is guaranteed that two nodes can establish a pairwise key Overhead nodes only need to store two t degree polynomial shares and the IDs of each compromised node Communication overhead is mostly from path discovery Attacks against a pair of nodes How difficult is it to compromise a pairwise key without compromising the related nodes Even if an attacker compromises t 1 nodes the nodes can still establish a new pairwise key via path discovery Interesting attack if a node involved in a key path that was used to establish a pairwise key is compromised the previously established key is then compromised if the attacker has recorded the message that established the key Attacks against a pair of nodes cont To prevent two nodes from establishing a pairwise key the attacker has to block all possible key paths between the nodes There are 2m 2 key paths between any two nodes that involve one or two intermediate nodes There are at least 2m 3 paths and an attacker must compromise at least one node in each path to prevent two particular nodes from communicating Attacks against the network The attacker can try to systematically or randomly compromise nodes in the network to lower the probability that two nodes can establish a pairwise key to simply