|
|
When an attacker commands a compromised node, he is able to perform link spoofing (as described in Section 3.2) with the purpose of perturbing the network. To withstand the link spoofing attack, we have designed a protocol which uses multiple signatures (generated by different nodes) to validate link state information [130]. Like the solution for OLSR signatures, our protocol relies on creating and sending a new additional message in conjunction with routing control messages. We call such a message an ADVSIG (for ADVanced SIGnature) message. Our main approach is based on authentication checks of new information injected into the network, and reuse of this information by a node to prove its link state at a later time. To our knowledge, this is the first time such a protocol has been proposed.
In general, HELLO and TC control messages have the semantics of the originator advertising “I have a link with these other neighbor nodes”. The signature on these messages, introduced in Section 5, serves to verify that the originator is indeed the one claiming such a link to exist. The task is now to validate that the other nodes also believe such a link to exist.
In OLSR, and in any other link state protocol, the network topology, with respect to the local neighborhood of a node, is related to what the network topology was at a previous instant. This because the link state at a given time t depends on the link state at an immediately previous time t - Δt.
E.g. at time t, node A selects node B as a MPR. We can therefore state that, at time t′ = t - Δt, node B declared a symmetrical link with node A. We can further state that, at time t′′ = t′- Δt′, node A had an asymmetrical link with B (i.e. A heard B), and declared this fact in a HELLO message which was received by B. In fact, this is exactly the way the nodes verify and establish symmetrical links in order to build a connected network; these steps, and their order in chronological sequence, are mandatory. Here we assume that all nodes correctly follow the protocol.
In summary, topology does not make leaps; instead, it proceeds smoothly with continuity. The transitions of link states is modeled in the automaton shown in Figure 9.1.
We might exploit this fact to avoid false routing information being injected in the network. The philosophy is that every node stores the most recent link state information about itself, as received by its neighbors (in their HELLOs); then the node reuses this information by including it, as a proof, in its control messages (HELLOs and TCs). In this way a node can prove that it supplies routing information accordingly and consistently with its previous neighborhood status. Of course, link state information has to be signed by the node that generated the message, otherwise a compromised node could easily produce false proofs.
It would be inefficient to sign and redistribute a whole HELLO message as a proof, because each HELLO contains many links related to many nodes. As OLSR control messages are not modified, we should split this data into reusable pieces of information.
In order to keep the protocol as light and simple as possible, we must identify the minimal quantity of exchanged link state information. The link atomic information generated by a node A concerning a neighbor node B consists of:
The address of the originator node is found in the message header as the Originator Address field, and is part of the standard packet. The address of the advertised node and its link state are exchanged through a HELLO message, respectively in the Neighbor Interface Address and Link Code fields. The timestamp and the signature will be contained in the ADVSIG message coupled to that HELLO. Depending on its use, this atomic information is called either a Certificate or a Proof.
Hence a node, upon reception of an HELLO and its companion ADVSIG message, extracts from both the information regarding itself (i.e. where “advertised” contain the node’s address). When used in this manner, we call the atomic information described above a Certificate. The Certificates are stored by the node in a Certiproof Table.
Later, when the node sends a HELLO or TC message, it will select the relevant Proof from its Certiproof Table and include it in the ADVSIG message coupled to that HELLO/TC message.
Note that we call the same atomic piece of information a Certificate when it is created and supplied to inform about the neighborhood, as fresh reusable topology information; and we call it a Proof when it is reused and supplied to prove a link state. The Certiproof Table of node B contains only Certificates signed by various neighbors of B; in each of these Certificates, the “advertised” field contains the address of B (except in the Certificate Zero, as explained later).
|
|
As mentioned above, if node A wishes to report a link in a HELLO/TC message with a neighbor node B, the required proof must be built using elements of a HELLO message and the accompanying ADVSIG message that were recently sent by node B. The proofs are then stored (as Certificates) in the Certiproof Table and reused (as Proofs) whenever necessary. The proofs must be sent along packed in a new companion ADVSIG message, with the new HELLO/TC messages they are intended to prove.
Table 9.1 gives a scheme of the required proofs, based on the OLSR specifications [31]. Refer also to Table 1.1 for an explanation of the link codes. The table can be integrated with other link types to define the requested behavior when declaring links of type UNSPEC_LINK or LOST_LINK.
For instance, when A wishes to report (in a HELLO) a SYM_LINK with B, the proof must be a recent HELLO from B reporting an ASYM_LINK or SYM_LINK with A. We remind that link codes (ASYM_LINK, SYM_LINK, SYM_NEIGH, and MPR_NEIGH) are advertised through HELLO messages, and advertising a node as a neighbor is done through TC messages.
For an asymmetric link (ASYM_LINK), the proof is part of the heard packet, because the advertised node does not hear the originator. A previous version of the protocol [130] required no proof for an asymmetric link. This because all critical operations in OLSR concern symmetrical neighbors: MPRs are selected from among the nodes with which there exist a symmetric link, MPR selection is accepted from nodes with which there exist a symmetric link, and TC messages advertise symmetric links only. Asymmetrical links have the sole purpose to (possibly) establish symmetrical links in an immediate future: these symmetric links can (possibly) be established only by an answer from the advertised node. When a malicious node X falsely advertises an ASYM_LINK, the link is maintained as asymmetric and eventually deleted (after expiration of its validity time, which depends on the Vtime); except if the advertised node effectively comes in the neighborhood of X, in which case a symmetric link may truly be established.
However, this may lead to an attack where a compromised node X advertises a fake ASYM_LINK with a node Y that X does not hear; Y may be a 2-hop neighbor of X and X may have known about its existence from a HELLO sent by a common neighbor. Node Y may actually hear X’s declaration, and therefore it would advertise a SYM_LINK with X instead of an ASYM_LINK as it should be. Hence node Y advertises a false symmetric neighborhood which may be declared in its TCs. If node X advertises a large number of fake ASYM_LINK with several nodes, it is possible that one of these nodes is or moves in the neighborhood of X, making the attack successful.
We present in this thesis a corrected version of the protocol. In this version, a declaration of an asymmetric link requires a proof, called Certificate Zero. A compromised node X can still carry out the aforementioned attack by recycling the Certificate Zero from Y as overheard as a Proof from another node Z, and not as a Certificate from Y as it should be. However, this would cause a delay in X’s declaration, and this delay could therefore be detected by using a tighter synchronization and more stringent checks on timestamps.
When a node B receives from A a HELLO and its accompanying ADVSIG message, it extracts from both any information regarding itself, and stores the tuple
Note that, in the implementation, it is obviously not necessary to store the advertised field in the tuple, as it is a constant. We present nonetheless the protocol in this way to be consistent with the Certificate/Proof format, and to avoid confusion.
The key of the tuple is the originator address. Only one tuple for each originator is maintained in the table: when B receives a subsequent HELLO message (with its ADVSIG) from A, it updates the tuple entry with the freshest information, established as such by comparing the timestamp fields. In this manner, node B stores in the Certiproof Table only the most recent Certificate about itself, as given by a neighbor.
The format of this security-enhanced ADVSIG message is shown in Figure 9.2.
An ADVSIG message must be generated and sent with every HELLO or TC
message, and possibly in the same packet. However, there is a difference between
HELLOs and TCs: while both message types always require Proofs, HELLOs
can contain Certificates whereas TCs do not. Hence the Signature of
Certificate #i fields exist only in those ADVSIG messages which are coupled to
HELLOs.
The Global Timestamp is the timestamp of this ADVSIG message and of the HELLO/TC it is coupled with.
The Global Signature is computed on the sequence of bits made up of the
whole HELLO/TC message (header included) and the associated ADVIG message
except, of course, the Global Signature field itself. As seen in Section 5, the
Time To Live and Hop Count fields are considered as set to zero, because they
change in transit.
The Signature of Certificate #i is present only when the ADVSIG is coupled with a HELLO. This fields contains the signature of the Certificate related respectively to the Neighbor Interface Address at position i in the HELLO coupled message.
An exception is the Signature of Certificate #0 field, which is not related
to any advertised neighbor link, but is always included in those ADVSIGs that are
coupled to HELLOs.
The subsequent three fields (Link Code #i, Timestamp of Proof #i, and Signature of Proof #i) purport to the Proof related to a neighbor node declared in the HELLO/TC message. More in detail, the Proof is related: to the Neighbor Interface Address at position i if the coupled message is a HELLO, or to the Advertised Neighbor Main Address at position i if the coupled message is a TC.
The Reserved #i field is used to make all fields 32 bit aligned, and may be reserved for future use.
The Link Code #i is the link state in the Proof related to neighbor node i. An alternate implementation might omit this field, as it can be extrapolated from Table 9.1; in this case, when verifying a signature of a Proof, a receiver node must test all link codes that apply.
The Timestamp of Proof #i and Signature of Proof #i are the timestamp and signature of the Proof related to the neighbor node i.
The link status, timestamp, and signature of the Proof were taken respectively
from: Link Code, Global Timestamp, and Global Signature of a previous
HELLO and its accompanying ADVSIG. These data were then saved in a tuple and
stored in the Certiproof Table. If a proof is not required according to
Table 9.1, these three fields, as well as the Reserved #i field, are not
present.
Every Signature of Certificate and every Signature of Proof is computed on the sequence of bits made up of:
The Signature of Certificate #0 is computed only on the Originator Address and Global Timestamp, because there is no neighbor to advertise, and hence no link. The purpose of this Certificate Zero is to certify to a neighbor the hearing of an empty HELLO, or a HELLO that does not include that neighbor; in this case the neighbor can issue a declaration of ASYM_LINK with the sender of the HELLO message. Consequently, the advertised and linkstate fields are empty in the relevant tuple of the Certiproof Table.
In sum, when A sends an ADVSIG message, every Signature of Certificate is signed by A, while every Signature of Proof is signed by other nodes (which are, or have recently been, neighbors of A).
In the following example we illustrate the algorithm by scrutinizing the building of a neighborhood. We recall that the notation A → B : {M,M′,TA(t0)}A means “A sends B the message M with the Proof M′, timestamped by A at the time t0, and signed with the private key of A”.
In step 1, A sends an empty HELLO, including a Certificate Zero, and no Proof. In step 2, B receives the HELLO from A and declares an ASYM_LINK with B, using the Certificate Zero as proof. In step 3, A declares a SYM_LINK with B; node C is sure that A’s statement about its link state with B is correct. To be able to give the Proof in step 3, A stored in its Certiproof Table the tuple 〈B,A,ASY M_LINK,TB(t2),{}B〉 which was extracted from the data A received from B in step 2: {“A : ASY M_LINK”,TB(t2)}B.
We denote t0 the current time. The value Δtg is the time interval after which a Global Timestamp expires. The value Δtp is the maximum acceptable time interval between a Certificate and its Proof, after which the Proof is stale and can no longer be used; this is done in order to thwart replay attacks using old Proofs. (We leave aside the problem of clock skew.) Upon reception of an ADVSIG message, the receiving node must check that the following conditions are satisfied for every k:
The following subsection outlines the algorithm. The full detailed version of the algorithm is given in the next subsection.
When a node generates a HELLO or TC message, it must also generate a ADVSIG message, following this protocol:
When a node receives a control message and its ADVSIG, it must follow this protocol:
If any of the previous checks fail, the HELLO/TC and ADVSIG message must be dropped.
When a node generates a HELLO or TC message, it must also generate a ADVSIG message, following this protocol:
When a node receives a control message and its ADVSIG, it must follow this protocol:
If any of the previous checks fail, the node must stop processing the HELLO/TC and the ADVSIG, and must discard them.
We assume the use of DSA to generate the signatures in the ADVSIG message.
The size of an ADVSIG message sent with a HELLO message is:
ADVSIG coupled to HELLO: 352 + 704n bits
An ADVSIG message sent with a TC is shorter (because it does not contain Certificates) and has the following size:
ADVSIG coupled to TC: 352 + 384n bits
Counting the IP, UDP, and OLSR packet headers, the size of a OLSR packet containing a HELLO or TC message plus its companion ADVSIG message are therefore:
HELLO + ADVSIG (packet): 936 + 744n bits
TC + ADVSIG (packet): 832 + 416n bits
We assume that each HELLO/TC message and its companion ADVSIG message are sent together in the same OLSR packet, and the packet does not contain other messages.
With the assumptions above and those made in Section 5.4.1 (n = 9), the flowrate can be evaluated as follows:
OLSR with ADVSIG: 4731 bit/sec
Figure 9.3 shows the additional message overhead for the ADVSIG architecture.
As can be seen, the message overhead is quite large (even if a large part of this overhead comes from ADVSIGs that are coupled to HELLOs and that therefore do not travel further that one hop in the network). The computation overhead is elevate too, as sending a HELLO message requires n + 2 signature computations, while sending a TC requires one; checking the validity of either messages requires n + 1 signature verifications. This is unsuitable for low-equipment nodes. For this reason, this protocol may be fit for high-capacity machines in a military network operating in a battlefield, where integrity of topology is of primary importance.
The message overhead can be reduced by using shorter signatures (e.g. Boneh-Lynn-Shacham). By using 64-bit signatures and removing the Reserved fields for a more efficient padding, the size of a packet containing a HELLO or a TC plus its ADVSIG would respectively be 680 + 208n and 576 + 136n. The equivalent flowrate would be 1636 bit/sec. Figure 9.4 shows the message overhead for the ADVSIG architecture with shorter signatures.
With respect to the vulnerabilities explained in Section 3.2, this architecture protects against an attacker trying the link spoofing attack. This means reaching an important goal. A compromised node can no longer choose the (false) routing information to issue, because this information has to be validated by previous routing information issued beforehand. Hence the network is now robust against one lone attacker. The network is protected even if there are more than one compromised node at the same time, provided that they cannot communicate between them.
If the attacker compromises two or more nodes and is able to have them
communicate, it can forge any kind of Certificate or Proof where originator and
advertised node are both compromised. Hence any distributed information
concerning link state between two compromised nodes may be false. This includes
the case in which the attacker is able to create multiple identities of a node (Sybil
attack [39]), in order to certify the (false) information from a compromised
node.
