Elsevier

Computer Networks

Volume 55, Issue 5, 1 April 2011, Pages 1168-1180
Computer Networks

OREN: Optimal revocations in ephemeral networks

https://doi.org/10.1016/j.comnet.2010.11.010Get rights and content

Abstract

Public-key certificates allow a multitude of entities to securely exchange and verify the authenticity of data. However, the ability to effectively revoke compromised or untrustworthy certificates is of great importance when coping with misbehavior. In this paper, we design a fully distributed local certificate revocation scheme for ephemeral networks – a class of extremely volatile wireless networks with short-duration and short-range communications – based on a game-theoretic approach. First, by providing incentives, we can guarantee the successful revocation of the malicious nodes even if they collude. Second, thanks to the records of past behavior, we dynamically adapt the parameters to nodes’ reputations and establish the optimal Nash equilibrium (NE) on-the-fly, minimizing the social cost of the revocation. Third, based on the analytical results, we define OREN, a unique optimal NE selection protocol, and evaluate its performance through simulations. We show that our scheme is effective in quickly and efficiently removing malicious devices from the network.

Introduction

The emerging availability of wireless devices able to communicate directly with other peers is opening new ways for people to interact and exchange information [1], [2], [3]. The absence of a centrally-managed infrastructure, however, makes it harder to cope with misbehavior. In the literature, a considerable effort is being devoted to the analysis of security mechanisms performed by self-interested agents [4], [5]. In particular, the revocation of compromised public-key certificates is a very important primitive for environments where authentication is required.

In ephemeral networks, the short-lived and heterogeneous contacts among nodes (potentially unbeknownst to each other) make it imperative to address the revocation issue in a distributed and efficient way. One step in this direction has been taken by Raya et al. [6] through their game-theoretic local certificate revocation protocol RevoGame. Their model, however, has some limitations. First, it is often difficult to obtain correct estimates of crucial parameters very frequently and thus the outcome of the revocation could be unpredictable. Second, the dynamic kind of games used by their model assumes that each node can observe the actions of the others before taking its own decision, which is not always be feasible in ephemeral environments. For example, the duration of the related public-key operations, such as signature verification and generation, might take an excessive amount of time.

In this paper, we design a substantially improved and extended local certificate revocation framework for ephemeral networks. With respect to [6], our contribution is fourfold. First of all, we consider revocations in which nodes take actions simultaneously, i.e. they do not know others’ decisions before taking their own, as it might take too much time in practice and the nodes might have already lost contact. Second, we provide incentives that stimulate participation and guarantee a successful revocation of malicious nodes even when they collude or when the parameter estimations are difficult. Third, by considering the past behavior of devices as their reputation, we are able to allow for personalized and dynamic costs that depend on the behavior of each node in past games. Fourth, as each device could potentially have a different reputation, we design a fully distributed on-the-fly NE selection protocol, OREN, that establishes, if more than one NE exist, the best course of action for each player with the least social cost. Simulation results finally show that our analytical framework is effective in removing the misbehaving nodes’ certificates through the socially optimal NE of the revocation game.

The paper is organized as follows. After discussing the related work in Section 2, we present our system model in Section 3. We describe the revocation process in Section 4 and we perform the game theoretic analysis in Section 5. We devote Section 6 to the design of the socially optimal Nash equilibrium selection protocol OREN and we evaluate its performance through simulations in Section 7. We conclude the paper in Section 8.

Section snippets

Related work

Li et al. [7] propose a key management model based on a web of trust, where nodes sign each other’s certificates without any trusted third party. Revocation is performed by a single node that broadcasts the revocation request to all two-hop neighbors, who then add the accused node’s certificate to their blacklists. However, the communication overhead related to blacklist exchange and the trust assumptions derived from indirect chains of certificates could lead to security compromises when

System model

We consider an ephemeral network with short-duration (1–10 s), short-range (10–100 m) contacts that can take place both in licensed and unlicensed frequency bands. We only require the wireless devices to be able to establish direct communication among themselves.

Furthermore, we assume that all devices are powerful enough to run public-key cryptographic algorithms. This assumption is based on the evidence that most of today’s smartphones (and future cell phones [13]) have integrated public-key

Revocation process

The revocation procedure begins when a node detects the presence of a misbehaving peer (node m) and decides to accuse it. Note that for each accused node m, there is one revocation process and each node can participate in at most one at any given time, even though there could be many processes running in parallel. For simplicity and without loss of generality, in this paper we consider one revocation only. Moreover, we focus on the reaction [17] of a set of nodes once a malicious node has

Game-theoretic analysis

In this section, we present our game-theoretic framework and the analytical results. First, we consider revocation games where payoffs depend on the current strategies and game outcome only. Afterwards, we extend the framework to include nodes’ past behavior in the computations of payoffs, strategies and outcomes by considering the counter as the indicator of a node’s reputation.

We define a non-cooperative static revocation game as Gn={P,S,U}, where P={Pi}i=1n is the set of the n wireless

Social welfare and protocols

In this section, we describe the method that we use to select a single NE, in case more are present, with the related protocols. The underlying principle is that of the price of anarchy [22], which takes into account the utility of all players or, in other words, the social welfare function ω. There are different kinds of these functions and two among them are the utilitarian and egalitarian functions:Utilitarian:ω(s)=i=0nui(s),Egalitarian:ω(s)=miniui(s).By maximizing ω(s) over all possible

Performance evaluation

We implemented and simulated the optimal NE selection protocol OREN in Matlab, assuming a single attacker, although there could be as many attackers as revocation games running in parallel. We run 10 iterations for each number of players between 2 and 15, as we assume a highly mobile environment and short-range communications. The confidence interval is 95%. As in Section 5.4 for the system-wise efficiency of the self-sacrifice cost cs,i, we assume here that b  v < e(M/N) in order to avoid any

Conclusion

In this paper, we have designed a game-theoretic framework for local certificate revocation in ephemeral networks. First, the scheme makes use of incentives in order to guarantee the revocation of the malicious node even in presence of inaccurate estimation of the attack-induced cost. Second, the scheme makes also use of reputations, based on each node’s past behavior, and we have optimized the game model such that the adapted cost parameters guarantee a successful revocation of the malicious

Acknowledgments

We would like to express our sincere gratitude to Tansu Alpcan, Georgios Theodorakopoulos, Mathias Humbert, Marcin Poturalski and to the anonymous reviewers who contributed to improve the quality of this work.

Igor Bilogrevic is a research assistant and Ph.D student at the Laboratory for computer Communications and Applications (LCA1), at the Ecole Polytechnique Fédérate de Lausanne (EPFL), under the supervision of Prof. Jean-Pierre Hubaux. He earned his M.Sc. and B.Sc. in communication systems from EPFL in 2009 and 2007 respectively, with specialization in Wireless Communications. Igor’s main areas of interest include wireless networks and, in particular, security and privacy issues thereof. //people.epfl.ch/igor.bilogrevic

References (23)

  • S. Chinni et al.

    Trust model for certificate revocation in ad hoc networks

    Ad Hoc Networks

    (2008)
  • G. Arboit et al.

    A localized certificate revocation scheme for mobile ad hoc networks

    Ad Hoc Networks

    (2008)
  • AKAAKI. <http://www.aka-aki.com/> (accessed...
  • BlueStar∗. <http://www.csg.ethz.ch/research/projects/Blue_star> (accessed...
  • Serendipity. <http://reality.media.mit.edu/serendipity.php> (accessed...
  • J. Katz

    Bridging game theory and cryptography: recent results and future directions

  • L. Buttyan et al.

    Security and Cooperation in Wireless Networks: Thwarting Malicious and Selfish Behavior in the Age of Ubiquitous Computing

    (2008)
  • M. Raya et al.

    Revocation games in ephemeral networks

  • R. Li, J. Li, H. Kameda, P. Liu, Localized public-key management for mobile ad hoc networks, in: GLOBECOM ’04: Global...
  • H. Luo, P. Zerfos, J. Kong, S. Lu, L. Zhang, Self-securing ad hoc wireless networks, in: ISCC 2002: Proceedings of the...
  • P. Michiardi et al.

    Core: a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks

  • Cited by (8)

    View all citing articles on Scopus

    Igor Bilogrevic is a research assistant and Ph.D student at the Laboratory for computer Communications and Applications (LCA1), at the Ecole Polytechnique Fédérate de Lausanne (EPFL), under the supervision of Prof. Jean-Pierre Hubaux. He earned his M.Sc. and B.Sc. in communication systems from EPFL in 2009 and 2007 respectively, with specialization in Wireless Communications. Igor’s main areas of interest include wireless networks and, in particular, security and privacy issues thereof. http://people.epfl.ch/igor.bilogrevic.

    Mohammad Hossein Manshaei earned his B.S. degree in electrical engineering and his M.S. degree in communication engineering from the Isfahan University of Technology (IUT), Iran, in 1997 and 2000, respectively. He earned another M.S. degree in computer science and his Ph.D. in computer science and distributed systems from the University of Nice Sophia-Antipolis, France, in 2002 and 2005, respectively. He completed his thesis work at INRIA Sophia- Antipolis. He currently works as a senior researcher and lecturer at the Laboratory for Computer Communications and Applications (LCA) in EPFL. His research interests include wireless networking, security and privacy, social networks, cognitive radios, and game theory. http://people.epfl.ch/manshaei.

    Maxim Raya received his B.Eng. degree in Computer and Communications Engineering in 2002 from the American University of Beirut, Lebanon. He earned his Ph.D degree from EPFL in 2009. His research interests are in the area of security in wireless networks, and especially vehicular networks. He served in the program committee of VANET 2007.

    Jean-Pierre Hubaux joined the faculty of EPFL in 1990. His research activity is focused on wireless networks, with a special interest in security and cooperation issues. In 1991, he designed the first curriculum in Communication Systems at EPFL. He was promoted to full professor in 1996. In 1999, he defined some of the main ideas of the National Competence Center in Research named “Mobile Information and Communication Systems” (NCCR/MICS). In this framework, he has notably defined, in close collaboration with his students, novel schemes for the security and cooperation in wireless networks; in particular, he has devised new techniques for key management, secure positioning, and incentives for cooperation in such networks. In 2003, he identified the security of vehicular networks as one of the main research challenges for real-world mobile ad hoc networks. In 2008, he completed a graduate textbook entitled “Security and Cooperation in Wireless Networks”, with Levente Buttyan. Most of his current research activities revolve around privacy issues in mobile networks and are partially funded by Nokia. He is co-founder and chairman of the steering committee of WiSec (the ACM Conference for Wireless Network Security). He has served on the program committees of numerous conferences and workshops, including SIGCOMM, INFOCOM, MobiCom, MobiHoc, SenSys, WiSe, and VANET. Since 2007, he has been one of the seven commissioners of the Federal Communications Commission (ComCom), the “Swiss FCC”. He held visiting positions at the IBM T.J. Watson Research Center and at UC Berkeley. He has been on the advisory board of Deutsche Telekom Laboratories (T-Labs) since their creation in 2004. He is a Fellow of both IEEE and ACM. He was born in Belgium, but spent most of his childhood and youth in Northern Italy. After completing his studies in electrical engineering at Politecnico di Milano, he worked 10 years in France with Alcatel, primarily in the area of switching systems architecture and software.

    View full text