30-04-2012, 12:34 PM
Efficient Secure Aggregation in VANETs
Efficient Secure Aggregation in VANETs.pdf (Size: 297.52 KB / Downloads: 24)
ABSTRACT
In VANETs, better communication efficiency can be achieved
by sacrificing security and vice versa. But VANETs cannot
get started without either of them. In this paper, we propose
a set of mechanisms that can actually reconcile these two
contradictory requirements. The main idea is to use message
aggregation and group communication. The first class
of solutions is based on asymmetric cryptographic primitives,
the second class uses symmetric ones, and the third
one mixes the two. We have also evaluated the performance
potential of one technique and arrived at the conclusion that
aggregation in VANETs increases not only efficiency but also
security.
Categories and Subject Descriptors
C.2.0 [Computer-Communication Networks]: General—
Security and protection; C.2.1 [Computer-Communication
Networks]: Network Architecture and Design—Network
communications, Wireless communication.
General Terms
Algorithms, Performance, Security
Keywords
Vehicular networks, Security, Efficiency, Onion signature,
Aggregation, Group communication
1. INTRODUCTION
The recent academic and industrial research on VANETs
has reached the maturity to consider security as a fundamental
building block of any deployable architecture. Several
existing works confirm this development. Yet, all VANET
security solutions are subject to the same founded criticism:
overhead. In fact, the most reasonable choice for
a VANET security architecture is a PKI-supported asymmetric
authentication, in addition to other functions, such
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
VANET’06, September 29, 2006, Los Angeles, California, USA.
Copyright 2006 ACM 1-59593-540-1/06/0009 ...$5.00.
as anonymity. But in this scheme, every message would
have to be signed in order for the receiver to authenticate
it. Although cryptographers have greatly improved the efficiency
of asymmetric algorithms, notably ECC (Elliptic Curve
Cryptography), these still are resource-hungry in terms
of computation and communication. This leads us to the
obvious question: can VANET security be more efficient?
This is the question we will try to answer in this paper.
Most VANET application designers attempt to minimize
costs, sometimes even suggesting to scrap security totally.
On one hand, this can be understood if we consider that
the percentage of attackers will probably be very small. On
the other hand, leaving open breaches in huge networks like
VANETs can lead to devastating results even if there is
only one determined and skillful attacker. This means that
both efficiency and security are essential, though seemingly
contradictory, conditions for the success of VANETs. The
problem we address in this paper is hence finding a tradeoff
between the two. This can be achieved by exploiting several
properties of VANETs that include geographically constrained
paths, vehicle density and high mobility; we will
further discuss these properties in a later section.
In this paper, we explore the approach of secure message
aggregation, the long-time trademark of resource constrained
sensor networks. Roughly speaking, instead of letting the de
facto flooding approach take care of message dissemination
in a VANET, this is delegated only to selected vehicles who
share a similar view of their environment. We will describe
several algorithms for achieving this and compare them with
each other. We will also introduce the concept of onion
signature, which can be considered the counterpart of onion
routing [4]. Relying on realistic simulations, we have come
to the conclusion that VANET security can be more efficient
when using our aggregation mechanisms.
A useful by-product of secure aggregation is the increase
in information dependability. In fact, grouping several messages
provides the receiver with more evidence concerning a
given event. Our simulation results show this effect.
Another aspect that we address is secure group1 formation,
in itself an open problem in VANET research. Hence
we do not claim to provide a complete solution, but rather
a feasible option that takes security into consideration.
The paper is organized as follows. Section 2 overviews
related work. Section 3 describes the system model and addresses
relevant secure group issues. Section 4 presents the
1In this paper, we use the term group in a networking rather
than distributed systems sense. Hence, it can be used interchangeably
with the term cluster.
67
secure aggregation mechanisms. Section 5 studies one of the
proposed techniques using simulations. Section 6 concludes
the paper.
2. STATE OF THE ART
The research on VANET security is still developing. Most
existing efforts on the industrial [2], as well as the academic
[8, 9, 11, 17], side focus on describing the problem statement
and proposing the outline of a general solution for VANET
security. To provide vehicle authentication, all these works
commonly agree on the need for a PKI (Public Key Infrastructure)
and the use of digital signatures. Fewer papers
focus on specific issues such as the detection and correction
of malicious data [5]. The topic of secure aggregation in
VANETs has not been addressed so far, except for a brief
mention in [9] although it was introduced in a sensor networking
sense (e.g., vehicles computing the count of encountered
vehicles). Hence, our paper is the first to study in
detail this topic in VANETs.
The closest reference in literature to secure aggregation
in networks can be found in sensor networking papers. In
[7], Hu and Evans propose using delayed aggregation (at
the second hop rather than the first) and delayed authentication
(by delaying key disclosure) to counter the threat
of false data in the network. Their assumptions of a static
network with pre-established shared secrets (between sensor
nodes and the base station), as well as the key idea of delaying
authentication, make their work unsuitable for VANETs.
The focus of [10] by Przydatek et al. is also on mitigating
the effects of false aggregation results (the so-called stealthy
attack) by using an aggregate-commit-prove mechanism that
involves interactive proofs between the aggregators and the
home server. Their work also introduces the efficiency vs.
accuracy tradeoff. But again, the assumption of a static network
and the use of interactive protocols hamper the use of
their techniques in VANETs. In a similar network setting,
Yang et al. [16] introduce secure hop-by-hop aggregation
by using divide-and-conquer and commit-and-attest mechanisms;
thus, aggregates can be obtained from multiple subgroups
rather than the whole network, reducing the effect
of false data injection attacks in some of these subgroups.
Last but not least, Wagner [15] also seeks to achieve approximate
integrity of data through statistical methods, such as
outlier elimination. This makes aggregation functions resilient
to small changes in sensor observations by attackers.
This approach can be complementary to the techniques introduced
in the following sections, especially to resolve the
group agreement problem described in Section 3.4.2.
3. SYSTEM MODEL
In the following, we present several aspects related to the
core mechanisms introduced in the next sections. These include
relevant VANET properties, geographic routing, group
formation, and the attacker model. Finally, we use these elements
to describe the problem statement.
3.1 Network Model
In this paper, we address only safety related applications.
Each vehicle broadcasts messages to its immediate neighborhood.
In addition to vehicles, the network may include
roadside base stations but these are not pervasive. All entities
are equipped with positioning devices, such as a GPS.
Security provision in VANETs is foreseen mainly by the
means of digital signatures. With the existence of a vehicular
PKI, each vehicle will possess a set of public/private key
pairs that it will use to sign broadcasted safety messages.
This ensures that other vehicles will be able to authenticate
a received message if it includes a digital signature and
the corresponding certificate issued by a CA (Certification
Authority). For the sake of comparison, we will dub this
mechanism the basic scheme throughout the rest of the paper.
3.2 Efficiency-Propitious Properties ofVANETs
VANETs consist of large numbers of vehicles moving at
high speeds over a continent-size network of roads. Most
vehicles are private, which means a lack of a central online
coordinating entity. All this may look like a nightmare
for VANET application designers. But when it comes to
the aggregation mechanisms discussed in this paper, these
properties turn out to be very helpful. In fact, the higher the
density of vehicles, the more accurate the aggregate information.
In addition, VANET safety messages are mainly sent
to all vehicles in a given geographic region rather than to
specific vehicles. In this case, the predefined road topology
makes it easier to route these messages. And the mobility
of vehicles in both directions can also optimize message
delivery.
3.3 Attacker Model
To avoid reinventing the wheel, we refer the reader to
other works [9, 11] for a full discussion of the attacker model.
In the context of this work, we focus on the assumptions
and properties that are directly related to the aggregation
mechanisms introduced later.
Similarly to sensor networks [7, 10, 15, 16], the major
threat that can target specifically VANET aggregation mechanisms
is that of false information dissemination. In fact,
with a PKI and digital signatures in place, message authentication
is not a direct issue here. Also, availability problems
(due to jamming) are not aggravated and can actually be alleviated
by aggregation due to the reduction of channel congestion.
But the fact that aggregation reduces the number
of messages (and not the amount of information) can allow
cheaters to insert false data into the network. Therefore, we
have to make the following single assumption:
Any group of vehicles should contain a majority of honest
nodes under normal density conditions.
The definition of groups will follow shortly in Section
3.4. Normal density conditions refer to typical scenarios
on roads: vehicles driving within at most few tens of meters
of each other. This assumption allows us to rely on the
existence of honest group members able to rectify the false
data disseminated by attackers. This is also in line with the
data correctness requirement introduced in Section 3.5.
3.4 Group Aspects
Our algorithms revolve around the core idea of information
relaying between groups of vehicles rather than individual
vehicles. This, of course, does not concern the physical
transmission of data but the data flow in the network. More
precisely, vehicles are arranged into groups. Within each
group, one or more vehicles, automatically determined by
their positions, transmit the data aggregated in that group
to neighboring groups. This is illustrated in Figure 1.
68
Geographic
group boundary
Group
Group
communication
Group leader
Figure 1: Efficient aggregation by means of overlapping
groups. Communication between the two outer
groups is possible because at least the leader of the
center group is in reach of relaying vehicles (in grey)
in both outer groups.
The area of group formation and management is one of the
most important and at the same time complicated topics in
VANET research. Groups have many intuitive applications
in VANET settings, especially platooning-like applications
[12]. From the security standpoint, a recent work [14] has
also suggested using groups to increase the anonymity of
vehicle to infrastructure communications. But there are two
major problems that need to be tackled when addressing
group aspects in VANETs: group formation and intra-group
agreement. In this work we will focus on the first and due
to the lack of space we will give only some hints concerning
the second problem.
3.4.1 Group Formation
There can be many ways to form groups in VANET applications.
For example, all public transport buses can be
members of a preset group. This is the easiest and most efficient
way of group formation, but it requires prior knowledge
of group members, as well as a common authority over
them. This is not the case when individual drivers on a highway
decide to join a platoon in order to improve their driving
experience. This necessitates on-the-fly group formation
where a group leader2 is elected and group membership is
managed dynamically. This latter category of groups is the
most useful functionally due to its flexibility, but it is also
the most difficult to form due to a multitude of issues, such
as group leader election, group overlap (e.g., how to decide
which group to join if a vehicle is within the boundaries of
two overlapping groups), and the related security hurdles.
2A group leader can also be called a clusterhead.
In order to escape the rigidity of preset groups and the
complexity of on-the-fly groups while retaining, at least partially,
the efficiency of the first and the flexibility of the latter,
we have sought a hybrid solution. The result is locationbased
groups. In fact, for safety applications, which are the
focus of this paper, it is essential to know where, and not
who, the neighbors of a vehicle are. As mentioned earlier,
messages are mostly destined to geographic regions rather
than individual vehicles. For example, if there is sliding terrain
behind a curve, all vehicles entering the curve should be
informed. Hence the intuitive idea of sending messages from
groups of vehicles in one location to groups of vehicles in another.
This brings us to the group formation primitive we
use in this paper: the map (more precisely, the roads) is dissected
into small area cells that actually define the groups. A
vehicle will automatically know to which group it belongs by
comparing its GPS position to a preloaded dissection of the
area map into cells. The group leader, the vehicle closest to
the center of the cell, is determined dynamically. Cells, and
hence groups, overlap in such a way that any vehicle moving
from one cell to the next remains in transmission range of
both group leaders. This means that the cell size depends on
the transmission range of vehicles. Using the typical DSRC
(Dedicated Short Range Communications) [1] range of 300
m, we have set the cell length in our simulations to 400 m,
which proved to be a suitable value. Further improvements
on cell size calculations could be possible, which we leave
to future work. Figure 1 illustrates this concept, as well as
some details.
A seemingly difficult - but in fact straightforward - process
associated with location-based group formation is that
of group leader election. As mentioned in the previous paragraph,
the group leader is the vehicle closest to the group’s
cell center. Because cells are predetermined, the center location
is also known to all vehicles in the cell. In addition,
by leveraging on the periodic safety message broadcasts (at
most each 300 ms [1]) that include a vehicle’s position, each
vehicle is aware of the positions of its neighbors within a tolerable
margin of error (few meters) due to the imprecision
of GPS. Thus, a group leader election takes place within a
delay of at most 300 ms. If there are several vehicles close
enough to the center such that the error margin does not
allow a clear-cut decision, the vehicle with the lowest ID
among these will be elected as group leader. We should
note here that vehicles do not broadcast their actual IDs
but rather pseudonyms for privacy purposes.
By using location-based groups, we can reap two major
benefits:
• Efficiency: A vehicle will automatically know to which
group it belongs. Hence, group formation will not require
any additional communication overhead or delay.
• Routing: As most routing in safety applications is geographic,
determining which groups should relay messages
is straightforward.
To achieve the above advantages, almost the only costs
involved in this type of group formation is the preloading of
map dissections into vehicles. But this can be easily included
on the vehicle navigation maps that will probably be an
integral part of each vehicle when VANET communications
hit the market.
69
3.4.2 Group Agreement
In order for information to be generated and propagated
by groups rather than individual vehicles, all vehicles in a
group should share a similar view of their environment. Any
kind of group agreement protocol would be expensive in
terms of communication overhead and delay, without mentioning
security. Hence we adopt a simpler yet effective approach:
each vehicle locally processes all events, either directly
observed or reported by other vehicles, before making
a decision concerning that event. By using this approach,
we make the following reasonable assumptions:
• Most vehicles in one cell receive messages with similar
information from other cells. This would be the case
if the cell size is comparable to the transmission range
(the respective values that we use in this paper are 400
m and 300 m).
• Under normal traffic density (defined in Section 3.3),
any event happening in a cell is observed by several
vehicles. This means that there are alternative sources
of information that can be crosschecked for consistency
verification.
• Most honest vehicles observing the same event report
similar observations. Possible errors are due only to
differences in on-board sensor readings.
In addition, we leverage on the assumption that attackers
are a minority among network members, which means that
there is a majority of correct observers.
Under the above conditions, the majority of vehicles in a
cell share a similar view of the environment within tolerable
margins of error. We leave the details of this algorithm for
future work - due to the lack of space. A good existing
example of such an approach can be found in [5].
3.4.3 Secure VANET Group Protocol
We end the discussion on group aspects by introducing
a simple protocol for symmetric group key establishment
in VANETs: SVGP (Secure VANET Group Protocol). It is
inspired notably from the Group Key Management Protocol
(GKMP) [6] but with geographically defined groups. This
protocol will be later used in Sections 4.2 and 4.3.
As explained before, roads are divided into cells that define
groups, with the group leader being the vehicle closest
to the cell center. Leveraging on periodic broadcasts of certified
public keys, the group leader (L in this example) distributes
the group key K to members A, B, and C encrypted
with their respective public keys as follows:
L → ∗ : {K}PuKA, {K}PuKB , {K}PuKC ,
SigPrKL[{K}PuKA
|{K}PuKB
|{K}PuKC ]
Subsequent message broadcasts will include only a HMAC
in addition to the message itself:
L → ∗ : m,HMACK(m)
When a new vehicle D enters the cell, it receives the group
key from the current group leader:
L → D : {K}PuKD, SigPrKL[{K}PuKD]
When a vehicle leaves the cell, nothing needs to be done.
In fact, the creation of secure groups will only contribute
to reducing the security overhead and not defining different
security levels among VANET members. Similarly to
digital signatures, the use of secure groups protects the network
from outsiders (entities that do not possess certified
public/private key pairs). Hence, while renewing or transferring
existing keys during member joins is still necessary,
member leaves should not necessarily entail an update of the
group key.
Special attention needs to be paid to exchanges on cell
boundaries when a vehicle switches from one group to another.
In order to make this operation smooth, cell dimensions
should be smaller than the diameter of the transmission
range disk. For example, if the transmission range is
300 m (the disk diameter is 600 m), we can choose a cell
size of 400 m. Hence, at the cell boundaries, a vehicle will
receive messages from the leaders of both its previous and
new groups.
There are several other functional details of this protocol
that need to be worked out. But our purpose is to make it as
simple as possible in order to demonstrate its usage in secure
message aggregation. Hence, we describe this protocol only
as an example; other mechanisms are also possible. It is
also important to note that shared group keys are limited in
space and time due to the small fixed cells and high vehicle
mobility. This makes the vulnerability windows, opened by
the compromise of these keys, small.