BISS: Building Secure Routing out of anIncomplete Set of Security AssociationsSrdjanˇCapkun and Jean-Pierre HubauxLaboratory for Computer Communications and Applications (LCA)School of Information and Communication Sciences (I&C)Swiss Federal Institute of Technology Lausanne (EPFL)CH-1015 Lausanne, [email protected], [email protected] investigate secure routing in ad hoc networks in whichsecurity associations exist only between a subset of all pairsof nodes. We focus on source routing protocols. We showthat to establish secure routes, it is in general not necessarythat security associations exist between all pairs of nodes;a fraction of security associations is sufficient. We analyzethe performance of existing proposals for secure routing insuch conditions. We also propose a new protocol, designedspecifically for ad hoc networks with an incomplete set ofsecurity associations between the nodes. We call this pro-tocol BISS: a protocol for Building Secure Routing out ofan Incomplete Set of Security Associations. We present adetailed analysis of this protocol, based on simulations, andshow that it can be as secure as the existing proposals thatrely on a complete set of security associations.1Categories and Subject DescriptorsC.0 [Computer-Communication Networks]: [Securityand protection]; C.2.2 [Network Protocols]: [Routing Pro-tocols]General TermsSecurityKeywordsSecurity, Ad Hoc Networks, Mobility, Security associations,Routing1The work presented in this paper was supported(in part) by the National Competence Center in Re-search on Mobile Information and Communication Sys-tems (NCCR-MICS), a center supported by the Swiss Na-tional Science Foundation under grant number 5005-67322(http://www.terminodes.org).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.WiSE’03, September 19, 2003, San Diego, California, USA.Copyright 2003 ACM 1-58113-769-9/03/0009 ...$5.00.1. INTRODUCTIONBy definition, a mobile ad hoc network [31, 22, 23] doesnot rely on any fixed infrastructure; instead, all network-ing functions (e.g., routing, mobility management, etc.) areperformed by the nodes themselves in a self-organizing man-ner. For this reason, designing routing protocols for mobilead hoc networks is challenging and securing these protocolseven more so.So far, the problem of routing in ad hoc networks hasbeen mainly studied in a non-adversarial setting, and onlyrecentlyhasthefocusofresearchshiftedtothedesignofsecure routing protocols; researchers have already deviseda number of proposals to secure both reactive (on-demand)and proactive routing protocols [18, 20, 19, 17, 29, 32, 16].The authors of the most robust (but also of the most de-manding) solutions generally assume that, prior to networkoperation, security associations exist between all pairs ofnodes in the network. This means that either symmetrickeys are shared between all nodes, or that the nodes knoweach others’ authentic public or Tesla [30] keys; this assump-tion is important for avoiding the routing-security depen-dency loop. We elaborate this in more detail in Section 2.2.Several solutions have been proposed for the initial keysetup. One solution consists in pre-loading pairwise keys inall nodes to create all the security associations at the ini-tialization. However, this approach makes the insertion ofnew nodes in the network very difficult. Hu, Perrig andJohnson [18] propose a solution to this problem. Their ap-proach makes use of an on-line key distribution center andis thus very effective, although it requires a costly initializa-tion phase and relies on the availability of (and connectivityto) the key distribution center.In [11], we propose a system for the self-organized estab-lishment of security associations based on mobility. We showthat mobility can be used to set up security associationsbetween nodes, including in order to secure routing. Thismobility-based approach enables a more flexible setup of thesecurity associations and requires only an off-line author-ity; the drawback, with respect to other approaches, is thatthe establishment of the security associations requires sometime. As we will see, this problem is dramatically alleviatedby the findings in this paper.In many scenarios, it is unrealistic to assume that securityassociations have been established between all pairs of nodesprior to network operation. In practice, node mobility, net-work partitioning, and sporadic connectivity to other nodes21or to key distribution centers will prevent nodes from estab-lishing or timely renewing security associations with othernodes.In this paper, we show that even if only a fraction of thesecurity associations are established between nodes, rout-ing can still be secured. We focus on on-demand routingprotocols, in which a node attempts to discover a route tosome destination only when it has a packet to send to thatdestination; more specifically, we assume a source routingprotocol and consider DSR as an example. First, we showhow Ariadne [18] can cope with an incomplete set of securityassociations (although it was not designed with this objec-tive in mind). Second, we propose a new protocol that wecall BISS: (Building Secure Routing out of an IncompleteSet of Security Associations). We present a detailed analy-sis of these protocols, based on simulations.The work presented in this paper is a part of the Termin-odes Project [4, 21].The organization of the paper is the following. In Sec-tion 2, we survey the related work. In Section 3, we providethe model of our system. In Section 4, we describe our so-lution and we analyze it in Section 5. Finally, we concludethe paper in Section 6.2. STATE OF THE ART2.1 Setting up security associationsSeveral solutions have been proposed specifically to set upsecurity associations for secure routing in ad hoc networks.In [35], Zhou and Haas propose a distributed public-keymanagement service for ad hoc networks. The service, asa whole, has a public/private key pair K/k,thatisusedto verify/sign public-key certificates of the network nodes.The private key k is divided into n shares using a (n, t
View Full Document
Unlocking...