Ariadne: A Secure On-Demand Routing Protocol for Ad Hoc Networks

The Presentation inside:

Slide 0

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

Slide 1

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

Slide 2

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

Slide 3

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

Slide 4

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

Slide 5

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

Slide 6

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

Slide 7

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

Slide 8

TESLA Overview (cont.) Sender attaches MAC to each packet Computed over the packet’s 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

Slide 9

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

Slide 10

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

Slide 11

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

Slide 12

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)

Slide 13

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 Authority’s public key at each node

Slide 14

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

Slide 15

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)

Slide 16

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

Slide 17

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

Slide 18

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

Slide 19

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)

Slide 20

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

Slide 21

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

Slide 22

Route Discovery (cont.) Upon receiving ROUTE REQUEST, a node: Processes the request only if it is new Processes the request only if the time interval is valid (not too far in the future, but not for an already disclosed TESLA key) 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 KAi where i is the index for the time interval specified in the REQUEST

Slide 23

Route Discovery (cont.) When the target receives the route request: 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) 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

Slide 24

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

Slide 25

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

Slide 26

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

Slide 27

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 sender’s TESLA key) recent TESLA key: most recent disclosable TESLA key

Slide 28

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

Slide 29

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