|
|
We design here an infrastructure [4, 2] to protect OLSR. A prototype of this infrastructure has been built for an INRIA contract with the DGA CELAR, the French government agency for weaponry. This framework can operate with either symmetric or asymmetric keys. To prevent malicious nodes from injecting incorrect information into the OLSR network, an additional security element is generated by the originator of each control message and transmitted with the control message. For the sake of simplicity, in this chapter we call the additional element a “signature” even if in the case of a shared symmetric key it should, more properly, be called a “digest”. A timestamp is associated with each signature in order to estimate message freshness. Thus, upon receiving the control message, a node can determine if the message originates from a trusted node, or if message integrity is preserved.
Signatures are, inherently, separate entities from OLSR control traffic: while OLSR control messages answer the purpose of acquiring and distributing topological information, signatures serve to validate information origin or integrity. For this reason we implement the signature as a separate type of OLSR message (called SIGNATURE message), instead of appending the timestamp and the signature to the control message. The resulting signature message is considered and handled like any other OLSR standard message. Furthermore, while this implementation slightly increases the total message size, it does not involve considerable modifications to the standard OLSR protocol as it uses the standard format for the control messages.
For each control message (HELLO, TC, MID, or HNA) generated, a corresponding SIGNATURE message is generated, and sent in the same packet containing the control message, immediately before it. Signatures are used by a receiving node to authenticate the corresponding OLSR control message: every control message without a matching corresponding signature is dropped.
In our architecture, a signature purports to a message, not to a whole packet. It is not possible to sign or digest a whole OLSR packet because it may change in transit between one node to another. This is because a packet may contain TCs, which are flooded in the network, as well as HELLOs, which are not forwarded further. Hence after a few hops the packet might no longer bear a valid signature, because it was computed on the original packet.
A remedy to the payload change problem would otherwise be to check the signature on a hop-by-hop basis (with re-computation of the signature at each hop) instead of an end-to-end check. However, signing a OLSR packet would also have profound implications with respect to accountability in the case of a compromised node: as many nodes repeat the TC messages that are diffused by MPR flooding, if a message is found to be incorrect, any of the nodes which repeated it might be a compromised node. When the authentication is per packet, it may only be deduced that the compromised node is part of the (previously) trusted network. When the authentication is per message, the node originator of the message is easily identified as the origin of the faulty information. For these reasons, the logical conclusion for the choice of a packet signature algorithm would be a digest computed with a symmetric shared secret key for the whole group of nodes, protecting the messages on a per-group basis, and not offering the possibility to check which node sent a specific message. This very architecture has in fact been proposed [60]. The advantage of this option is that it makes it possible to include the TTL and Hop Count, which are mutable fields, in the digest.
We decided on the choice of signing single messages also because it permits switching to an asymmetric algorithm with minimal changes and effort. Moreover, this architecture is better compatible with the standard OLSR, as signature checking can be turned off if bandwidth is needed and security requirements become looser.
The control message and its SIGNATURE message are sent in the same OLSR packet in order to simplify handling of the messages: the packet contains first the SIGNATURE message, then immediately after the control message it purports to. (If these messages were not sent in the same packet, their order of arrival could not be guaranteed. Therefore each node would need a buffer to temporarily store them after reception, before trying to couple them.)
The difficulty posed by handling long packets that exceed the MTU is solved as follows. The control message may be fragmented if necessary, so that the control message and its SIGNATURE are smaller or equal to the MTU of the network. If the control message is fragmented, an independent SIGNATURE message must be computed and assigned to each fragment. Fragmentation may also be used for messages that are waiting in the relaying queue, in order to insert these messages in the packet ready to be sent. Note that is not strictly necessary to consider the MTU of the network (i.e. the minimum bound of the MTUs of all the link pairs in the network): in fact, for fragmentation of HELLO messages, only the MTU size of the sender-receiver link needs to be considered, because HELLOs are not forwarded further. For simplicity, however, we always consider the network MTU in the fragmentation rule.1
A unique OLSR packet may contain more than one pair of control message and SIGNATURE message, provided that the payload contains a SIGNATURE immediately before its companion control message, in this exact order.
The SIGNATURE message is encapsulated and transmitted as the data portion of the standard OLSR packet format described in Section 1.4.4.
The Message Type field is set to the SIGNATURE constant value; this value may also include information about the cryptographic primitives and keys to use. The Time To Live and Vtime fields are set to the values of the Time To Live and Vtime fields of the message with which the signature is associated. The other fields of the message header are set as usual.
An old version [2] of the SIGNATURE message is shown in Figure 5.1. The message carries a MSN Referrer field in order to identify bijection between a control message and its SIGNATURE message.
The Sign. Method field specifies which method, among a predefined set, is being used to generate the signature. This includes information about keys, cryptographic functions, and timestamp algorithms.
The Reserved field is used for padding, to make all fields 32 bit aligned. It is set to 0 and reserved for future use.
The MSN Referrer field of the SIGNATURE message contains the value of the Message Sequence Number of the control message with which this signature is associated. The correspondence achieved by the Message Sequence Number is unique only if possible overflow and wraparound of the 16-bit field is disregarded; however this is not a problem, since a node uses further signature (and timestamp) verification to check the correspondence between the control message and the signature message.
The Timestamp and Signature fields are the same as in the actual version of the message.
The approach implemented in the previous version makes it unnecessary to send the SIGNATURE message and its associated control message in the same packet, as the messages could be reordered and re-associated later. However, this means that every node would need to store the received messages (control and signature messages) in a buffer. This requires more system resources and is more prone to failure and DoS attacks (regarding control messages whose signature is lost, or vice versa). Furthermore, delay is unfavorable when a message and its signature are not aggregated in the same packet [158]. This approach was hence abandoned in favor of the actual simplified version.
The actual format of a SIGNATURE message is specified in Figure 5.2.
|
|
The Timestamp field contains the timestamp itself, measured in seconds. This is the timestamp of both the SIGNATURE message and the associated control message. For compatibility reasons, the timestamp is 32 bits long and represents the standard Unix time, which is encoded in a 32-bit signed integer2 data type. The Unix time measures the time elapsed in seconds since 00:00:00 UTC on January 1, 1970.
The current time is obtained from the node’s internal BIOS clock. The BIOS clock has a linear drift of about 1 sec/day, which can therefore be corrected via an algorithm. See Section 7.2 for an empirical study on time synchronization techniques.
The Signature field contains the signature, computed on the sequence of bits made from the following fields:
The criterion to verify whether a timestamp is stale is ∣ Timestamp -t0∣≤ Δt, where t0 is the current time at the receiving node and Δt is the accepted value for discrepancy, including the difference in the synchronization of clocks.
A strict clock synchronization of the nodes is not necessary; the timestamp is used to disambiguate possible wraparound of the Message Sequence Number. The synergy of timestamp and Message Sequence Number in every message is used to check the freshness of the message, and wraparounds of Message Sequence Number are a rare event. In fact, counting a time interval of 2 seconds for HELLOs and 5 seconds for the other control messages (standard OLSR values), and the Message Sequence Number field being 16 bits long, wraparounds of the MSN occur no more frequently than every 16 hours for the standard OLSR or 8 hours for the secured OLSR.
However, the synchronization must not be coarser than the lifetime of the Duplicate Set; in fact, a Duplicate Tuple is deleted from the Duplicate Set when it is 30 seconds old (DUP_HOLD_TIME constant), and a node may be subject to the possible replay of a message that has the same MSN as that of a deleted Duplicate Tuple.
In our CELAR implementation, we let Δt = DUP_HOLD_TIME/2.
Our security architecture [4] relies on the use of asymmetric cryptography. An offline Certification Authority has the duty of assigning an identity-based key pair for each participating node. Before joining the network, a node contacts the Certification Authority through a secure channel, and obtains a global key. The node also generates a key pair, and diffuses its public key (local key) to the network via a specific key exchange protocol: it originates Key Distribution messages, signed with its global key, that are spread by pure flooding. From this point on, the node uses its local key to sign its control messages.
This implementation utilizes identity-based Cha-Cheon signatures [25] (pairing based) for the global keys, and Boneh-Lynn-Shacham short signatures [17] for the local keys. In both cases, a Weil pairing is used on supersingular elliptic curves of embedding degree k = 1, with the family of curves proposed by Koblitz and Menezes [89]. The parameters are shown in Table 5.1. The implementation has been tested on an Intel i486 133 MHz, on an Intel Pentium III 1 GHz, and on an Intel Pentium 4 2.8 GHz, giving the results shown in Table 5.2. These solutions must be seen as prototypes, as the figures show that size of global keys is sufficient to ensure some degree of security but the computation is slow, while local keys have fast computation times but small size (insecure).
|
|
|
|
It may be discussed whether it is appropriate to sign every type of control message, or just some types. In the first case, there would obviously be a larger overhead. As the primary purpose is to protect the network topology, it is mandatory to choose to associate a signature to control traffic messages (HELLO and TC) only. We decided nonetheless to sign even the other OLSR control messages (MID and HNA), in order to avoid false information about multiple interfaces being spread over the network.
As previously said, the Time To Live and Hop Count fields in the message headers cannot be included in the signature computation, since these fields change at each hop of the message and this would interfere with the correct verification of the signature by the receiving node. This unfortunately leaves the door open to an attack where an adversary relays tampered messages whose TTL has been set to 0 or 1 or, more generally, to a lower value than the original. This weakness can be overcome by ignoring the Time To Live field, and referring to the Timestamp field (which is protected by the signature) to limit the forwarding radius of the message.
We recall that, in order to make flooding more robust, it is possible to allow each node to select two (or even more) MPRs to cover all its 2-hop neighborhood, by setting an appropriate MPR_COVERAGE constant. Redundant MPR coverage will be, of course, at the expense of MPR flooding efficiency. This remedy can also be used to cure blackhole attacks and incorrect MPR selection from malicious nodes; incorrect selection of MPRs is also sometimes performed by legitimate nodes as an effect of wrong topology spread by malicious nodes, as explained in Section 3.2.
This security architecture is not interoperable with the standard OLSR. Non-secured nodes, i.e. the nodes which do not have the ability to check the signature (because of limited computing power or non-knowledge of the key), may simply drop SIGNATURE messages upon reception. However, their unsigned control messages would be dropped by secured nodes. This means that secured nodes could not reply to HELLO messages from non-secured nodes, therefore no symmetrical link and subsequently no MPR relationship could be created between secured and non-secured nodes. As a result, there would be two disjoint networks, one composed of secured nodes and the other composed of non-secured nodes. The secured nodes would totally ignore messages from non-secured nodes, while non-secured nodes would process messages from secured nodes but only to create asymmetrical links which disappear shortly thereafter. The coexistence of the two networks would only have the effect of producing a larger bandwidth consumption.
Securing the OLSR protocol involves modifying some parts of its basic functioning.
In brief, to compute a signature corresponding to a control message, the following protocol is used:
Then, the node sends the packet, or repeats the protocol for another control message before sending the packet.
The Duplicate Set of the standard OLSR is modified to include a new field D_timestamp. This field stores the value of the Timestamp field, once the matching between the SIGNATURE message and the control message has been found. The D_timestamp field is filled with the same value for the control message and its SIGNATURE. Incoming messages are recorded in the Duplicate Set as usual.
Upon receiving a control message with its SIGNATURE message, a node processes both. The protocol is outlined as follows:
To fit the secured infrastructure, some modifications also need to be made to the packet processing algorithm described in the standard specifications [31]. We briefly describe these modifications. A receiving node must process an incoming packet following this algorithm:
Else if the message is of another Message Type that you implement, then
Erasing the Duplicate Tuple purporting to bad messages (i.e. with a stale timestamp or an invalid signature) ensures that only good messages in the Duplicate Set are kept track of. This to avoid a DoS attack carried out by a malicious node that floods the network with junk messages not coupled to a signature message (or coupled to an invalid signature message). These junk messages fill the Duplicate Set of receiving nodes, therefore causing receiving nodes reject valid messages that bear the same MSN as a previously received junk message.
Adding a digital signature to all control messages guarantees message authentication or integrity, as unsigned control messages coming from alien nodes are discarded. Table 5.3 shows the resilience of this security architecture to attacks, provided that any node owning a key respects the protocol (i.e. there are no compromised nodes; for a discussion on compromission of nodes, please refer to Chapter 8).
Here we evaluate the transmission overhead of this signature protocol, compared to the standard OLSR. To give an example, we use two cryptographic schemes: a symmetric algorithm, HMAC-MD5, which results in a 128-bit digest; and an asymmetric algorithm, DSA, which results in a 320-bit signature. We do not take into account the computation overhead, i.e. the time expended in signature generation and verification, as they are machine-dependent. The computation speed is evaluated in Section 6.2.1.
The size of a HELLO message varies depending on the number of advertised neighbor nodes and on their link/neighbor status. This is because neighbors of the same link/neighbor status are listed under the same group of Neighbor Type and Link Type (identified by the Link Code field), and 32 bits are added for each new advertised group. There are 11 valid values for the Link Code field as combinations of Neighbor Type and Link Type.
Therefore, the length of a HELLO message varies greatly depending on network density, neighbors’ distance, and nodes’ speed. This makes difficult choosing a sample. For instance, we may speculate that, amongst n advertised neighbors, the number of different link/neighbor status is half of the number of advertised nodes, obtaining the following function for the “common” HELLO size: 32 + 48n bits.
We observe that the size of a HELLO message advertising n neighbor nodes is bounded by the following limits:
From these numbers we can compute (as an arithmetic mean) the average size of a HELLO:
The average OLSR neighborhood counting from 9 to 12 nodes, we can re-average the results to obtain a linear function. We are conscious that this gives a roughly approximated value, however it is sufficient to give an idea of the message size. (This value coincides with the “common” HELLO function for n = 13.)
We obtain the following result:
HELLO: 136 + 40n bits
The size of a TC message advertising n neighbor nodes is:
TC: 32 + 32n bits
These are the sizes of each control message, without the message header. Considering also the IP header (160 bits), the UDP header3 (64 bits), and the OLSR packet header (32 bits + 96 bits per message), the resulting packet lengths including all headers are:
HELLO (packet): 488 + 40n bits
TC (packet): 384 + 32n bits
These are the sizes of a packet containing only one HELLO or TC. We assume that the IP datagram is not fragmented, and that node addresses are in IPv4 format.
The SIGNATURE message being 32 bits in size plus the size of the Signature field, the sizes of a packet containing a signed HELLO/TC message are:
HELLO + SIGNATURE HMAC-MD5 (packet): 744 + 40n bits
HELLO + SIGNATURE DSA (packet): 936 + 40n bits
TC + SIGNATURE HMAC-MD5 (packet): 640 + 32n bits
TC + SIGNATURE DSA (packet): 832 + 32n bits
We assume that each HELLO/TC message and its companion SIGNATURE message are sent together in the same OLSR packet, and that the packet does not contain other messages. This is a “worst case” scenario, as including more control messages in the same packet, along with the signatures of these messages, would reduce the overhead.
Figure 5.3 and Figure 5.4 show the diagrams comparing the packet overhead, full headers included, for unsecured and secured HELLO/TC messages. The figures compare the size (drawn as a line for better readability) of a packet containing a HELLO/TC with the size of a packet containing a HELLO/TC plus its SIGNATURE.
An estimation of a node’s flowrate, for both the standard OLSR and OLSR with signatures, gives the following figures:
Standard OLSR: 558 bit/sec
OLSR with HMAC-MD5 SIGNATURE: 738 bit/sec
OLSR with DSA SIGNATURE: 872 bit/sec
We utilize as model a node advertising 9 neighbors (an average neighborhood size) in its HELLO/TCs. The node broadcasts a HELLO every 2 seconds, and a TC every 5 seconds. The model assumes that the node has one interface, so that MID and HNA messages are not emitted. Each OLSR packet contains one HELLO or TC; plus, in the secured version, its associated SIGNATURE message. These values include the computation of IP, UDP, and OLSR packet headers, with all the assumptions made above.
We analyse here the overhead for a whole OLSR packet containing a HELLO, comparing the overhead of OLSR with SIGNATURE with that of other security solutions: Secure OLSR [60] and MAE [128]. Results are shown in Table 5.4. We assume an average neighborhood of 9 nodes. The results for MAE concern messages not including CERT objects. A quantity of 352 bits has been added to the figures regarding MAE to include the IP, UDP, and OLSR packet headers; these figures are given for a network from 10 (min) to 1000 (max) nodes [127].
