Anonymous Routing in Wireless Networks: Onion Routing

Abstract: Security and privacy are the major concerns while routing data through a wired or wireless network. Although encryption is used to protect data from being read by unintended recipients it still does not ensure complete safeness. The reason being that information can be gathered by an eavesdropper by indirect inferences like traffic analysis etc. In my literature survey project I have focused on the topic of anonymous routing – onion routing in wired networks and extended it to wireless networks. In onion routing the data is wrapped in layers of encryption in a data structure called as an onion, which is transmitted over the network. The onion is constructed in such a way that it prevents any eavesdropper from gaining information about the parties involved in the communication or the nature of their data exchange. Anonymous routing in wired networks cannot be directly mapped to wireless networks. This is because wireless networks are more vulnerable to privacy issues as compared to wired networks due to the mobility of nodes, limited battery power, and nature of message transmission. Hence it is more challenging to create anonymous routing protocols for a wireless scenario.

The World Wide Web (WWW) is the most popular and widespread discovery of the millennium. Although it has been a few years since its inception, security is still a major concern over the web. Data that is transmitted over the network is subject to various threats ranging from privacy, confidentiality, integrity etc by an active or a passive attacker. An active attacker [3] not only snoops over the communication but also corrupts communication by injecting malicious data. To minimize the vulnerability of data during transmission encryption is used. A passive attacker [3] on the other hand simply eavesdrops and gathers information by observing the ongoing traffic. At times the mere fact that communication is being carried over a particular link or between two parties could be more valuable than the actual data that is being transmitted between them. Hence meta data can sometimes be more sensitive than the actual transmission data content. Meta data includes the sender and receiver identities, their location, length and time of the message etc[1]. Hence by analyzing such traffic data, indirect inferences can be made about the people communicating over a public network like their identities, their relationships etc. This is in line with evidence gathered by MIT reality mining project [2- Exploiting location Data].

Traffic analysis [I] , [II] is the process of intercepting and examining messages in order to deduce information from the patterns in communication. It can be performed even when the messages are encrypted and cannot be decrypted. Thus an intruder can simply sniff packets and capture them. And analyzing the header content which has the source and destination address the intruder can gather valuable information about the ongoing communication. For example: an attacker can gain important information by monitoring, the frequency and timing of network packets.

Internet data packets have two parts: a data payload and a header used for routing.

• The data payload is the information being sent; e.g.: an email message, a web page etc.
• The header consists of the source address, destination address, timing information, sizing information etc.

Although the data payload is encrypted, traffic analysis still reveals a great deal about what a communicator is doing and, possibly, what they’re saying. This is because it focuses on the header, which discloses the source, destination, size, timing, and other critical information. Thus encryption does not help against these attackers, since it only hides the content of internet traffic and not the headers. And it is not possible to encrypt the headers since the destination will not be able to identify the packet meant for it. Thus by analyzing the data headers and observing the packet movement trend an attacker can indirectly gather sensitive information about the communicating parties. A very simple form of traffic analysis might involve sitting somewhere between sender and recipient on the network, looking at headers.

• Although traffic analysis provides lower quality information, it is preferred over cryptanalysis because it is easier than breaking complex encrypted messages [2].
• It is also cheaper because traffic data can be automatically collected and processed to provide a high degree of intelligence [2].
• It is used for military purposes [2] and by various organizations to track unpleasant events over the internet.

As it can be seen traffic analysis can be used to extract a lot of sensitive information and it can strip a person of all his communication privacy over the internet. Hence it becomes important to take precautions against it and to increase the level of anonymity on the web. This is the main motivation for anonymous routing. Thus Onion routing, Chaums Mixes, Tor are a few methods that provide resilience towards traffic analysis.

Onion routing [IV] was conceived in 1996 by David.M.Goldschlag, Michael.G.Reed and Paul.F.Syverson for the Naval Research Laboratory’s research group in high asurance system [6]. It lives just beneath the application layer and is designed to inteface with a wide variety of unmodified internet services by means of proxies. Onion routing is the the mechanism in which the sender (initiator) and the receiver (responder) nodes communicate with each other anonymously by means of some anonymous intermediate nodes called as onion routers. It protects against traffic analysis and makes it very hard for an eavesdropper to determine who is talking to whom over the network. It concentrates on encrypting the packet header in such a way that only the intended destination understands that the packet is meant for him.

Instead of making a socket connection directly with the destination machine, the sender makes a connection to an onion proxy on a remote machine. This onion proxy then randomly selects a set of onion routers upto the destination and builds an anonymous connection to the destination via them. It then constructs a special data structure called as an onion and routes it through this established connection.

Onion routing relies on public key cryptography.This enables the creation of an onion which is nothing but the transmission data wrappped in multiple layers of encryption with the route information in each layer of encryption. It is done in such a way that when the data moves from one onion router to the next, each onion router strips a layer of the onion using its private key to find its next hop, and routes the packet accordingly [5],[6].This goes on till the packet reaches the receiver. Thus every onion router knows only its previous and next hop. Padding may be applied at each onion router to maintain the size of the onion. So data passed along this anonymous connection appears different to each onion router. Also since an onion is decrypted at each router there is no correspondence between an incoming and outgoing onion for a particular router. Hence data cannot be tracked en route and even a comprosmised onion router cannot be of much help. Even if an onion router is compromised only the previous and next hop would be visible but the actual sender and receiver would still be hidden.This provides added resistance to an attacker.

Onion routing hardware can be subdivided into two parts:

• Network Infrastructure:
As shown in the figure the network infrastructure consists of onion routers that carry traffic between the initiator and the responder (via the intermediate onion routers). Each onion router has a single connection to each of its neighbouring onion routers. The job of a onion router is to decrpyt an incoming packet using its private key and pass it to the next onion router mentioned in the onion packet. It may also apply padding to maintain the size of the onion thus making traffic analysis more difficult.




• Proxy interfaces:
The proxy links the initiator to the anonymous connection (node W) on the initiator end and at the responder end it links the anonymous connection to the responder (node Z).eg:When the initiator sends a request for say a particular URL; instead of directly connecting to the server where the URL content is stored, it connects to an onion proxy W. This proxy then randomly chooses a set of onion routers say X-Y-Z. It then encrypts the packet with Y’s, X’s and Z’s public key and their addresses and sends it to the first onion router on the desired root. The data then moves along the route and is transmitted by Z to the responder. Z also acts as a proxy because it passes data from the responder to the anonymous connection.
Each onion proxy maintains a list of onion routers on the network and their IP addresses. There are also directory servers where active routers register with. So onion proxies can query directory servers from time to time in order to get an up-to-date list of servers on the network [5].

Onion routing consists of the following steps:

• Defining a route.
• Constructing an anonymous connection.
• Moving data through an anonymous connection.
• Destroying the anonymous connection.

The following steps give a brief description of the above steps.

When an onion proxy receives a message it first randomly selects a set of onion routers upto the destination by checking in its existing list of onion routers. It then uses public key cryptography to construct the onions in such a way that only the intended onion routers can peel off the outer layer. The following example illustrates the process.

Consider the case where there are n onion routers numbered from 1 to n. The public and the private key of a particular router say i is denoted by Ipu and Ipr respectively. The onion proxy knows the public keys of all the onion routers in its list. The private keys are known only to that particular router. An encryption and decryption function is used to encrypt and decrypt the data. The encryption function is Ekey(data) and the decryption function is Dkey(data). Data encrypted by a public key can be decrypted by a private key and vice versa. Hence we have
DI_public_key ( EI_private_key (data)) = data. DI_private_key ( EI_public_key (data)) = data

On receiving a packet the onion proxy selects a random sequence of routers from its list say 4, 3 and 5. So it constructs the onion in the following manner. It first encrypts the data packet with public key of 5 followed by public key of 3 and finally 4. So the encrypted data now looks like E4pu (3’s IP address, E3pu ((5’s IP address, (E5pu (recipient’s IP address, data))))). This is then sent to onion router 4. Onion router 4 uses its private key to peel the outermost encryption layer. It finds the IP address of the next hop i.e. router 3. So it passes to router 3 the onion which now looks like E3pu ((5’s IP address, (E5pu (recipient’s IP address, data)))). Again router 5 uses its private key to peel the outermost encryption layer. It finds the data and the recipient’s IP address and concludes that it is the final anonymous hop to the destination. It simply forwards the packet to the destination.

Thus sending an onion over a chosen path creates a virtual circuit. This circuit is bidirectional i.e. the destination can also send a message to the source along the same path. In the given example it simply encrypts the data with its private key and forwards it to onion router 5. Erecipient_private(IP address, data). Onion router 5 then encrypts it with its private key and forwards it to 3 as E5pr (Erecipient_private(IP address, data)). Similarly router 3 and 4 also encrypt it step by step with their private key and outer 4 sends it to the onion proxy that initiated connection with it. The data that is received by the onion proxy looks like E4pr (E3pr (E5pr (Erecipient_private(IP address, data)))). The onion proxy now uses the public keys of these routers and decrypts each layer of the onion, using the outermost layers key first. It retrieves the data and simply routes it to the sender.

Since the size of the onion reduces as it nears the destination an attacker can infer details about the destination. To avoid this onions are padded at each onion router to maintain the size of the onion. Padding is simply adding redundancy. This is a really big advantage because it complicates traffic analysis, as an attacker cannot infer location or other details of the destination by getting hold of an onion. Every onion router has details of only its previous and next hop. So even if an onion router has been compromised the attacker can only get the encrypted onion with the next hop. He will not be able to decrypt the onion without the private keys and hence will not infer any valuable information from it.

Each layer of onion also contains an expiration time. An onion router is to ignore expired and replayed onions. Further if the connection breaks during the routing process then all the onion routers are informed via a destroy message. Ensuring that all onion are of the same size, timing information of the circuit is obfuscated and adding noise makes traffic analysis very difficult.

It is susceptible to denial of service attacks. This can be done by forcing onion routers to do a large number of cryptographic operations by many sending packets to it. Eventually the router simply ends up doing cryptographic operations and is not able to forward packets.

This can be mitigated using client puzzles. Here the onion proxy (i.e. the server) forces a requesting client to complete a puzzle before it allocates resources. This forces an attacker to find additional resources. But puzzle solving has an impact on the latency although it reduces DOS vulnerability.

An attacker can record data going on between routers and can compromise a router at a later stage, to acquire private key and decrypt data. This can be avoided by using a session key between communicating parties. The session key is used to encrypt data and is valid only for the duration of the communication.

• It supports multiple applications like email, web browsing etc.
• A tunable configuration allows various degree of protection to individual users.
• Data is unreadable throughout the route except at the end points.

• In a wireless medium there is node mobility and lack of infrastructure. There is no central point governing the flow of traffic. So nodes rely on intermediate nodes to relay their data. If intermediate nodes are compromised then onion routing fails.
• Also packets are broadcast into the network. Thus traffic analysis becomes easier and may go undetected.
• Lack of central management makes it susceptible to active attacks.
• It takes longer to construct paths due to the dynamic nature of the environment.
• Key distribution for encrypting traffic is a challenge.

• The source need not know the topology of the entire network since path discovery is a dynamic process.
• Hence traffic analysis becomes more difficult.
• Symmetric keys of intermediate nodes are collected using a global trapdoor managed by the source and destination nodes, thus providing anonymity and end to end data privacy.

This protocol is also based on the concept of onion routing. Like the previous protocol it is divided into 3 phases; route discovery, route reply and data forwarding. This protocol makes a few assumptions as follows:

• Every node in the network has a permanent identity known to all other nodes in the network.
• The source and destination share a secret key KSD and a secret pseudonym.
• A pseudonym between a source and a destination can be used only for one RREQ i.e. it acts as a unique identifier for RREQ.
• Nodes share pseudonyms and secret keys only with a limited set of other nodes.
• Every node establishes a broadcast key with its one hop neighborhood.

The protocol takes place in three parts namely route discovery, route reply and data forwarding.

Route Discovery: A source node S wishes to send a message to the destination D. They share a secret key KSD and pseudonym for D is NymSD. S performs the following steps:

1. It generates an asymmetric key pair pubD and privD.
2. It generates a secret key k.
3. It generates trapdoor identifier iddest that can be only opened by the destination knowing KSD. iddest = KSD [D, k, privD] , k[NymSD].
4. It generates a pair of link identifiers (ns, ks) .These ids are used to recognize the RREP packets.
5. It encrypts the link ids with public key of destination.
6. It broadcasts the packet: NymSD , ttl, pubD, iddest, pubD(ns, ks).

When a node receives Ni receives a RREQ it performs the following steps:

1. It checks if it is the destination by verifying whether NymSD exists in its list of valid pseudonyms.
2. If yes then it decrypts iddest using KSD and goes to step 3 else it goes to step 8.
3. It checks too see if the first part in the trapdoor identifier matches with its id. If not, then it implies that the node is not the intended destination.
4. Irrespective of the result of step 3 it checks if has been already recorded in its routing table. If yes, then the node discards the message else it goes to step 5.
5. It checks if ttl <= 1. If it is , then it decrements ttl by 1 and generates a random pair of link identifiers (ni, ki).
6. It appends (ni, ki) to the received encrypted link identifiers and encrypts everything with public key of the destination.
7. It stores < NymSD , ni, ki , k[NymSD] > in its routing table and broadcasts the following message NymSD , ttl, pubD, iddest, (pubD ….(pubD (ni-1, ki-1),ni, ki)
8. If Ni is not the intended destination it fills the link identifiers with random data of appropriate length and broadcasts it.

When the destination node receives a route request packet it uses the link identifiers of all the intermediate nodes to create a reply onion. The detailed steps are explained below:

9. Node D receives a message NymSD , ttl, pubD, iddest, (pubD ….(pubD (ni-1, ki-1),ni, ki).
10. It decrypts iddest to get k.
11. It uses its private key to get link identifiers of all the intermediate nodes on the route.
12. It constructs a reply onion which contains the link ids of all the intermediate nodes and encrypts them several times using the ids of intermediate nodes in the reverse order.
13. It generates a random ttl and broadcasts this route reply packet as KD[NYMSD, ttl], onion.

Route Reply: The destination wraps all the link ids of the intermediate nodes in a message and encrypts the packet with the keys of all the intermediate nodes on the route before forwarding it. When a node Ni receives a route reply packet it performs the following steps:

1. It checks if it has forwarded a RREQ packet with the pseudonym NYMSD.
2. If no, it goes to step 3, else it goes to step 4.
3. It replaces the onion by random data, decrements ttl and broadcasts packet.
4. It checks if it has received a RREP with the same identifier i.e. pseudonym. If yes, then it performs step 3 else it goes to step 5.
5. It decrypts the onion using ki and checks if the first part of the message is equal to its id Ni.
6. If yes, then it decrypts NYMSD using the k it retrieved from the RREP and checks if it equal to NYMSD. If they are not equal then the packet is discarded, else it goes to step 7.
7. Node Ni strips a layer of the reply onion and generates a new random ttl and broadcasts the RREP packet.

Data Forwarding: When the source receives a RREP for its RREQ it sends the DATA message to the destination. DATA messages will have one time identifiers attached to them similar to RREQ messages. This identifier allows a node on the route to recognize the fact that it is the next hop and that it should forward the message. Forwarding data messages is similar to forwarding RREP messages using the same ttl scheme, but without padding.

• No cryptographic operations are required for a node to be able to recognize that it is the intended recipient.
• It effectively hides the routes in the network.
• A node on the network that receives a message from its source cannot determine if it is the source of the message or a mere forwarder.

Security is an important aspect of communication over the web. Mere encryption of messages doesn’t keep it from malicious attackers. An attacker can gain a lot of information by indirect traffic analysis as can be seen from the study above. Hence it becomes very essential to mitigate traffic analysis. Onion routing is by far the best solution for maintaining anonymity over the web. In onion routing (for wired networks) data is wrapped under multiple layers of encryption and forwarded towards the destination and each node on the route decrypts a layer and forwards it. But certain modifications need to be made while applying onion routing on the wireless network. Wireless networks are more vulnerable to attacks due to lack of central management, dynamic nature of the network, broadcast nature of packet forwarding etc. Thus onion routing is modified appropriately to suit the wireless environment. WAR, SDAR, ARM provide anonymity to a great deal although they have drawbacks. Research is currently on in this field to develop more and more better suited protocols that can be more resilient towards traffic analysis.

I] http://en.wikipedia.org/wiki/Traffic_analysis

II] http://www.more.net/technical/netserv/troubleshooting/trafficanalysis.html

III] http://tor.eff.org/overview.html.en

IV] http://en.wikipedia.org/wiki/Onion_routing

1] Mary Elisabeth Gaup Moe. “Security Models for Anonymous Routing”. Norwegian University of Science and Technology.

2] George Danezis. “Introducing traffic Analysis- Attacks, Defenses and public Policy Issues”. Invited Talk.

3] Yih Chun Hu, Adrian Perrig. “A Survey of Secure Wireless Ad Hoc Routing”. University of California- Berkeley, Carnegie Mellon University.

4] Adam Back, Ulf Moller, Anton Stiglic. “Traffic Analysis Attacks and Trade-Offs in Anonymity Providing Systems”. Zero-knowledge Systems Inc.

5] Marc O’ Morain, Vladislav Titov, Wendy Verbuggen. “Onion Routing for Anonymous Communication”.

6] Michael G. Reed, Paul F. Syverson, David M. Goldschlag. “Proxies for anonymous Routing”. Naval Research Laboratory, Washington DC.

7] Nicholas A. Fraser, Richard A. Raines, Rusty O. Baldwin. “Tor: An Anonymous Routing Network for Covert On-line Operations.” Air Force Institute of Technology, Wright Patterson AFB.

8] Michael E. Locasto, Clayton Chen, Ajay Nambi. “WAR: Wireless Anonymous Routing”. Department of Computer Science, Columbia University.

9] Liu Yang, Markus Jacobson, Susanne Wetzel. “Discount Anonymous On Demand Routing for Mobile Ad hoc Networks”.

10] Azzedine Boukerche, Khalil El-Khatib, Li Xu, Larry Korba. “SDAR: A Secure Distributed Anonymous Routing Protocol”. University of Ottawa.

11] Dehn Sy, Rex Chen, Lichun Bao. “ODAR: On-Demand Anonymous Routing in Ad-Hoc Networks”. University of California.

12] Stefaan Seys, Bart Preneel. “ARM: Anonymous Routing Protocol for Mobile Ad hoc Networks”. Department of Electrical Engineering-ESAT, SCD/COSIC