A pairwise key pre-distribution scheme for wireles

APairwiseKeyPre-DistributionSchemeforWirelessSensorNetworksWENLIANGDUandJINGDENGSyracuseUniversityYUNGHSIANGS.HANNationalChiNanUniversity,TaiwanPRAMODK.VARSHNEYSyracuseUniversityandJONATHANKATZandARAMKHALILIUniversityofMaryland,CollegeParkToachievesecurityinwirelesssensornetworks,itisimportanttobeabletoencryptandauthenticatemessagessentbetweensensornodes.Beforedoingso,keysforperformingencryptionandauthenticationmustbeagreeduponbythecommunicatingparties.Duetoresourceconstraints,however,achievingkeyagreementinwirelesssensornetworksisnon-trivial.Manykeyagreementschemesusedingeneralnetworks,suchasDiffie-Hellmanandotherpublic-keybasedschemes,arenotsuitableforwirelesssensornetworksduetothelimitedcomputationalabilitiesofthesensornodes.Pre-distributionofsecretkeysforallpairsofnodesisnotviableduetothelargeamountofmemorythisrequireswhenthenetworksizeislarge.Tosolvethekeypre-distributionproblem,twoelegantkeypre-distributionapproacheshavebeenproposedrecently.Inthispaper,weprovideaframeworkinwhichtostudythesecurityofkeypre-distributionschemes,proposeanewkeypre-distributionschemewhichsubstantiallyimprovestheresilienceofthenetworkcomparedtopreviousschemes,andgiveanin-depthanalysisofourschemeintermsofnetworkresilienceandassociatedoverhead.Ourschemeexhibitsanicethresholdproperty:whenthenumberofcompromisednodesislessthanthethreshold,theprobabilitythatcommunicationsbetweenanyadditionalnodesarecompromisedisclosetozero.Thisdesirablepropertylowerstheinitialpayoffofsmaller-scalenetworkbreachestoanadversary,andmakesitnecessaryfortheadversarytoattackalargefractionofthenetworkbeforeitcanachieveanysignificantgain.CategoriesandSubjectDescriptors:C.2.0[Computer-CommunicationNetworks]:General—Securityandpro-tection;C.2.1[Computer-CommunicationNetworks]:NetworkArchitectureandDesign—Wirelesscommuni-cationGeneralTerms:Security,Design,AlgorithmsAdditionalKeyWordsandPhrases:Wirelesssensornetworks,keypre-distribution,securityThisworkwassupportedinpartbygrantsISS-0219560andCCR-0310751fromtheNationalScienceFounda-tion,bytheSUPRIAprogramoftheCASECenteratSyracuseUniversity,andbytheNationalScienceCouncilofTaiwan,R.O.C.,undergrantsNSC90-2213-E-260-007andNSC91-2213-E-260-021.Thispaperisanextendedversionof[Duetal.2003].Permissiontomakedigital/hardcopyofallorpartofthismaterialwithoutfeeforpersonalorclassroomuseprovidedthatthecopiesarenotmadeordistributedforprofitorcommercialadvantage,theACMcopyright/servernotice,thetitleofthepublication,anditsdateappear,andnoticeisgiventhatcopyingisbypermissionoftheACM,Inc.Tocopyotherwise,torepublish,topostonservers,ortoredistributetolistsrequirespriorspecificpermissionand/orafee.c°20YYACM0000-0000/20YY/0000-0001$5.00ACMJournalName,Vol.V,No.N,Month20YY,Pages1–0??.2¢1.INTRODUCTIONRecentadvancesinelectronicandcomputertechnologieshavepavedthewayforthepro-liferationofwirelesssensornetworks(WSNs).Sensornetworksusuallyconsistofalargenumberofultra-smallautonomousdevices.Eachdevice,calledasensornode,isbatterypoweredandequippedwithintegratedsensors,dataprocessingcapabilities,andshort-rangeradiocommunications.Intypicalapplicationscenarios,sensornodesarespreadran-domlyovertheterrainunderscrutinyandcollectsensordata.ExamplesofsensornetworkprojectsincludeSmartDust[Kahnetal.1999]andWINS.1Sensornetworksarebeingdeployedforawidevarietyofapplications[Akyildizetal.2002],includingmilitarysensingandtracking,environmentmonitoring,patientmonitor-ingandtracking,smartenvironments,etc.Whensensornetworksaredeployedinahostileenvironment,securitybecomesextremelyimportant,asthesenetworksarepronetodiffer-enttypesofmaliciousattacks.Forexample,anadversarycaneasilylistentothetraffic,impersonateoneofthenetworknodes,orintentionallyprovidemisleadinginformationtoothernodes.Toprovidesecurity,communicationshouldbeencryptedandauthenticated.Theopenproblemishowtobootstrapsecurecommunicationsbetweensensornodes,i.e.howtosetupsecretkeysbetweencommunicatingnodes.Thisproblemisknownasthekeyagreementproblem,whichhasbeenwidelystudiedingeneralnetworkenvironments.Therearethreetypesofgeneralkeyagreementschemes:trusted-serverschemes,public-keyschemes,andkeypre-distributionschemes.Trusted-serverschemesdependonatrustedserverforkeyagreementbetweennodes;anexampleisKerberos[NeumanandTso1994].Thistypeofschemeisnotsuitableforsensornet-worksbecauseinthelocationswhereWSNsaredeployed,onecannotgenerallyassumethatanytrustedinfrastructureisinplace.Public-keyschemesdependonasymmetriccryp-tographyandrequiresomesortofpublic-keyinfrastructuretobeinplace;anexampleofsuchschemesisanauthenticatedkeyagreementprotocolusingpublic-keycertificates.However,aspointedoutbyPerrig,etal.[Perrigetal.2001],thelimitedcomputationandenergyresourcesofsensornodesoftenmakeitundesirabletousepublic-keyalgorithmsinWSNs.Athirdwaytoestablishkeysisviapre-distribution,where(secret)keyinfor-mationisdistributedtoallsensornodespriortodeployment.SuchschemesseemmostappropriateforWSNs.Ifitisknownwhichnodeswillbeinthesameneighborhoodbeforedeployment,pair-wisekeyscanbeestablishedbetweenthesenodes(andonlythesenodes)apriori.How-ever,