Castor

Aus wiki.freifunk.net
Zur Navigation springenZur Suche springen

Castor is a routing protocol for wireless ad hoc networks. One of its main goals is to secure the routing process, i.e. to prevent and react to attacks and failures affecting routing. The protocol also supports node mobility but was primarily designed for networks of static nodes. Castor is an acronym for Continuously Adapting Secure Topology-Oblivious Routing. While Castors design is agnostic to the exact network layer it is running on top of, Implementations are usually based on the Transport Layer (OSI Layer 3) with some exceptions also including Layer2 information to provide certain enhancements (further details in the implementation section below).

The contents of this page are a summarized explanation of the protocol from its original paper by Papadimitratos et al.

How it works

The core routing metric of Castor is reliability, followed by response time. Nodes determine metrics independently from each other, and take routing decisions with their own locally-collected information. The routing state is determined per-flow (a flow is a particular path between a source and a destination) at each node.

Each node has a unique ID that can be cryptographically validated if needed. The source of a packet must not only know this ID but also the public key of the destination (or somehow pre-share a symmetric key with it). However there is no hierarchy introduced for the set of nodes so one might argue it is a Layer2 protocol. For reasons stated elsewhere it is reasonable to assume Layer3 nonetheless Vorlage:Citation needed.

The protocol requires no control traffic. The only two types of packets are data packets (PKT) or acknowledgements (ACK).

Packet structure

A data packet contains the following fields:

  • s: source identifier
  • d: destination identifier
  • H: flow identifier
  • bk: packet identifier
  • fk = [x1, x2, ..., xl]: flow authenticator
  • ek: encrypted ACK authenticator
  • M: payload

An acknowledgement packet contains a single field ak, the ACK authenticator.

ek is ak encrypted with the public key of the destination (or the pre-shared key between sender and destination). This ensures that only the correct recipient can acknowledge the delivery of a packet.

Routing

Packet generation

For each flow, the sender generates the following:

  • a set of packet identifiers bk = h(ak), where h is a cryptographic hash function (i.e. a hash function practically impossible to invert)
  • a Merkle tree with root H and h(b1), ..., h(bw) as leaves

The flow authenticators x1, ..., xk form a sequence of siblings of the vertices on the path from a leaf h(bk) up to the root H.

Forwarding

For every neighbor and for every flow, a node stores a reliability estimator. When it receives a packet, it determines the next hop based on the reliability estimator for that particular flow. If no neighbor is deemed reliable, the node broadcasts the packet to all neighbor nodes and starts a timer limited by some specified timeout value.

The reliability threshold can be adjusted for how much bandwidth we can invest in route discovery, thus impacting the packet delivery rates.

If a node receives a duplicate packet, it does not forward it. However, multiple acknowledgements of a packet are rebroadcasted.

Verification

The properties of the the hash function and of the Merkle tree allow the nodes to verify certain properties of a packet, which we explain in the following paragraphs:

In order to verify if a packet belongs to the flow it claims to be part of, an intermediate node or the destination compare h(...h(h(bk)||x1)||x2)...||xl) to H. If the values differ, the packet does not belong to flow H and is dropped.

The destination additionally verifies whether bk = h(D(e_k)), where D is the decryption operation with the destination's private key (or the pre-shared key with the source, if that's the case). Then it also verifies the integrity of the payload M. Only if all these steps are successful does the destination calculate ak = D(ek) and sends it as an acknowledgement to the node it received the packet from.

Updating the reliability estimators

When an intermediate node receives an acknowledgement ak, it computes bk = h(ak). If it corresponds to the bk from packets it has routed before, the node knows the delivery of that packet was successful. It increases the reliability metric for the flow and rebroadcasts ak.

The reliability metric is based both on the successful delivery rates and on the failed delivery rates of a flow.

Implementation

Unfortunately there is no full implementation yet. There is work in progress at TU Darmstadt. The Secure Mobile Networking Lab has a partial implementation on the Click! modular router platform, which can be compiled to run on mesh nodes. The current implementation is a Layer3 routing protocol taking also certain information in account from Layer2 to provide extensions to better support multicast transmissions. It is highly unlikely that this implementation will be shared with the outer world any time soon, though :(

If the advantages of a secure routing protocol are relevant for us, we can work on an implementation ourselves.

Siehe Auch

External Links