Key establishment and authentication are the building blocks of network
security. Also, these two are also probably the toughest problem in
network security. In the following two sections we look at the basic
concepts of threshold cryptography which forms the basis of most key
establishment and authentication schemes that are being discussed for
multihop ad hoc networks.
Threshold Secret Sharing
One of the most prominent solutions to the problem of key establishment
and authentication is the use of certificates. Any two nodes in a
network may secure (provide confidentiality, data integrity,
authentication and nonrepudiation) their communication using
certificates. However, issuing and validating certificates requires the
deployment of public key infrastructure (PKI).
The use of PKI relies on a trusted third party (the certificate
authority (CA)) to verify the identity and authenticity of other nodes.
Therefore, the use of PKI and PKC helps create a trust model in the
network where all nodes inherently trust the CA. Note that this means
that if a node trusts the CA, it will also trust the identity of
another node if the CA verifies this identity.
Let's do a short recap of the role of CA in a PKI. Supposing that
Bob wants to talk to Alice using PKC, the following sequence takes
place:
1. Bob asks the
CA for Alice's public key.
2. The CA
responds back with a certificate of the form KiCA{Alice's
public key is KwA}. In other words, the CA sends the message
"Alice's public key is KwA" encrypted with its own private
key.
3. When Bob
receives this message, it uses the CA's public key (KwCA) to
decrypt the certificate and obtain Alice's public key.
The trust model in the system is this: since CA's private key is
known only to the CA, no one can forge the certificate and claim
another key as Alice's public key. This allows Bob to obtain Alice's
public key securely. Once Bob has Alice's public key, he can easily
authenticate 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 is
that only the CA knows its own private key KiCA. Therefore,
the security of the whole system is based on ensuring that the KiCA is
known only to the CA.
We can therefore also refer to this private key, KiCA as the system
secret. Since the PKI by definition requires the existence of
infrastructure which is unavailable in ad hoc networks, the threshold
secret sharing approach tries to adapt the PKI model to an ad hoc
environment by creating a virtual certificate authority. In ad hoc
networks since there is no single CA which is always accessible,5 what
is needed is a virtual CA. (Or at
least not always easily and timely accessible.)
This virtual CA is formed by distributing the CA's functionality to
each local neighborhood. This noncentralized approach also has the
advantage that there is no single point of security compromise. (Note that by distributing the role of a
CA, the scalability problems of a centralized approach are also
resolved.)
Unfortunately, the role of distributing the CA among multiple physical
entities is easier said than done. Realize that the CA is characterized
by the possession of the system secret, KiCA. In our
distributed-CA model, who would possess this system secret? A trivial
solution is to have each of the S nodes which form the virtual-CA
possess the system secret.
However, this approach has several problems. By having each of the S
nodes posses the system secret, we have effectively created multiple
instances of the same CA and not a distributed CA as we had intended.
This approach also compromises the system secret since it is available
to multiple nodes and therefore more vulnerable to compromise.
Figure
8.2: Bluetooth Networks
To achieve a virtual CA, we turn to threshold cryptography, also
known as threshold secret sharing, which works by distributing trust
among multiple nodes. In this approach, the system secret is divided
into Q parts such that any S (< Q) of these parts are enough to
carry out a cryptographic operation that would have been possible with
the system secret. (There are various
approaches to achieve this division but we do not go into the details
for reasons of brevity.)
Note that to carry out a cryptographic operation at least S parts of
the system secret are required. A system employing threshold
cryptography is therefore defined by the use of two parameters: Q and
S. Q nodes posses shares of the system secret and any S of these nodes
can work in coalition as a CA.
This means that the system can tolerate a compromise of up to S-1
nodes without the security of the whole system being compromised. We
now describe how threshold cryptography is extended to build a virtual
CA 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 to
provide any CA service. However, if S (< Q) such shares are
combined, they can be used to provide CA services. Each of these shares
is assigned or distributed to a server. (There is an interesting initialization
problem here which will be discussed later in this series.)
The term server is used to refer to a node which will participate in
forming the virtual CA. Servers in an ad hoc data network have the
following special properties:
1. A server can
be initialized securely with its share of the system secret which
allows them to act as the server.
2. A server
knows 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 with
node B securely.
To do so, A needs to authenticate B. A could simply use a
challengeresponse system with PKC as follows:
1. A sends a
challenge (random number) to B
2. B encrypts the
challenge with its private key (KiB) to generate a response
and sends it back to A.
3. A decrypts
the response with B's public key (KwB) and compares the
decrypted value with the challenge and if the two match, A concludes
that it is communicating with B.
The security of this system lies in the fact that A reliably knows
the public key of B. In a PKI, this is achieved by using a signed
certificate from the CA. In ad hoc networks using threshold
cryptography, when A needs to find out the public key of B, it sends
out a broadcast message to its neighbors requesting a certificate for
B.
Each server which hears this message generates a partial certificate
with its partial system secret kx and sends it to a
combiner. A combiner is a server which takes on the responsibility of
combining 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 the
system secret by being a combiner. Once the combiner has generated the
complete certificate by combining S partial certificates, it can send
the certificate to A.
Now, let's look at the security of an ad hoc network using threshold
cryptography to implement a virtual CA. What happens if a server in the
network is compromised?
This server can then be used by an adversary to generate an
incorrect partial signature. When the combiner uses this invalid
partial certificate to generate a complete certificate, it would
obviously lead to the complete certificate being invalid.
Fortunately, the public key of the virtual CA (KwCA) is
known to all nodes in the system. (That the public key of the CA is
well known to all nodes in the system is an underlying assumption of
every PKI system.)
The combiner can therefore use the public key to verify the validity
of 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 and
verifying 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 valid
complete certificate. This means that as long as the combiner has
access to at least S valid partial signatures it would be able to
generate a valid complete certificate.
For this reason, the value of S should not be too large. Note that
if S (or more than S) servers are compromised, the security of the
whole system is compromised. For this reason the value of S should not
be too small. These two constraints make the value of S an engineering
trade-off.
Consider what happens, however, if the combiner itself is
compromised. This is a much more potent threat since it is the combiner
which is finally responsible for combining the partial certificates and
issuing the complete certificate. A compromised combiner can therefore
inject invalid certificates into the system.
One solution is to assign the role of a combiner to a server which
is more secure than other nodes in the system and thus has a lower
probability of being compromised. Since this is not always possible in
an ad hoc environment, another approach is to use multiple combiners.
In this scenario each combiner issues a complete certificate using its
set of partial certificates. The nodes in the system have now multiple
sources to get the certificate they want and can use a majority-based
scheme to ensure the validity of a certificate.
To protect against attacks where an adversary may compromise
multiple servers over a long period of time, the use of secret share
updates has been proposed. In this approach, the secret share of each
server has to be periodically updated in collaboration with other
servers in the system. Since the secret share's validity is limited in
time, the adversary must compromise enough servers within a period of
finite time to launch a successful attack.
The use of threshold cryptography to create a virtual CA makes two
important assumptions regarding system initialization. First, it is
assumed that Q servers can be initialized securely with their
respective shares of the system secret. Second, it is assumed that each
server can be configured securely with the public keys of all nodes
which can potentially join the ad hoc network.
Both these assumptions basically boil down to the single assumption
that the servers can be initially configured over a secure channel.
This important assumption can sometimes act as a limitation in
providing security in ad hoc networks.
One approach which has been proposed to reduce the dependency of the
system on this assumption is localized self initialization. In this
approach we still require that the first Q servers be initialized over
a secure medium. However, once the first Q servers have been
initialized, 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 secret
share which can be assigned to the node which is being initialized as a
server. Let's do a short recap of how a virtual CA works in ad hoc
networks.
As is true in any PKC system, each node in the ad hoc network has a
private-key, public-key pair which it uses to secure communication with
other nodes. To certify its keys, each node X, must have a valid
certificate 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 X
is KwX and this key is valid between times Tsign
and Texpire. Such certificates which are signed using the
system secret (KiCA) are inherently trusted by all nodes in
the network. It is these certificates which are then used to provide
various security features in the network.
So, the aim of a virtual CA is to issue certificates signed using
the system secret. The virtual CA is implemented as multiple physically
separate nodes (servers) none of which knows the system secret (KiCA)
but each one of them knows a share of the system secret. When a node
wants a certificate, it sends out a broadcast request. The servers then
co-operate to supply the certificate thus providing security in the
system.
Confidentiality and Integrity
Previously, we discussed how key establishment and authentication may
be provided in multihop ad hoc networks. These two security services
form the backbone of providing security in any network.
Once two nodes in a network have authenticated each other and
securely established a security context (that is, securely established keys),
encryption and integrity algorithms can be used to secure
communication.
This part of system security is relatively simple. What is needed is
the selection of algorithms and modes suitable for the environment in
which the network is expected to operate.
Since the nodes in an ad hoc network environment usually have
limited processing power and limited battery lifetimes, most ad hoc
networks would prefer a stream cipher for encryption and an integrity
algorithm which is not too computation intensive.
There are many stream ciphers to choose from as long as we keep in
mind that there are some caveats while using stream ciphers in a
wireless environment (as WEP
demonstrated).
Bluetooth
One of the most popular ad hoc standards today is Bluetooth. Some of
the 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 frequency
shift 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) and
media access control (MAC) layers.
The Bluetooth standard limits its scope by dealing only with
single-hop ad hoc networks with limited geographical coverage (PAN). In
the previous sections we saw that multihop ad hoc networks present a
unique set of challenges which are still an active area of research.
The Bluetooth standard brings ad hoc networks to the commercial
forefront by concentrating on single-hop PAN ad hoc networks. Removing
the multihop feature from ad hoc networks makes things a lot simpler.
The Bluetooth Special Interest Group (SIG) was founded in 1998 with
the aim of developing Bluetooth as a short-range wireless
inter-connectivity standard. (The
Bluetooth standard is also being accepted as the IEEE 802.15 standard.)
In other words, Bluetooth deals with ad hoc networks whose
geographical coverage is limited to PAN. Typical applications of
Bluetooth today include connecting a wireless headset with its cell
phone, 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 is
important to emphasize that Bluetooth is by no means the only ad hoc
network standard. Another popular ad hoc standard is 802.11 in its IBSS
mode. Since Bluetooth networks have been so commercially successful, we
briefly look at Bluetooth security .
Bluetooth Basics
A typical Bluetooth network, called the piconet, is shown in Figure 8.2 above. Each piconet has
one master and can have up to seven slaves. (To be precise, a piconet has one master
and up to seven active slaves. There is no limit on the number of
slaves in a piconet which are in "park" or "hold" state. This
distinction is irrelevant from a security perspective however.)
Figure
8.3: Piconets and Scatternets in Bluetooth
Therefore, there can be at most eight devices in a piconet. A slave
can communicate only with the master and a master can obviously
communicate with any of the slaves. If two slaves wish to communicate
with each other, the master should relay this traffic. In effect, we
have a logical star topology in a piconet, with the master device at
the center.
Comparing the piconet to a 802.11 network, the piconet is the
equivalent of a BSS (though with a
much smaller geographical coverage), the master device is the
equivalent of the AP (except that it
is not connected to any distribution system) and the slave
devices are the equivalent of the Stations (STAs).
A Bluetooth device may participate in more than one piconet
simultaneously, as shown in Figure
8.3 above. In such a scenario, it is possible for the devices in
two piconets to communicate with each other by having the common node
act as the bridge and relay the inter-piconet traffic.
The two piconets are now joined together and form a scatternet. Even
though scatternets are theoretically possible, they are rare in
commercial deployments since they pose tough practical problems like
routing and timing issues.
The Bluetooth standard concentrates mostly on single-hop piconets
and we limit our discussion to piconet security. Scatternets (and their
security) are an active area of research and involve a lot of the
security issues.
This
article is excerpted from "Bulletproof
wireless security," by Praphul Chandra, with permission from
Elsevier/Newnes which hold the copyright. It is a part of the
publisher's Communications Engineering Series.
Praphul Chandra currently works as
a senior research scientist at HP
Labs, India, which focuses on "technological innovation for
emerging countries."
