Ariadne: A Secure On- Demand Routing Protocol for Ad Hoc Networks Yih-Chun Hu Carnegie Mellon University Adrian Perrig Carnegie Mellon Univeristy David B. Johnson Rice University

Motivation Wired network routing protocols – Do not handle high mobility – Have high communication overhead – Send periodic routing messages Ad hoc routing protocols – Address these concerns – …but do not address security

On-Demand (Reactive) Routing A sending node attempts to discover a route to a destination only when it has a need to send data to that destination Tend to perform better – Have significantly lower overheads – Reduce (or eliminate) routing overhead in periods or areas of the network in which changes are infrequent

Contributions Model for the types of possible attacks – Including several new attacks on ad hoc network protocols Design and performance evaluation of a new on- demand secure ad hoc routing network protocol (Ariadne) – Withstands node compromise – Relies on highly efficient symmetric cryptography – Does not require trusted hardware or powerful processors

Ariadne Overview Authenticate routing messages using one of: – Shared secrets between each pair of nodes Avoids need for synchronization – Shared secrets between communicating nodes combined with broadcast authentication Requires loose time synchronization Allows additional protocol optimizations – Digital signatures

DSR Review Route Discovery – Initiated when a node needs to send to a destination for which it does not have a route – Propagation of ROUTE REQUEST builds path – ROUTE REPLY returns route to initiator Data sending Route Maintenance – Detects broken links on route – Generates ROUTE ERROR for initiator – Removes link from path cache

TESLA Overview Broadcast authentication protocol used here for authenticating routing messages – Efficient and adds only a single message authentication code (MAC) to a message – Requires asymmetric primitive to prevent others from forging MAC TESLA achieves asymmetry through clock synchronization and delayed key disclosure

TESLA Overview (cont.) 1.Each sender splits the time into intervals 2.It then chooses random initial key (K N ) 3.Generates one-way key chain through repeated use of a one-way hash function (generating one key per time interval) K N-1 =H[K N ], K N-2 =H[K N-1 ]… These keys are used in reverse order of generation 4.The sender discloses the keys based on the time intervals

TESLA Overview (cont.) Sender attaches MAC to each packet – Computed over the packets contents – Sender determines time interval and uses corresponding value from one-way key chain – With the packet, the sender also sends the most recent disclosable one-way chain value

TESLA Overview (cont.) Receiver knows the key disclosing schedule – Checks that the key used to compute the MAC is still secret by determining that the sender could not have disclosed it yet – As long as the key is still secret, the receiver buffers the packet When the key is disclosed, receiver checks its correctness (through self-authentication) and authenticates the buffered packets

Network Assumptions Network links are bidirectional The network may drop, corrupt, reorder or duplicate packets Each node must be able to estimate the end-to-end transmission time to any other node in the network Disregard physical attacks and Medium Access Control attacks

Node Assumptions Resources of nodes may vary greatly, so Ariadne assumes constrained nodes All nodes have loosely synchronized clocks

Security Assumptions Three authentication mechanism possibilities: – Pairwise secret keys (requires n(n+1)/2 keys) – TESLA (shared keys between all source- destination pairs) – Digital signatures (requires powerful nodes)

Key Setup Shared secret keys – Key distribution center – Bootstrapping from a Public Key Infrastructure – Pre-loading at initialization Initial TESLA keys – Embed at initialization – Assume PKI and embed Certifications Authoritys public key at each node

Attacker Model Passive attacker – Threaten privacy and anonymity – Not in this paper Active attacker – Injects packets and eavesdrops – Characterized based on the number of controlled nodes in the network

Attack Classification Routing disruption attacks – Causes legitimate data packets to be routed dysfunctionally (e.g., routing loop, black hole, gray hole, detour, partition) Resource consumption attacks – Consumes valuable network resources or node resources (e.g., injecting data packets, injecting control packets)

Ariadne Notation A and B are principals (e.g., communicating nodes) K AB and K BA are secret MAC keys shared between A and B MAC KAB (M) is computation of MAC of message M using key K AB

Route Discovery Assume sender and receiver share secret (non-TESLA) keys for message authentication Target authenticates ROUTE REQUESTS – Initiator includes a MAC computed with end- to-end key – Target verifies authenticity and freshness of request using shared key

Route Discovery (cont.) Data authentication using TESLA keys – Each hop authenticates new information in the REQUEST – Target buffers REPLY until intermediate nodes release TESLA keys TESLA security condition is verified at the target Target includes a MAC in the REPLY to certify the condition was met

Route Discovery (cont.) Attacker can remove a node from node list in a REQUEST One-way hash functions verify that no hop was omitted (per-hop hashing)

Route Discovery (cont.) Assume all nodes know an authentic key of the TESLA one-way key chain of every other node Securing ROUTE REQUEST – Target can authenticate the sender (using their additional shared key) – Initiator can authenticate each path entry using intermediate TESLA keys – No intermediate node can remove any other node in the REQUEST or REPLY

Route Discovery (cont.) ROUTE REQUEST packet contains eight fields: – ROUTE REQUEST: label – initiator: address of the sender – target: address of the recipient – id: unique identifier – time interval: TESLA time interval of the pessimistic arrival time – hash chain: sequence of MAC hashes – node list: sequence of nodes on the path – MAC list: MACs of the message using TESLA keys

Route Discovery (cont.) Upon receiving ROUTE REQUEST, a node: 1. Processes the request only if it is new 2. Processes the request only if the time interval is valid (not too far in the future, but not for an already disclosed TESLA key) 3. Modifies the request and rebroadcasts it –Appends its address to the node list, replaces the hash chain with H[A, hash chain], appends MAC of entire REQUEST to MAC list using K Ai where i is the index for the time interval specified in the REQUEST

Route Discovery (cont.) When the target receives the route request: 1. Checks the validity of the REQUEST (determining that the keys from the time interval have not been disclosed yet and that hash chain is correct) 2. Returns ROUTE REPLY containing eight fields –ROUTE REPLY, target, initiator, time interval, node list, MAC list –target MAC: MAC computed over above fields with key shared between target and initiator –key list: disclosable MAC keys of nodes along the path

Route Discovery (cont.) Node forwarding ROUTE REPLY – Waits until it can disclose TESLA key from specified interval Appends that key to the key list This waiting does delay the return of the ROUTE REPLY but does not consume extra computational power

Route Discovery (cont.) When initiator receives ROUTE REPLY 1. Verifies each key in the key list is valid 2. Verifies that the target MAC is valid 3. Verifies that each MAC in the MAC list is valid using the TESLA keys

Route Maintenance Based on DSR – Node forwarding a packet to the next hop returns a ROUTE ERROR to the original sender Prevent unauthorized nodes from sending errors, we require errors to be authenticated by the sender

Route Maintenance (cont.) ROUTE ERROR contains six fields – ROUTE ERROR: label – sending address: node encountering error – receiving address: intended next hop – time interval: pessimistic arrival time of error at destination – error MAC: MAC of the preceding fields of the error (computed using senders TESLA key) – recent TESLA key: most recent disclosable TESLA key

Route Maintenance Errors are propagated just as regular data packets – Intermediate nodes remove routes that use the bad link Sending node continues to send data packets along the route until error is validated – Generates additional errors, which are all cleaned up when the error is finally validated

Conclusions Ariadne is a secure ad hoc routing protocol – Operates on-demand – Efficient and general security mechanisms Key exchange is complicated – In the ad hoc environment especially, this is most likely not feasible