Interleaved Hop-by-Hop Authentication

A synopsis of:

Zhu, S., S. Setia, S. Jajodia, and P. Ning, “An Interleaved Hop-by-Hop Authentication Scheme for Filtering False Data Injection in Sensor Networks,” IEEE Symposium on Security and Privacy, Oakland, CA, May 9-12, 2004, pp. 260-272.

When analyzing security of wireless sensor network protocols, designers assume that nodes will be compromised. The compromise could be as simple as physical destruction of a node or sophisticated enough to allow an attacker to manipulate messages originating from the compromised node. Compromising an active node gives the attacker access to keying material, thus the attacker has the ability to calculate legitimate message authentication codes. These reputedly authentic messages can misguide the base station, divert intrusion alerts, or deplete network resources. Zhu presents an interleaved hop-by-hop authentication method that can detect such false data injection attacks. The method defines a threshold t for the number of compromised nodes and requires t + 1 nodes to send an authenticated reports of an event.

The scheme guarantees that if no more than t nodes are compromised, falsely injected data can be detected and dropped. The value t is a design parameter that can be adjusted based on the threat of node compromise. Since compromised nodes may collude in an attack against the network, at least t + 1 nodes must agree on an alert before it can be trusted.

Zhu’s proposal assumes that the network is organized into clusters, with a subset of nodes acting as cluster heads. There are t + 1 nodes in each cluster, including the cluster head. The cluster may reside multiple hops from the base station. Nodes within the network can send unicast messages up and down the tree, and broadcast messages to their neighbors. Nodes share a master key with the base station and have the ability to establish pairwise keys with most of their one-hop neighbors.

The scheme relies on an association of nodes that are t + 1 hops apart on the path to the base station. The node closest to the base station is referred to as the upper associated node; the lower peer is referred to as the lower associated node. Upper associated nodes validate the message authentication code (MAC) appended to messages from their lower associated peers. Each alert may carry as many as t + 1 MACs as it travels from leaf nodes to the base station. As it travels toward the base station, a validation failure on any of the MACs will cause the message to be dropped. As long as the number of compromised nodes remains below the value t, the system can detect false data injection.

Five unique phases comprise the hop-by-hop authentication technique, including initialization and deployment, association discovery, report endorsement, en-route filtering, and base-station verification.

During node initialization and deployment, the key server loads each node with a unique id and a unique key that node shares with the base station. The node derives an authentication key from the encryption key it shares with the base station. The key server then can use one of many key establishment algorithms to initiate network key distribution. This enables nodes to establish pairwise keys with their neighbors.

The association discovery phase allows nodes to discover their associated peers both on the path downward from the base station and in reverse. The base station kicks off the process by broadcasting a hello message. Each node that receives the broadcast checks for the id of the node t + 1 hops up the tree, replaces that id with its own, and rebroadcasts the modified hello. This provides an upper bound of t + 1 node ids attached to the hello message. A receiving node records the id of the node t + 1 hops up the tree as its upper associated node. Note that nodes less than t + 1 hops from the base station do not have an upper associated node. When the hello message reaches a cluster, the cluster head assigns its leaves to upper associated nodes. The hello message can be authenticated with a broadcast authentication scheme such as microTESLA.

After the cluster notifies its leafs of their peers, it sends an acknowledgment back to the base station. The lower associated nodes authenticate the acknowledgment with the pairwise key they share with their upper associated node. Along with the MAC, the acknowledgment includes the node ids of the cluster head and the leaf nodes. As the acknowledgment is returned up the tree toward the base station, upper associated nodes learn the node id of their lower associated node. They replace the id of their lower associated node with their own id and forward the acknowledgment back up the tree. In cases where upper nodes have branches to multiple clusters, they record cluster ids and nodes in a table.

When nodes witness an event, they send a report to the base station. This hop-by-hop proposal requires t + 1 nodes to witness an event and endorse a report of the event. As the endorsement moves upstream, the ids of the nodes that witnessed the events and authentication codes will be appended to it. Each node computes two MACs for the event. The individual MAC is computed using the node’s key with the base station. The pairwise MAC is computed using the node’s pairwise key with its upper associated node. If the cluster head can authenticate a report from all its leaf nodes, it compresses the individual MACs by XORing its individual MAC with the individual MACs from the leaf nodes. The pairwise MACs are not compressed.

Upper level nodes that receive this report must authenticate it using their pairwise key with their lower associated node. If authentication succeeds, the node will extract the MAC from its lower associated node and append its own. If authentication fails, the message will be dropped. This in-route filtering assures that as long as no more than t nodes are compromised, then falsely injected data will be dropped.

Once the alert reaches the base station, the base station performs its own verification. It extracts the event data and node ids from the report. It then computes its own compressed MAC on the event data using its keys shared with the nodes in the node list. If the MAC matches the compressed MAC in the report, the alert is considered valid.

Since wireless sensor network are susceptible to damage, the Zhu proposal includes maintenance techniques. One strategy proposes piggybacking association discovery messages on base station beacons such as those sent in TinyOS. Nodes accept the first beacon they receive as their parent node. Since these beacons are sent every epoch, it is possible for nodes to change parents every epoch. While this strategy is satisfactory for dynamic networks, it is costly for networks that do no change frequently. A less costly base station initiated strategy has the parent change only if the node determines that any of the nodes in the beacon from its parent have changed. Repair can also be initiated locally when nodes detect failure of a neighbor. The proposed technique requires nodes to use GPS or similar technology to determine the physical location of their neighbors. When a node detects that its parent has failed, it will send a REPAIR message to the first node counterclockwise from the edge between itself and its deceased parent. It will then exchange messages with this node to learn the ids of the upstream nodes and rebuild any broken node associations.

Zhu’s proposal provides a higher level of security than simple pairwise authentication between neighboring nodes. The base station can trust that reports from leaf nodes are authentic based on the MAC computed with pairwise key between itself and the leaf node. Intermediary nodes can authenticate reports based on pairwise keys with their lower associated nodes. As long as t + 1 nodes agree on an event, the system will detect a falsely injected report sent by t nodes or less. This high level of security comes requires a high level of node redundancy.

December 27, 2007 Posted in: Computing