Once that the security architecture has been designed in terms of which routing protocol to use, it is necessary to precise the requirements that a cryptographic infrastructure must satisfy in order to be usable.
As illustrated in Section 2.1, symmetric cryptography is fast and light for encryption and digesting, while asymmetric cryptography is efficient for signature and multiple key management.
Asymmetric algorithms offer many advantages in the securing process of an ad hoc network. However, these ciphers are unsuitable when the nodes are unable to verify asymmetric signatures quickly enough, or when network bandwidth is insufficient.
In a generic way it is desirable that the signature algorithm used in ad hoc networks has these characteristics:
The same applies for a hashing algorithm, with the remark that generation and verification of the digest are the same operation.
An extremely strong algorithm is usually not required; the algorithm should be strong enough only to protect the exchanged messages until the next key renewal. In this point of view, a smaller key may be suitable.
Choosing which cryptographic scheme to use for the protection of the messages is not an easy task. The choice depends largely on the requirements: whether we want to identify messages from each node (i.e. ensure non-repudiation) or just guarantee the integrity of messages – hence if we have to use asymmetric key pairs or just a symmetric key; available techniques for key distribution; computational complexity; robustness against different kind of cryptanalysis; size of the signature or digest; required time for signature generation and verification, or digest generation; and more. Furthermore, once the requirements are set, an algorithm can be carefully implemented in software and/or dedicated hardware in a way to perform better than another. With this in mind, comparing the different known algorithms has sense only if all-purpose hardware is employed. The cipher should be chosen once the requirements are clear, and while looking both at the algorithms and the software and hardware available.
Asymmetric algorithms eligibles for use in ad hoc networks may include RSA, DSA, and ECNR. If a symmetric cipher must be used instead, a good choice would be HMAC with MD5 or SHA-1, i.e. HMAC-MD5 or HMAC-SHA1. Note that the MD5 hash function has been broken i.e. collisions have been found [36, 109, 156]; however, this does not compromise the security of HMAC-MD5.
For informational use, we publish a list of benchmark tests on the Crypto++ 5.2.1 Library1, a free C++ class library of cryptographic schemes. The speed results for the different ciphers are shown in Table 6.1, and signature/digest lengths of these ciphers are shown in Table 6.2.
We ran the benchmarks on the following machines: Intel i486 133 MHz, Intel Pentium III 1 GHz, and Intel Pentium 4 2.8 GHz. All benchmarks were computed on algorithms compiled with gcc 3.x.x and ran under Linux, kernel version 2.4. Columns marked with a † are relative to the optimized version of the Crypto++ Library, compiled with the gcc -O9 flag.
|
|
|
|
The following notes are excerpted from Crypto++’s documentation.
Schemes marked with the symbol ‡ use precomputation; values are looked up from a table of 16 precomputed powers of each fixed base to make the exponentiation operation faster.
The implementations of RSA and ECNR follow the IEEE P1363 [76, 77] standard. RSA uses 17 as the public exponent, while DSA uses a 160-bit long value for q. ECNR is done over the Galois field GF(p) and GF(2n): operations in GF(2n) are accomplished using trinomial basis and, compared to the other algorithms, Crypto++’s implementation of ECNR over GF(2n) is less optimized.
The generation of a HMAC-MD5 hashing is done over an average HELLO and TC signed message advertising 9 neighbors, as reported in Section 5.4.
With reference to the problematics explained in the previous chapters, asymmetric cryptography appears to be an efficient model under many aspects. However, applying this model to an ad hoc network raises several questions and difficulties. This because the deployment of a Public Key Infrastructure includes the creation of a system for key distribution, which is often incarnated under the form of a centralized Certification Authority. However, the dependence by a centralized authority does not match very well the architecture and philosophy of an an ad hoc network, where all nodes are independent and mobile. For instance, it is highly unlikely that any node is able to connect to the CA at any time. Furthermore, a centralized entity raises a problem concerning network weaknesses; this constitutes in fact a vulnerable point, which opens the door to Denial of Service attacks or compromission of the entire network. This is a problem in itself, and even in a wired network the solution is not trivial. The state of the art includes several solutions that have been proposed for key management, as an alternative to a centralized TTP.
The burden of a Certification Authority may be shared amongst many parties by using threshold cryptography [143, 90]. Very first threshold schemes have been studied by Shamir [141].
A (n,z) threshold cryptography scheme (with n ≥ z) allows n parties to share the ability to perform a cryptographic operation, such as a digital signature, which can be done jointly by any z parties, where the same operation is infeasible for a group of z - 1 or less parties. For a network of n or more nodes, the CA’s secret key is divided into n shares, and each share is assigned to a node of the network. Each of the n nodes then compute a partial signature for a certificate and submit its partial signature to a “combiner” node; after receiving z partial signatures, the combiner is able to generate a correct signature for the certificate. This scheme therefore tolerates up to z - 1 compromised nodes.
A share refreshing system [165] allows the nodes to regenerate new shares, protecting the network against an attacker that may compromise more than z - 1 nodes, one after each other, over time. Another optimization called dynamic coalescing [100] deals with the problem of contacting enough nodes at the same time in an ad hoc network, whose topology is by its very nature constantly mutating.
The threshold cryptography scheme has been implemented in a wired environment with the COCA (Cornell Online Certification Authority) framework [166] and in an ad hoc wireless network with MOCA (MObile Certification Authority) [162]. There exists also an implementation for the OLSR framework [34].
Čapkun et al. propose a public-key management system [151, 69] in which no CA exists: certificates are issued by the users themselves, which build and maintain a local certificate repository. For A to verify the authenticity of B’s public key, A must try to find a certificate chain from A to B in the repository build up from the merging of A’s and B’s local repositories. This infrastructure is based upon the analysis [152] of the PGP [167] certificate graph (web of trust). The PGP trust graph exhibits the small-world property, i.e. it has a small diameter and is highly clustered.
Identity-based encryption (IBE) [47] is a form of public key cryptography in which the public key of any participant is derived from the identity, or any other intrinsic quality, of the participant itself. For instance, the public key of a node can be its IP address. In this way there is no need for a CA, as a public key is bound unambiguously to a specific participant. Identity-based encryption has also other interesting properties, such as simplifying key revocation, key delegation, and user credentials management.
Identity-based encryption requires nonetheless the presence of a Trusted Third Party, called Private Key Generator (PKG), which firstly generates the master key. A node communicates via a secure channel with the PKG, requesting the private key corresponding to its identity – its IP address in the previous example. The node can afterwhile use its private key to decrypt messages sent to it.
Shamir was the first to concoct identity-based cryptosystems [142]. After him, Boneh and Franklin [16] designed an efficient and secure IBE scheme, which was further ameliorated by Lynn [101] with the addition of message authentication. Lynn’s scheme guarantees that the integrity of the message is preserved, serving as a digital signature scheme.
Perhaps the easiest solution at all is to require that a node accepts a key only at the bootstrap, possibly manually (by direct contact). This is called imprinting by Stajano and Anderson [144], with reference to ethology: imprinting is the phenomenon which makes a duckling emerging from the egg choose the first seen animated object as mother. Another system for key renewal can subsequently prevent keys becoming stale. This solution is used by Balfanz et al. to provide pre-authentication on a location-limited wireless channel [7].
Some schemes relies on probabilistic key distribution methods on a distributed environment to establish pairwise keys [41, 97]. In these schemes, each node picks up randomly a certain number of keys from a key pool, so that any pair of nodes has a certain probability to share at least one same key.
In a key agreement protocol, two (or more) parties derive a shared secret key from information contributed by each party and exchanged over a channel that does not need to be secure. Eavesdropped information does not lead to disclosure of the secret key.
The Diffie-Hellman key agreement protocol [35] is the first public key algorithm invented. Its security comes from the fact that computing exponentiation in a finite field is easy, while the inverse operation of calculating discrete logarithms in unfeasible. The original DH key exchange protocol is designed for two parties, but it can be extended to three or more parties (generalized Diffie-Hellman). This extension leads to the Group Key Agreement protocols [146, 12, 6].
The generalized DH protocol may therefore be employed to establish keys in an ad hoc environment; it is used for instance in SRP. The CLIQUES family of protocols [147, 161] for authenticated group key distribution is based on Diffie-Hellman. In the simplest form of the CLIQUES protocol, the computation of the key proceeds from node to node, the last node broadcasting the result to allow the other nodes to generate the final key.
We outline two simple PKIs for OLSR. They both serve the purpose of making public keys available to nodes in the network in a way such that the authenticity of the keys can be trusted. The two PKIs differ mainly in that the first is proactive, in the way it aims at diffusing periodically public key information to nodes in the network, while the second is reactive: nodes request keys only when needed.
This PKI operates with three classes of nodes:
As an option, it is also possible to use the PKI infrastructure for time synchronization, and have the signing authority periodically distribute the signed time.
Each node that wishes to participate in the network is required to register its public key with a signing authority. The signing authority will issue certificates periodically, which will then be broadcast to the entire network. Nodes receiving the certificates will store these for a specified amount of time, after which they expire. Hence periodic refresh of certificates is required.
No explicit mechanisms for revoking keys is presented. To facilitate key revocation, certificate messages may be equipped with a sequence number associated with the set of keys advertised. Whenever the set changes (when keys are added or removed) the sequence number is incremented, and included in following certificate messages. Upon receiving a certificate message the nodes can distinguish between older and newer information, and remove expired keys. In order to counter possible replay attacks, timestamps should be employed.
While we could foresee to use this architecture to reject messages from untrusted nodes, this is an approach that must be carefully reviewed, as it is proven that it leads to a deadlock at network initialization. In fact, at the bootstrap, before the signing authority start distributing certificates, all nodes are untrusted; if their control messages are rejected, then formation of the network will never take place, and without network, the certificates cannot be spread to nodes. Next we present a detailed discussion of the problem and of the proposed solution.
From the perspective of network connectivity, the primary aim is to ensure that false topology information is not spread amongst the nodes. This translates into protecting the integrity of OLSR’s most important feature: the creation and relaying of TC messages through MPRs. Therefore, a node should:
When node A selects node B as MPR, A gives to B the responsibility for the A-B link. This responsibility is fulfilled only if B is trusted; otherwise, there is an hazard of B performing incorrect traffic relaying, as described in Section 3.2.
When node A is selected as MPR by node B, A assumes the responsibility for the contents of TC messages coming from B. If B is not trusted, the hazard is that it could inject false TC messages in the network. This is an instance of incorrect traffic generation. The same happens when node A accepts TC messages originating from node B, except that in this case the hazard is circumscribed to A only.
The situation is similar when node A forwards broadcast messages from node B. If B is not trusted, it could maliciously generate excessive amounts of broadcast traffic that, once flooded to the network, may consume excessive resources and potentially prevent transmission of legitimate traffic.
The simplest possible mechanism to keep untrusted nodes out of the network would be a rule stating: “A message sent by an untrusted node is silently discarded and neither processed nor forwarded.” However, while simple, this condition is too restrictive and not applicable. If all nodes require that all traffic they receive must be signed and verified, accepting therefore only traffic from trusted nodes, this would lead to a deadlock problem on network initialization, when public key certificates start being spread around.
In fact, upon network initialization, no node know any public keys other than that of the signing authority (and, of course, their own). Disregarding control traffic from the signing authority, all nodes will by default ignore control traffic from each other. Thus, no nodes will select MPRs, and no broadcast messages will be forwarded. The only node which may be selected as MPR is the signing authority itself. Control traffic from the signing authority will be accepted by its neighbors since they know the public key of the signing authority in advance; until the signing authority starts broadcasting certificate messages, no network formation will take place. Unless special provisions are made, only neighbor nodes of the signing authority will ever receive the broadcast certificates: since successful verification of a signature is a criteria for accepting any control messages, 2-hop neighbors of the signing authority will never accept control messages from 1-hop neighbors of the signing authorities. This implies that a symmetric link between 1-hop and 2-hop neighbors of the signing authority will never be established. The signing authority will therefore never select MPRs and, subsequently, its certificates will never be broadcast into the network.
To avoid this situation and enable network initialization, special provisions for accepting some control messages without validation of signatures must be made. The desired goal is to allow MPR flooding to take into account the fact that broadcast messages should be able to reach also untrusted nodes in the network. Hence the following additional conditions apply:
The 2-hop neighborhood of a node will contain both trusted and untrusted nodes. MPRs are selected from among the trusted nodes such that, as much as possible of, all nodes in the 2-hop neighborhood are covered. This ensures that a maximum of untrusted neighbors of trusted nodes will be reached by MPR flooding, as they are covered by at least one MPR.
Thus, upon network initialization, the signing authority will transmit its certificate which will be received by its 1-hop neighbors. Following HELLO message exchange, the 1-hop neighbors will accept the untrusted 2-hop neighbors as symmetric but not select MPRs among them. The signing authority will then select MPRs from among the 1-hop neighborhood such that the next broadcast certificate will reach the 2-hop neighbors. The scheme follows, in such a way that certificates will, upon network initialization, propagate from the signing authorities and towards the edges of the network.
Note that some information coming from untrusted nodes is only used to handle untrusted nodes. MPR selection, etc. is performed only among trusted nodes, as MPR selection information is diffused only about trusted nodes.
We assume the same framework as in the proactive PKI. Two new types of messages are introduced: Key Request and Key Reply.
A Key Request is a message from a node A, containing a nonce NA initialized with random values for each request and a list of nodes Bi for which the public key is needed: A → all : {A,NA,B1,…,Bn}A.
Upon receiving such a request message, a signing authority U:
Upon receiving such a reply message, the originating node A performs the following checks:
If those checks succeed, node A finally updates its public key database with the newly acquired keys.
In order to ensure proper delivery of Key Request and Key Reply messages,
pure flooding is used instead of the standard MPR forwarding. As with the
proactive PKI, considerations regarding key revocation are not presented. These
features, however, can be fashioned through lifetime of the public keys and
periodic refreshing through renewed request-reply cycles.