ANODR: ANonymous On Demand Routingwith Untraceable Routes for Mobile Ad-hoc NetworksJiejun Kong, Xiaoyan HongComputer Science DepartmentUniversity of California, Los Angeles, CA 90095{jkong,hxy}@cs.ucla.eduABSTRACTIn hostile environments, the enemy can launch traffic analysis again-st interceptable routing information embedded in routing messagesand data packets. Allowing adversaries to trace network routes andinfer the motion pattern of nodes at the end of those routes maypose a serious threat to covert operations. We propose ANODR,an anonymous on-demand routing protocol for mobile ad hoc net-works deployed in hostile environments. We address two closely-related problems: For route anonymity, ANODR prevents strongadversaries from tracing a packet flow back to its source or desti-nation; for location privacy, ANODR ensures that adversaries can-not discover the real identities of local transmitters. The designof ANODR is based on “broadcast with trapdoor information”, anovel network security concept which includes features of two ex-isting network and security mechanisms, namely “broadcast” and“trapdoor information”. We use simulations and implementation tovalidate the effectiveness of our design.Categories and Subject DescriptorsC.2.2 [Computer-Commmunication Networks]: Network Proto-cols—Routing protocolsGeneral TermsSecurity, Design, Measurement, Experimentation, PerformanceKeywordsAnonymity, Untraceability, Pseudonymity, Broadcast, Trapdoor, On-demand Routing, Mobile Ad-hoc Network1. INTRODUCTIONIn hostile environments, allowing adversaries to trace networkroutes and nodes at the end of those routes may pose serious threatsto the success of covert missions. Consider for example a battlefieldscenario with ad hoc, multi-hop wireless communications support.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.MobiHoc’03, June 1–3, 2003, Annapolis, Maryland, USACopyright 2003 ACM 1-58113-684-6/03/0006 ...$5.00.Suppose a covert mission is launched, which includes swarms ofreconnaissance, surveillance, and attack task forces. The ad hocnetwork must provide routes between command post and swarms(for delivery of reliable commands/controls from commander toswarms and for situation data/video reporting from swarms to thecommander) as well as routes between swarms (data fusion, fail-ure recovery, threat evasion etc). Providing anonymity and locationprivacy supports for the task forces is critical, else the entire mis-sion may be compromised. This poses challenging constraints onrouting and data forwarding. In fact, the adversary could deployreconnaissance and surveillance forces in the battlefield and main-tains communications among them. They could form their ownnetwork to infer the location, movement, number of participants,and even the goals of our covert missions.On-demand routing schemes are more “covert” in nature in thatthey do not advertise in advance—they just set up routes as needed.Nevertheless, the enemy may gain a lot of information about themission by analyzing on-demand routing information and observ-ing packet flows once the connection is established. Since a neces-sary byproduct of any mission, whether covert or not, is communi-cations across swarms and to/from command post, these flows andthe routes temporarily set up at intermediate nodes must be pro-tected from inference and intrusion.The purpose of this paper is to develop “untraceable” routes orpacket flows in an on-demand routing environment. This goal isvery different from other related routing security problems such asresistance to route disruption or prevention of “denial-of-service”attacks. In fact, in our case the enemy will avoid such aggressiveschemes, in the attempt to be as “invisible” as possible, until ittraces, locates, and then physically destroys the assets. We addressthe untraceable routing problem by a route pseudonymity approach.In our design, the anonymous route discovery process establishesan on-demand route between a source and its destination. Eachhop en route is associated with a random route pseudonym. Sincedata forwarding in the network is based on route pseudonyms withnegligible overhead, local senders and receivers need not revealtheir identities in wireless transmission. In other words, the routepseudonymity approach allows us to “unlink” (i.e., thwart infer-ence between) network member’s location and identity. For eachroute, we also ensure unlinkability among its route pseudonyms.As a result, in each locality eavesdroppers or any bystander otherthan the forwarding node can only detect the transmission of wire-less packets stamped with random route pseudonyms. It is hard forthem to trace how many nodes in the locality, who is the transmit-ter or receiver, where a packet flow comes from and where it goesto (i.e., what are the previous hops and the next hops en route), letalone the source sender and the destination receiver of the flow. We291further tackle the problem of node intrusion within the same frame-work. In our design a strong adversary with node intrusion capabil-ity must carry out a complete “vertex cover” process to trace eachon-demand ad hoc route.The design of route pseudonymity is based on a network secu-rity concept called “broadcast with trapdoor information”, whichis newly proposed in this work. Multicast/broadcast is a network-based mechanism that has been explored in previous research [31,32] to provide recipient anonymity support. Trapdoor informationis a security concept that has been widely used in encryption andauthentication schemes. ANODR is realized upon a hybrid form ofthese two concepts.The contribution of this work is to present a untraceable andintrusion tolerant routing protocol for mobile ad hoc networks.• Untraceability: ANODR dissociates ad hoc routing from thedesign of network member’s identity/pseudonym. The en-emy can neither link network members’ identities with theirlocations, nor follow a packet flow to its source and destina-tion. Though the adversaries may detect the existence of lo-cal wireless transmissions, it is hard for them to infer a
View Full Document
Unlocking...