D3.3: Study on Mobile Identity Management

Study on Mobile Identity Management ANONYMITY IN SELF-ORGANISING NETWORKS – DIFFICULTIES AND CONCEPTS

Anonymity in self-organising Networks – Difficulties and Concepts

In recent years, autonomous, self-organising, wireless multi-hop networks have received increased attention due to their potential applications. In contrast to common communication models, e.g., cellular mobile networks, self-organising multi-hop networks do not rely on any pre-existing infrastructure. Instead, every user-device is a potential intermediate node for forwarding data packets thus becoming part of the network infrastructure. Due to their distributed design these networks become a powerful and reliable tool for establishing a transport infrastructure using equipment already deployed and under operation. 

However, ensuring reliable services in self-organising networks raises different problems than in common networks with a centrally managed infrastructure. By large this is due to the fact that for individual nodes, forwarding traffic for others for one is a losing deal as it consumes potentially limited resources. On the other hand, each node will need the help of others when trying to send its own packets. Thus, finding a balance and motivating nodes to cooperate in forwarding packets is one of the main problems to be solved in the context of self-organising networks.

In the past few years, a couple of frameworks were presented that encourage collaboration in multi-hop networks. However, all of them have a serious, negative impact on the anonymity of the system, namely keeping the communication relationships unlinkable and ensure the anonymity of the participating nodes. In this chapter we briefly discuss the current approaches and sketch a potential solution. 

Related Work

Most models addressing this problem to date are based on the rational assumption of selfish behaviour of participating nodes. That is, a node will engage in the protocol if it is beneficial to do so. Consequently, incentives are used to encourage the nodes to participate, either by rewarding nodes for their efforts of forwarding other nodes’ packets (e.g., (Buttyan and Hubaux, 2000; Buttyan and Hubaux, 2003; Jakobsson, Buttyan and Hubaux, 2003; Zhong, Chen and Yang, 2003; Ben Salem, Buttyan, Hubaux and Jakobsson, 2003)) or, by punishing them if a deviation from the protocol is discovered (e.g., (Buchegger and Le Boudec, 2002; Michiardi and Molva, 2002; Marti, Giuli, Lai and Baker, 2000)).

Ad hoc network models. One generally distinguishes between fully self-organising multi-hop networks and hybrid networks. While the former do not rely on the existence of any infrastructure, the latter introduce some operational authority such as, for example, a provider-driven base-station (e.g., (Ying-Dar Jason Lin, 2003; Jakobsson, Buttyan and Hubaux, 2003; Ben Salem, Buttyan, Hubaux and Jakobsson, 2003)). In symmetric hybrid networks both the route to and from the base station are multi-hop. In contrast in asymmetric hybrid networks (e.g., (Jakobsson, Buttyan and Hubaux, 2003)), the routes to any base station are multi-hop while the routes from any base station to any node are single-hop.

Secure Routing protocols. Secure routing protocols such as, for example, (Papadimitratos and Haas, 2002), address security vulnerabilities ranging from DoS attacks, cheating nodes, forging of routing information to impersonation of nodes. Solutions include the use of strong cryptography (e.g., authentication methods, hash chains, threshold cryptography) as well as reputation based methods. Solutions that also address the issues of anonymity and unlinkability include protocols such as (Jiejun Kong, 2003; Jakobsson, Capkun and Hubaux, 2004). While (Jiejun Kong, 2003) uses a public key protected onion (Syverson, Goldschlag and Reed, 1997), Capkun et al. (Jakobsson, Capkun and Hubaux, 2004) propose a solution for hybrid networks in which the operator not only has access to location and identity of registered nodes but also shares a secret key with each individual node.

Incentive mechanisms. Mechanisms to encourage collaboration can be positive (reward) or negative (punishment) in nature. The latter approach is, for example, taken in reputation systems like CONFIDANT (Buchegger and Le Boudec, 2002), CORE  (Michiardi and Molva, 2002) and the watchdog/pathrater approach by Marti et al. (Marti, Giuli, Lai and Baker, 2000). They mainly consist of sophisticated observation and reporting mechanisms combined with a clear punishment strategy. Rewarding systems like (Buttyan and Hubaux, 2000; Buttyan and Hubaux, 2003; Jakobsson, Buttyan and Hubaux, 2003; Zhong, Chen and Yang, 2003; Ben Salem, Buttyan, Hubaux and Jakobsson, 2003), on the other hand, employ some payment or crediting system in order to charge and reward participants: one participant (in most cases the originator or the destination) is charged for services and all intermediate nodes along the route are paid for their forwarding efforts. In hybrid networks, the base station can monitor packets, enforce the rewarding policy and detect attacks (Ben Salem, Buttyan, Hubaux and Jakobsson, 2003; Jakobsson, Buttyan and Hubaux, 2003). In self-organising multi-hop networks, on the other hand, rewards can, for example, be redeemed through a clearing authority (Zhong, Chen and Yang, 2003). An alternative approach, is the local broadcast technique (Buttyan and Hubaux, 2000). This technique links the actual forwarding of packets with remuneration. The information a node needs for getting remunerated is included in the packet which is sent by the subsequent hop. Receiving the broadcast from the next hop forwarding the original package confirms that the claiming node forwarded the package and that it was received by the next hop. The technique relies on the assumption that radio links are symmetric.

Most incentive schemes proposed to date require some sort of trust. Trust is established, for example, by means of a public key infrastructure (e.g., (Zhong, Chen and Yang, 2003)) or through the use of tamper-resistant hardware—which can be viewed as a distributed trusted third party (e.g., (Buttyan and Hubaux, 2000; Buttyan and Hubaux, 2003; Jakobsson, Buttyan and Hubaux, 2003)).

An untraceable incentive scheme

The main problem which is not yet addressed by common solutions is how to provide incentive mechanisms for multi-hop networks which not only encourage collaboration between nodes but at the same time keep communication relationships unlinkable and ensure the anonymity of participating nodes. In single-hop wireless networks, e.g., base-station-oriented cellular networks, a subscriber can obtain a sufficient level of privacy by deactivating his device while not sending or receiving data. In contrast, in multi-hop networks the user is required to keep his device activated at all times in order to maintain a viable networking infrastructure for everyone.  

In the following, we sketch a protocol that not only meets the increasing need of (location-) privacy but also provides an efficient incentive mechanism for forwarding packets in a multi-hop wireless network (Alkassar and Wetzel, 2004). 

Incentive Mechanism. The incentive mechanism is based on electronic coins as a system-wide currency. Each node may withdraw coins from and clear coins with a so-called clearing service. The system allows for coins of different but fixed denominations. For each intermediate node (on the route from the source to the destination) the source node will withdraw one coin of sufficient denomination from the clearing service. The denomination of a coin directly corresponds to the maximum number of data packets to be transmitted during a session. That is, in order to have n intermediate nodes each forward p data packets (of fixed size), the source node must withdraw n single coins of denomination pd from the clearing service. Coins are valid for one particular session only, used portions of a coin cannot be used up in subsequent sessions. A node is charged upon withdrawing coins and rewarded when presenting received coins. Rewards are given only in the amount corresponding to the actual number of forwarded packets.

A source node may claim refund for the difference between the denomination of the coin (used to pay an intermediate node for its efforts during a particular session) and the amount corresponding to the packets for which a reward was claimed. For simplicity we assume that every node can regularly establish a direct, i.e., single-hop link to the clearing service. In order to assure unlinkability, the refund is to be handled by a separate trusted third party.

Security model. The system is considered to be secure if the incentive mechanism is fair and messages, respectively participants are anonymous and unlinkable. The incentive mechanism is fair if no node can gain any (monetary) advantage by cheating, i.e., deviating from the protocol. With respect to cheating one generally distinguishes (see for example  (Ben Salem, Buttyan, Hubaux and Jakobsson, 2003)) between the refusal to pay and a false reward claim. The latter is a node trying to claim monetary reward for packet forwarding he never performed. The refusal to pay is characterised by a node refusing to pay for the forwarding services performed by intermediate nodes. Free-riding is a special case of refusing to pay in that collaborating nodes are trying to misuse the protocol in order to avoid charges (e.g., by interleaving sessions, using side-channels).

The Scheme. Skipping the details of the building blocks, we can now describe our construction for an untraceable coin-based incentive scheme. We discuss each one of the stages set-up, withdrawal, packet delivery and rewarding separately. A more sophisticated, alternative protocol that allows for more flexibility in terms of the payload to be transmitted can be found in (Alkassar and Wetzel, 2004).

Set-up. The clearing service and the nodes are set up as in Brands’ payment system (Brands, 1993). That is, the clearing service generates different hd’s for different denominations Dd and publishes them in a non-repudiatable way.

Withdrawal:  A source node S intending to send a certain number of payload packets with the help of n intermediate nodes is required to withdraw at least n coins of sufficient denomination in order to pay for the service. The withdrawal is done as described in Brands’ payment protocol (Brands, 1993).

Packet delivery. In order for a source node S to send a number of data packets to destination D, the source node S will first use a corresponding route discovery protocol to determine route RDS to destination node D. Source node S may receive several answers to its route request corresponding to alternative routes to reach the destination D. The source node will select one route (e.g., one with the least number of hops in order to minimise costs). Let ||i=1,…,n (ki,ri) be the route description for the selected route and let N1,…,Nn be the intermediate nodes on this route.

Using the selected route RDS, the transmission of the payload packets is organised in two steps: The initialisation step in which one coin is sent to each one of the intermediate nodes and the packet delivery step itself, in which the data is sent. In order to simplify matters, we will first focus on the structure of the messages sent during payload delivery. Afterwards, we will discuss the initialisation phase in detail.

Payload message structure. Let pd be the number of packets that S intends to send during this particular session. We write msgij for the i-th packet (i=1,…,p) sent by the j-1st node to the jth node on the route from S to D. The system is designed such that the last message (sent from node Nn to D) is of form

    msgiD=encD(payload)

and for nodes Nj (j=1,…,n) of form

    msgij=enckj(msgij+1).

Initialisation phase. At first, the source node computes so-called authenticators Apj=||i=1,…paij as they will later on be seen by the respective intermediate nodes Nj (1jn). The individual components aij are defined as

    aij=hash0(hash1(msgij+1))

(i corresponds to the ith packet with 1ip) using two one-way hash functions hash0 and hash1. Now S can send a coin coin’j to each intermediate node Nj with coin’j=(A,B,,r1,r2). In order to ensure that the coin is bound to both the respective node as well as the corresponding authenticator Apj, we need to extend payment step in Brands’ scheme by adding the authenticator Apj to the hashed challenge, thus obtaining C=H(A,B,n,Apj). The actual initialisation messages msg0j are determined as

    msg0j=encekj(coin’j,Apj,msg0j+1) and

    msg0n=encekN(coin’j,ApN)

with j=1,…,n-1. Upon receiving msg0j, node Nj verifies the signature within the coin (as in Brands’ payment step).

Sending of data packets. After completing the initialisation, the source S can send off the data packets. The intermediate node Nj, receiving msgij (corresponding to data packet 1ip), will decrypt and authenticate the message using its private key kj. If decryption was successful (i.e., did not return ), node Nj may forward the decryption result msgij+1=dec(msgij) to the next intermediate node Nj+1 on the route to destination D.

Rewarding. In order to ensure that only those coins can be cleared by intermediate nodes for which the respective packets have been forwarded by the node, the nodes must justify their claims by providing additional information. According to our model, messages are broadcasted and network links are assumed to be symmetrical. Hence, node Nj will also receive msgij+2, the message sent from hop Nj+1 to Nj+2. The sending of this message, however, can not occur unless node Nj had complied with the protocol forwarding msgij+1 to node Nj+1 which in turn decrypted the message and sent on msgij+2. Thus, node Nj will keep xij=H1(msgij+2) as authenticator. Together with coin’j and the preimage xij of aij, Nj can prove its claims.

Except for the rewarding stage, the anonymity and unlinkability follows directly from the property of semantic security of the encryption algorithm and that every combination (kj,Nj) is used only once.

Anonymity and unlinkability during the rewarding stage is guaranteed because of the anonymity and unlinkability property in Brands’ payment scheme: Linking two nodes in the rewarding stage would enable linking of two coins which in turn would break the underlying payment scheme. This is due to the fact that the coins are only pair wise known (onion encryptions) and in the basic protocol the authenticators have no relationship to other nodes. In the alternate protocol, the authenticators are linked to other nodes authenticators. However, for anybody else than the intermediate node and the source node, the authenticators are indistinguishable from random data.

Outlook

The problem of encouraging cooperation in multi-hop networks, while keeping the participating nodes anonymous is still a challenging task. 

So far, we proposed an incentive scheme, based on a common anonymous, coin-based payment scheme. In terms of future work, we intend to incorporate an efficient error handling and acknowledgements into the protocol making reliable packet delivery more efficient. Finally, we will explore how to realize an anonymous routing protocol that prevents free-riding, which still seems to be an open problem.