# Obfuscated RSUs Vector Based Signature Scheme for Detecting Conspiracy Sybil Attack in VANETs

Authors: Xia Feng; Jin Tang
Journal: Mobile Information Systems
 (2017)

---

## Abstract

Given the popularity of vehicular Ad hoc networks (VANETs) in traffic management, a new challenging issue comes into traffic safety, that is, security of the networks, especially when the adversary breaks defence. Sybil attack, for example, is a potential security threat through forging several identities to carry out attacks in VANETs. At this point, the paper proposed a solution named DMON that is a Sybil attack detection method with obfuscated neighbor relationship of Road Side Units (RSUs). DMON presents a ring signature based identification scheme and replaces vehicles’ identities with their trajectory for the purpose of anonymity. Furthermore, the neighbor relationship of RSUs is obfuscated to achieve privacy preserving of locations. The proposed scheme has been formally proved in the views of security and performance. Simulation has also been implemented to validate the scheme, in which the findings reveal the lower computational overhead and higher detection rate comparing with other related solutions.


---

## Body

## 1. Introduction

Generally, VANETs require that all connected vehicles register with given identity codes, just as the Plata Number in reality [1]. However, most vehicle users expect their identity information can be preserved in VANETs for they are afraid that their traveling will leak with the identity. Thus, anonymous methods are employed to hide their privacy [1, 2]. Sybil attack is a typical security thread from malicious vehicles, which can take more communication resources or offline economical profits through multiple identities [3]. The false traffic messages from attackers not only cause congestions but also increase risk of traffic accidents [1, 4].Most recent Sybil detection methods can be grouped in two types: hardware based scheme [5–8] and cryptology based identification method [9–13]. The hardware based scheme commonly applies technologies of signal strength [5–7] or resource testing [8]. However, the overdependence on hardware restrains its application; moreover, high cost in hardware improvements is another drawback for users to connect their vehicles to VANETs. The cryptology based scheme adopts identity authentication technology which is independent of vehicles and compatible with identity based management system [1]. Thus, the cryptology based scheme becomes the main solution for attack detection in VANETs. Although network users benefit from identity authentication and attack detection technologies, risks still exist in preserving users’ privacy.Conspired Sybil attacks are first presented in [14], in which attackers can masquerade as conspiracy vehicles using their identities in order to send malicious messages to other vehicles nearby. However, the conspired Sybil attacks cannot be prevented efficiently due to the weakness of current detection scheme supposing identities are always held securely. According to Sybil attack detection, reputation system based scheme was presented in [14]. Reputation system issues a trust value for each node, which can be reduced by an distrustful or malicious behaviour [15–17]. Thus, Sybil attackers can be distinguished based on the trust value. The identities with lower values will be considered as malicious nodes and ruled out no matter where these identities come from, either bound vehicles or faked attackers. However, as noted in [17], two significant features should be considered for VANETs: firstly, VANETs do not allow decreasing the reputation after the serious traffic accidents to prevent another attack, because the damage of life and things in this attack cannot be repaired; secondly, most vehicles replace their identities with pseudonyms or authorized messages to achieve privacy preserving, and it is difficult to associate an ID to a vehicle and a trust value to an ID, respectively.This paper proposes a method that completes identity certificate through tracing vehicles’ wheel path based on RSUs. The method authenticates vehicles’ identification in an anonymous manner just as the trajectory based signature scheme in Footprint [10, 18]. RSUs’ neighbor relationship is also obfuscated to prevent trajectory privacy from being leaked to RSUs and other vehicles. Our main contributions can be highlighted as follows:(i)
A ring signature scheme is proposed as secret material to generate identity certificate of vehicles. The signature includes a vector with concealment information of the signing RSU’s neighbor relationship.(ii)
Location privacy is preserved by obfuscating the mapping function between relationship vector and RSUs’ adjacent connections. However, the obfuscated vector still marks and conceals the RSU’s neighbors.(iii)
A method is presented to compute the adjacent connection of two RSUs using the obfuscated vectors of two RSUs. In the methods, RSUs and vehicles can obtain the result whether two RSUs are located in two-hop neighbor area without knowing the relationship concealed in vector.The rest of the paper is organized as follows. Section2 describes the related work and an example of conspiracy Sybil attack. Section 3 illustrates the architecture of VANETs and the research objectives. Section 4 gives a brief description of the protocol. Section 5 conducts performance evaluation of the proposed method. Section 6 concludes the whole research.


## 2. Related Work

Sybil attack is an attack by forging multiple identities which is firstly presented in peer-to-peer networks by Douceur [19]. Factually, Sybil attack also happens in ad hoc networks [3], sensor networks [7, 20], and VANETs [6, 9, 10]. This work will focus on an identity authentication scheme that benefits from the identification based Sybil attack detection.Pseudonyms are firstly used as a privacy protected scheme for identification of vehicles. Zhou et al. [9] proposed a pseudonym based Sybil attack detection scheme for privacy preserving. In the scheme, the Trust Authority distributes a number of pseudonyms for each vehicle. Abused pseudonyms can be detected by RSUs. Since RSUs are heavily involved in the detection process, this scheme requires the full coverage of RSUs in the field and makes RSUs a little overloading in computation and communication. What is worse, in such a scheme, vehicles should be managed by a centralized trusted center. If there is no an online centralized trusted center, pseudonyms based identification is invalid to conspiracy Sybil attack, for the attacker can borrow some pseudonyms from the conspired vehicles, and it is difficult to detect because each vehicle has many pseudonyms. Each time RSU detects suspicious pseudonyms, it should send all the pseudonyms to the trust center for further decision, which makes the trust center be the bottleneck of the detection.Lee et al. [11] lighten RSUs’ load by only relaying message for vehicles, and malicious vehicles will be recognized by a local VANET server (LCertVANET). Hussain et al. [12] proposed a privacy-friendly RSU driven Sybil attack detection, in which vehicle should have obtained “tokens” from BRSU before reporting any event. Lin et al. [13] proposed an efficient local Sybil resistance scheme. In [13], RSU periodically broadcasts an authorized time stamp to vehicles in its vicinity as the proof of appearance at this location. Vehicles collect these authorized time stamps which can be used for future identity verification. Park et al. [21] present an approach where RSUs are the only components issuing the certificates. In these schemes, if a vehicle signs two or more signatures at the same time period, it would be judged as the Sybil vehicle. In these methods, a different method for identification was presented, in which vehicles obtain secret materials from authorized Trust Authority (TA) to generate their tokens served as the identity certificates, but vehicles’ unique ID and master key are registered and downloaded from a VANET server and will not be revealed in the authentication process. Unfortunately, the failure of any RSU will lead to no relaying message, no tokens, and no stamps; then vehicles near the failed RSU will be unable to report any event in the scheme.The Sybil detection schemes in [10, 18] utilize location information to realize identification. Footprint [10] has been proposed to use the trajectories of vehicle for identification while still preserves the anonymity and location privacy of vehicles. However, it fails in detecting conspiracy Sybil attack; in particular, the conspired identity certificates are obtained from malicious vehicles that are far away from the area of Sybil attacker.Figure1 shows an example of conspiracy Sybil attack: the attacker VA came from RSU1 to RSU6; he will have the certificate assigned by {R1,R3,R5,R6}. If VA has conspired with V1, V2, and V3 and gets their ID materials, then he can obtain the certificate of V1 with trajectory {R2,R3,R5,R6} and V2 and V3 with trajectory {R4,R5,R6}, although V1, V2, and V3 did not come to RSU6. That is to say, VA gets 4 identity certificates and fakes that all 4 vehicles came into RSU6; then VA can cheat the traffic system to get more resource with his multiple identity certificate.Figure 1
Example of conspiracy Sybil attack.We proposed DMON (a Sybil attack detection method with obfuscated neighbor relationship of RSUs) in this paper, which is based on the idea of using Footprint as vehicles’ identity certificates. However, the neighbor relationship of signed RSUs is set in the certificates, and the adjacent connections are obfuscated in their relationship vectors. Based on these technologies, the conspired identity certificates can be detected with the signed relationship vectors; meanwhile, vehicles’ locations are preserved as well as the adjacent connections of RSUs.


## 3. System Model and Design Objective

In vehicular networks, a moving vehicle can communicate with other neighbor vehicles or RSUs via vehicle-to-vehicle communications and roadside-to-vehicle communications. RSUs are commonly connected together and have an access to the Internet. Thus, RSUs are called road side infrastructures and the VANETs are named the Internet of Vehicles. This section will introduce key components of VANETs as well as their formal definitions and then illustrate what is conspiracy Sybil attack in detail including some security assumptions and design objectives.


### 3.1. System Model and Formulized Symbol

The components of VANETs in security research include Trust Authority (TA), Road Side Units (RSU), and vehicles with on-board unit (OBU), and there are two communication models: V2V (Vehicle-to-Vehicle) and R2V (RSU-to-Vehicle) communications. Figure2 illustrates the system architecture. We illustrate the components of Figure 2 in detail as follows.Figure 2
Architecture of VANETs.Trust Authority (TA). Trust Authority (TA) is assumed to be completely trustable and secure. In security system, TA is responsible for security operation requiring a trusted third party of the system, such as key management and secret material generation.Road Side Units (RSU). Road Side Units (RSU) can be deployed at intersection or any area of interest to provide wireless access to vehicles as a wireless AP. All RSUs are connected with each other, have an access to Internet, and have a secure channel with TA. RSU is equipped with a wireless model and can send messages to the vehicles located in the nearby area. In this paper, we assume that there are m RSUs in the VANET, denoted as (1)RSU=R1,R2,…,Rm.That is to say, each RSU in VANET will map a numberi, 1≤i≤m, and Ri∈RSU is satisfied.On-Board Unit (OBU). Vehicles are equipped with OBU. With current technologies, OBUs are capable of carrying out cryptographic computations. Vehicles call for authorized information from RSUs with OBUs. We denote that the number of vehicles in the VAET is n, and the set of vehicles could be formulized as follows:(2)V=Vi∣1≤i≤n.We also give the formulized symbol and its description in Notations; these will be used in the remainder of this paper.


### 3.2. Conspiracy Sybil Attack

The conspiracy Sybil attacker is based on abusing multiple identities. There are two ways to obtain the lavished identities from accomplice vehicles.(i)
Attacker takes the accomplice vehicles’ identity directly as themselves.(ii)
Attacker sends the accomplice vehicles’ identity to the RSU for update and then obtains a new temporal identities certificate.If an attacker succeeds in getting identity certificate and passes the authentication, it can launch Sybil attacks. So the Sybil attack detection should be emphasized in identification. However, the conspiracy Sybil attack is different from the others for its Sybil identities are not faked but borrowed from the lavished accomplice vehicles. We conclude 3 challenges as follows.First, the Sybil identity certificate is borrowed from the network inside vehicles, it is real and legitimate, and it has the right to pass the identification. We should recognize whether the ID certificate is used by the correct vehicle. It is more difficult than recognizing whether it is a correct certificate.The second challenge is in the trajectory based identification. The attacker can obtain many authenticated routing messages; then he can fake a new certificate to masquerade a new trajectory based identity as illustrated in Figure1.Finally, the Sybil attacker can update the borrowed conspiracy identity certificate, because the attacker and the certificate are real. If the conspiracy certificate is updated by a RSU, then it is totally the same as a certificate of the attacker. Thus, conspiracy Sybil attacker should be detected before the attacker updates the conspired certificate.


### 3.3. Security Assumption and Design Objective

In this work, we make assumptions as in [10, 12, 21–23].Assumption 1.
Discrete logarithm problem for finite field is hard-solved.Assumption 2.
TA and all RSUs are fully trustworthy.Assumption 3.
RSUs are synchronized.According to Assumptions1 and 2, they are basic assumptions in security research. Assumption 3 is a little strong for the practical system. But a weak synchronization among RSUs is easy to achieve since all RSUs are interconnected by the RSU backbone network in a wire manner.In this paper, our objective is to design an identification scheme for detecting conspiracy Sybil attacker in vehicular ad hoc networks. In the meantime, the detection scheme should satisfy the following 3 items.Privacy Preserving in Vehicles’ ID and Location. Vehicles will not conceal the real unique ID Number when they apply certificate from RSUs, and the signature should be unconditional anonymity as RSUs’ information is bound with the location information of passing vehicles.Online and Independent Detection. Sybil attack should be detected and prevented before the attack starts. An offline detection may cause unbearable loss of life and property before the attack is found. The detection should also be independent, for the collaboration with other RSU will conduct more information leakage and require higher density of RSU deployment.High Efficiency and Low Overhead. Due to the high mobility of vehicles, signature and authentication program should also consider the efficiency requirements in terms of low computation overhead and rapid authentication.


## 3.1. System Model and Formulized Symbol

The components of VANETs in security research include Trust Authority (TA), Road Side Units (RSU), and vehicles with on-board unit (OBU), and there are two communication models: V2V (Vehicle-to-Vehicle) and R2V (RSU-to-Vehicle) communications. Figure2 illustrates the system architecture. We illustrate the components of Figure 2 in detail as follows.Figure 2
Architecture of VANETs.Trust Authority (TA). Trust Authority (TA) is assumed to be completely trustable and secure. In security system, TA is responsible for security operation requiring a trusted third party of the system, such as key management and secret material generation.Road Side Units (RSU). Road Side Units (RSU) can be deployed at intersection or any area of interest to provide wireless access to vehicles as a wireless AP. All RSUs are connected with each other, have an access to Internet, and have a secure channel with TA. RSU is equipped with a wireless model and can send messages to the vehicles located in the nearby area. In this paper, we assume that there are m RSUs in the VANET, denoted as (1)RSU=R1,R2,…,Rm.That is to say, each RSU in VANET will map a numberi, 1≤i≤m, and Ri∈RSU is satisfied.On-Board Unit (OBU). Vehicles are equipped with OBU. With current technologies, OBUs are capable of carrying out cryptographic computations. Vehicles call for authorized information from RSUs with OBUs. We denote that the number of vehicles in the VAET is n, and the set of vehicles could be formulized as follows:(2)V=Vi∣1≤i≤n.We also give the formulized symbol and its description in Notations; these will be used in the remainder of this paper.


## 3.2. Conspiracy Sybil Attack

The conspiracy Sybil attacker is based on abusing multiple identities. There are two ways to obtain the lavished identities from accomplice vehicles.(i)
Attacker takes the accomplice vehicles’ identity directly as themselves.(ii)
Attacker sends the accomplice vehicles’ identity to the RSU for update and then obtains a new temporal identities certificate.If an attacker succeeds in getting identity certificate and passes the authentication, it can launch Sybil attacks. So the Sybil attack detection should be emphasized in identification. However, the conspiracy Sybil attack is different from the others for its Sybil identities are not faked but borrowed from the lavished accomplice vehicles. We conclude 3 challenges as follows.First, the Sybil identity certificate is borrowed from the network inside vehicles, it is real and legitimate, and it has the right to pass the identification. We should recognize whether the ID certificate is used by the correct vehicle. It is more difficult than recognizing whether it is a correct certificate.The second challenge is in the trajectory based identification. The attacker can obtain many authenticated routing messages; then he can fake a new certificate to masquerade a new trajectory based identity as illustrated in Figure1.Finally, the Sybil attacker can update the borrowed conspiracy identity certificate, because the attacker and the certificate are real. If the conspiracy certificate is updated by a RSU, then it is totally the same as a certificate of the attacker. Thus, conspiracy Sybil attacker should be detected before the attacker updates the conspired certificate.


## 3.3. Security Assumption and Design Objective

In this work, we make assumptions as in [10, 12, 21–23].Assumption 1.
Discrete logarithm problem for finite field is hard-solved.Assumption 2.
TA and all RSUs are fully trustworthy.Assumption 3.
RSUs are synchronized.According to Assumptions1 and 2, they are basic assumptions in security research. Assumption 3 is a little strong for the practical system. But a weak synchronization among RSUs is easy to achieve since all RSUs are interconnected by the RSU backbone network in a wire manner.In this paper, our objective is to design an identification scheme for detecting conspiracy Sybil attacker in vehicular ad hoc networks. In the meantime, the detection scheme should satisfy the following 3 items.Privacy Preserving in Vehicles’ ID and Location. Vehicles will not conceal the real unique ID Number when they apply certificate from RSUs, and the signature should be unconditional anonymity as RSUs’ information is bound with the location information of passing vehicles.Online and Independent Detection. Sybil attack should be detected and prevented before the attack starts. An offline detection may cause unbearable loss of life and property before the attack is found. The detection should also be independent, for the collaboration with other RSU will conduct more information leakage and require higher density of RSU deployment.High Efficiency and Low Overhead. Due to the high mobility of vehicles, signature and authentication program should also consider the efficiency requirements in terms of low computation overhead and rapid authentication.


## 4. DMON

DMON is a Sybil attack detection method using obfuscated neighbor relationship of RSUs, which is based on cryptographic ring signature. We set a label vector of the signing RSU’s neighbor relationship into a ring signature scheme [22] to obtain unconditional anonymity and linkable attribution and then hide the adjacent connection relationship of RSU by obfuscating the label vector. Finally, we can detect the Sybil identity certificate by the relation information hidden in the label vectors.


### 4.1. System Initialization

Initializing TA. Let G be a group of prime order p such that the underlying discrete logarithm problem is intractable. Let H:0,1∗→G and H′:0,1∗→Zp be two hash functions. The TA chooses two public parameters g∈G,h∈G. The TA generates the public parameters Sys_P as follows:(3)Sys_P=G,Zp,H,H′,g,h,PKL,Δt,where PKL is the list of RSUs’ public key and Δt is the life period of a RSU signature. The Sys_P will be downloaded into the registered RSU and vehicles.Setting Up RSUs. Each RSU, denoted as Ri, joins the VANET; TA will send Ri a pair of keys of public cryptology system (Key_pubi, Key_seci) and save the public key of this key pair in its Public Key List (PKL) of the public parameters Sys_P. More specifically, when a new RSU enrolls in the system, TA will update the PKL with a new version number and broadcast this updated PKL to all the RSUs in the system.Setting Up Vehicles. Once a vehicle Vi gets in a VANET, it will obtain its registering information and download system parameter Sys_P from TA in an offline way, which means the vehicles should not be allowed to register in Internet. That is to say, the vehicle should be driven to a TA office and the registering information will be written in the hardware of its OBU, just as a vehicle registers in DMV (Department of Motor Vehicles) to get new plate number. Vehicles communicate with RSUs for the authorized message with a session key. TA will generate some pairs of keys for the registering vehicle, we denote the key pairs as the set {(Vi_pubj,Vi_secj)∣j=1,2,…,k}, and then the vehicle can arbitrarily select a pair of key from this set to communicate with a RUS.


### 4.2. Obfuscation for the Relationship Vectors of RSU

After the VANET is initialized, we set a neighbor relationship matrix of RSUs, and the matrix is defined asA_RSU in (4), where the set of the neighbor nodes of Ri are denoted as neighb(Ri),(4)A_RSUij=2i=j1Rj∈neighbRi0others.LetLabj be a label vector of Ri(Ri∈{R1,R2,…,Rm}), as shown in Figure 3, which is a random bijection between the column vectors ofA_RSU and {Labj∣j=1,2,…,m}. Thus, the random bijection obfuscates the mapping relation between the column vectors ofA_RSU and {Labj∣j=1,2,…,m}. We only know that Labj is column vectors ofA_RSU, but we do not know what is column ofA_RSU; that is to say, the obfuscation hides the correlation between the vectors and RSU.Figure 3
Obfuscated mapping from RSU to label vector.Then (5) formulized the obfuscated label matrix composed of the label vector:(5)Lij=A_RSUpqiffLabi⟶Rp,Labj⟶Rq,where → denotes that the label is a mapped neighbor relationship vector of the RSU and the vector of RSU is defined by (4). Usually, the ith column of Lij is denoted as vector Li. Obviously, Li hides the neighbor relationship of a RSU (denoted as Rp), and Rp saves Li but it does not know the hidden relationship in Li for the mapping function from RSU to label is random and obfuscated. Further, this obfuscated mapping will be updated by TA after a certain period of time.Lemma 4.
LetLabi→RpandLabj→Rq; if Rp is a neighbor node of Rq, then it satisfies(6)LiT·Lj≥2i≠j.Proof.
From (4) and (5), when Rp is a neighbor RSU of Rq, we have Lij=Lji=1 and Lii=Ljj=2; then(7)LiT·Lj=∑1≤k≤mLik×Ljk≥Lii×Lji+Lij×Ljj=2+2=4>2.
Thus, (6) is satisfied. In Lemma 4, we assume that a node is not the neighbor of itself, so we let i≠j. In fact, if we define that A_RSUij=1 when i=j in (4); then the following equation is obtained:(8)Lii×Lji+Lij×Ljj=2.Equation (6) is still satisfied.
For clearance in illustration, we denote the label vector ofRp as L(Rp), when Labi→Rp; that is,(9)LRp≡LiwhenLabi⟶Rp.


### 4.3. Ring Signature Based Identification

In DMON, registered vehicles should apply signed messages from the RSU they are passing, and the signature will be used as the secret materials to generate their identity certificates. And an identity certificate will be updated if the owned vehicle passes the authentication of another RSU. The signature of RSU, the identity generation, and the updating process will be discussed in this subsection.


#### 4.3.1. Temporal Identity Generation

When a vehicleVi approaches a RSU, denoted as Rp, it calls for authorized messages by sending one of its public keys M0=Vi_pubj to Rp. Then Rp generates a message M1 as follows:(10)M1=ts,Vi_pub,LRp,where L(Rp) is the obfuscated label vector as defined by (9) and ts is the sending time recorded from Vi’s application message that belong to period [tk,tk+1] as mentioned before.ThenRp signs the message M1 and obtains Sign_Rp(M1). Considering the location privacy, we chose Liu et al. [22] ring signature scheme to provide the RSU anonymity for its security and efficiency.After receivingM1, vehicle Vi encrypts Sign_Rp(M1) by the secret key of the pair (Vi_pubj,Vi_secj) and obtains the core material of its temporal identity Id_Vi(Rp,ts); that is,(11)Encrypt_Vi_secSign_RpM1∝Id_ViRp,ts,where symbol ∝ illustrates that Encrypt_Vi_secSign_RpM1 is only a core component and is not equal to Id_ViRp,ts. The complete description of Id_ViRp,ts is given in (16).Figure4 gives a concise illustration for the temporal identity generation protocol, and the detailed description of the algorithms in the protocol is as follows. It is assumed that the system is driven by the time period event. We denote that the current time ts belongs to time period [tk,tk+1], and the public key pair of Rp is (Key_pubp, Key_secp). In discrete logarithm based signature, we denote that (12)Key_secp=x,y,where x and y are prime number. With the system parameters defined in (1), Rp will sign the application from Vi at the kth time period. Algorithm 5 describes the operating process of Rp in Sign_Rp(M1).Figure 4
Temporal identity generation protocol.Algorithm 5 (Sign_Rp(M1)).
⁡
Step 1. Compute e=H(tk), tag_Rp=ex.
Step 2. Randomly generate rx,ry,c1,…,ch-1,ch+1,…,cm∈RZp, and compute S1 and S2 as in (13) as follows:(13)S1=grxhry∏i=1,i≠hmKey_pubici,S2=erx·tag_Rp·∑1≤i≤m,i≠hci.
Step 3. Solve (14) to obtain ch,(14)c1+⋯+ch+⋯+cmmodp=H′ts∥Y∥LRp∥tag_Rp∥M1∥S1∥S2,where vector Y=Key_pub1,Key_pub2,…,Key_pubmT and Key_pubi(i=1,…,m) is the public key of Ri as setting in the system initializing.
Step 4. Output the signature (15)Sign_RpM1=tag_Rp,ts,LRp,x′,y′,c1,…,cm,where x′=(rx-ch·x)modp, y′=(ry-ch·y)modp, and ch is solved from (14).After receiving Sign_Rp(M1) from Rp, Vi will check the signature Sign_Rp(M1), and the checking process is descripted in Algorithm 6. If the signature checking of Sign_Rp(M1) is passed in Algorithm 6, Vi can obtain its temporal identity certificate as (16)Id_ViRp,ts=M1∥Sign_RpM1∥Vi_pub′∥Encrypt_Vi_secM1∥Sign_RpM1∥Vi_pub′,where Vi_pub′ is another public key of Vi gotten from TA in the setting phase; that is, Vi_pub′∈Vi_pubj,Vi_secj∣j=1,2,…,k.Algorithm 6 (checking process of Sign_Rp(M1)).
⁡
Step 1. Compute e=H(tk).
Step 2. Abstract the value of (tag_Rp,x′,y′,c1,…,cm) from Sign_Rp(M1), and compute W1, W2, c0 as follows:(17)W1=gx′hy′∏i=1mKey_pubici,W2=ex′·tag_Rpc1+⋯+cm,c0=H′ts∥Y∥LRp∥tag_Rp∥M1∥W1∥W2.
Step 3. Checks whether (18) is satisfied,(18)c0=?∑1≤i≤mcimodp.
If it is true, then pass; elseVi regards this round of protocol application as failure.


#### 4.3.2. Temporal Identity Update

In VANETs, vehicles ask for authentication when driving in the area of a new RSU. This subsection considers the authentication process of a vehicleVi coming from the area of Rp and joining in the area of Rq, and we let Rq update the identity certificate of Vi.Figure5 gives a concise description of the updating process of the temporal identity, and Protocol 7 gives detailed operation and computing process, where Id_Vi(Rp,ts) was denoted in (16), M1 was defined by (10), Sign_Rp(M1) denotes message M1 signed by Rp, and Algorithm 6 was presented in Section 4.3.1.Figure 5
Update protocol of vehicle’s temporal identity.Protocol 7 (update protocol of vehicle’s temporal identity).
⁡
Step 1. Vi send Id_Vi(Rp,ts) to Rq and request an update.
Step 2. Rq uses Vi_pub to authenticate Id_Vi(Rp,ts), then checking Sign_Rp(M1) according to Algorithm 6; if the authentication and checking are both passed, then generate M2: (19)M2=ts+1,Vi_pub′,LRp,LRq,Rq obtains Sign_Rq(M2) by using Algorithm 6 to sign on M2 and sends M2∥Sign_Rq(M2) to Vi.
Step 3. After receiving the message M2∥Sign_Rq(M2), Vi uses Algorithm 6 to check it and generates his new identity certification: (20)Id_ViRq,ts+1=M2∥Sign_RqM2∥Vi_pub′′′∥Encrypt_Vi_sec′M1∥Sign_RqM2∥Vi_pub′′,where Vi_pub′′∈{(Vi_pubj,Vi_secj)∣j=1,2,…,k}.In Figure1, when a vehicle Vi calls for an identity update, it sends its current temporal identity Id_Vi(Rp,ts) to the nearest RUS, denoted as Rq, where Rp was the former RSU who signed the current identity and Rq is the RSU who will sign a new identity in this protocol. After receiving the application message from Vi, Rq starts the checking process as Step 2 in Protocol 7 and then generates and sends M2∥Sign_Rq(M2) to Vi if the application message passes the checking. And Vi will obtain the new temporal identity Id_Vi(Rq,ts+1) by Step 3 in Protocol 7.


### 4.4. Detection Method for Conspiracy Sybil Attack

Obtaining multiple legal identity is the basic and key step of Sybil attack; thus, we detect the abusing identity certificates to prevent the attack. In DMON, we employ multiple pairs of public key for vehicles and ring signature scheme of RSU as discussed in [10, 22]. The prevention of the abusing in multiple public key pairs or ring signature is also discussed in the related work [10, 22]. So we focus on conspiracy Sybil attack in this subsection.In conspiracy Sybil attack, the conspired vehicles send their identity information to the attacker; thus, the attacker brings multiple certificate in travel. There are two situations: one is that the conspired vehicle comes along with the attacker; then we think it is not an attack for the identity certificate is always generated by the correct vehicle; another situation is that the conspired vehicles send their identity certificates to the attack far away from the attacker, and the attacker generates a new legal identity by passing the authentication of RSU and further update the certificate.Theorem 8.
If an attackerV obtains the temporal identity certificate Id_Vi(Rp,ts) of a vehicle Vi, it cannot replace the signature information of Rp in Sign_Rp(M1), even if it gets the secret key of Vi.Proof.
We assume that discrete logarithm problem is hard-solved. If an attacker fakes a new signature New_Sign_Rp(M1) to replace Sign_Rp(M1), according to Algorithm 5, it should make the parameters in New_Sign_Rp(M1) satisfy (13) and (14).
Assume thatK=gβhβ′, where β,β′∈Zp, if the attacker succeeds in faking the authentication message (tagi,tsi,Lii,x′i,y′i,c1i,…,cni), i=1,…,n, then we have a linear system of n equations as follows:(21)β=x′i+c1ix1+⋯+cnixni=1,…,n.By the forking Lemma in [24], there is a chance that each successful rewind simulation is at most (ϵ/4)n, where ϵ is the probability that an attacker knows all the parameters, but the attacker did not know ck. Hence, it is quite a small chance to forge New_Sign_Rp(M1).Theorem 9.
When a vehicle obtains a temporal certificate from Rp and updates the certificate in Rp by Protocol 7, if L(Rp)T·L(Rq)≥2, then Rp is in the 2-hop area of Rq.S i g n _ R p ( M 1 ) and Sign_Rq(M2) cannot be replaced from Theorem 8. Then L(Rp) and L(Rq) cannot be altered, which are the label vectors contained in Sign_Rp(M1) and Sign_Rq(M2). According to the proof of Lemma 4, if L(Rp)T·L(Rq)≥2, then there are at least 2 values of k, satisfying that Lik≠0 and Ljk≠0, where Labi→Rp and Labj→Rq. That is to say, Rp and Rq have 2 mutual neighbors RSU at least. Thus, Rp is the neighboror 2-hop neighbor of Rq.We can conclude that the certificate of our DMON cannot be faked from Theorem8, and the conspiracy identity certificate from 2-hop away will be detected by Theorem 8. As mentioned before, the conspiracy identity in the nearby area and the abusing of multiple pseudonym will be detected by the scheme proposed in [10, 22], and we can directly use these schemes in DMON.Now we will also limit the life period of the signature message of RSU, which will recognize the fresh identity from the certificates deliberately assembled by repeated signature. For example, in Figure1, if VA saves the used certificates those were obtained when it travels the routing just like V1, V2, and V3 in the past. In this detection process, it can still use these old certificates with another pseudonym to cheat. Hence, we set a judgment condition in Algorithm 6 to check the freshness and validity of identity certificate:(22)ts+Δt>t,where time ts belongs to time period [tk,tk+1] and t is the current identification time which should belong to period [tk+1,tk+2]. In the meantime, the life period Δt in Sys_P should be carefully set: although a short life period could largely increase the detection rate, a longer period will permit a vehicle drive from a RSU to another and never need to apply a certificate in the same RSU.


## 4.1. System Initialization

Initializing TA. Let G be a group of prime order p such that the underlying discrete logarithm problem is intractable. Let H:0,1∗→G and H′:0,1∗→Zp be two hash functions. The TA chooses two public parameters g∈G,h∈G. The TA generates the public parameters Sys_P as follows:(3)Sys_P=G,Zp,H,H′,g,h,PKL,Δt,where PKL is the list of RSUs’ public key and Δt is the life period of a RSU signature. The Sys_P will be downloaded into the registered RSU and vehicles.Setting Up RSUs. Each RSU, denoted as Ri, joins the VANET; TA will send Ri a pair of keys of public cryptology system (Key_pubi, Key_seci) and save the public key of this key pair in its Public Key List (PKL) of the public parameters Sys_P. More specifically, when a new RSU enrolls in the system, TA will update the PKL with a new version number and broadcast this updated PKL to all the RSUs in the system.Setting Up Vehicles. Once a vehicle Vi gets in a VANET, it will obtain its registering information and download system parameter Sys_P from TA in an offline way, which means the vehicles should not be allowed to register in Internet. That is to say, the vehicle should be driven to a TA office and the registering information will be written in the hardware of its OBU, just as a vehicle registers in DMV (Department of Motor Vehicles) to get new plate number. Vehicles communicate with RSUs for the authorized message with a session key. TA will generate some pairs of keys for the registering vehicle, we denote the key pairs as the set {(Vi_pubj,Vi_secj)∣j=1,2,…,k}, and then the vehicle can arbitrarily select a pair of key from this set to communicate with a RUS.


## 4.2. Obfuscation for the Relationship Vectors of RSU

After the VANET is initialized, we set a neighbor relationship matrix of RSUs, and the matrix is defined asA_RSU in (4), where the set of the neighbor nodes of Ri are denoted as neighb(Ri),(4)A_RSUij=2i=j1Rj∈neighbRi0others.LetLabj be a label vector of Ri(Ri∈{R1,R2,…,Rm}), as shown in Figure 3, which is a random bijection between the column vectors ofA_RSU and {Labj∣j=1,2,…,m}. Thus, the random bijection obfuscates the mapping relation between the column vectors ofA_RSU and {Labj∣j=1,2,…,m}. We only know that Labj is column vectors ofA_RSU, but we do not know what is column ofA_RSU; that is to say, the obfuscation hides the correlation between the vectors and RSU.Figure 3
Obfuscated mapping from RSU to label vector.Then (5) formulized the obfuscated label matrix composed of the label vector:(5)Lij=A_RSUpqiffLabi⟶Rp,Labj⟶Rq,where → denotes that the label is a mapped neighbor relationship vector of the RSU and the vector of RSU is defined by (4). Usually, the ith column of Lij is denoted as vector Li. Obviously, Li hides the neighbor relationship of a RSU (denoted as Rp), and Rp saves Li but it does not know the hidden relationship in Li for the mapping function from RSU to label is random and obfuscated. Further, this obfuscated mapping will be updated by TA after a certain period of time.Lemma 4.
LetLabi→RpandLabj→Rq; if Rp is a neighbor node of Rq, then it satisfies(6)LiT·Lj≥2i≠j.Proof.
From (4) and (5), when Rp is a neighbor RSU of Rq, we have Lij=Lji=1 and Lii=Ljj=2; then(7)LiT·Lj=∑1≤k≤mLik×Ljk≥Lii×Lji+Lij×Ljj=2+2=4>2.
Thus, (6) is satisfied. In Lemma 4, we assume that a node is not the neighbor of itself, so we let i≠j. In fact, if we define that A_RSUij=1 when i=j in (4); then the following equation is obtained:(8)Lii×Lji+Lij×Ljj=2.Equation (6) is still satisfied.
For clearance in illustration, we denote the label vector ofRp as L(Rp), when Labi→Rp; that is,(9)LRp≡LiwhenLabi⟶Rp.


## 4.3. Ring Signature Based Identification

In DMON, registered vehicles should apply signed messages from the RSU they are passing, and the signature will be used as the secret materials to generate their identity certificates. And an identity certificate will be updated if the owned vehicle passes the authentication of another RSU. The signature of RSU, the identity generation, and the updating process will be discussed in this subsection.


### 4.3.1. Temporal Identity Generation

When a vehicleVi approaches a RSU, denoted as Rp, it calls for authorized messages by sending one of its public keys M0=Vi_pubj to Rp. Then Rp generates a message M1 as follows:(10)M1=ts,Vi_pub,LRp,where L(Rp) is the obfuscated label vector as defined by (9) and ts is the sending time recorded from Vi’s application message that belong to period [tk,tk+1] as mentioned before.ThenRp signs the message M1 and obtains Sign_Rp(M1). Considering the location privacy, we chose Liu et al. [22] ring signature scheme to provide the RSU anonymity for its security and efficiency.After receivingM1, vehicle Vi encrypts Sign_Rp(M1) by the secret key of the pair (Vi_pubj,Vi_secj) and obtains the core material of its temporal identity Id_Vi(Rp,ts); that is,(11)Encrypt_Vi_secSign_RpM1∝Id_ViRp,ts,where symbol ∝ illustrates that Encrypt_Vi_secSign_RpM1 is only a core component and is not equal to Id_ViRp,ts. The complete description of Id_ViRp,ts is given in (16).Figure4 gives a concise illustration for the temporal identity generation protocol, and the detailed description of the algorithms in the protocol is as follows. It is assumed that the system is driven by the time period event. We denote that the current time ts belongs to time period [tk,tk+1], and the public key pair of Rp is (Key_pubp, Key_secp). In discrete logarithm based signature, we denote that (12)Key_secp=x,y,where x and y are prime number. With the system parameters defined in (1), Rp will sign the application from Vi at the kth time period. Algorithm 5 describes the operating process of Rp in Sign_Rp(M1).Figure 4
Temporal identity generation protocol.Algorithm 5 (Sign_Rp(M1)).
⁡
Step 1. Compute e=H(tk), tag_Rp=ex.
Step 2. Randomly generate rx,ry,c1,…,ch-1,ch+1,…,cm∈RZp, and compute S1 and S2 as in (13) as follows:(13)S1=grxhry∏i=1,i≠hmKey_pubici,S2=erx·tag_Rp·∑1≤i≤m,i≠hci.
Step 3. Solve (14) to obtain ch,(14)c1+⋯+ch+⋯+cmmodp=H′ts∥Y∥LRp∥tag_Rp∥M1∥S1∥S2,where vector Y=Key_pub1,Key_pub2,…,Key_pubmT and Key_pubi(i=1,…,m) is the public key of Ri as setting in the system initializing.
Step 4. Output the signature (15)Sign_RpM1=tag_Rp,ts,LRp,x′,y′,c1,…,cm,where x′=(rx-ch·x)modp, y′=(ry-ch·y)modp, and ch is solved from (14).After receiving Sign_Rp(M1) from Rp, Vi will check the signature Sign_Rp(M1), and the checking process is descripted in Algorithm 6. If the signature checking of Sign_Rp(M1) is passed in Algorithm 6, Vi can obtain its temporal identity certificate as (16)Id_ViRp,ts=M1∥Sign_RpM1∥Vi_pub′∥Encrypt_Vi_secM1∥Sign_RpM1∥Vi_pub′,where Vi_pub′ is another public key of Vi gotten from TA in the setting phase; that is, Vi_pub′∈Vi_pubj,Vi_secj∣j=1,2,…,k.Algorithm 6 (checking process of Sign_Rp(M1)).
⁡
Step 1. Compute e=H(tk).
Step 2. Abstract the value of (tag_Rp,x′,y′,c1,…,cm) from Sign_Rp(M1), and compute W1, W2, c0 as follows:(17)W1=gx′hy′∏i=1mKey_pubici,W2=ex′·tag_Rpc1+⋯+cm,c0=H′ts∥Y∥LRp∥tag_Rp∥M1∥W1∥W2.
Step 3. Checks whether (18) is satisfied,(18)c0=?∑1≤i≤mcimodp.
If it is true, then pass; elseVi regards this round of protocol application as failure.


### 4.3.2. Temporal Identity Update

In VANETs, vehicles ask for authentication when driving in the area of a new RSU. This subsection considers the authentication process of a vehicleVi coming from the area of Rp and joining in the area of Rq, and we let Rq update the identity certificate of Vi.Figure5 gives a concise description of the updating process of the temporal identity, and Protocol 7 gives detailed operation and computing process, where Id_Vi(Rp,ts) was denoted in (16), M1 was defined by (10), Sign_Rp(M1) denotes message M1 signed by Rp, and Algorithm 6 was presented in Section 4.3.1.Figure 5
Update protocol of vehicle’s temporal identity.Protocol 7 (update protocol of vehicle’s temporal identity).
⁡
Step 1. Vi send Id_Vi(Rp,ts) to Rq and request an update.
Step 2. Rq uses Vi_pub to authenticate Id_Vi(Rp,ts), then checking Sign_Rp(M1) according to Algorithm 6; if the authentication and checking are both passed, then generate M2: (19)M2=ts+1,Vi_pub′,LRp,LRq,Rq obtains Sign_Rq(M2) by using Algorithm 6 to sign on M2 and sends M2∥Sign_Rq(M2) to Vi.
Step 3. After receiving the message M2∥Sign_Rq(M2), Vi uses Algorithm 6 to check it and generates his new identity certification: (20)Id_ViRq,ts+1=M2∥Sign_RqM2∥Vi_pub′′′∥Encrypt_Vi_sec′M1∥Sign_RqM2∥Vi_pub′′,where Vi_pub′′∈{(Vi_pubj,Vi_secj)∣j=1,2,…,k}.In Figure1, when a vehicle Vi calls for an identity update, it sends its current temporal identity Id_Vi(Rp,ts) to the nearest RUS, denoted as Rq, where Rp was the former RSU who signed the current identity and Rq is the RSU who will sign a new identity in this protocol. After receiving the application message from Vi, Rq starts the checking process as Step 2 in Protocol 7 and then generates and sends M2∥Sign_Rq(M2) to Vi if the application message passes the checking. And Vi will obtain the new temporal identity Id_Vi(Rq,ts+1) by Step 3 in Protocol 7.


## 4.3.1. Temporal Identity Generation

When a vehicleVi approaches a RSU, denoted as Rp, it calls for authorized messages by sending one of its public keys M0=Vi_pubj to Rp. Then Rp generates a message M1 as follows:(10)M1=ts,Vi_pub,LRp,where L(Rp) is the obfuscated label vector as defined by (9) and ts is the sending time recorded from Vi’s application message that belong to period [tk,tk+1] as mentioned before.ThenRp signs the message M1 and obtains Sign_Rp(M1). Considering the location privacy, we chose Liu et al. [22] ring signature scheme to provide the RSU anonymity for its security and efficiency.After receivingM1, vehicle Vi encrypts Sign_Rp(M1) by the secret key of the pair (Vi_pubj,Vi_secj) and obtains the core material of its temporal identity Id_Vi(Rp,ts); that is,(11)Encrypt_Vi_secSign_RpM1∝Id_ViRp,ts,where symbol ∝ illustrates that Encrypt_Vi_secSign_RpM1 is only a core component and is not equal to Id_ViRp,ts. The complete description of Id_ViRp,ts is given in (16).Figure4 gives a concise illustration for the temporal identity generation protocol, and the detailed description of the algorithms in the protocol is as follows. It is assumed that the system is driven by the time period event. We denote that the current time ts belongs to time period [tk,tk+1], and the public key pair of Rp is (Key_pubp, Key_secp). In discrete logarithm based signature, we denote that (12)Key_secp=x,y,where x and y are prime number. With the system parameters defined in (1), Rp will sign the application from Vi at the kth time period. Algorithm 5 describes the operating process of Rp in Sign_Rp(M1).Figure 4
Temporal identity generation protocol.Algorithm 5 (Sign_Rp(M1)).
⁡
Step 1. Compute e=H(tk), tag_Rp=ex.
Step 2. Randomly generate rx,ry,c1,…,ch-1,ch+1,…,cm∈RZp, and compute S1 and S2 as in (13) as follows:(13)S1=grxhry∏i=1,i≠hmKey_pubici,S2=erx·tag_Rp·∑1≤i≤m,i≠hci.
Step 3. Solve (14) to obtain ch,(14)c1+⋯+ch+⋯+cmmodp=H′ts∥Y∥LRp∥tag_Rp∥M1∥S1∥S2,where vector Y=Key_pub1,Key_pub2,…,Key_pubmT and Key_pubi(i=1,…,m) is the public key of Ri as setting in the system initializing.
Step 4. Output the signature (15)Sign_RpM1=tag_Rp,ts,LRp,x′,y′,c1,…,cm,where x′=(rx-ch·x)modp, y′=(ry-ch·y)modp, and ch is solved from (14).After receiving Sign_Rp(M1) from Rp, Vi will check the signature Sign_Rp(M1), and the checking process is descripted in Algorithm 6. If the signature checking of Sign_Rp(M1) is passed in Algorithm 6, Vi can obtain its temporal identity certificate as (16)Id_ViRp,ts=M1∥Sign_RpM1∥Vi_pub′∥Encrypt_Vi_secM1∥Sign_RpM1∥Vi_pub′,where Vi_pub′ is another public key of Vi gotten from TA in the setting phase; that is, Vi_pub′∈Vi_pubj,Vi_secj∣j=1,2,…,k.Algorithm 6 (checking process of Sign_Rp(M1)).
⁡
Step 1. Compute e=H(tk).
Step 2. Abstract the value of (tag_Rp,x′,y′,c1,…,cm) from Sign_Rp(M1), and compute W1, W2, c0 as follows:(17)W1=gx′hy′∏i=1mKey_pubici,W2=ex′·tag_Rpc1+⋯+cm,c0=H′ts∥Y∥LRp∥tag_Rp∥M1∥W1∥W2.
Step 3. Checks whether (18) is satisfied,(18)c0=?∑1≤i≤mcimodp.
If it is true, then pass; elseVi regards this round of protocol application as failure.


## 4.3.2. Temporal Identity Update

In VANETs, vehicles ask for authentication when driving in the area of a new RSU. This subsection considers the authentication process of a vehicleVi coming from the area of Rp and joining in the area of Rq, and we let Rq update the identity certificate of Vi.Figure5 gives a concise description of the updating process of the temporal identity, and Protocol 7 gives detailed operation and computing process, where Id_Vi(Rp,ts) was denoted in (16), M1 was defined by (10), Sign_Rp(M1) denotes message M1 signed by Rp, and Algorithm 6 was presented in Section 4.3.1.Figure 5
Update protocol of vehicle’s temporal identity.Protocol 7 (update protocol of vehicle’s temporal identity).
⁡
Step 1. Vi send Id_Vi(Rp,ts) to Rq and request an update.
Step 2. Rq uses Vi_pub to authenticate Id_Vi(Rp,ts), then checking Sign_Rp(M1) according to Algorithm 6; if the authentication and checking are both passed, then generate M2: (19)M2=ts+1,Vi_pub′,LRp,LRq,Rq obtains Sign_Rq(M2) by using Algorithm 6 to sign on M2 and sends M2∥Sign_Rq(M2) to Vi.
Step 3. After receiving the message M2∥Sign_Rq(M2), Vi uses Algorithm 6 to check it and generates his new identity certification: (20)Id_ViRq,ts+1=M2∥Sign_RqM2∥Vi_pub′′′∥Encrypt_Vi_sec′M1∥Sign_RqM2∥Vi_pub′′,where Vi_pub′′∈{(Vi_pubj,Vi_secj)∣j=1,2,…,k}.In Figure1, when a vehicle Vi calls for an identity update, it sends its current temporal identity Id_Vi(Rp,ts) to the nearest RUS, denoted as Rq, where Rp was the former RSU who signed the current identity and Rq is the RSU who will sign a new identity in this protocol. After receiving the application message from Vi, Rq starts the checking process as Step 2 in Protocol 7 and then generates and sends M2∥Sign_Rq(M2) to Vi if the application message passes the checking. And Vi will obtain the new temporal identity Id_Vi(Rq,ts+1) by Step 3 in Protocol 7.


## 4.4. Detection Method for Conspiracy Sybil Attack

Obtaining multiple legal identity is the basic and key step of Sybil attack; thus, we detect the abusing identity certificates to prevent the attack. In DMON, we employ multiple pairs of public key for vehicles and ring signature scheme of RSU as discussed in [10, 22]. The prevention of the abusing in multiple public key pairs or ring signature is also discussed in the related work [10, 22]. So we focus on conspiracy Sybil attack in this subsection.In conspiracy Sybil attack, the conspired vehicles send their identity information to the attacker; thus, the attacker brings multiple certificate in travel. There are two situations: one is that the conspired vehicle comes along with the attacker; then we think it is not an attack for the identity certificate is always generated by the correct vehicle; another situation is that the conspired vehicles send their identity certificates to the attack far away from the attacker, and the attacker generates a new legal identity by passing the authentication of RSU and further update the certificate.Theorem 8.
If an attackerV obtains the temporal identity certificate Id_Vi(Rp,ts) of a vehicle Vi, it cannot replace the signature information of Rp in Sign_Rp(M1), even if it gets the secret key of Vi.Proof.
We assume that discrete logarithm problem is hard-solved. If an attacker fakes a new signature New_Sign_Rp(M1) to replace Sign_Rp(M1), according to Algorithm 5, it should make the parameters in New_Sign_Rp(M1) satisfy (13) and (14).
Assume thatK=gβhβ′, where β,β′∈Zp, if the attacker succeeds in faking the authentication message (tagi,tsi,Lii,x′i,y′i,c1i,…,cni), i=1,…,n, then we have a linear system of n equations as follows:(21)β=x′i+c1ix1+⋯+cnixni=1,…,n.By the forking Lemma in [24], there is a chance that each successful rewind simulation is at most (ϵ/4)n, where ϵ is the probability that an attacker knows all the parameters, but the attacker did not know ck. Hence, it is quite a small chance to forge New_Sign_Rp(M1).Theorem 9.
When a vehicle obtains a temporal certificate from Rp and updates the certificate in Rp by Protocol 7, if L(Rp)T·L(Rq)≥2, then Rp is in the 2-hop area of Rq.S i g n _ R p ( M 1 ) and Sign_Rq(M2) cannot be replaced from Theorem 8. Then L(Rp) and L(Rq) cannot be altered, which are the label vectors contained in Sign_Rp(M1) and Sign_Rq(M2). According to the proof of Lemma 4, if L(Rp)T·L(Rq)≥2, then there are at least 2 values of k, satisfying that Lik≠0 and Ljk≠0, where Labi→Rp and Labj→Rq. That is to say, Rp and Rq have 2 mutual neighbors RSU at least. Thus, Rp is the neighboror 2-hop neighbor of Rq.We can conclude that the certificate of our DMON cannot be faked from Theorem8, and the conspiracy identity certificate from 2-hop away will be detected by Theorem 8. As mentioned before, the conspiracy identity in the nearby area and the abusing of multiple pseudonym will be detected by the scheme proposed in [10, 22], and we can directly use these schemes in DMON.Now we will also limit the life period of the signature message of RSU, which will recognize the fresh identity from the certificates deliberately assembled by repeated signature. For example, in Figure1, if VA saves the used certificates those were obtained when it travels the routing just like V1, V2, and V3 in the past. In this detection process, it can still use these old certificates with another pseudonym to cheat. Hence, we set a judgment condition in Algorithm 6 to check the freshness and validity of identity certificate:(22)ts+Δt>t,where time ts belongs to time period [tk,tk+1] and t is the current identification time which should belong to period [tk+1,tk+2]. In the meantime, the life period Δt in Sys_P should be carefully set: although a short life period could largely increase the detection rate, a longer period will permit a vehicle drive from a RSU to another and never need to apply a certificate in the same RSU.


## 5. Performance Analysis and Evaluation

Four objectives are given in designing DMON: detecting conspiracy Sybil attack, preserving privacy information (vehicles’ ID and Location), achieving online and independent detection, and obtaining high efficiency and low overhead. Section4.4 descripts the detection method, and Theorems 8 and 9 support online and independent detection. This section will evaluate the performance of proposed scheme in views of privacy leaking and computation overhead; thereafter, detection rates will be simulated.


### 5.1. Privacy Protection

Vehicles have two aspects of privacy, identity privacy and trajectory privacy. The ring signature scheme is employed in DMON ensuring the identity privacy. Trajectory privacy can be guaranteed by Theorem10.Theorem 10.
Attacker cannot obtain the vehicle’s trajectory from the location of RSU included in the identity certificate defined by Algorithms5 and 6 and Protocol 7.Proof.
In Algorithm5, a vehicle Vi will generate tag_Rp=ex when it drives in the area of a RSU, where x is abstracted from the random selected public key of Vi. Thus, RSU signs different messages for different vehicles, and the signature is unlinkable and untraceable. That is to say, the attacker cannot obtain the location and trajectory information from the signed certificate of RSU.
On the other hand, the identity certificate defined in (16) does not reveal any information of RSU in plain text. The label vector L(Rp) contains the neighbor relationship, but the relationship was obfuscated and hidden by Figure 3, (4), (5), and (9). Unordered obfuscation and periodic update make the other RSUs and vehicle unable to catch the relation between L(Rp) and Rp. Hence, the attacker cannot analyze the routing information from the label vector L(Rp) contained in the signature of RSU.


### 5.2. Computation Cost

There are four kinds of operations in the ring signature scheme. They are modular addition, modular multiplication, modular exponentiation, and secure cryptographic hash, denoted asAdd,Mul,Exp, andHash, respectively. Since theExp andHash operations are far more computationally expensive than the other two operations, so we only consider the number of Expand Hash operations to analyze the computational complexity of this scheme. We evaluate the computation cost of DMON as follows.(1) Cost of Signing a Signature in Algorithm5. Once a RSU joins in the system, it first gets the system parameter and computes e and tag_Rp. Then RSUs randomly choose parameters for signature, that is, rx,ry,c1,…,ch-1,ch+1,…,cm, and compute S1 and S2. The computed S1 and S2 are both multibases exponentiation. However, S1, S2, e, and tag_Rp can be used in the next signature after one-time computing until the certificate updates. Therefore, at most occasion, the RSU just computes the hash value cm.(2) Cost of Signature Verification in Algorithm6. When a vehicle verifies a signature issued by a certain RSU, it should compute W1, W2, and c0, where the cost of computing W1 and W2 are almost two multibases exponentiation. So we need two multibases exponentiation and one hash to verify the signature. We contrast the computation overhead of verification of DMON with Footprint [10] as shown in Figure 6.Figure 6
Computation cost of signature verification.


### 5.3. Performance Simulation

MOVE [25] and SUMO [26] are used to configure experimental environments. The real world map is downloaded from TIGER database file, as showed in Figure 7. In this map, there are 383 points and 1,188 road segments in total.Figure 7
Real world map downloaded from TIGER.In the simulation experiments, the traffic light is set to get more reliable results. In the situation of traffic congestion, vehicles would wait for a long time, but in a smooth traffic, a conspiracy vehicle might pass 2 or 3 RSUs in one minute. The number of Sybil attackers is set as the ratioρ=10% of all nodes. The attackers can independently launch a Sybil attack by the conspired ID, but the conspiracy vehicles are not involved in the attacks.We first study the influence of RSU deployment in detection. In the experiment, we set the minimum distance between RSUs change from 150 meters to 350 meters; Figure8 shows an obvious influence on the conspiracy Sybil attack detection, in which sparser RSU deployment would rapidly reduce the system performance. From Figure 8, we argue that 250 is a good minimum distance for RSU quantity which is not too large, and false positive error and false negative error are adoptable.Figure 8
Influence of RSU distance.Then we simulate the life periodΔt of vehicle identities to analyze its influence. We set the RSU in 2 steps. First, we deploy RSUs at the intersections which have large traffic volume. Then an RSU is deployed at an intersection if it is more than 250 meters away from the nearest deployed RSU, where 250 meters is a good value concluded from Figure 7. By this way, we deploy 100 RSUs in the map. We define that 2 RSUs are neighbors if the distance between them is less than 400 meters. As shown in Figure 9(a), 10 percent of vehicles are set as conspiracy vehicles in the simulation system; when Δt comes to 200 seconds, the false negative error increases in Figure 9(a). The reason is that attackers have enough time to obtain more valid conspiracy temporal identity certificates. Meanwhile, the false positive drops for the reason that legal vehicles would not be verified illegal for the life period when they collect more temporal identity certificates in their trajectory.Figure 9
Influence of life periodΔt.
(a)
10% conspiracy vehicles (b)
10% vehicles will be chosen as conspiracyIn Figure9(b), we still set 10 percent of vehicles are conspired, but the conspiracy vehicles are randomly selected by the attacker. Then the false negative is a higher than that with static ones in Figure 9(a). The reason is that the mobility of vehicles is independent; an attacker will get more temporal identity certificate if it can choose the conspiracy vehicles nearby.


## 5.1. Privacy Protection

Vehicles have two aspects of privacy, identity privacy and trajectory privacy. The ring signature scheme is employed in DMON ensuring the identity privacy. Trajectory privacy can be guaranteed by Theorem10.Theorem 10.
Attacker cannot obtain the vehicle’s trajectory from the location of RSU included in the identity certificate defined by Algorithms5 and 6 and Protocol 7.Proof.
In Algorithm5, a vehicle Vi will generate tag_Rp=ex when it drives in the area of a RSU, where x is abstracted from the random selected public key of Vi. Thus, RSU signs different messages for different vehicles, and the signature is unlinkable and untraceable. That is to say, the attacker cannot obtain the location and trajectory information from the signed certificate of RSU.
On the other hand, the identity certificate defined in (16) does not reveal any information of RSU in plain text. The label vector L(Rp) contains the neighbor relationship, but the relationship was obfuscated and hidden by Figure 3, (4), (5), and (9). Unordered obfuscation and periodic update make the other RSUs and vehicle unable to catch the relation between L(Rp) and Rp. Hence, the attacker cannot analyze the routing information from the label vector L(Rp) contained in the signature of RSU.


## 5.2. Computation Cost

There are four kinds of operations in the ring signature scheme. They are modular addition, modular multiplication, modular exponentiation, and secure cryptographic hash, denoted asAdd,Mul,Exp, andHash, respectively. Since theExp andHash operations are far more computationally expensive than the other two operations, so we only consider the number of Expand Hash operations to analyze the computational complexity of this scheme. We evaluate the computation cost of DMON as follows.(1) Cost of Signing a Signature in Algorithm5. Once a RSU joins in the system, it first gets the system parameter and computes e and tag_Rp. Then RSUs randomly choose parameters for signature, that is, rx,ry,c1,…,ch-1,ch+1,…,cm, and compute S1 and S2. The computed S1 and S2 are both multibases exponentiation. However, S1, S2, e, and tag_Rp can be used in the next signature after one-time computing until the certificate updates. Therefore, at most occasion, the RSU just computes the hash value cm.(2) Cost of Signature Verification in Algorithm6. When a vehicle verifies a signature issued by a certain RSU, it should compute W1, W2, and c0, where the cost of computing W1 and W2 are almost two multibases exponentiation. So we need two multibases exponentiation and one hash to verify the signature. We contrast the computation overhead of verification of DMON with Footprint [10] as shown in Figure 6.Figure 6
Computation cost of signature verification.


## 5.3. Performance Simulation

MOVE [25] and SUMO [26] are used to configure experimental environments. The real world map is downloaded from TIGER database file, as showed in Figure 7. In this map, there are 383 points and 1,188 road segments in total.Figure 7
Real world map downloaded from TIGER.In the simulation experiments, the traffic light is set to get more reliable results. In the situation of traffic congestion, vehicles would wait for a long time, but in a smooth traffic, a conspiracy vehicle might pass 2 or 3 RSUs in one minute. The number of Sybil attackers is set as the ratioρ=10% of all nodes. The attackers can independently launch a Sybil attack by the conspired ID, but the conspiracy vehicles are not involved in the attacks.We first study the influence of RSU deployment in detection. In the experiment, we set the minimum distance between RSUs change from 150 meters to 350 meters; Figure8 shows an obvious influence on the conspiracy Sybil attack detection, in which sparser RSU deployment would rapidly reduce the system performance. From Figure 8, we argue that 250 is a good minimum distance for RSU quantity which is not too large, and false positive error and false negative error are adoptable.Figure 8
Influence of RSU distance.Then we simulate the life periodΔt of vehicle identities to analyze its influence. We set the RSU in 2 steps. First, we deploy RSUs at the intersections which have large traffic volume. Then an RSU is deployed at an intersection if it is more than 250 meters away from the nearest deployed RSU, where 250 meters is a good value concluded from Figure 7. By this way, we deploy 100 RSUs in the map. We define that 2 RSUs are neighbors if the distance between them is less than 400 meters. As shown in Figure 9(a), 10 percent of vehicles are set as conspiracy vehicles in the simulation system; when Δt comes to 200 seconds, the false negative error increases in Figure 9(a). The reason is that attackers have enough time to obtain more valid conspiracy temporal identity certificates. Meanwhile, the false positive drops for the reason that legal vehicles would not be verified illegal for the life period when they collect more temporal identity certificates in their trajectory.Figure 9
Influence of life periodΔt.
(a)
10% conspiracy vehicles (b)
10% vehicles will be chosen as conspiracyIn Figure9(b), we still set 10 percent of vehicles are conspired, but the conspiracy vehicles are randomly selected by the attacker. Then the false negative is a higher than that with static ones in Figure 9(a). The reason is that the mobility of vehicles is independent; an attacker will get more temporal identity certificate if it can choose the conspiracy vehicles nearby.


## 6. Conclusion

This paper focuses on a novel conspiracy Sybil attack which has main difference in obtaining Sybil identities from conspired vehicles. The forged identities are legal and cannot be detected by a general detection scheme. For this reason, a new detection scheme, named DMON, is proposed to detect conspiracy Sybil attack. DMON applies the signed certificate as the temporal identity of vehicles in VANETs and adopts the neighbor relationship of RSUs to detect faked identity. Meanwhile, an obfuscated label is presented to hide RSU’s neighbor relationship with the purpose of preventing trajectory based privacy from leakage. DMON also has limitations in an assumption that indicates information synchronization of all RSUs in signature verification. The assumption is argued to be a little strong in practice, though the independent detection is realized through computing vector product in DMON. In future work, we will focus on identity authentication with local information only.



---

*Source: 4682538-2017-02-07.xml*