Introduction

As we have mentioned in Chapter 3, the way of the future for the proper operation of wireless networks consists in the deployment of appropriate rule enforcement mechanisms. These mechanisms should prevent or discourage malicious and selfish behavior. The design of the latter can tremendously benefit from game theoretic modeling.

Game theory is a discipline aimed at modeling situations in which decision-makers have to choose specific actions that have mutual, possibly conflicting, consequences. It has been used primarily in economics, in order to model competition between companies: for example, should a given company enter a new market, considering that its competitors could make similar (or different) moves? Game theory has also been applied to other areas, including politics and biology.

In wireless networks, the players can be either wireless stations striving to obtain as much possible bandwidth from the (shared) medium; or they can be wireless operators aimed at increasing their market share or their revenue. It is clear that in both cases, the actions of a given player can affect other players, sometimes in a negative way.

In this tutorial, we carefully explain how situations of this kind can be modeled by making use of game theory; for the sake of simplicity, we restrict ourselves in this appendix to the case in which the players are wireless stations (the reader interested in the interactions between operators should refer to Chapter 11).

Before discussing wireless networks, it is necessary to take a broad look at networking in general and to see why malicious and selfish behavior is such a relevant issue. For this purpose, we will consider the Internet.

The Internet is probably the most impressive achievement ever in networking: A simple set of brilliant engineering rules has led to the deployment of the most pervasive network that, in spite of its size (or rather, thanks to it), supports a growing number of services and applications. At the core of these rules stands of course the principle of universal connectivity.

Unfortunately, the Internet is plagued by several major problems, fuelled by this very principle. Viruses and spam have become a daily issue for most users around the world, many people fall prey to phishing attacks, and denial-of-service (DoS) attacks are routinely perpetrated against the servers of major corporations. An additional problem is that some network providers tend to establish walled gardens, by which they offer specific capabilities exclusively to their customers. Finally, some providers are tempted to interconnect their network in a way that is beneficial to themselves, but can be detrimental to the rest of the community. The situation is so critical that many prominent specialists, including some of the founding fathers of the Internet, call for a profound revamping of the network. Ambitious research projects, funded notably by the NSF and by the European Commission, have adopted a clean slate approach to respond to this challenge.

In the previous chapter, we have studied selfish behavior at the MAC layer. We will now focus on the network layer. For this purpose, we will consider self-organized wireless ad hoc networks. As we have explained in Chapter 2, in such networks the networking services are provided by the nodes themselves. As a fundamental example, the nodes must make a mutual contribution to packet forwarding in order to ensure an operable network. If the network is under the control of a single authority, as is the case for military networks and rescue operations, the nodes cooperate for the critical purpose of the network. However, if each node is its own authority, cooperation between the nodes cannot be taken for granted; on the contrary, it is reasonable to assume that each node has the goal of maximizing its own benefits by enjoying network services and at the same time minimizing its contribution. This selfish behavior can significantly damage network performance.

In this chapter, we focus on the most resource demanding operation of the network layer, namely packet forwarding. We address the case of self-organized wireless ad hoc networks, in order to derive some fundamental results. In particular, we will see that a network without incentives for cooperation is very likely to collapse. In Chapter 12, we will describe incentive techniques to solve this problem.

In any network, nodes need to be addressable, notably in order for the routing protocol to be able to convey traffic to them. As the node addresses usually have arcane formats, it is common practice to also make use of names, which are easier to manipulate by human beings; there are specific servers (such as the Domain Name System (DNS) in the case of the Internet) that convert names into addresses.

In static networks, it is common practice to relate the address of a node to its location in the network; in this way, routing can typically be organized in a hierarchical fashion. This principle becomes problematic, however, as soon as some nodes start moving.

Naming and addressing strategies have been heavily debated within the Internet community, essentially because of mobility and security, as we have seen in Sub section 2.2.5; it is very difficult to predict how naming and addressing will evolve in the coming years. But this topic is crucial for us, because naming and addressing mechanisms are vulnerable to a number of attacks.

In this chapter, we will first describe an ambitious naming and addressing architecture envisioned for the Internet. We will then focus on the network layer and describe specific attacks related to the mobility and to the intrinsic vulnerability of the nodes. Finally, we will describe the corresponding protection techniques.

In the previous two chapters, we have focused on the behavior of selfish nodes and shown how this can be modeled by means of game theory. In this chapter, we will consider the co-existence of several operators in shared spectrum. We will first discuss multi-domain sensor networks and then address the more involved case of cellular operators.

It is important to stress, as we already did at the beginning of Part III, that the cases presented hereafter must be understood as examples that capture the interactions of operators in shared spectrum, and not as the scenarios on which the manufacturers and operators will focus in the very near future.

Multi-domain sensor networks

An important design criterion for sensor networks is the minimization of the sensors' energy consumption. The sensors are often battery powered and it is impractical (and, in some cases, even impossible) to change or recharge the batteries once the sensors have been deployed. It is known that the energy required to transmit a data packet increases (at least) as the square of the distance of the transmission. In practice, this means that, as far as energy consumption is concerned, it is often more advantageous to transmit a packet in several small hops than to transmit it in a single large hop. Hence, if there are numerous sensors near each other, then they could transmit the packets together and thus increase the lifetime of their batteries radically.

In the previous chapter, we have seen how a given device can be properly and un-ambiguously designated by a name or an address. In this chapter, we will explain how two wireless devices can securely identify each other and get ready to communicate securely with each other; in other words, we will see how they can perform authentication and key establishment.

Authentication and key establishment are strongly related to each other, because of their mutual dependency: once two (or more) entities have authenticated each other, they can usually establish a key, in order to secure their future communications; conversely, an already established key can be very useful to perform future authentication.

These two operations are considered to be among the most fundamental (if not the two most fundamental) mechanisms of network security. As a result, a huge number of protocols have been proposed (and a sizeable number of them have already been standardized and implemented) in order to support authentication and key establishment in (wired) networks. The choice of a protocol depends notably on the role of the trusted server (if any), on whether the key is established by one of the principals (and then transported to the other(s)) or agreed among the principals, and on the underlying cryptographic mechanisms (symmetric or asymmetric).

So far, in Part III of the book, we have shown through examples (MAC layer, packet forwarding, and co-existence of wireless operators) how to model selfish behavior. We have also explained how it is possible to enforce a desirable behavior by observing other players' behavior. For this purpose, we have made extensive use of game theory. Yet, the security techniques that we have shown in Part II can also be of help in this framework; for example, authentication of the wireless nodes is necessary in order to thwart selfish behavior at the MAC layer.

In Chapter 3, we have explained that it is difficult to provide a fully satisfactory definition of malicious and selfish behavior, because the two notions are strongly intertwined. In this chapter, we will make a fundamental additional step and show how security and game theoretic techniques can be combined to thwart misbehavior in wireless networks.

In compliance with the other chapters of Part III, we will articulate our development around an example. As we have seen in Chapter 10, cooperation does not happen “naturally” for packet forwarding in self-organized ad hoc networks. This means that cooperation must be encouraged. There are several ways to achieve this goal. One of them consists in relying on micropayments.

Before diving into the mechanisms of malice and selfishness prevention, which will be the topic of the rest of this book, we will now focus on the notion of trust and we will refine the definition of the adversary model.

About trust

As we have already hinted in the previous chapter, building and maintaining trust will be much more difficult in upcoming wireless networks than in existing ones. Yet, trust is absolutely fundamental for the future of (wireless) communications. Once computing has become ubiquitous, it will probably be de facto mandatory, as are already today mobile phones and personal computers; but what if it is not trustworthy? What if it is as unsafe as today's Internet? Moreover, no business is possible without trust, and wireless networks are essentially driven by business considerations.

Trust can be defined as the belief that another party (a person, an organization, but also a device) will behave according to a set of well-established rules and will thus meet one's expectations. This notion is fundamental in all human societies (and also in many animal groups); generally, a breach of trust is considered to be a major offense.

But trust is a fuzzy notion, be it considered across persons or across areas of competence: no matter how close they are to each other, different people may trust very different things, even in front of the same evidence.

Privacy means that one can control when, where, and how information about oneself is used and by whom. Privacy is not about hiding one's personal information from everybody else in the world. In fact, revealing personal information to authorized parties under well-defined circumstances can be very useful and should be made possible. For instance, assume that someone suffers an accident and she is transferred to the hospital in an unconscious state. In this case, it is quite useful if the medical doctors can look up her medical record in a database.

It is clear, however, that we do not want that everyone can access our medical record. In particular, employers and insurance companies should not have access to it. However, the problem is that once personal information has fallen into the wrong hands, we cannot control its use anymore. Therefore, hiding personal information from unauthorized parties is indeed very important. This is one of the most powerful (and sometimes the only) means to retain control.

Privacy is a problem that cannot be solved solely by technical means. For instance, there is no technical solution that guarantees that a misbehaving doctor cannot reveal sensitive medical data to an unauthorized party (e.g., an employer). Therefore, the problem is usually addressed with a combination of technical and legal means. In fact, the technical and the legal approaches can nicely complement each other. Problems that cannot be solved technically are often related to human behavior.

For our first analysis of selfish (or greedy) behavior in wireless networks, we will focus on the MAC layer. More specifically, we will focus on IEEE 802.11, (the security of which we have already discussed in Chapter 1) because (i) this protocol is by far the most popular in existing wireless LANs, (ii) the devices (access points and wireless adapters) are very inexpensive, (iii) simulation code is widely available, and (iv) consequently the interested reader can relatively easily experiment the ideas developed in this chapter. In other words, the prominence of this protocol in wireless networks is such that it is the optimal candidate to illustrate the concepts of Part III of this book with a concrete example. The subsequent chapters will be (as all of the ones of Part II) standard-independent, with the exception of Section 11.2 in which we will refer to UMTS.

In IEEE 802.11, the stations (including the access point) in a given radio domain can transmit only one at a time. The temptation for selfish behavior is obvious, as the radio link is shared between all stations in power range: by departing from the protocol, a cheating station can substantially increase its bandwidth, at the expense of the other stations.

In the first section of this chapter, we briefly describe the operating principles of IEEE 802.11, which need to be known for a proper understanding of this chapter.

Introduction

Security of information and communication systems is concerned with the prevention or the detection (if prevention is not possible or too costly) of attacks, where an attack is meant to be a deliberate attempt to compromise the system. A system is compromised if it reaches a non-desirable state or it behaves in a non-desirable way, and where the latter can be the result of the former.

A system can also reach a non-desirable state or behave in a non-desirable manner due to some random faults. Random faults, however, are usually less sophisticated than attacks; hence, coping with attacks is more difficult. For instance, a Cyclic Redundancy Code (CRC) can detect random errors in a transmitted message well enough, but it is ineffective in detecting deliberate modifications, because an attacker can compute the correct CRC value for the modified message.

Stealing a password file and cracking passwords off-line is an example of an attack. In this case, the attacker tries to put the system into a non-desirable state where some passwords are known not only to the corresponding legitimate users, but also to the attacker. This allows the attacker to login in the name of a legitimate user and to use the privileges of that user to perform some operations in the system. This then allows the attacker to further compromise the system. For instance, the attacker can modify or delete some important configuration files, which can lead to a non-desirable behavior of the system.

As we have described in Chapter 2, some of the upcoming wireless networks use multi-hop wireless communications. In those networks, the nodes have two roles: they act as end-systems and they also perform routing functions. This means that routing control messages are sent over wireless channels. Moreover, because of the lack of their physical protection, some of the routers could be corrupted and not follow the routing protocol faithfully. This can have undesirable effects on the operation of the network. In extreme cases, the operation of the entire network can be disabled by attacking the routers and manipulating the messages of the routing protocol. This chapter is devoted to this problem. More precisely, we study the problem of securing the routing protocol in two kinds of multi-hop wireless networks: mobile ad hoc networks and wireless sensor networks.

Routing protocols for mobile ad hoc networks

A large amount of work on routing in mobile ad hoc networks has been carried out in the research community, which has resulted in a multitude of routing protocols. One way to classify ad hoc network routing protocols is illustrated in Figure 7.1. As we can see, there exist topology-based routing protocols and position-based routing protocols. Topology-based protocols are based on traditional routing concepts, such as maintaining routing tables or distributing link-state information, but they are adapted to the special requirements of mobile ad hoc networks.

We have entered the era of wireless networks. By now, the number of wireless phones has superseded that of wired ones. Wireless LANs are routinely used by millions of nomadic users. Wireless devices have become commonplace in offices, private homes, factories, and hospitals. And technologists promise us a world of ubiquitous computing, in which myriads of tiny, untethered sensors and actuators will communicate with each other, promptly taking care of our various needs and wishes.

In addition to this pervasiveness, we are witnessing a change of paradigm: initially, wireless devices had limited or no programmability and were managed (and secured) in a highly centralized fashion. Today, high-tier wireless end-systems are full-fledged personal computers and take an increasingly active role in the networking mechanisms. In the extreme case of multi-hop ad hoc networks, the end-systems are the network.

Unfortunately, this evolution is creating new vulnerabilities. Even existing wireless networks (and especially wireless LANs) exhibit a number of security weaknesses, some of which have been painstakingly fixed a posteriori. It is now clear that the security solutions devised for wired networks cannot be used as such to protect the wireless ones. An additional problem is that the frenzy to commercialize quickly new products and new services is in contradiction with the design of a well-thought (and possibly standardized) security architecture.

This textbook aims at preventing ubiquitous computing from becoming a pervasive nightmare. It contains a thorough description of existing and envisioned mechanisms devised to thwart misdeeds against wireless networks.

This second part of this book is about malicious behavior in wireless networks. Each of the chapters describes a fundamental aspect, by first introducing some possible attacks, and then detailing the corresponding countermeasures.

Chapter 4 describes the question of how to designate an end station in a network. It shows that the question is far from being solved, even in the Internet. It then describes the related attacks, namely the Sybil and the replication attacks. Finally, it explains how they can be thwarted.

Chapter 5 is about bootstrapping security between wireless devices located in radio range of each other. An attacker can try to fool one of the parties by establishing a security association with the attacker (herself) rather than with another intended party. The described countermeasures take advantage of physical vicinity or of the mobility of the nodes.

Chapter 6 focuses on the notion of (radio) neighbor. With the wormhole attack, it is possible to let a given node believe that another node is in its radio range, when in reality it is not. This chapter explains why this attack is dangerous, and details the several techniques to thwart it.

Chapter 7 addresses the problem of secure routing in multi-hop wireless networks. It explains that, if unprotected, routing is vulnerable to a vast collection of devastating attacks. It then explains the basic mechanisms to prevent them.

Introduction

As we have seen in the previous chapter, the development of wireless networks has followed a centralized pattern: the network infrastructure (meaning all pieces of equipment except the terminal) has remained under the full supervision of the network operator, who traditionally used to be a large organization, very careful at respecting the legislation (and at nurturing the value of its own brand). As a result, the users generally tend to trust the operator, but do not generally trust the other users.

As we have also seen, current technology such as WiFi makes infrastructure equipment (and in particular access points) affordable to very small operators or even individuals, thus allowing the emergence of community networks and similar initiatives.

In this chapter, we will show that we are only at the beginning of this evolution, and that not only WiFi, but also other wireless technologies are about to dramatically transform the deployment and operation philosophy of wireless networks. As a consequence, the notions of authority and of trust need to be completely revisited, and this is exactly one of the reasons for writing this book: the novel organization of the wireless networks calls for a thorough study of the possible malicious and selfish behaviors, and of the techniques to thwart them.

In order to be as concrete as possible, we will first provide a certain number of examples of emerging wireless networks, spanning personal networks, vehicular networks, sensors, and RFID (Radio Frequency IDentification, described later in this chapter).

Every smart-card vendor has its implementation of the ISO 7816 file structure and application selection process: these form the vendor's native operating system and, as we have seen in Chapter 6, they can be used to create a multi-application card scheme.

To gain the full benefits of portability, a high-level language and post-issuance downloading of applications, you need a multi-application operating system like JavaCard or Multos. But there are several operating systems that sit between these two extremes, and which may offer advantages in some situations.

IBM MFC

IBM developed its first multi-function card (MFC) 1 in the early 1990s. It has since been developed to extend the cryptographic support and add new features. One of its most important features, however, is the ability to support applications in E2PROM, which can be updated or downloaded after the initial issuance, using a scripting protocol.

IBM stopped supplying smart cards directly in 1999, but it has licensed the MFC to several manufacturers, and also develops tailored versions for specific schemes. It is now used by the French multi-application payment and e-purse card Monéo 2.

Advantis

Spanish card technology and systems supplier SERMEPA developed its ‘TIBC’ operating system in 1994 in order to run the ‘Visa Cash’ electronic purse product; TIBC was licensed to several card manufacturers and is still widely used in Spain and Latin America.