A Key-Management Scheme for Distributed SensorNetworks∗Laurent EschenauerElectrical and Computer EngineeringDepartmentUniversity of MarylandCollege Park, MD, [email protected] D. GligorElectrical and Computer EngineeringDepartmentUniversity of MarylandCollege Park, MD, [email protected] Sensor Networks (DSNs) are ad-hoc mobile net-works that include sensor nodes with limited computationand communication capabilities. DSNs are dynamic in thesense that they allow addition and deletion of sensor nodesafter deployment to grow the network or replace failing andunreliable nodes. DSNs may be deployed in hostile areaswhere communication is monitored and nodes are subject tocapture and surreptitious use by an adversary. Hence DSNsrequire cryptographic protection of communications, sensor-capture detection, key revocation and sensor disabling. Inthis paper, we present a key-management scheme designedto satisfy both operational and security requirements of DSNs.The scheme includes selective distribution and revocation ofkeys to sensor nodes as well as node re-keying without sub-stantial computation and communication capabilities. It re-lies on probabilistic key sharing among the nodes of a ran-dom graph and uses simple protocols for shared-key dis-covery and path-key establishment, and for key revocation,re-keying, and incremental addition of nodes. The securityand network connectivity characteristics supported by thekey-management scheme are discussed and simulation ex-periments presented.Categories and Subject DescriptorsC.2.0 [Computer-communication networks]: General—security and pr otectionGeneral TermsDesign, Security∗This work was supported in part by the U.S. Army Re-search Office under Award No. DAAD19-01-1-0494, andby the U.S. Army Research Laboratory under CooperativeAgreement DAAD19-01-2-0011 for the Collaborative Tech-nology Alliance for Communications and Networks.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.CCS’02, November 18–22, 2002, Washington, DC, USA.Copyright 2002 ACM 1-58113-612-9/02/0011 ...$5.00.Keywordskey management, sensor networks, random graphs, proba-bilistic key sharing1. INTRODUCTIONDistributed Sensor Networks (DSNs) share several char-acteristics with the more traditional embedded wireless net-works [13]. Both include arrays of sensor nodes that are bat-tery powered, have limited computational capabilities andmemory, and rely on intermittent wireless communicationvia radio frequency and, possibly, optical links. Both in-clude data-collection nodes, which cache sensor data andmake it available for processing to application componentsof the network, and control nodes, which monitor the statusof and broadcast simple commands to sensor nodes. Al-though in both networks most nodes have limited, if any,mobility after deployment, some nodes are highly mobile(e.g., data collection and control nodes placed on humans,vehicles, aircraft). However, DSNs differ from the tradi-tional embedded wireless networks in several important ar-eas, namely: their scale is orders of magnitude larger thanthat of embedded wireless networks (e.g., tens of thousandsas opposed to just tens of sensor nodes); they are dynamicin the sense that they allow addition and deletion of sensornodes after deployment to extend the network or replace fail-ing and unreliable nodes without physical contact; and theymay be deployed in hostile areas where communication ismonitored and sensor nodes are subject to capture and ma-nipulation by an adversary. These challenging operationalrequirements place equally challenging security constraintson DSN design. (For a detailed analysis of the operationaland security constraints of DSNs, the reader is referred tothe work of Carman, Kruus, and Matt [3]).Communic ation Security Constraints. The capabilities ofthe sensor nodes for large-scale DSNs range from those ofSmart Dust sensors [5, 9] that have only 8Kb of program and512 bytes for data memory, and processors with 32 8-bit gen-eral registers that run at 4 MHz and 3.0V (e.g., the ATMEL90LS8535 processor), to sensors that are over an order ofmagnitude more capable in terms of processing speed (e.g.,the MIPS R4000 processors) and memory capacity. Thepower, energy and the related computational and communi-cation limitations of nodes in this range make it impracticalto use typical asymmetric (public-key) cryptosystems to se-cure communications. For example, Carman, Kruus, and41Matt [3] report that on a mid-range processor, such as theMotorola MC68328 “DragonBall,” the energy consumptionfor a 1024-bit RSA encryption (signature) operation is muchhigher than that for a 1024-bit AES encryption operation;i.e., about 42 mJ (840 mJ) versus 0.104 mJ. Further, theenergy consumption for transmitting a 1024-bit block overa distance of approximately 900 meters using a typical com-munication subsystems such as Sensoria WINS NG RF at10 Kbps and 10 mW of power is about half that of RSAencryption (i.e., 21.5 mJ) and even less for reception (14.3mJ). Substantially less energy is spent to communicate oversmaller distances, since power is proportional to the squareof the distance. Also, in the range of sensor capabilities weconsider, symmetric-key ciphers and hash functions are be-tween two to four orders of magnitude faster than digitalsignatures [3]. Hence, symmetric-key ciphers, low-energy,authenticated encryption modes [6, 8, 11], and hash func-tions become the tools of choice for protecting DSN commu-nications.Key Management Constraints. Traditional Internet stylekey exchange and key distribution protocols based on infras-tructures using trusted third parties are impractical for largescale DSNs because of the unknown network topology priorto deployment, communication range limitations, intermit-tent sensor-node operation, and network dynamics. To date,the only practical options for the distribution of keys tosensor nodes of large-scale DSNs whose physical topology isunknown prior to deployment would have to rely on key pre-distribution. Keys would have to be installed in sensor nodesto accommodate secure connectivity between