A Low-Overhead Message Authentication and Secure Message Dissemination Scheme for VANETs

Abstract

Given the enormous interest shown by customers as well as industry in autonomous vehicles, the concept of Internet of Vehicles (IoV) has evolved from Vehicular Ad hoc NETworks (VANETs). VANETs are likely to play an important role in Intelligent Transportation Systems (ITS). VANETs based on fixed infrastructures, called Road Side Units ($RSU$s), have been extensively studied. Efficient, authenticated message dissemination in VANETs is important for the timely delivery of authentic messages to vehicles in appropriate regions in the VANET. Many of the approaches proposed in the literature use $RSU$s to collect events (such as accidents, weather conditions, etc.) observed by vehicles in its region, authenticate them, and disseminate them to vehicles in appropriate regions. However, as the number of messages received by $RSU$s increases in the network, the computation and communication overhead for $RSU$s related to message authentication and dissemination also increases. We address this issue and propose a low-overhead message authentication and dissemination scheme in this paper. We compare the overhead, related to authentication and message dissemination, of our approach with an existing approach and also present an analysis of privacy and security implications of our approach.

1. Introduction

Given the enormous interest shown by customers as well as industry in autonomous vehicles, the concept of an Internet of Vehicles (IoV) has evolved from Vehicular Ad hoc NETworks (VANETs). Thus, VANETs are likely to play an important role in Intelligent Transportation Systems (ITS). According to some estimates, the global market for IoV is likely to exceed USD 200 billion by 2024. Many auto manufacturers have programs in place for developing a platform for connecting to IoV services such as route management and smart parking. VANET consists of vehicles and $RSU$s. Each vehicle is equipped with On-Board Unit (OBU), which allows the vehicle to collect data from their environment, process, and send information to other vehicles and/or $RSU$s through wireless communication (e.g., Dedicated Short-Range Communication (DSRC)). Therefore, using Vehicle-to-Vehicle (V2V) communication, vehicles can send and receive alert messages. For example, modern vehicles have Emergency Electronic Brake Lights (EEBL). This system aims to warn other vehicles if there is a need for sudden hard braking, for example, in foggy weather, where visibility may become low and brake lights are not bright enough to be recognized by other drivers [1,2].

Vehicle-to-Infrastructure (V2I) communication can help with avoiding accidents. The $RSU$ can collect and process the information from vehicles moving within its transmission range; looking at the data that had been analyzed, if an accident is about to happen, $RSU$ broadcasts a warning message to vehicles in its transmission range so they can take appropriate action to avoid it [2,3]. A dynamic traffic congestion pricing system for IoV [4] has been proposed. In this system, to alleviate traffic congestion, the participating vehicles are rewarded for taking an alternative path. The proposed system is implemented using VANETs, which eliminate the need for installing a costly electronic toll collection system. The authors in [5] proposed an accident prediction system for VANET. The crash risk in their system can be observed using velocity, driver fatigue, weather conditions, vehicles density, and crash location. They used a hidden Markov model to model the correlation between these observations and the crash risk. The results of their proposed system show the ability to detect potential crashes [5]. Over the past few years, researchers in both academia and industry have continuously worked on designing efficient schemes for privacy-preserving authentication and secure message dissemination in VANETs.

Clustering techniques have been used in V2V communication-based VANET architectures, wherein the network is divided into multiple clusters and one node in each cluster is selected as their Cluster Head ($CH$). The $CH$ is responsible for all local cluster communication. This clustering technique helps with reducing the message overhead because it restricts the communication between $CH$ and the members in its cluster. The $CH$ can collect and also process and aggregate information from its cluster members and then propagate them to other clusters through other $CH$s [6,7]. Many researches proposed schemes [8,9] for electing $CHs$ in each cluster based on specific parameters, such as vehicle location, vehicle speed, etc. Dividing the network into multiple clusters reduces the communication overhead and improves the network efficiency.

In infrastructure-based architectures for VANETs, vehicles use Road Side Units ($RSU$s) to form a VANET. In some schemes [10,11], vehicles authenticate each other, while in other schemes [12,13], vehicles use $RSU$s for authenticating disseminating messages sent by vehicles in its region. If traffic becomes heavy, it may not be possible for $RSU$s to receive messages about events observed by all vehicles in its region, authenticate them, and disseminate them in a timely manner, especially because the same event will be observed and sent by many vehicles in its region. In this paper, we address this problem and propose a solution.

In our approach, when the density of vehicles in an $RSU$’s region is high, the $RSU$ divides its region within its transmission range into several sub-regions and selects one vehicle in each sub-region as the Group Leader ($GL$). The $GL$ selected in a sub-region is supposed to collect messages sent by vehicles in its sub-region, authenticate them, aggregate them, and forward them to the $RSU$. This reduces the overhead related to message authentication for the $RSU$.

Following are the major contributions of our work:

• We propose a low overhead message authentication and secure message dissemination scheme for VANETs. Vehicles themselves do not authenticate messages. $RSU$s are responsible for collecting, aggregating, authenticating and disseminating messages to vehicles.
• To reduce the message authentication overhead, $RSU$s can select some vehicles in its region as group leaders ($GL$s) to collect/aggregate messages from vehicles in their subregions and send them to the $RSU$ for further aggregation and dissemination.
• Our scheme ensures authenticity and integrity of messages using digital signature based on public key cryptography.

The rest of the paper is organized as follows. We discuss some related works in Section 2. In Section 3, we describe our proposed approach. In Section 4, we present the security and privacy analysis of our approach. Finally, Section 5 concludes the paper.

Next, we discuss some related works.

2. Related Works

Cluster-based vehicular cloud architectures have been proposed in [14,15] for infrastructureless VANETs; under these approaches, vehicles are grouped into clusters based on their location, speed, computation capability, etc. Vehicles belonging to a cluster elect a Cluster Head ($CH$). The $CH$ performs the creation, maintenance, and deletion of vehicles in that cluster. A scheme in  [16] proposed a similar approach, where vehicles in a specific region form a vehicular cloud elect a broker among them. The broker collects the desired data from the vehicles and then sends it to a cloud server if further processing is required. Security-related issues are not addressed in these schemes. The authors in [15] designed a secure communication protocol for exchanging messages among vehicles in a smart city using an Elliptic Curve Cryptography ($ECC$) technique. In their scheme, Cluster Heads ($CHs$) are responsible for communicating and verifying messages within their clusters, and the CHs are verified by the Certification Authority ($CA$). In this scheme, frequent $CH$ elections could occur if vehicles move fast.

Many privacy-preserving authentication schemes, such as anonymous authentication [17], cooperative authentication [10], and dual authentication [18] have been proposed. For example, Azees et al. [17] proposed a PKI-based efficient anonymous authentication scheme with a conditional privacy-preserving (EAAP) scheme for VANETs. The vehicles and $RSU$s communicate anonymously to provide privacy and anonymity during the authentication process, and the TA can revoke a misbehaving vehicle and find out its real identity in case of dispute. This scheme is secured against different attacks (e.g., impersonation attacks, message modification attacks, etc). However, in the above schemes [10,17,18], vehicles communicate not only with each other but also with the $RSU$s to verify the authenticity of the messages.

Schemes presented in [19,20,21] used $RSU$s for authenticating, processing, and disseminating messages received from vehicles in its region. In [19], a safety warning system in fog-cloud-based VANETs using a Certificateless Aggregation Signcryption Scheme (CASS) have been proposed. Vehicles send traffic messages to the $RSU$s, which act as fog nodes. These fog nodes process and aggregate the received messages. These schemes [19,20,21] address the security and privacy issues for VANETs. However, they do not consider heavy densities of vehicles, which may cause increased computation and communication overhead.

In our scheme, vehicles do not form clusters among themselves. Each $RSU$ can decide when and where to form clusters in its region, based on the density of vehicles and other parameters such as the region from which the $RSU$ receives a large number of messages. In addition, the $RSU$ assigns the Group Leader $GL$ (the Group Leader is not elected) for each cluster, and the $GL$ is responsible for collecting, authenticating, and aggregating the messages received from its cluster/group and for forwarding them to the $RSU$. The $RSU$ is responsible for collecting the messages sent by the $GL$s in its region, authenticating them, aggregating them, and forwarding them to the vehicles in its region and/or other $RSU$s for further dissemination. This approach reduces the computation and communication overhead for the $RSU$s.

3. Proposed Approach

In this section, we present our system model and describe the proposed method for authenticated message dissemination in detail. The acronyms used in this paper are listed in

Table 1. Notations.

Notation	Description
$I{D}_A$	Identity of Entity A
$PI{D}_A$	Pseudo Identity of Entity A
M	A Message
v	Vehicle v
$ts$	Timestamp
$P{R}_A$	Private Key of Entity A
$P{U}_A$	Public Key of Entity A
K	Symmetric Key established between two communicating parties
$SI{G}_A\left(M\right)$	Signature of M Signed using A’s Private Key
H()	Hash Function
$E(M,K)$	Encryption of M with Key K
$RSU$	Roadside unit
$GL$	Group Leader
$DMV$	Department of Motor Vehicles
$Cer{t}_v$	Certificate issued to vehicle v by the $DMV$
$Cer{t}_{RSU}$	Certificate issued to $RSU$ by the $DMV$

.

3.1. System Model

The system model for our scheme is shown in Figure 1. It consists of Department of Motor Vehicles (DMV), Road Side Units ($RSU$s), On-Board Units (OBUs), and Group Leaders (GLs). We describe the functions of these entities next.

• DMV: We assume that all vehicles are registered with a trusted authority ($TA$), such as the Department of Motor Vehicles ($DMV$), that administers the registration of the vehicles. The $DMV$ is assumed to be trusted and cannot be compromised. The $DMV$ generates its public and private keys ($P{U}_{DMV}$, $P{R}_{DMV}$) and distributes a $P{U}_{DMV}$ to all $RSU$s and vehicles securely. In addition, the $DMV$ generates pseudo-IDs ($PI{D}_v$) for each vehicle, certificates corresponding to each pseudo-ID of a vehicle ($Cer{t}_v$) where $Cer{t}_v=E((PI{D}_v,P{U}_v,ts),P{R}_{DMV})$, and certificates of $RSU$s ($Cer{t}_{RSU}$) where $Cer{t}_{RSU}=E((I{D}_{RSU},P{U}_{RSU},ts),P{R}_{DMV})$.
• Vehicle: Each vehicle is assumed to be equipped with an On-Board Unit ($OBU$) for computation and communication with $RSU$s as well as with other vehicles. The $OBU$ stores the vehicle’s public and private key pair ($P{U}_v$, $P{R}_v$), its pseudo-IDs ($PI{D}_v$), its certificates corresponding to each pseudo-ID of the vehicle ($Cer{t}_v$ signed by the $DMV$), and the public key of the $DMV$ ($P{U}_{DMV}$).
• RSU: The Road Side Units ($RSU$s) are fixed entities along the roadside which facilitate V2V and V2I communication. $RSU$s are connected to each other and to the $DMV$, possibly through the Internet. In our scheme, a $RSU$ collects the messages sent by the vehicles in its region, authenticates the messages, aggregates the messages, and forwards them to vehicles within its region, as well as to vehicles in other regions as needed.
• Group Leader ($\mathbf{GL}$): Each $RSU$ divides its region into sub-regions based on the density of vehicles in the region. Then, the $RSU$ selects one vehicle in each sub-region as a $GL$. The $GL$ is responsible for collecting, authenticating, and aggregating messages sent by vehicles in its sub-region and for sending them to the $RSU$. The $GL$ is also responsible for receiving messages from the $RSU$, authenticating them, and disseminating them to vehicles in its sub-region.

We describe the proposed method in detail next.

3.2. Proposed Method

In our scheme, $RSU$s are responsible for verifying the authenticity and integrity of messages sent by vehicles before disseminating them to other vehicles or $RSU$s. If traffic is heavy in the region of an $RSU$, the $RSU$ may not be able to receive messages from all vehicles in its region, process them, and disseminate them in a timely manner due to the authentication, aggregation, and communication overhead involved. To help $RSU$ minimize this overhead, the $RSU$ divides its region into sub-regions and selects one vehicle in each sub-region as the Group Leader ($GL$). These Group Leaders help the $RSU$ with receiving, authenticating, and aggregating messages from vehicles in its sub-regions and forwards them to the $RSU$. The $RSU$, in turn, is responsible for collecting, authenticating, and further aggregating the messages received from all the $GL$s in its region, and for disseminating them to all vehicles in its region through the $GL$s or to vehicles in other regions through other $RSU$s, as necessary. Thus, $RSU$s incur less computation and communication overhead for collecting, authenticating, and disseminating messages. Following is the list of assumptions made in this paper:

1.

We assume that the clocks of $RSU$s, the $DMV$, and the vehicles are loosely synchronized. This can be achieved using time received from a GPS. Messages are time-stamped using the local clock time to verify the freshness of the messages;

2.

Certificates issued by the $DMV$ for the vehicles and $RSU$ are used for the authentication of vehicles and $RSU$s;

3.

We do not address the issue of determining malicious vehicles or $RSU$s. Several approaches have been proposed in the literature to identify malicious entities in VANETs. Any of those approaches can be used for determining malicious vehicles. Once a vehicle is determined to be malicious, the $DMV$ revokes its certificate and includes the certificate in the Certificate Revocation List ($CRL$). The $DMV$ broadcasts the $CRL$ to all $RSU$s when it changes. The $RSU$s, in turn, broadcast the $CRL$ to vehicles in its region;

4.

When a vehicle v enters the region of an $RSU$ (i.e., v is within the transmission range of an $RSU$), even though v will be able to receive messages sent by the $RSU$, v may not be able to send messages directly to the $RSU$ because the $RSU$ may not be within the transmission range of v. In this case v uses an underlying routing algorithm to send messages to the $RSU$ through other vehicles. Any of the many routing algorithms proposed in the literature can be used for that purpose.

Next, we describe our approach in detail.

When a vehicle $\mathbf{v}$ enters the region of an $\mathbf{RSU}$: Each $RSU$ periodically broadcasts its $Cer{t}_{RSU}$. When a vehicle v enters an area covered by an $RSU$, v retrieves the public key of the $RSU$ from $Cer{t}_{RSU}$ and checks its $CRL$ to see if this $RSU$’s certificate has been revoked (the certificate of an $RSU$ could be revoked if it is removed from the system). If not, then v sends a join request message M to the $RSU$. The join request message M contains its currently used $PI{D}_v$, the corresponding certificate $Cer{t}_v$, and a timestamp ($ts$). After receiving this message, the $RSU$ checks the freshness of the message using the $ts$. Then, the $RSU$ retrieves the public key $P{U}_v$ and pseudo-ID $PI{D}_v$ of the vehicle from $Cer{t}_v$, and checks the $CRL$ to determine if the vehicle’s certificate has been revoked. If not, then the $RSU$ sends an accept message to v. The accept message contains a symmetric key K to be used for secure communication between the $RSU$ and v, and a timestamp $ts$, encrypted using the public key $P{U}_v$ of v; it also attaches the certificate of the $RSU$, signed by the $DMV$ ($Cer{t}_{RSU}$), and the signature of the $RSU$ ($SI{G}_{RSU}$) to the message as follows:

$$M_1=(RSU,PI{D}_v,(E(“Accept”,K,ts),P{U}_v),Cer{t}_{RSU},SI{G}_{RSU}),$$

where

$$SI{G}_{RSU}=E(H(“Accept”,K,ts),P{R}_{RSU}).$$

Upon receiving the above accept message from the $RSU$, the vehicle uses the received $ts$ to verify the freshness of the accept message. After that, it verifies the $Cer{t}_{RSU}$ and the signature of the $RSU$. Algorithm 1 contains the algorithm illustrating the joining process of a vehicle v when v enters the region of an $RSU$.

Algorithm 1: When a vehicle v enters the region covered by an $RSU$

When a vehicle v enters the region covered by an $RSU$:    Verifies $Cer{t}_{RSU}$ received in the broadcasted message using    $P{U}_{DMV}$;    Retrieves $P{U}_{RSU}$ from the $Cer{t}_{RSU}$;    Computes $M_1=(“Join”,ts)$;    Encrypts $M_1$ using public key $P{U}_{RSU}$ of $RSU$;    Sends $M_1^{\prime }=(PI{D}_v,RSU,E(M_1,P{U}_{RSU}),Cer{t}_v,SI{G}_v$)    to the $RSU$, where $SI{G}_v=E(H\left(M_1\right),P{R}_v)$ When the $RSU$ receives $M_1^{\prime }$ from v:    Decrypts $M_1^{\prime }$ using $P{R}_{RSU}$;    Verifies $Cer{t}_v$ using $P{U}_{DMV}$;    Retrieves $P{U}_v$ from $Cer{t}_v$;    Verifies the signature using $P{U}_v$;    If verification succeeds {          Computes $M_2=(“Accept”,K,ts)$;          // $M_2$ contains the acceptance message          // for the joining message from v;          // K is the symmetric key to be used between v and $RSU$;          Encrypts $M_2$ using public key $P{U}_v$ of v;          Sends $M_2^{\prime }=(RSU,PI{D}_v,E(M_2,P{U}_v),Cer{t}_{RSU},SI{G}_{RSU}$)          to v, where $SI{G}_{RSU}=E(H\left(M_2\right),P{R}_{RSU})$};    Else { Discards $M2$; }    When a vehicle v receives $M_2^{\prime }$ from $RSU$:    Decrypts $M_2^{\prime }$ using its private key $P{R}_v$ to obtain $M_2$;    Verifies $SI{G}_{RSU}$ using $P{U}_{RSU}$;    If verification succeeds {          Stores ($M_2$);}    Else { Discards $M2$. }

    Next, we describe how an $RSU$ selects Group Leaders in its region and informs them about being selected.

Informing selected vehicles as Group Leaders: When a vehicle v enters the region covered by an $RSU$, it sends a join message to the $RSU$ after authenticating the $RSU$. Then, the $RSU$ authenticates v and sends an “Accept” message, which includes a symmetric key K to be used between v and the $RSU$. Afterwards, the vehicle can send messages about sensed events to the $RSU$, encrypting them using K. If the $RSU$ is not within the vehicle’s transmission range, the messages are sent to the $RSU$ using an underlying routing algorithm, as we mentioned earlier. Upon receiving “join” messages from vehicles in its region, an $RSU$ can determine the number of vehicles in its region and their location. If the density of vehicles in the region of an $RSU$ is low, the $RSU$ does not need to select a $GL$. If the density of vehicles in an $RSU$’s region is high, it divides its region into sub-regions and selects one vehicle from each sub-region as the Group Leader ($GL$). After selecting $GL$s, the $RSU$ informs the selected vehicles ($GL$s) of their leadership and sends a proof-of-leadership message $M_1=E((“Leader”,P{U}_{G{L}_i},ts),P{R}_{RSU})$. The $RSU$ encrypts the $M_1$ using a symmetric key K, established between v and $RSU$ when v entered the $RSU$’s region, attaches its signature ($SI{G}_{RSU}$) to the message, and sends the $M_1^{\prime }$, where $M_1^{\prime }=(RSU,PI{D}_v,E(M_1,K),SI{G}_{RSU})$, and $SI{G}_{RSU}=E(H\left(M_1\right),P{R}_{RSU})$.

When a $GL$ receives the above message $M_1^{\prime }$ from the $RSU$, it decrypts the message using a symmetric key K and uses the received $ts$ to verify the freshness of the message. After that, it verifies the signature of the $RSU$ and stores $M_1$ as proof of leadership, so it can present it to the vehicles in its sub-region as proof that it is a leader. Algorithm 2 illustrates how an $RSU$ informs the selected vehicles of their leadership ($GL$s). The $GL$s are responsible for authenticating, aggregating, and forwarding messages collected from vehicles in its sub-region. Thus, the $RSU$ only needs to authenticate and process messages that come from $GL$s. Therefore, the communication and computation overhead for $RSU$s will be reduced. Moreover, when an $RSU$ needs to send some message to all vehicles in its region or only to vehicles in some sub-regions, it will send that message only to the $GL$s in those sub-regions, which, in turn, will send it to all the vehicles in its sub-region.

Algorithm 2:Assigning Group Leaders ($GL$s) for selected vehicles by $RSU$

$RSU$ determines the number of vehicles and their locations in its region:    Based on the density of vehicles in the $RSU$’s region,    If Density is high {       $RSU$ selects a set of vehicles as Group Leaders ($GL$s);       For each vehicle selected as a $GL$ {          Computes $M_1=(E(“Leader”,P{U}_{GL},ts),P{R}_{RSU});$          Encrypts $M_1$ using symmetric key K;          // K is the symmetric key established between v and          // the $RSU$ when v joined $RSU$’s region;          $M_1^{\prime }=(RSU,PI{D}_v,E(M_1,K),SI{G}_{RSU})$,          where $SI{G}_{RSU}=E(H\left(M_1\right),P{R}_{RSU})$;          Sends $M_1^{\prime }$ to $GL$; } }    else{       No $GL$s are selected;       $RSU$ authenticates and process messages from all vehicles; } When a $GL$ receives $M_1^{\prime }$ from $RSU$:    Decrypts $M_1^{\prime }$ using K;    Verifies the signature using $P{U}_{RSU}$;    If verification succeeds{       Stores ($M_1$) as proof of leadership;}    Else {Discards $M_1$.}

Next, we describe how a vehicle in a sub-region establishes a connection with its Group Leader and communicates with its Group Leader.

When a vehicle v enters the sub-region of a $GL$: Each $GL$ periodically broadcasts its public key $P{U}_{GL}$ and the proof of leadership received from the $RSU$, namely, $E((“Leader”,P{U}_{GL},ts),P{R}_{RSU})$. When a vehicle v enters a sub-region covered by a $GL$, it retrieves $P{U}_{GL}$ from the proof of leadership. Then, v sends a join request message M to the $GL$; M contains a $PI{D}_v$, $Cer{t}_v$, and timestamp ($ts$). Upon receiving M, the $GL$ checks the freshness of the message using $ts$. Then, the $GL$ retrieves the $PI{D}_v$ and public key $P{U}_v$ of the vehicle from $Cer{t}_v$ and checks the $CRL$ to determine if the vehicle’s certificate has been revoked. After verification, $GL$ sends an acceptance message and a symmetric key K to be used for secure communication between the vehicle v and the $GL$. The acceptance message $M_1^{\prime }$ contains the certificate of the $GL$, signed by the DMV ($Cer{t}_{GL}$), a K, and a $ts$, encrypted using the public key $P{U}_v$ of v as follows: $M_1^{\prime }=GL,PI{D}_v,(E(“Accept”,K,ts),P{U}_v),Cer{t}_{GL},SI{G}_{GL})$

Upon receiving the above acceptance message from the $GL$, v uses the received $ts$ to verify the freshness of the message. After that, it verifies the signatures of the $DMV$ and $GL$. Note that if v does not recieve proof of leadership from a $GL$ (this happens when the $RSU$ has not determined leaders due to low density of vehicles in its region), after entering an $RSU$’s region, v sends/receives messages to/from the $RSU$ directly, using an underlying routing protocol. Algorithm 3 illustrates the joining process when v is in the sub-region of a $GL$.

Algorithm 3:When vehicle v enters a sub-region covered by a Group Leader $GL$

When v enters the region covered by a $GL$:    Receives proof of leadership message    $E((“Leader”,P{U}_{GL},ts),P{R}_{RSU})$ from the $GL$;    Retrieves $P{U}_{GL}$ from the encrypted message using $P{U}_{RSU}$;    Computes $M_1=(“Join”,ts$);    Encrypts $M_1$ using public key of Group Leader $P{U}_{GL}$    Sends $M_1^{\prime }=(PI{D}_v,GL,E(M_1,P{U}_{GL}),Cer{t}_v,SI{G}_v)$ to    $GL$, where $SI{G}_v=E(H\left(M_1\right),P{R}_v)$; When a $GL$ receives $M_1^{\prime }$ from v:    Decrypts $M_1^{\prime }$ using $P{R}_{GL}$    Verifies $Cer{t}_v$ using $P{U}_{DMV}$;    Verifies the signature using $P{U}_v$;    If verification succeeds{       Computes $M_2=(“Accept”,K,ts)$;       // $M_2$ contains the acceptance of $GL$ for v;       // K is a symmetric key between v and $GL$ for further       // communication;       Encrypts $M_2$ using public key $P{U}_v$ of v;       Sends $M_2^{\prime }=(GL,PI{D}_v,E(M_2,P{U}_v),SI{G}_{GL})$ to v,       where $SI{G}_{GL}=E(H\left(M_2\right),P{R}_{GL})$};    Else { Discards $M_2$;}    When v receives $M_2^{\prime }$ from the $GL$:    Decrypts $M_2^{\prime }$ to obtain $M_2$;    Verifies $SI{G}_{GL}$ using $P{U}_{GL}$;    If verification succeeds{       Stores ($M_2$); }    Else { Discards $M_2$; }

When a vehicle $\mathbf{v}$ wants to send a message $\mathbf{M}$ to its $\mathbf{GL}$: When v wants to send a message M about an observed event to its $GL$, it signs and encrypts M and sends $M_1$ to the $GL$, where $M_1=(PI{D}_v,GL,E((M,ts),K),SI{G}_v)$; here, $ts$ is the timestamp, K is the symmetric key established between v and $GL$, and $PI{D}_v$ is the pseudo-ID of v.

When $GL$ receives $M_1$, it decrypts the message using the symmetric key K and checks the freshness of the message using the $ts$. It uses a signature $SI{G}_v$ to verify the authenticity and integrity of the message. Then, the $GL$ aggregates the received message with the messages received from other vehicles in its sub-region and forwards the aggregated message to the $RSU$, and the $RSU$ can further aggregate messages received from other $GL$s in its region and disseminate them to the appropriate sub-regions of its region or regions covered by other $RSU$s. Algorithm 4 shows this message collection and dissemination process.

Algorithm 4:Vehicle v sending a Message M to its Group Leader $GL$

When a vehicle v wants to send a message M about an observed event:    Computes $M_1=(PI{D}_v,GL,E((M,ts),K),SI{G}_v)$;    Sends $M_1$ to $GL$;    // K is the symmetric key established in the    // Algorithm 3. When the $GL$ receives $M_1$ from v:    Decrypts $M_1$ using the symmetric key K and retrieves    the message M;    Checks the timestamp $ts$;    Verifies the signature using public key $P{U}_v$ of v;    Aggregates (M) with other messages sent by other vehicles;    Computes $M_2=(GL,RSU,E((M,ts),K),SI{G}_{GL});$    Sends $M_2$ to $RSU$;    // K is the symmetric key established between the $GL$ and    // the $RSU$ when it entered the $RSU$’s region. When the $RSU$ receives $M_2$ from $GL$:    Decrypts $M_2$ using the symmetric key K and retrieves    the message M;    Checks the timestamp $ts$;    Verifies the signature using public key $P{U}_{GL}$ of $GL$;    Aggregates (M) with other messages sent by other $GL$s;    Disseminates the message to the appropriate regions through    other $RSU$s as well as vehicles in its region through the $GL$s.

Certificate Revocation List (CRL) distribution and certificate revocation process. Misbehaving vehicles can send malicious messages to other vehicles; these misbehaving vehicles should be detected and punished. IEEE 1609.2, the standard for Wireless Access in Vehicular Environments (WAVE)—Security Services for Applications and Management Messages [22], has specified that the vehicle must be authenticated using certificates issued by the $TA$ and defined the $CRL$ that contains the list of the revoked certificates that are updated timely and disseminated in the vehicular network. Once the $CRL$ is distributed to the vehicles, it can compare the certificate of a vehicle with the list and determine if it has been revoked.

In our scheme, the $DMV$ will manage and maintain the updated $CRL$. The $DMV$ will distribute the $CRL$ to the $RSU$s, which, in turn, will distribute them to all vehicles in their region directly or through the $GL$s, if the $GL$s have been selected. The $RSU$s and $GL$s always check the authenticity of the vehicles using the $CRL$. If a vehicle is found to be malicious, the $RSU$ sends the certificate information of the vehicle to the $DMV$. Then, the $DMV$ adds the certificate to the $CRL$ and distributes the updated $CRL$ to all $RSU$s. Note that vehicles only communicate either with the $RSU$ or the $GL$ and that no communication between themselves occurs, which reduces the communication and computation overhead. We do not address the problem of detecting malicious vehicles. Many researchers have addressed the malicious vehicle detection problem in VANETs [23,24]. Any of those schemes can be used to detect malicious vehicles.

3.3. Some Optimizations for Our Approach

In our scheme, when a vehicle v enters the region of an $RSU$, it obtains a symmetric key K through the $Accept$ message $M_2=(“Accept”,K,ts)$ from the $RSU$ for establishing secure communication between v and the $RSU$ (please see Algorithm 1). This key K is used by v to encrypt messages and send them to the $RSU$ in the absence of $GL$s; this key is also used by the $RSU$ to send messages, as well as $CRLs$, securely to v, in the absence of $GL$s. To reduce this overhead caused by sending unicast messages, the $RSU$ can attach a group key $GK$ to the accept message as $M_2=(“Accept”,GK,K,ts)$; then, $GK$ can be used by the $RSU$ to broadcast (instead of unicasting) securely the $CRLs$ as well as other messages to all vehicles in its region. Similar optimizations can be performed in Algorithm 3 when a $GL$ assigns a symmetric key K to a vehicle v through the message $M_2=(“Accept”,K,ts)$.

4. Results

In our scheme, the encryption and the signature are fundamental security mechanisms used to resist impersonation, eavesdropping, replay, and modification attacks. The message that is sent by a vehicle v to its $GL$ to be modified must be decrypted, modified, and then encrypted by an attacker using the $v’s$ shared symmetric key. To decrypt the message, the attacker needs the symmetric key shared between the v and $GL$, which is not available to the attacker, thus making it impossible to modify the message. Replay attacks are prevented using timestamps. In our scheme, an attacker cannot generate a valid signature of other vehicles because the attacker does not know the private key of the vehicle. As a result, an attacker cannot send a malicious signed message without being detected.

Our scheme is secure against impersonation attacks: To perform an impersonation attack, the attacker should be able to obtain the private key $P{R}_v$ of a legitimate vehicle v, which the attacker does not possess. In addition, an attacker cannot impersonate a vehicle v, as the message encrypted using a shared symmetric key K between v and $GL$ (or between v and the $RSU$) cannot be decrypted without using K, which the attacker does not possess.

Our scheme preserves privacy—an attacker cannot discover the vehicle’s identity: Vehicles are assigned pseudo-IDs. A vehicle never uses its real ID in any communication. This prevents discovering the real identity of the vehicle and prevents attackers from linking messages from the same vehicle using multiple pseudonyms. During registration, a vehicle is assigned a set of pseudonyms and associated certificates. Vehicles can use any of the pseudonym-changing strategies presented in the literature [21,25] to change pseudonyms. Therefore, the privacy of vehicles is preserved.

Communication and Computation Overhead: In our scheme, if the density of vehicles present in an $RSU$’s region is low, it does not select $GL$s. If the density of vehicles in its region is high, then the $RSU$ selects $GL$s from the vehicles to help the $RSU$ with authenticating messages. The $GL$s are responsible for authenticating, aggregating, and forwarding messages received from vehicles from its sub-region. Thus, an $RSU$ only needs to authenticate and process messages that come from the $GL$s. Therefore, the communication and computation overhead for an $RSU$ is reduced. Note that an $RSU$ sends messages to vehicles in its region through $GL$s; vehicles only need to authenticate messages received from its $GL$ if the density of vehicles is high, and not from other vehicles, so the communication and computation overhead is low for the vehicles as well.

Figure 2 shows a comparison of the total communication cost of our scheme and that of the SEMA scheme [26], in terms of the number of messages exchanged between an $RSU$ and the vehicles in its region. For the purpose of comparison, vehicle density within the region of an $RSU$ is assumed to be high when the number of vehicles in its region is 1000 or more, and the average number of messages exchanged between a vehicle v and $RSU$ is 2; otherwise, we assume that the density is low. Figure 2 shows the average number of messages exchanged between an $RSU$ and vehicles in its region with this assumption; if the number of vehicles is less than 1000 in its region, the $RSU$ authenticates and processes messages received from all vehicles within its region; if there are more than 1000 vehicles in its region, the $RSU$ needs to authenticate messages that comes from the $GL$s only. As a result, in our scheme, the communication cost is lower on the $RSU$ side. For example, if there are only 400 vehicles present in the region of an $RSU$, the $RSU$ will authenticate the same number of messages (which is $400*2=800$ messages) in our scheme and in the SEMA scheme [26]. For comparison purposes, to compute the number of $GL$s needed in an $RSU$’s region, we assume that a predefined threshold is 100 for each $GL$; i.e., if there are 1000 vehicles, the number of $GL$s needed is ($\lceil (1000/100)\rceil =10$) and the number of messages exchanged between the $GL$s and the $RSU$ would be ($\lceil (1000/100)\rceil *2=20$) under our scheme, whereas under SEMA [26], the number of messages exchanged would be ($1000*2=2000$). Therefore, the total communication cost increases significantly with the increase of the number of vehicles under SEMA [26]. On the contrary, under our scheme, the communication cost is significantly lower. This is primarily because message collection overhead is shared by selected vehicles (GLs) in the RSU’s region.

We analyzed the computation overhead associated with encryption and authentication using a Toshiba computer with an Intel i3 quad-core processor with 2.50-GHZ clock frequency and 6 gigabytes of memory, running Windows 8.1 operating system. The public key cryptography-based signature and encryption scheme are based on RSA (Rivest–Shamir–Adleman) cryptography. Following are some notations used for presenting our results: time for computing RSA-based signatures ($T_{sign}$); time for signature verification ($T_{verify}$); time for encrypting a message using a public key ($T_{EPU}$); time for decrypting the message using a private key ($T_{DPR}$); time for encrypting a message using a symmetric key ($T_{EK}$); time for decrypting a message using a symmetric key ($T_{DK}$). We used the AES (Advanced Encryption Standard) to encrypt and decrypt the messages using a symmetric key. The execution time of the above operations is presented in

Table 2. Execution time for different operations (milliseconds).

Operation	Time
$T_{sign}$	0.06
$T_{verify}$	0.005
$T_{EPU}$	1.274
$T_{DPR}$	2.654
$T_{EK}$	1.166
$T_{DK}$	2.128

. We used a message size of 39 bytes, as specified in the IEEE 1609.2 standard, for the encryption and the corresponding decryption operations.

Computation Overhead on $\mathbf{G}\mathbf{L}$: The $GL$ is responsible for collecting, authenticating, and aggregating messages received from vehicles in its sub-region and forwarding them to the $RSU$. Figure 3 shows the computation overhead incurred by a $GL$ for decrypting and verifying the signature of messages received from the vehicles in its sub-region as well encrypting and signing those messages for sending them to the $RSU$ for a number of messages ranging from 50 to 500.

Computation Overhead for $\mathit{RSU}$:Figure 4 shows a comparison of the computation overhead between our scheme and SEMA [26] at an $RSU$ for a varying number of signature verifications. Our scheme incurs significantly lower overhead compared to SEMA [26]. This is due to the use of the $GL$s, which help the $RSU$ with the authentication and aggregation process of the messages sent by vehicles. For example, when the number of signatures reaches 1400, the overall cost is approximately 7 ms for the scheme in [26], whereas it is only 0.7 ms for our scheme.

5. Conclusions and Discussion

In this paper, we presented a low-overhead $RSU$-aided message authentication and dissemination scheme. In this scheme, when the overhead for collecting, authenticating, aggregating, and disseminating messages increases for an $RSU$, the $RSU$ can designate some of the vehicles in its region as Group Leaders and make them share the overhead involved in authenticating, aggregating, and disseminating messages. Thus, this scheme helps the $RSU$s with reducing the computation and communication overhead related to collecting, authenticating, aggregating, and disseminating messages. We have also shown that our scheme is privacy-preserving and secure and resilient to various attacks. We also analyzed and compared the communication and computation overheads of our scheme with an $RSU$-aided approach for authentication and message dissemination.