Securing wireless ad hoc networks: Part 2 - Key Establishment and Authentication -

Securing wireless ad hoc networks: Part 2 – Key Establishment and Authentication

Key establishment and authentication are the building blocks of networksecurity. Also, these two are also probably the toughest problem innetwork security. In the following two sections we look at the basicconcepts of threshold cryptography which forms the basis of most keyestablishment and authentication schemes that are being discussed formultihop ad hoc networks.

Threshold Secret Sharing
One of the most prominent solutions to the problem of key establishmentand authentication is the use of certificates. Any two nodes in anetwork may secure (provide confidentiality, data integrity,authentication and nonrepudiation) their communication usingcertificates. However, issuing and validating certificates requires thedeployment of public key infrastructure (PKI).

The use of PKI relies on a trusted third party (the certificateauthority (CA)) to verify the identity and authenticity of other nodes.Therefore, the use of PKI and PKC helps create a trust model in thenetwork where all nodes inherently trust the CA. Note that this meansthat if a node trusts the CA, it will also trust the identity ofanother node if the CA verifies this identity.

Let's do a short recap of the role of CA in a PKI. Supposing thatBob wants to talk to Alice using PKC, the following sequence takesplace:

1. Bob asks theCA for Alice's public key.

2. The CAresponds back with a certificate of the form KiCA {Alice'spublic key is KwA }. In other words, the CA sends the message”Alice's public key is KwA ” encrypted with its own privatekey.

3. When Bobreceives this message, it uses the CA's public key (KwCA ) todecrypt the certificate and obtain Alice's public key.

The trust model in the system is this: since CA's private key isknown only to the CA, no one can forge the certificate and claimanother key as Alice's public key. This allows Bob to obtain Alice'spublic key securely. Once Bob has Alice's public key, he can easilyauthenticate any node claiming to be Alice by issuing a challenge(RAND) and checking the received response (SRES = KiA (RAND))using Alice's public key (Is RAND = KwA (KiA (RAND)?).

Note that the property of the CA which makes it the trusted node isthat only the CA knows its own private key KiCA . Therefore,the security of the whole system is based on ensuring that the KiCA isknown only to the CA.

We can therefore also refer to this private key, KiCA as the systemsecret. Since the PKI by definition requires the existence ofinfrastructure which is unavailable in ad hoc networks, the thresholdsecret sharing approach tries to adapt the PKI model to an ad hocenvironment by creating a virtual certificate authority. In ad hocnetworks since there is no single CA which is always accessible,5 whatis needed is a virtual CA. (Or atleast not always easily and timely accessible. )

This virtual CA is formed by distributing the CA's functionality toeach local neighborhood. This noncentralized approach also has theadvantage that there is no single point of security compromise. (Note that by distributing the role of aCA, the scalability problems of a centralized approach are alsoresolved.)
Unfortunately, the role of distributing the CA among multiple physicalentities is easier said than done. Realize that the CA is characterizedby the possession of the system secret, KiCA . In ourdistributed-CA model, who would possess this system secret? A trivialsolution is to have each of the S nodes which form the virtual-CApossess the system secret.

However, this approach has several problems. By having each of the Snodes posses the system secret, we have effectively created multipleinstances of the same CA and not a distributed CA as we had intended.This approach also compromises the system secret since it is availableto multiple nodes and therefore more vulnerable to compromise.

Figure8.2: Bluetooth Networks

To achieve a virtual CA, we turn to threshold cryptography, alsoknown as threshold secret sharing, which works by distributing trustamong multiple nodes. In this approach, the system secret is dividedinto Q parts such that any S (< Q) of these parts are enough tocarry out a cryptographic operation that would have been possible withthe system secret. (There are variousapproaches to achieve this division but we do not go into the detailsfor reasons of brevity. )

Note that to carry out a cryptographic operation at least S parts ofthe system secret are required. A system employing thresholdcryptography is therefore defined by the use of two parameters: Q andS. Q nodes posses shares of the system secret and any S of these nodescan work in coalition as a CA.

This means that the system can tolerate a compromise of up to S-1nodes without the security of the whole system being compromised. Wenow describe how threshold cryptography is extended to build a virtualCA in an ad hoc environment. We first divided the system secret, KiCA (the private key of the CA) into Q secret shares (k1 , k2 ,., kQ ).

A single share of the system secret by itself cannot be used toprovide any CA service. However, if S (< Q) such shares arecombined, they can be used to provide CA services. Each of these sharesis assigned or distributed to a server. (There is an interesting initializationproblem here which will be discussed later in this series. )

The term server is used to refer to a node which will participate informing the virtual CA. Servers in an ad hoc data network have thefollowing special properties:

1. A server canbe initialized securely with its share of the system secret whichallows them to act as the server.

2. A serverknows the public keys of all nodes which can join the ad hoc network.Now, consider an ad hoc network where node A wishes to communicate withnode B securely.

To do so, A needs to authenticate B. A could simply use achallengeresponse system with PKC as follows:

1. A sends achallenge (random number) to B

2. B encrypts thechallenge with its private key (KiB ) to generate a responseand sends it back to A.

3. A decryptsthe response with B's public key (KwB ) and compares thedecrypted value with the challenge and if the two match, A concludesthat it is communicating with B.
The security of this system lies in the fact that A reliably knowsthe public key of B. In a PKI, this is achieved by using a signedcertificate from the CA. In ad hoc networks using thresholdcryptography, when A needs to find out the public key of B, it sendsout a broadcast message to its neighbors requesting a certificate forB.

Each server which hears this message generates a partial certificatewith its partial system secret kx and sends it to acombiner. A combiner is a server which takes on the responsibility ofcombining S partial certificates and generates a complete certificate.Any server can take on the role of a combiner.

A server does not require any extra capabilities to be a combiner.Conversely, a server does not gain any extra information about thesystem secret by being a combiner. Once the combiner has generated thecomplete certificate by combining S partial certificates, it can sendthe certificate to A.

Now, let's look at the security of an ad hoc network using thresholdcryptography to implement a virtual CA. What happens if a server in thenetwork is compromised?

This server can then be used by an adversary to generate anincorrect partial signature. When the combiner uses this invalidpartial certificate to generate a complete certificate, it wouldobviously lead to the complete certificate being invalid.

Fortunately, the public key of the virtual CA (KwCA ) isknown to all nodes in the system. (That the public key of the CA iswell known to all nodes in the system is an underlying assumption ofevery PKI system.)

The combiner can therefore use the public key to verify the validityof the complete certificate that it has generated. This can be done,for example, by decrypting the certificate (which has been encrypted using KiCA) using KwCA andverifying that the information in the certificate is correct.

If the combiner determines that the complete certificate is invalid,it can use another set of S partial certificates to generate a validcomplete certificate. This means that as long as the combiner hasaccess to at least S valid partial signatures it would be able togenerate a valid complete certificate.

For this reason, the value of S should not be too large. Note thatif S (or more than S) servers are compromised, the security of thewhole system is compromised. For this reason the value of S should notbe too small. These two constraints make the value of S an engineeringtrade-off.

Consider what happens, however, if the combiner itself iscompromised. This is a much more potent threat since it is the combinerwhich is finally responsible for combining the partial certificates andissuing the complete certificate. A compromised combiner can thereforeinject invalid certificates into the system.

One solution is to assign the role of a combiner to a server whichis more secure than other nodes in the system and thus has a lowerprobability of being compromised. Since this is not always possible inan ad hoc environment, another approach is to use multiple combiners.In this scenario each combiner issues a complete certificate using itsset of partial certificates. The nodes in the system have now multiplesources to get the certificate they want and can use a majority-basedscheme to ensure the validity of a certificate.

To protect against attacks where an adversary may compromisemultiple servers over a long period of time, the use of secret shareupdates has been proposed. In this approach, the secret share of eachserver has to be periodically updated in collaboration with otherservers in the system. Since the secret share's validity is limited intime, the adversary must compromise enough servers within a period offinite time to launch a successful attack.

The use of threshold cryptography to create a virtual CA makes twoimportant assumptions regarding system initialization. First, it isassumed that Q servers can be initialized securely with theirrespective shares of the system secret. Second, it is assumed that eachserver can be configured securely with the public keys of all nodeswhich can potentially join the ad hoc network.

Both these assumptions basically boil down to the single assumptionthat the servers can be initially configured over a secure channel.This important assumption can sometimes act as a limitation inproviding security in ad hoc networks.

One approach which has been proposed to reduce the dependency of thesystem on this assumption is localized self initialization. In thisapproach we still require that the first Q servers be initialized overa secure medium. However, once the first Q servers have beeninitialized, they can then collaborate to elect new servers.

This is achieved by having at least S servers use their secret share(kx ) to generate a partial secret share (ssx ).These partial secret shares are then combined to generate a new secretshare which can be assigned to the node which is being initialized as aserver. Let's do a short recap of how a virtual CA works in ad hocnetworks.

As is true in any PKC system, each node in the ad hoc network has aprivate-key, public-key pair which it uses to secure communication withother nodes. To certify its keys, each node X, must have a validcertificate issued by the CA of the form KiCA (X, KwX ,Tsign , Texpire ).

This certificate basically says that the CA certifies (by signing the certificate using KiCA) that the public key of node Xis KwX and this key is valid between times Tsign and Texpire . Such certificates which are signed using thesystem secret (KiCA ) are inherently trusted by all nodes inthe network. It is these certificates which are then used to providevarious security features in the network.

So, the aim of a virtual CA is to issue certificates signed usingthe system secret. The virtual CA is implemented as multiple physicallyseparate nodes (servers) none of which knows the system secret (KiCA )but each one of them knows a share of the system secret. When a nodewants a certificate, it sends out a broadcast request. The servers thenco-operate to supply the certificate thus providing security in thesystem.

Confidentiality and Integrity
Previously, we discussed how key establishment and authentication maybe provided in multihop ad hoc networks. These two security servicesform the backbone of providing security in any network.

Once two nodes in a network have authenticated each other andsecurely established a security context (that is, securely established keys),encryption and integrity algorithms can be used to securecommunication.

This part of system security is relatively simple. What is needed isthe selection of algorithms and modes suitable for the environment inwhich the network is expected to operate.

Since the nodes in an ad hoc network environment usually havelimited processing power and limited battery lifetimes, most ad hocnetworks would prefer a stream cipher for encryption and an integrityalgorithm which is not too computation intensive.

There are many stream ciphers to choose from as long as we keep inmind that there are some caveats while using stream ciphers in awireless environment (as WEPdemonstrated ).


One of the most popular ad hoc standards today is Bluetooth. Some ofthe salient features of Bluetooth are as follows:

Wireless ad hoc networking technology.
Operates in the unlicensed 2.4 GHz frequency range.
Geographical coverage limited to personal area networks (PAN).
Point-to-point and point-to-multipoint links.
Supports synchronous and asynchronous traffic.
Concentrates on single-hop networks.
Frequency hopping spread spectrum (FHSS) with gaussian frequencyshift keying (GFSK) modulation at the physical layer.
Low power and low cost given important consideration.
Adopted as the IEEE 802.15.1 standard for physical layer (PHY) andmedia access control (MAC) layers.

The Bluetooth standard limits its scope by dealing only withsingle-hop ad hoc networks with limited geographical coverage (PAN). Inthe previous sections we saw that multihop ad hoc networks present aunique set of challenges which are still an active area of research.

The Bluetooth standard brings ad hoc networks to the commercialforefront by concentrating on single-hop PAN ad hoc networks. Removingthe multihop feature from ad hoc networks makes things a lot simpler.

The Bluetooth Special Interest Group (SIG) was founded in 1998 withthe aim of developing Bluetooth as a short-range wirelessinter-connectivity standard. (TheBluetooth standard is also being accepted as the IEEE 802.15 standard .)

In other words, Bluetooth deals with ad hoc networks whosegeographical coverage is limited to PAN. Typical applications ofBluetooth today include connecting a wireless headset with its cellphone, interconnecting the various components (keyboard, mouse,monitor, and so on) of a PC, and so on.

Before we get into the details of Bluetooth and its security, it isimportant to emphasize that Bluetooth is by no means the only ad hocnetwork standard. Another popular ad hoc standard is 802.11 in its IBSSmode. Since Bluetooth networks have been so commercially successful, webriefly look at Bluetooth security .

Bluetooth Basics
A typical Bluetooth network, called the piconet, is shown in Figure 8.2 above . Each piconet hasone master and can have up to seven slaves. (To be precise, a piconet has one masterand up to seven active slaves. There is no limit on the number ofslaves in a piconet which are in “park” or “hold” state. Thisdistinction is irrelevant from a security perspective however .)

Figure8.3: Piconets and Scatternets in Bluetooth

Therefore, there can be at most eight devices in a piconet. A slavecan communicate only with the master and a master can obviouslycommunicate with any of the slaves. If two slaves wish to communicatewith each other, the master should relay this traffic. In effect, wehave a logical star topology in a piconet, with the master device atthe center.

Comparing the piconet to a 802.11 network, the piconet is theequivalent of a BSS (though with amuch smaller geographical coverage ), the master device is theequivalent of the AP (except that itis not connected to any distribution system ) and the slavedevices are the equivalent of the Stations (STAs).

A Bluetooth device may participate in more than one piconetsimultaneously, as shown in Figure8.3 above. In such a scenario, it is possible for the devices intwo piconets to communicate with each other by having the common nodeact as the bridge and relay the inter-piconet traffic.

The two piconets are now joined together and form a scatternet. Eventhough scatternets are theoretically possible, they are rare incommercial deployments since they pose tough practical problems likerouting and timing issues.

The Bluetooth standard concentrates mostly on single-hop piconetsand we limit our discussion to piconet security. Scatternets (and theirsecurity) are an active area of research and involve a lot of thesecurity issues.

(Editor's note: For more onembedded security, check out the cover story in the Octoberissue of Embedded Systems Design Magazine: Embedded systems security has moved to theforefront,” as well as “Employ a secure flavorof Linux.”

Next in Part 3: “Dealing withBluetooth security .”
To read Part 1, go to “Routing in multihop ad hoc networks.”

Thisarticle is excerpted from “Bulletproofwireless security,” by Praphul Chandra, with permission fromElsevier/Newnes which hold the copyright. It is a part of thepublisher's Communications Engineering Series.

Praphul Chandra currently works asa senior research scientist at HPLabs, India, which focuses on “technological innovation foremerging countries.”

Recent articles on security
Securingwireless MCUs is changing embedded systems design
Stateof security technology: embedded to enterprise
Securiingmobile and embedded devices: encryptioon is not security
Guidelinesfor designing secure PCI PED EFT terminals
Overcomingsecurity issues in embedded systems
Buildingmiddleware for security and safety-critical applications
Securityconsiderations for embedded operating systems
Diversityprotects embedded systems
Aproactive strategy for eliminating embedded software vulnerabilities
Understandingelliptic curve cryptography
Securingad hoc embedded wireless networks with public key cryptography

Aframework for considering security in embedded systems
Calculatingthe exploitability of your embedded software
Badassumptions lead to bad security

Securingembedded systems for networks
Implementingsolid security on a Bluetooth product
Smartsecurity improves battery life
Howto establish mobile security
Ensuringstrong security for mobile transactions
Securingan 802.11 network

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.