| 1 Introduction | | | | current public keys of other nodes or to establish |
| Ad hoc networks are a new paradigm of wireless | | | | secure communication with others. If the CA is |
| communication for mobile hosts (which we call | | | | compromised and leaks its private key to an |
| nodes). In an ad hoc network, there is no fixed | | | | adversary, the adversary can then sign any |
| infrastructure such as base stations or mobile | | | | erroneous certificate using this private key to |
| switching centers. Mobile nodes that are within | | | | impersonate any node or to revoke any |
| each other’s radio range communicate directly | | | | certificate. |
| via wireless links, while those that are far apart | | | | A standard approach to improve availability of a |
| rely on other nodes to relay messages as | | | | service is replication. But a naive replication of the |
| routers. Node mobility in an ad hoc network | | | | CA makes the service more vulnerable: |
| causes frequent changes of the network | | | | compromise of any single replica, which possesses |
| topology. Military tactical operations are still the | | | | the service private key, could lead to collapse of |
| main | | | | the entire system. To solve this problem, we |
| Application of ad hoc networks today. For | | | | distribute the trust to a set of nodes by letting |
| example, military units (e.g., soldiers, tanks, or | | | | these nodes share the key management |
| planes), equipped with wireless communication | | | | responsibility. |
| devices, could form an ad hoc network when | | | | 3. Push! Photo: Informal Photo Sharing in Ad-Hoc |
| they roam in a battlefield. Ad hoc networks can | | | | Networks |
| also be used for emergency, law enforcement, | | | | As mobile camera phones become ubiquitous the |
| and rescue missions. Since an ad hoc network can | | | | practice of photography changes. Camera phone |
| be deployed rapidly with relatively low cost, it | | | | pictures are usually taken with sharing in mind. |
| becomes an attractive option for commercial | | | | Meanwhile, publicly sharing photographs online has |
| uses such as sensor networks or virtual | | | | become increasingly popular with websites such as |
| classrooms. | | | | Flickr. Push! Photo is a mobile photo sharing |
| 1.1 Security goals | | | | application where photos can be made public and |
| Security is an important issue for ad hoc | | | | immediately accessed by anyone nearby. The |
| networks, especially for those security-sensitive | | | | application also automatically searches for photos |
| applications. To secure an ad hoc network, we | | | | on nearby devices to find interesting and relevant |
| consider the following attributes: availability, | | | | photos. Push! Photo shows how it is possible to |
| confidentiality, integrity, authentication, and | | | | share digital photos just as easy as paper photos. |
| non-repudiation. | | | | Shoot! |
| Availability ensures the survivability of network | | | | Publicize! |
| services despite denial of service attacks. A denial | | | | Discover! |
| of service attack could be launched at any layer | | | | Enjoy! |
| of an ad hoc network. On the physical and media | | | | 3.1 THE PUSH! PHOTO PROTOTYPE |
| access control layers, an adversary could employ | | | | The current prototype of Push! Photo allows |
| jamming to interfere with communication on | | | | photos to be made public, and users can browse |
| physical channels. On the network layer, an | | | | their own photo collection as well as those of |
| adversary could disrupt the routing protocol and | | | | others nearby. When devices are in proximity of |
| disconnect the network. On the higher layers, an | | | | one another, they will automatically start to |
| adversary could bring down high-level services. | | | | search each other’s public photo collections |
| One such target is the key management service, | | | | for |
| an essential service for any security framework. | | | | Photographs relevant to one self. These photos |
| Confidentiality ensures that certain information is | | | | are shown as a multi-picture slideshow, which is |
| never disclosed to unauthorized entities. Network | | | | extended as new photos are found. To browse |
| transmission of sensitive information, such as | | | | photos from an event shown in a particular photo |
| strategic or tactical military information, requires | | | | the user can click on that picture in the slideshow. |
| confidentiality. Leakage of such information to | | | | The application will then download all photos from |
| enemies could have devastating consequences. | | | | nearby devices taken at that event. In this way, |
| Routing information must also remain confidential | | | | if a user spots an interesting picture in the |
| in certain cases, because the information might be | | | | slideshow, she can easily find more photos from |
| valuable for enemies to identify and to locate their | | | | the same occasion. To decide |
| targets in a battlefield. | | | | Whether two photos are from the same event, |
| Integrity guarantees that a message being | | | | information about whom else was around and the |
| transferred is never corrupted. A message could | | | | time of shooting is used. The application |
| be corrupted because of benign failures, such as | | | | implements a discovery service to find other |
| radio propagation impairment, or because of | | | | devices when they are within Wi Fi-range. Thus |
| malicious attacks on the network. | | | | the application is always aware of who else (using |
| Authentication enables a node to ensure the | | | | Push!Photo) is around at a particular time. As a |
| identity of the peer node it is communicating with. | | | | photograph is taken, the resulting picture is tagged |
| Without authentication, an adversary could | | | | with this information together with the time and |
| masquerade a node, thus gaining unauthorized | | | | the identity of the photographer. The current |
| access to resource and sensitive information and | | | | prototype is an application running on |
| interfering with the operation of other nodes. | | | | Pocket PCs with WiFi-cards and external |
| Finally, non-repudiation ensures that the origin of a | | | | SD-cameras |
| message cannot deny having sent the message. | | | | 3.2 RELATED WORK |
| No repudiation is useful for detection and isolation | | | | In previous work with Push! Music [2] music files |
| of compromised nodes. When a node A receives | | | | were replaced with so called media agents which |
| an erroneous message from a node B, | | | | were enabled to autonomously copy themselves |
| non-repudiation allows A to accuse B using this | | | | between devices over a wireless ad hoc network. |
| message and to convince other nodes that B is | | | | The media agents try to find theirway to |
| compromised. | | | | potential listeners as users meet, and as a song is |
| There are other security goals (e.g., authorization) | | | | copied it automatically enters the play list. In this |
| that are of concern to certain applications, but we | | | | way the users discover new music while passively |
| will not pursue these issues in this paper. | | | | listening. Other projects have looked at mobile |
| 1.2 Challenges | | | | photo sharing. Davis et al. in MM2 uses the notion |
| The salient features of ad hoc networks posses | | | | of co-presence to simplify the decision of with |
| both challenges and opportunities in achieving | | | | whom to share [1]. Photos are then uploaded |
| these security goals. | | | | automatically to a central web server where the |
| First, use of wireless links renders an ad hoc | | | | sharing recipients can access the photos. Kohno |
| network susceptible to link attacks ranging from | | | | and Rekimoto instead use GPS information and |
| passive eavesdropping to active impersonation, | | | | time stamps to decide if pictures are from the |
| message replay, and message distortion. | | | | same event or not [4]. This is used to let users |
| Eavesdropping might give an adversary access to | | | | easily browse each others photos when standing |
| secret information, violating confidentiality. Active | | | | in a group to serve as a topic of discussion. The |
| attacks might allow the adversary to delete | | | | system also let users drag and drop pictures |
| messages, to inject erroneous messages, to | | | | between your own and other’s devices. As a |
| modify messages, and to impersonate a node, | | | | contrast, Push! Photo aims to look into how mobile |
| thus violating availability, integrity, authentication, | | | | sharing can be simplified by allowing seamless |
| and non-repudiation. | | | | sharing, and using context and tagging to |
| Secondly, nodes, roaming in a hostile environment | | | | automatically find interesting and relevant |
| (e.g., a battlefield) with relatively poor physical | | | | photographs |
| protection, have non-negligible probability of being | | | | 4 Conclusions |
| compromised. Therefore, we should not only | | | | In this paper, we have analyzed the security |
| consider malicious attacks from outside a | | | | threats an ad hoc network faces and presented |
| network, but also take into account the attacks | | | | the security objectives that need to be achieved. |
| launched from within the network by | | | | On one hand, the security-sensitive applications of |
| compromised nodes. Therefore, to achieve high | | | | ad hoc networks require high degree of security; |
| survivability, ad hoc networks should have a 2 | | | | on the other hand, ad hoc networks are |
| distributed architecture with no central entities. | | | | inherently vulnerable to security attacks. |
| Introducing any central entity into our security | | | | Therefore, security mechanisms are indispensable |
| solution could lead to significant vulnerability; that | | | | for ad hoc networks. The idiosyncrasy of ad hoc |
| is, if this centralized entity is compromised, then | | | | networks poses both challenges and opportunities |
| the entire network is subverted. | | | | for these mechanisms. This paper focuses on |
| Thirdly, an ad hoc network is dynamic because of | | | | how to secure routing and how to establish a |
| frequent changes in both its topology and its | | | | secure key management service in an ad hoc |
| membership (i.e., nodes frequently join and leave | | | | networking environment. These two issues are |
| the network). Trust relationship among nodes also | | | | essential to achieving our security goals. Besides |
| changes, for example, when certain nodes are | | | | the standard security mechanisms, we take |
| detected as being compromised. Unlike other | | | | advantage of the redundancies in ad hoc network |
| wireless mobile networks, such as mobile IP [21, | | | | topology and use diversity coding on multiple |
| 48, 34], nodes in an ad hoc network may | | | | routes to tolerate both benign and Byzantine |
| dynamically become affiliated with administrative | | | | failures. To build a highly available and highly secure |
| domains. Any security solution with a static | | | | key management service, we propose to use |
| configuration would not suffice. It is desirable for | | | | threshold cryptography to distribute trust among |
| our security mechanisms to adapt on-the-fly to | | | | a set of servers. Furthermore, our key |
| these changes. | | | | management service employs share refreshing to |
| Finally, an ad hoc network may consist of | | | | achieve proactive security and to adapt to |
| hundreds or even thousands of nodes. Security | | | | changes in the network in a scalable way. Finally, |
| mechanisms should be scalable to handle such a | | | | by relaxing the consistency requirement on the |
| large network. | | | | servers, our service does not rely on synchrony |
| 1.3 Routing Protocol and Threats | | | | assumptions. Such assumptions could lead to |
| Routing protocols for ad hoc networks are still | | | | vulnerability. A prototype of the key management |
| under active research. There is no single standard | | | | service has been implemented, which shows its |
| routing protocol. Therefore, we aim to capture | | | | feasibility. The paper represents the first step of |
| the common security threats and to provide | | | | our research to analyze the security threats, to |
| guidelines to secure routing protocols. In most | | | | understand the security requirements for ad hoc |
| routing protocols, routers exchange information on | | | | networks, and to identify existing techniques, as |
| the topology of the network in order to establish | | | | well as to propose new mechanisms to secure ad |
| routes between nodes. Such information could | | | | hoc networks. More work needs to be done to |
| become a target for malicious adversaries who | | | | deploy these security mechanisms inan ad hoc |
| intend to bring the network down. There are two | | | | network and to investigate the impact of these |
| sources of threats to routing protocols. The first | | | | security mechanisms on the network |
| comes from external attackers. By injecting | | | | performance. |
| erroneous routing information, replaying old routing | | | | 5 Acknowledgments |
| information, or distorting routing information, an | | | | I would like to thank my friends for their |
| attacker could successfully partition a network or | | | | invaluable contributions to this work. I am also |
| introduce excessive traffic load into the network | | | | grateful to my family and the anonymous |
| by causing retransmission and inefficient routing. | | | | reviewers for their comments and suggestions |
| The second and also the more severe kind of | | | | that helped to improve the quality of the paper. |
| threats come from compromised nodes, which | | | | I am grateful to Almighty for His blessings upon |
| might advertise incorrect routing information to | | | | me. |
| other nodes. Detection of such incorrect | | | | 6 References |
| information is difficult: merely requiring routing | | | | [1] E. Ayanoglu, C.-L. I, R. D. Gitlin, and J. E. Mazo. |
| information to be signed by each node would not | | | | Diversity coding for transparent self-healing |
| work, because compromised nodes are able to | | | | andfault-tolerant communication networks. IEEE |
| generate valid signatures using their private keys. | | | | Transactions on Communications, |
| To defend against the first kind of threats, nodes | | | | 41(11):1677–1686, |
| can protect routing information in the same way | | | | November 1993. |
| they protect data traffic, i.e., through the use of | | | | [2] M. Castro and B. Liskov. Practical Byzantine |
| cryptographic schemes such as digital signature. | | | | fault tolerance. In Proceedings of the 3rd USENIX |
| However, this defense is ineffective against | | | | Symposium on Operating System Design and |
| attacks from compromised servers. Worse yet, | | | | Implementation (OSDI’99), pages |
| as we have argued, we cannot neglect the | | | | 173–186, New Orleans, |
| possibility of nodes being compromised in an ad | | | | LA USA, February 22–25, 1999. USENIX |
| hoc network. Detection of compromised nodes | | | | Association, IEEE TCOS, and ACM SIGOPS. |
| through routing information is also difficult in an ad | | | | [3] Y. Desmedt. Threshold cryptography. European |
| hoc network because of its dynamically changing | | | | Transactions on Telecommunications, |
| topology: when a piece of routing information is | | | | 5(4):449–457, |
| found invalid, the information could be generated | | | | July–August 1994. |
| by a compromised node, or, it could have | | | | [4] Y. Desmedt and Y. Frankel. Threshold |
| become invalid as a result of topology changes. It | | | | cryptosystems. In G. Brassard, editor, Advances |
| is difficult to distinguish between the two cases. | | | | in Cryptology— |
| On the other hand, we can exploit certain | | | | Crypto’89, the 9th Annual International |
| properties of ad hoc networks to achieve secure | | | | Cryptology Conference, Santa Barbara, CA USA, |
| routing. Note that routing protocols for ad hoc | | | | August 20–24, |
| networks must handle outdated routing | | | | 1989, Proceedings, volume 435 of Lecture Notes |
| information to accommodate the dynamically | | | | in Computer Science, pages 307–315. Springer, |
| changing topology. False routing information | | | | 1990. |
| generated by compromised nodes could, to some | | | | [5] Y. Desmedt and S. Jajodia. Redistributing |
| extent, be considered outdated information. As | | | | secret shares to new access structures and its |
| long as there are sufficiently many correct nodes, | | | | applications. |
| the routing protocol should be able to find routes | | | | Technical Report ISSE TR-97-01, George Mason |
| that go around these compromised nodes. Such | | | | University, July 1997. |
| capability of the routing protocols usually relies on | | | | [6] A. Ephremides, J. E. Wieselthier, and D. J. Baker. |
| the inherent redundancies — multiple, possibly | | | | A design concept for reliable mobile radio |
| disjoint, routes between nodes — in ad hoc | | | | networkswith frequency hopping signaling. |
| networks. | | | | Proceedings of the IEEE, 75(1):56–73, January |
| 2. Key Management Service | | | | 1987. |
| We employ cryptographic schemes, such as digital | | | | [7] P. Feldman. A practical scheme for |
| signatures, to protect both routing information and | | | | non-interactive verifiable secret sharing. In |
| data traffic. Use of such schemes usually requires | | | | Proceedings of the 28th |
| a key management service. We adopt a public | | | | Annual Symposium on the Foundations of |
| key infrastructure because of its superiority in | | | | Computer Science, pages 427–437. IEEE, |
| distributing keys and in achieving integrity and | | | | October 12–14, |
| non-repudiation. Efficient secret key schemes are | | | | 1987. |
| used to secure further communication after | | | | [8] M. J. Fischer, N. A. Lynch, and M. S. Peterson. |
| nodes authenticate each other and establish a | | | | Impossibility of distributed consensus with one |
| shared secret session key. In a public key | | | | faultyprocessor. Journal of the ACM, |
| infrastructure, each node has a public/private key | | | | 32(2):374–382, April 1985. |
| pair. Public keys can be distributed to other nodes, | | | | [9] Y. Frankel, P. Gemmel, P. MacKenzie, and M. |
| while private keys should be kept confidential to | | | | Yung. Optimal resilience proactive public-key |
| individual nodes. There is a trusted entity called | | | | cryptosystems. |
| Certification Authority (CA) [11, 47, and 26] for | | | | In Proceedings of the 38th Symposium on |
| key management. The CA has a public/private | | | | Foundations of Computer Science, pages |
| key pair, with its public key known to every node, | | | | 384–393, |
| and signs certificates binding public keys to nodes. | | | | Miami Beach, FL USA, October 20–22, 1997. |
| The trusted CA has to stay on-line to reflect the | | | | IEEE. |
| current bindings, because the bindings could | | | | [10] Y. Frankel, P. Gemmell, P. MacKenzie, and M. |
| change over time: a public key should be revoked | | | | Yung. Proactive RSA. In B. S. Kaliski Jr., editor, |
| if the owner node is no longer trusted or is out of | | | | Advances in Cryptology—Crypto’97, the |
| the network; a node may refresh its key pair | | | | 17th Annual International Cryptology Conference, |
| periodically to reduce the chance of a successful | | | | Santa Barbara, |
| brute-force attack on its private key. It is | | | | CA USA, August 17–21, 1997, Proceedings, |
| problematic to establish a key management | | | | volume 1294 of Lecture Notes in Computer |
| service using a single CA in ad hoc networks. The | | | | Science,pages 440–454. Springer, 1997. |
| CA, responsible for the security of the entire | | | | [11] M. Gasser, A. Goldstein, C. Kaufman, and B. |
| network, is a vulnerable point of the network: if | | | | Lampson. The digital distributed systems security |
| the CA is unavailable, nodes cannot get the | | | | architecture. |