Full paper: Postscript, PS.GZ, PDF

Authenticated Routing

Using the $\mu$TESLAprotocol, we developed a lightweight, authenticated ad hoc routing protocol that builds an authenticated routing topology. Ad hoc routing has been an active area of research [5, 13, 17, 18, 26, 29, 28, 37]. However, none of these solutions offer authenticated routing messages. Hence it is potentially easy for a malicious user to take over the network by injecting erroneous, replaying old, or advertise incorrect routing information. The authenticated routing scheme we developed mitigates these problems.

The routing scheme within our prototype network assumes bidirectional communication channels, i.e. if node $A$ hears node $B$, then node $B$ hears node $A$. The route discovery depends on periodic broadcast of beacons. Every node, upon reception of a beacon packet, checks whether it has already received a beacon (which is a normal packet with a globally unique sender ID and current time at base station, protected by a MAC to ensure integrity and that the data is authentic) in the current epoch . If a node hears the beacon within the epoch, it does not take any further action. Otherwise, the node accepts the sender of the beacon as its parent to route towards the base station. Additionally, the node would repeat the beacon with the sender ID changed to itself. This route discovery resembles a distributed, breadth first search algorithm, and produces a routing topology similar to Figure 1 (see [16] for details).

However, in the above algorithm, the route discovery depends only on the receipt of route packet, not on its contents. It is easy for any node to claim to be a valid base station. We note that the $\mu$TESLAkey disclosure packets can easily function as routing beacons. We accept only the sources of authenticated beacons as valid parents. Reception of a $\mu$TESLApacket guarantees that that packet originated at the base station, and that it is fresh. For each time interval, we accept as the parent the first node that sends a packet that is later successfully authenticated. Combining $\mu$TESLAkey disclosure with the distribution of routing beacons allows us to charge the costs of the transmission of the keys to network maintenance, rather than the encryption system.

This scheme leads to a lightweight authenticated routing protocol. Since each node accepts only the first authenticated packet as the one to use in routing, it is impossible for an attacker to reroute arbitrary links within the sensor network. Furthermore, each node can easily verify whether the parent forwarded the message: by our assumption of bidirectional connectivity, if the parent of a node forwarded the message, the node must have heard that.

The authenticated routing scheme above is just one way to build authenticated ad hoc routing protocol using $\mu$TESLA. In protocols where base stations are not involved in route construction, $\mu$TESLAcan still be used for security. In these cases, the initiating node will temporarily act as base station and beacons authenticated route updates .