Security for Mobile and Vehicular Ad hoc Networks

Abderrahim BENSLIMANE abderrahim.benslimane@univ-avignon.fr

LIA- Avignon University

1

IWCMC June 28, Caen, France

Outline
Security on Mobile Ad hoc Networks (MANETs) Security in Vehicular Ad hoc Networks (VANETs)

2
A. Benslimane IWCMC2010

Outline Part I
Security on Mobile Ad hoc Networks (MANETs)
Mobile Ad hoc Networks characteristics MANETs Applications Vulnerability and Challenges Network Security Requirements MANET Security Attacks Security protocols A new MAC layer contribution A new cross-layer contribution Some secure routing protocols Two new contributions at the routing layer
A Secure Architecture for MANET A Confident Community to Secure MANET
A. Benslimane IWCMC2010

Mobile Ad hoc Networks characteristics

Autonomous nodes create a network on their own initiative Self-organizing Open network Easy to deploy/extend Mobility and dynamic topology Wireless communication medium Absence of a fixed infrastructure Multi-hop communication

4
A. Benslimane IWCMC2010

MANETs Applications
Rescue missions, Military operations, WLAN extension, Video-conferencing

5
A. Benslimane IWCMC2010

Vulnerability & Challenges

Shared broadcast radio channel
Easier to passively eavesdrop

De-centralized Control
No trustworthy third party

Unreliable communication
Constantly changing topology

Limited Resources
Limited battery power Limited computational power

Unfriendly Environment
Malicious nodes, Selfish nodes,

Physical vulnerability
Vulnerable to theft,
6
A. Benslimane IWCMC2010

Security Requirements
Authentification
With a key or a card, With a password or a code, With a biometric identification

(1/2)

Confidentiality
protection against non-authorized disclosure of information

Integrity
protection against non-authorized modification of data

Availability
protection against services disturbances (Dos)

Non-repudiation
guarantee that the sender of a message cannot later deny A. Benslimane IWCMC2010 having sent the message
7

MANET Security Attacks

Attacks types can be classified by each layer: Physical layer attacks MAC layer attacks Network and routing layer attacks Transport layer attacks Cross-layer attacks
8
A. Benslimane IWCMC2010

MANET Security Attacks

Physical layer attacks
The jamming attack: is based on radio medium commu nication. A jamming source is able to disturb the entire n etwork or a part of the network; that depends on its powerf ul level. The tampering attack: node can physically be compro mised, the attacker can extract sensitive information such a s cryptography keys.

9
A. Benslimane IWCMC2010

MANET Security Attacks

MAC layer attacks
Greedy behavior: the back off manipulation by the attacker in
order to increase its bandwidth and create unfairness situation

Malicious collision: the attacker produces a collision in order to prevent its neighbours nodes to communicate or cooperate

10
A. Benslimane IWCMC2010

MANET Security Attacks

Network and routing layer attacks
Active attacks Routing procedure Passive attacks Packet silent Eavesdropping of discard data: -Traffic analysis, Wormhole attacks Impersonation Sybil attacks
11
A. Benslimane IWCMC2010

Flood network

False reply

Route request

Route broken message

False routing information

-Sniffing to compromise keys,

MANET Security Attacks

Transport layer attacks
Desynchronization attack: consists in the disruption of an
existing connection by desynchronization of the sequence number

SYN Flooding: the attacker may repeatedly make new connection

requests until the maximum limit connection is reached

12
A. Benslimane IWCMC2010

MANET Security Attacks

Cross-layer attacks
It is complex attacks based on more than one layer to form the attack

Shortcut or detour attack: is based on MAC layer to

create an attack at the network layer

13
A. Benslimane IWCMC2010

Security Protocols
Symmetric cryptography
the key which is used for encryption is the same that is used for decryption, DES, 3DES, ...) (

Asymmetric (public key) Cryptography

each node has a private key which it is the only one to own, and the public key known by its correspondents, (RSA, ElGamal, )

Cryptographic hash function

It is irreversible function which takes as input a message of arbirary lenght and produces as output a message digest of fixed length (MD5, SHA, )

Digital signatures
allows the message receiver to check the sender's identity and the sender also cannot refuse the message content then
14
A. Benslimane IWCMC2010

Security Protocols
Threshold cryptography
(n, k +1) threshold cryptography scheme, the secret key is divided into n partial shares where at least k+1 of n are partial shares which are needed to generate a secret S. The advantage is its increased availability,

PKI (Public Key infrastructure)

A framework for creating a secure method for exchanging information based on public key cryptography. The foundation of a PKI is the certificate authority (CA), which issues digital certificates that authenticate the identity of organizations and individuals The certificates are also used to sign messages
15
A. Benslimane IWCMC2010

Security Protocols
Trust models
1. Hierarchical model

2. peer to peer model

16
A. Benslimane IWCMC2010

A new MAC Layer Contribution

Modeling and Analysis of Predictable Random Backoff in Selfish Environments [15]

17 A. Benslimane IWCMC2010

Behavior: Selfish Behavior: Manipulation of CW

18 A. Benslimane IWCMC2010

Predictable Random Backoff

IEEE 802.11 Binary Exponential Backoff (BEB)
Initially, cw is randomly selected from [0, CWmin] In the presence of failed transmission, cw is selected from [0, 2i CWmin] , i is the number of failed transmission Upon successful transmission, cw is selected from [0, CWmin]

Predictable Random Backoff (PRB)

Initially, cw is randomly selected from [0, CWmin] In the presence of failed transmission, cw is selected from [0, 2i CWmin] , i is the number of failed transmission Upon successful transmission, however: If cw is less than threshold, cw is selected from [CWlb, CWmin] If cw is larger than threshold, cw is selected from [0, CWmin]
19 A. Benslimane IWCMC2010

CrossA new Cross-Layer Contribution

Inter Layer Attacks in Mobile Ad Hoc Networks [16]

A. Benslimane IWCMC2010

The Problem
cw, Due to the random selection of cw, manipulation of cw is t he most difficult selfish behavior to be detected Some work has been done on the detection and reaction of selfish behavior
UIUC scheme: 1) Let the receiver to assign the contention window for the tran smitter; 2) The receiver will monitor the idle time slots between consecu tive multiple transmissions, it will give an alarm if the transmit ter fails to obey the assignment upon a pre-defined threshold DOMINO: 1) No reaction scheme, only detection 2) Detection of manipulation of cw is similar to UIUC, however it can also detect manipulation of NAV and IFS

A. Benslimane IWCMC2010

The Problem cont.

Problems with current methods: a selfish / malicious node sel ectively manipulate cw for routing packets to distract/attract f lows:

Detour: selectively using large cw to reduce the chance to be selected as a forwarding node Shortcut: selectively using small cw to increase t he chance to be selected as forwarding node A misbehaved node does not need to know the ex act packet type, i.e., a broadcast packet most lik ely indicates a route request packet Hard to be detected because less packet informa tion can be collected for statistical analysis
Therefore, we need some new methods to mitigate these new at tacks
A. Benslimane IWCMC2010

Inter Layer Attacks in Mobile Ad Hoc Networks

PSD-I: Randomized Routing Message Selection (MA C)
Define a timeout timer; Buffer received routing/broadcasting packet within timer du ration; Randomized selection of messages collected within the tim er; Packet out of timer bounds could be misbehaved node(s).

PSD-II: Randomized Routing Message Delaying (Rou ting)

Introduce small delays for received routing messages
23 A. Benslimane IWCMC2010

Case (I):

Route Changes: Original: Original: S W0 M1 W2 D Attack: M2 D (M0, M2 attracts route request pkts) Shortcut Attack: S M0 M1 Detour Attack: S W0 W1 W2 D (M1 delays route request pkts)
24 A. Benslimane IWCMC2010

Case (II):

Route Changes: Original: three hops A. nine hops Detour: Benslimane IWCMC2010

Secure routing protocols

ARIADNE [8] Authentication Routing for Ad-hoc Network (ARAN) [7]

Securing Ad hoc Routing Protocols (SAODV) [13] Provably Secure On-demand Source Routing in Mobile Ad Hoc Networks (endairA) [14]
26
A. Benslimane IWCMC2010

Secure routing protocols

A R I A D N
Authentication of routing messages

Ariadne [8] is a reactive routing protocol, proposed by Hu, Perrig and Johnson. Goal: to secure the former DSR protocol
The packets integrity is insured by the symmetric cryptography and MAC (Message Authentication Code). The end-to-end authentication of original and destination nodes and of intermediate nodes which participate to the routing thanks to an authentication mechanism (TESLA: Timed Efficient Stream Loss-tolerant Authentication ) [5]

TESLA, or digital signatures, or standard MACs

27
A. Benslimane IWCMC2010

Secure routing protocols

A R I A D N E
K0 S0 F2 K1 Generation sequence of keys
A. Benslimane IWCMC2010

TESLA authentication protocol [9]

TESLA divides the time interval into N intervals that last the same duration.

i-1

i+1

i+2

n t

F1

S1 F2

F1

...

F1

Sn-1 F2 Kn-1

F1

Sn F2 Kn TESLA key
28

Secure routing protocols

A R I A D N E
29
A. Benslimane IWCMC2010

RREQ mechanism is reinforced by 8 parameters.

<ROUTE REQUEST, Source, Destination, ID, Time interval, hash chain, nodes list, MACs list >
ID : identification number of RREQ packet Time interval: TESLA interval: this is the maximum duration which is necessary so that an original node reaches its destination in the network Hash chain(i)=H(current node, hach chain(i-1)) Nodes list: nodes that have participated to the routing Macs list: calculated with TESLA keys at each nodes level

Secure routing protocols

A R I A D N E
30
A. Benslimane IWCMC2010

The operating steps of ARIADNE

1. After the synchronization, the sender sends a RREQ with a MAC which was encrypted with the TESLA key 2. Each node which participates to the packet routing must add its identity and a MAC encrypted with the TESLA key, that was hached several times (hop number) 3. As soon as the destination node receives the packet, it checks the security condition of TESLA:
Was the TESLA key not already broadcast?

4. After the TESLA key has been broadcast, the receiver checks the packet integrity, if everything worked well, the RREP is sent to an original node. If it did not, the packet is rejected

Secure routing protocols

A R I A D N E
31
A. Benslimane IWCMC2010

Advantages:
Every replay attack are avoided Non-centralized management of keys

Disadvantages:
Ariadne protocol is vulnerable to DoS attacks (buffer overflow before the packets have been checked) Not all real time protocols are supported

Secure routing protocols

e n d a i r A
32
A. Benslimane IWCMC2010

Same as Ariadne:
Instead of signing the rreq, intermediate nodes sign the rrep

security
endairA is provably secure if the signature scheme is secure against chosen message attacks

efficiency
endairA requires less computation
route reply is signed and verified only by the nodes on the route in Ariadne, route request is signed (and potentially verified) by every node in the network

Secure routing protocols

S A O D V
SAODV is a secure variant of AODV protects non-mutable information with a digital signature (of the originator of the control packet) uses hash chains for the protection of the HopCount value
new non-mutable fields:
MaxHopCount (= TTL) TopHash (= iterative hash of a random seed MaxHopCount times) Hash (contains the current hash value corresponding to the HopCount value)

new mutable field:

operation
initially Hash is set to the seed each time a node increases HopCount, it also replaces Hash with H(Hash) verification of the HopCount is done by hashing the Hash field MaxHopCountHopCount times and checking if the result matches TopHash 33
A. Benslimane IWCMC2010

Secure routing protocols

A R A N
Reactive protocol, Based on the introduction of a certification authority (CA), Goal is to insure:
Nodes authentication Messages integrity Non-repudiation

The principle: in order to participate to the routing, nodes must own a valid certification from CA

34
A. Benslimane IWCMC2010

Secure routing protocols

CA: certification authority

A R
Nud A

A N

Nud B Nud X Nud C

Operations principle:
1. The node A must request its certification to CA in order to join the network 2. CA gives the certification after it has checked the node s identity
CA A : CertA = [IPA, KA+, t, e] KCA-A. Benslimane IWCMC2010

35

Secure routing protocols

A R A N
3. The node A broadcasts an RDP (Route Discovery Packet) with its certification
A broadcast : [RDP, IPX, NA, t]KA--, certA

4. The node As neighbours will check the certification validity and then they add their certifications and broadcast the packet
B broadcast : [[RDP, IPX, NA, t]KA--]KB-- , certA, certB

5. When a node C receives the RDP packet, it will check both A and Bs certifications and then it removes Bs certification an d it adds its own
C broadcast : [[RDP, IPX, NA, t]KA--]KC--,certA, certC 36
A. Benslimane IWCMC2010

Secure routing protocols

A R A N
6. At the end the RDP packet arrives to the destination X and after checking the certifications the REP packet is sent to the original node A
X C : [REP, IPA, NA, t]KX--, certX

7. The REP packet will follow the same RDP path until the node A
B A : [[REP, IPA, NA, t]KX--]KB--, certX, CertB

8. If the node C does not find the path until the node X, it will generate the error message which will be sent to the node B
C B : [ERR, IPA, IPX, NC]KC--, CertC
37
A. Benslimane IWCMC2010

Secure routing protocols

Advantages :

A R A N

Non-authorized modifications are detected The nodes authentication and the non-repudiation are insured

Disadvantages :
The asymmetric cryptography is expensive in terms of computational and energy requirements (eg.: RSA and keys size 512 bits (Laptop: 1200MHz and RAM= 512 Mo)=> 2,2 ms). ARAN dont protect against the Wormhole attack (Tunneling) A heavy charge on the CA, if it breaks down, the network security will not be insured anymore

38
A. Benslimane IWCMC2010

TWO Contributions at routing layer

A Secure Architecture for MANET [1]

A Confident Community to Secure MANET [2]

39
A. Benslimane IWCMC2010

A Secure Architecture for MANET - Outline

Motivation Overview of the architecture

Trust Model Dynamic Demilitarized Zone (DDMZ) Secure Distributed Clustering Algorithm (SDCA)

Performance Evaluation: simulations Conclusion and Future Work

40
A. Benslimane IWCMC2010

A Secure Architecture - Motivation

In Mobile Ad Hoc Networks some nodes are:
Confident, cooperative Misbehave, selfish Relative mobility

=> To use the diversity with trust level and mobility among nodes in order to secure a network
41
A. Benslimane IWCMC2010

A Secure Architecture - Motivation

The goals
To define a hierarchical architecture when a network is divided into clusters, with one CA node for each cluster To Provide Public Key Infrastructure (PKI) in each cluster and to secure inter-cluster communication To elect CA among nodes having highest trust level and stability Maintain as long as possible the conceived architecture

42
A. Benslimane IWCMC2010

A Secure Architecture - Trust Model

Trust metric (Tm) : continuous value in [0 1] Only confident nodes have Tm = 1 Each node has trust table which is updated at each metric change and exchanged by nodes with high trust level Each new unknown node starts with Tm = 0 (lower trust level)

43
A. Benslimane IWCMC2010

A Secure Architecture - Trust Model

Definition
To get high trust metric (Tm = 1) either:
1. A node is known by confident nodes and has exchanged keys over secure channel [5] [6] OR 2. A node which has proved its full cooperation (i.e, forward)

=> The idea consists to oblige the unknown nodes to wellbehave

44
A. Benslimane IWCMC2010

A Secure Architecture - Trust Model

We define five types of role for the node :
1. 2. 3. 4. Certification authority of cluster (CA) with Tm = 1 Registration authority of cluster (RA) with Tm = 1 Gateway between clusters (GW) with Tm [0.7 1.0] Member (MN) which success to pass from visitor to member status by well behaviour with Tm [0.5 0.7] 5. Visitor (VN) with Tm [0.1 0.5]

45
A. Benslimane IWCMC2010

A Secure Architecture - Trust Path

The trust value of a path depends on its trust chain. The trust evaluation between two nodes consists to take the small trust value of nodes.

46
A. Benslimane IWCMC2010

A Secure Architecture - Dynamic Demilitarized Zone

Definition
A set of nodes at one hop from CA
- Each node is a Registration Authority (RA)

The role of these nodes is to protect the CA from untrusted nodes

47
A. Benslimane IWCMC2010

A Secure Architecture - Secure Distributed Clustering Algorithm

Main rules of SDCA
Only confident nodes (Tm(i) = 1) can be candidate to become CA Each cluster-head is CA of only one cluster All confident neighbors of CA, can become RA in the cluster Other nodes are at distance of maximum d-hop from the CA

48
A. Benslimane IWCMC2010

A Secure Architecture - Secure Distributed Clustering Algorithm

CA Selection Criteria:
Security: To increase the security of the cluster, SDCA selects the confident node with a maximum trust degree (Tm = 1) and at least one confident neighbor Stability: Is based on mobility metric [1]. It gives a good knowledge about the relative mobility between two neighbors nodes

49
A. Benslimane IWCMC2010

A Secure Architecture - Secure Distributed Clustering Algorithm

Each CA candidate node starts to send beacon with information for the election
Identity of CA candidate Dgree of confident neighbors (DTN) Relative mobility (RM) to its trust neighbors Number of hop from CA (Hop-Count) Sequence number of beacon Message Authenticated Code (MAC) of beacon (MACK[CA, Hop count,DTN,RM, Sq num])
50
A. Benslimane IWCMC2010

A Secure Architecture - Secure Distributed Clustering Algorithm

51
A. Benslimane IWCMC2010

A Secure Architecture - Secure Distributed Clustering Algorithm

Example

52
A. Benslimane IWCMC2010

A Secure Architecture - Security analysis

The security of our architecture depends directly on the trust model. The presence of a great number of confident nodes increases the security of the network. All communications from a malicious nodes or malicious cluster are ignored. The Denial-of-Service (DoS) attack over CA node is prevented by DDMZ where RA nodes filter all requests from unknown nodes. The robustness of DDMZ depends on the number of RAs which collaborate in order to protect CA of their cluster.

53
A. Benslimane IWCMC2010

A Secure Architecture - Security analysis

The malicious nodes can use the identity of legitimate nodes only if their privates keys are divulgated. If attackers try to compromise all the network, it must compromise all CA The cluster size must be adapted with number of confident nodes in order to well secure CA node (trade-off between the number of confident and unknown nodes must be founded). The presence of two confident nodes is the minimum configuration of clustering and it must be reinforced. We can use the thresholds cryptography scheme in each cluster after CA election.

54
A. Benslimane IWCMC2010

A Secure Architecture - Resume

Hierarchical architecture to distribute a certification authority Combination between security and stability to construct clusters in order to secure the network DDMZ concept to prevent attacks against CA nodes This architecture is adapted to topology changes

55
A. Benslimane IWCMC2010

A Confident Community to Secure MANET - Motivation

In order to maintain the network security when unknown nodes join the network, the monitoring process is necessary. The security of the cluster is insured by the cluster manager. The concept robustness of the DDMZ require to be well investigated

56
A. Benslimane IWCMC2010

A Confident Community to Secure MANET - Secure election process

Secure Distributed Clustering Algorithm (SDCA):
Select the a clusterhead (CH) which become the CA according the trust level and the stability

57
A. Benslimane IWCMC2010

A Confident Community to Secure MANET - Monitoring process (1/3)

Each node with a high trust level monitors its neighbor nodes with low trust level The monitor process acts in the different network protocol layer (MAC, Routing, )
MAC layer: Monitor nodes supervise the channel occupation by their neighbors. This function is motivated by one type of selfish misbehavior (The selfish nodes cheat from the choice of the backoff in order to access more bandwidth than other nodes) As solutions:
DOMINO for WLANs [10], PRB(Predectible Random Backoff) [11] for MANET,

Network layer: Monitor nodes supervise the packet forwarding activities of its neighbor nodes and packet integrity. As solutions: Watchdog [12]

58
A. Benslimane IWCMC2010

A Confident Community to Secure MANET - Monitoring process (2/3)

We focus on the network layer for the monitoring

59
A. Benslimane IWCMC2010

A Confident Community to Se cure MANET - Monitoring process (3/3)

Let node x and y with Tm(x) > Tm(y):
The node x can monitor the node y, The node x sends a certain number of packets to the node y with an other destination node, After a fixed time interval, the node x can calculate the reputation rating:

Each unknown node starts with a low trust metric (Tm=0.1) and increases when it proves its cooperation and well-behavior If R1 is the report generated for MAC layer, the final report about a node y is:
60
A. Benslimane IWCMC2010

A Confident Community to Secure MANET - Cluster Manager (CM) (1/2)

The cluster manager is formed by the:
The Certification Authority (CA) node A set of nodes with high trust levels (if these nodes are located at one hop from CA node, they become the Registration Authority RA)

The role of the CM is:

Insure the cluster security where the CA node will generate a certificate for a cluster member A set of RA nodes forms the DDMZ in order to protect the CA node ag ainst CA node attacks The DDMZ use the reputation rating from the monitoring process to ev aluate the cluster members.
61
A. Benslimane IWCMC2010

A Confident Community to Secure MANET - Cluster Manager (CM) (2/2)

If the CM receives k report from monitor nodes to evaluate the node y, then:

The different functions of the CM and the interaction with monitoring module

62
A. Benslimane IWCMC2010

A Confident Community to Secure MANET - SDCA, Monitoring, Cluster manager

The monitoring, the election (SDCA) and the cluster manager modules, interact with a trust model (transitions: 1, 2, 3) Modules election and cluster manager call the monitoring module to control the behviors of the nodes (transitions: 4, 6) The cluster management module is the result of SDCA with the transition 5

63
A. Benslimane IWCMC2010

A Confident Community to Secure MANET Confident connectivity model (1/4)

The idea is to distribute k confident nodes among n (total number of nodes in the network), In each cluster, the CA node and the confident nodes directly connected form the DDMZ, Two nodes (i) and (j) can directly communicate with each other, if |Xi-Xj| < R (R is a transmission range and Xi location of the node i) The confident community is defined as a set of confident nodes which have the highest trust level
64
A. Benslimane IWCMC2010

A Confident Community to Secure MANET Confident connectivity model (2/4)

Assumptions:
There is no obstacle in the area All nodes have the same transmission range R Each confident node knows the public cryptography keys of all confident nodes The nodes are distributed with Poisson arrival rate

The probability that a node (i) can directly communicate with a node (j) is:

65
A. Benslimane IWCMC2010

A Confident Community to Secure MANET Confident connectivity model (3/4)

The probability to have d+1 confident nodes directly connected is:

The higher the transmission range is, the greater the probability of connected network is The probability to get two nodes i and j directly connected, knowing that they belong to the set of confident community |K|=k in the networ k of n total number of nodes is:

66
A. Benslimane IWCMC2010

A Confident Community to Secure MANET Confident connectivity model (4/4)

The probability of (d+1) confident nodes directly connected
according to the transmission range (R), the percentage of confident nodes in the network (k/n) and the degree of direct connectivity d between confident nodes,

67
A. Benslimane IWCMC2010

A Confident Community to Secure MANET Results analysis

The clusters and CAs become more resistant against DoS (Denial of Services) attacks when the transmission range is getting longer. The result shows that: when the transmission range increases, the probability of two directly connected nodes is increased. Also, the probability of directly connected confident nodes is also increased. It indicates the probability to build robust DDMZ depends on the station transmission range. The best configuration of cluster is to find the trade-off between the number of RA and the number of nodes with low trust levels.
68
A. Benslimane IWCMC2010

A Confident Community to Secure MANET Resume (1/2)

a confident connectivity model to study the security robustness in the clusters. Dynamic Demilitarized Zone (DDMZ), this approach consists on the protection of the certification authority (CA) in each cluster. The security of each cluster depends of the robustness and the availability of the registration authority which form the DDMZ

69
A. Benslimane IWCMC2010

References
[1]A. Rachedi and A. Benslimane, "A Secure and Resistant Architecture against Attacks for Mobile Ad Hoc Networks", Journal of Security and Communication Network, John Wiley InterScience, Vol. 3, N 2-3, March-June 2010, pp.150-166. [2] A. Rachedi, A. Benslimane, Lei Guang and Chadi Assi , A Confident Community to Secure Mobile Ad-Hoc Networks, IEEE International Conference on Communications (ICC 2007), 24-28 June 2007, Glasgow, Scotland, UK. [3] P. Basu and N. Khan and T. Little, " A mobility based metric for clustering in MANET ", In Proceedings of Distributed Computing Systems Workshop, :4351, 2001. [4] M. Gerla and J. T.-C. Tsai, " Multicluster, Mobile Multimedia Radio Networks" , Wireless Networks. (1995) 255256 [5] S. Yi and R. Kravets, " Quality of Authentication in Ad Hoc Networks" , ACM, MobiCom 2004. [6] S. Capkun and J. P. Hubaux and L. Buttyan, " Mobility Helps Peer-to-Peer Security " , IEEE Transactions on Mobile Computing. 5 (2006) 4860 [7] Kimaya sanzgiri, Bridget Dahill, Secure Rourting Protocol for Ad Hoc Networks , IEEE ICNP 02 [8] Yih-Chun Hu, Adrian Perrig, David B. Johnson Ariadne : A Secure On-Demand Routing Protocol for Ad Hoc Networks, MobiCom2002
70
A. Benslimane IWCMC2010

References
[9] Adrian Perrig, Ran Canetti, J. D. Tygar, Dawn Song, The TESLA Broadcast Authentication Protocol, RSA CryptoBytes, 2002. [10] M. Raya and J.-P. Hubaux and I. Aad, DOMINO: A System to Detect Greedy Behavior in IEEE 802.11 Hotspots, In Proc. of MobiSys04 [11] L. Guang, C. Assi, and A. Benslimane, Enhancing IEEE 802.11 Random Backoff in Selfish Environments, IEEE Transactions on Vehicular Technology Journal, May 2008, Vol. 57, N 3, pp. 1806-1822. [12] K. L. S. Marti, T.J. Giuli et M. Baker, Mitigating Routing Misebehavior in Mobile Ad Hoc Networks, ACM/IEEE International Conference on Mobile Computing and Networking, 255265. [13] M. G. Zapata and N. Asokan, Securing Ad hoc Routing Protocols, ACM Workshop on Wireless Security (WiSe 2002), pages 1-10. September 2002. [14] G. Acs, L. Buttyan, and I. Vajda, Provably Secure On-demand Source Routing in Mobile A d Hoc Networks, IEEE Trans on Mob. Comp. 5(11), 2006. [15] L. Guang, C. Assi, and A. Benslimane, Enhancing IEEE 802.11 Random Backoff in Selfish Environments, IEEE Transactions on Vehicular Technology Journal, May 2008, Vol. 57, N 3, pp. 1806-1822. [16] L. Guang, C. Assi and A. Benslimane, On MAC Layer Misbehavior in Wireless Networks: C hallenges and Solutions, IEEE Wireless Communications Magazine, Special Issue on Security in W 71 ireless Mobile Ad Hoc and Sensor Networks, , Vol. 15, N 4, August 2008, pp. 6-14.
A. Benslimane IWCMC2010

Outline Part II
Security on Vehicular Ad hoc Networks (VANETs)
Motivations Security issues and solutions Applications based Dissemination Optimized Dissemination of Alarm Messages: ODAM A risk aware MAC protocol: CRCCA Connecting VANET to Internet: VANETII References

72
A. Benslimane IWCMC2010

Part II Vehicular Ad Hoc Networks: Security and Dissemination

IWCMC June 28, 2010

Professor Abderrahim BENSLIMANE

Outline
Motivations and applications of vehicular communications

Security issues and solutions Applications based Dissemination Optimized Dissemination of Alarm Messages: ODAM A risk aware Mac protocol: CRCCA Connecting VANET to Internet: VANETII References

6/26/2010

Background on Safety
In the US: 6+ million traffic accidents per year
90% driver errors, 43 000 deaths, 3 million injuries,

Financial cost: more than $230 billion Overall Goal: Reduce traffic accidents
Fewer injuries and fatalities Lower direct and indirect cost Reduced traffic congestion

In Europe:
Specific Goal: to reduce the car accidents of 50% by 2010 All world is compact in putting money on safety issues
6/26/2010 3

Background on Traffic Management Unregulated traffic cost much Congestion is a big source of waste
3.6 billion vehicle-hours of delay 5.7 billion gallons of wasted fuel

Improve traffic flow and reduce congestion

6/26/2010

Smart traffic signals Enhanced transit system Central traffic management Electronic toll collection
4

Wireless communications
GPRS/UMTS
Expensive, reliability, capacity, timing

IEEE 802.11-based
DSRC: Dedicated Short Range Communications Car-Car communications at 5.9Ghz 802.11p: IEEE Task Group that intends to standardize DSRC for Car-Car communications 802.11-based Mesh Networks

IEEE 802.16
802.20: extension to high mobility scenarios

Sensor Networks
Bluetooth (in-vehicle communications) ZigBee
6/26/2010 5

Smart Vehicles

Event data recorder (EDR) Forward radar Positioning system (GPS)

Communication facility

Rear radar Display Computing platform

Different components of a Smart vehicles

6/26/2010

VANET characteristics
High mobility: Fast topology changes, Predictable movements of vehicles : Trajectory are linked to roads, There are no constraints of weight or problems with energy conservation, Communications are short and the intervals are about microseconds.
6/26/2010 7

DSRC Network Architecture

Communication paradigms:
V2V V2I, Hybrid.

DSRC: Dedicated Short Range Communications(75

MHz in the 5.8/5.9 GHz band)
V2I V2I

IEEE802.11p (PHY and MAC layers)

6/26/2010

V2V V2V

Some applications (1/2)

Collision Avoidance*
Warn a driver that is not safe to enter an intersection Prevent many vehicle rear-ending each other after a single accident Early braking, Distance keeping and speed management, Lane changing/merging/crossing

Cooperative Driving*
Violation warning, Turn Conflict and Curve warning Lane merging warning

* Life critical
6/26/2010 9

Some applications (2/2)

Traffic Optimization *
Traffic delay continues to increase: Waste time, specially when peak time travelers

Vehicles can serve as data collectors

Transmit the traffic condition information: Number of neighbors and
their mean velocities.

Payment Services
Electronic toll payment

Location-based Services
Parking spot locator Enhanced route guidance and navigation
6/26/2010 10

Security Requirements Authentication and data integrity:

Verify properties of the sender: vehicle, ambulance, traffic sign Detect replay (Timestamp) The sender can be authenticated but the message is falsified

Driver Privacy Detect the actual and not the virtual

Sybil attack: an adversary can transmit safety-related packets
i.e., falsely identify a road as congested
6/26/2010 11

Security Requirements Non-repudiation Secure vehicles localization:

Verify if the sender is actually at the claimed position

High availability and strict message delivery deadline

Adversaries will always be able to reduce availability: Denialof-service attacks

6/26/2010

12

Challenges
Trade-off between authentication and non-repudiation versus privacy Nature of VANET
High speed Open network

Some protocols cannot be employed: voting, consensus and based-reputation Sheer scale
not for protocols that require pre-stored information about participants

Opposing incentives of participants Law enforcement agencies () Drivers

6/26/2010 13

Mitigating characteristics

Mobility of VANET can sometimes be beneficial, Circulation in two opposite directions, Well specified limits: road, motorway, determined number of lanes, etc. Not limited in power: complex cryptographic operations, All vehicles are to be registered in a central authority, Vehicles can leverage their knowledge from the drivers response.

6/26/2010

14

Adversaries

Rational or Malicious
Rational seeks personal benefits, more predictable attack, Malicious No personal benefit, intends to harm other users,

Industrial Insider is a valid user Active or passive attacks

Active: Generates packets, participates in the network, Passive: Eavesdrop, track users, etc.
6/26/2010 15

Some attacks

Disruption of network operation:

Deny of service, Selfish misbehavior

Disclosure of identities, Wormhole attack Cheating with identity or positioning information,

6/26/2010 16

Some Solutions 1/6

Security Hardware
Event Data Recorder (EDR)
Records all emergency-related information received: position data, speed data, acceleration data, time, etc. Liability-related messages should be stored in the EDR

Tamper-Proof device (TPD)

Provides the ability of processing Verify and signs messages Protects Hardware : a set of sensors to detect hardware tampering Has its own battery, own clock, High cost
6/26/2010 17

Some Solutions 2/6

Authentication
Digital Signature Each message should be signed and accompanied with a Timestamp/replay, Symmetric cryptography is not suitable messages are standalone, large scale, non-repudiation required, Cryptosystem based on asymmetric cryptography (VPKI: Vehicular PKI ) Hash function: message space
6/26/2010

hash-codes of specific size

18

Some Solutions 3/6

Non-repudiation
A single unique identity to each vehicle : Electronic License Plate (Affected by the Government) Electronic Chassis Number (Affected by the manufacturer) A CA store a mapping between the unique identity of the vehicle and its set of public keys. Digital signature (using the unique private key of the sender)

6/26/2010

19

Some Solutions 4/6

Save anonymity of drivers

Relationship between the unique identity and public keys must be not visible Use of pseudonyms (one or more): only authorities know the mapping to the unique identity Use of group key: To each group of vehicle is assigned a key

6/26/2010

20

Some Solutions 5/6

Authentication of aggregated data

Emergency road condition warning applications: In large network, a simple forward of all messages is inefficient: significant overhead Message related to the same road condition
Fusion, extrapolation, etc Reduce overhead : redundant transmissions

Example: in application of congestion avoidance: Position and speed of vehicles can be approximated step by step:
It is not very useful to have a high degree of accuracy of the position of an accident if this is further away from the originating nodes (neighboring of the accident)

6/26/2010

21

Some Solutions 6/6 Group formation and Communication

Static group formation: specific vehicles are part of specific group
Rigid and not scalable not suitable for VANET

Dynamic group formation:

Vehicles form groups based their driving pattern and their location Overhead of group formation must be very limited

6/26/2010

22

Some Solutions 6/6

Geographic-based group formation:
The map is divided into small cells: use of localization system (GPS ) Each vehicle knows which group it belongs to at any moment based on its location One group leader per cell: the one closest to the center limited overhead

6/26/2010

23

Optimized Dissemination of Alarm Messages: ODAM

6/26/2010

24

ODAM: Optimized Dissemination of Alarm Messages

To face the network fragmentation while avoiding neighbors computation Solution Geocast: use GPS coordinates of vehicles Introduce Defer Time Distance >> reduce the number of message collisions >> reduce the number of retransmission >> best use of bandwidth >> reduce the delay
Dynamical Relays >> to face the fragmentation Tacking into account the direction of circulation
6/26/2010 25

ODAM: Optimized Dissemination of Alarm Messages

Defer Time Distance

x a b c Accident Alarm message propagation Risk zone Transmission range

defertime ( x) = max_ defer _ time

6/26/2010

( R Dsx )

R
26

ODAM: Optimized Dissemination of Alarm Messages

Accident (1) Initial (0) Waiting (2) Relay broadcasts (4) Passive (5) Direction of circulation
6/26/2010 27

A cluster Based Risk aware cooperative collision avoidance: CRCCA

6/26/2010

28

CRCCA: Related Work

Traditional CCA:
A vehicle dispatches warning messages to vehicles behind it, Warning messages are transmitted over multiple hops, A recipient takes on account the direction of the message Message will be ignored if it arrives from behind generation of large number of messages generation of redundant messages access medium
6/26/2010

Collision in the
29

The 802.11 Mac layer: Issues

Back-off mechanism Increase of the data delivery latency, In case of CCA, decrease of the 802.11 effectiveness, Some vehicles will not have time to react.

6/26/2010

30

CRCCA: Dynamic clustering of vehicles

The clustering considers only vehicles moving in the same road towards the same direction, Three roles of nodes: CH: cluster head, SCH: sub cluster head, the last vehicle reached by the CA ON: ordinary member

6/26/2010

31

CRCCA: An example of three clusters

6/26/2010

32

CRCCA: a risk aware Mac protocol(1/3)

In a cluster i, to each vehicle correspond an emergency level as follow: i

i
S: cluster size : skew factor

(1 ) =

(1 S )

1 i S

The contention windows of a vehicle in cluster i: j

k

CW

j =1

(1 i ) .cw .

k : the number of transmission attempts cw : window size : the slot time of the used PHY layer
6/26/2010 33

CRCCA: a risk aware Mac protocol(2/3)

Calculate of i , maximum latency since the detection of emergency situation: if Ci and Ci +1 slow down with ae and ar respectively:

max Then i is:

i max = Max (

Vi ae

V 2 Vi .( (V i + 1 i ) d i +1, i _ L v ) , 0 ) ar ae 2

ar :Is the regular deceleration, ae : is the emergency deceleration, Lv : the average vehicle length.
6/26/2010 34

CRCCA: a risk aware MAC protocol(3/3)

As consequence :
(1 i ) j .cw. j =0
Min ( j = 0 (1 i ) j .cw. , i
k max

CWi =

if i max = 0
) otherwise

6/26/2010

35

Connecting VANET to Internet: An efficient routing protocol

6/26/2010

36

Connecting VANET to Internet: Related Work

Ad hoc

routing protocols do not typically select a route with sufficient lifetime to maintain the longest possible duration of communication with a mobility agent. The handover mechanism is not sufficiently fast to manage handovers in VANET environment known as Strong Mobility. More than one gateway may be available at the same time, How to discover gateways with the best quality of service (QoS) without wasting network resources.

6/26/2010

37

Connecting VANET to Internet: Related Work FleetNet Project

The FleetNet investigated the VANET Internet Integration through stationary roadside gateways, Use of a modified version of Mobile IPv6 to handle the mobility, Use of a service discovery protocol for gateway discovery, Use location based routing protocols.

Problems
Do not take vehicle movement parameters into account, Do not cover handovers.
6/26/2010 38

Connecting VANET to Internet: Related Work

MMIP6
A mobility management protocol (for VANETs): integrate IPv6-based VANETs into the Internet Use of a proactive service discovery protocol for Foreign Agent (FA) discovery. The service announcements are restricted to a limited broadcast zone: Using of geocast capabilities of VANET routing protocols. Avoid of the flooding of the overall network In route selection, a fuzzy-based approach is used It considers available information about gateways.
6/26/2010 39

Connecting VANET to Internet: VANETII

VANETII (VANET Internet Integration):
Purpose: discover of gateways creation routes to them.

Three phases in VANETII :

Agent (gateway) discovery Route selection handing the connection to the new gateway.

The aims :
reducing the overhead during the gateway discovery process selecting the most stable route to gateways performing seamless handovers.
6/26/2010 40

Connecting VANET to Internet: VANETII

In VANETII network , two types of nodes : Vehicles : stationary or mobile Gateways : stationary. Each vehicle is equipped with a positioning system, e.g., GPS, The coordinate of a vehicle u is denoted as (xu, yu). Each vehicle is also able to calculate its speed, Vu, and direction, u. Links between vehicles are established if the distance between them is less than their transmission range R.
6/26/2010 41

Connecting VANET to Internet: VANETII

Table : Agent Advertisement Message Fields Field Gateway Relay Sequence Number Sender Position Sender Speed Sender Direction RET Zm Description Address of the source gateway Relay address Message Sequence Number Geographical Position of the sender Speed of the sender Direction of the sender Expiration time of the route Message Broadcast Zone

6/26/2010

42

Connecting VANET to Internet: VANETII Proactive Gateway discovery:

X Y

A B C

A Gateway broadcasting an advertisement message periodically, then relays rebroadcast

6/26/2010 43

Connecting VANET to Internet: VANETII

Stability metric
Link Expiration Time (LET): time duration such that two nodes will remain connected. Let (xi , yi) and (xj , yj) be the coordinate of the vehicles i and j which are moving in direction i ,j (0 i , j < 2 ) with the speed of vi and vj, LETij is as follows :

LETij =
Where :

( ab + cd ) + ( a 2 + c 2 ) r 2 ( ad bc ) 2 a 2 +c2

a = vi cos i v j cos j ; b = xi x j c = vi sin i v j sin j ; d = yi y j

44

6/26/2010

Connecting VANET to Internet: VANETII

Stability function :

S = 1 e

LET a

a: a constant that defines the rate at which the function is rising: the lower is a, the faster the function rises:
Effect of selecting different values of a on function S

6/26/2010

45

Connecting VANET to Internet: VANETII

Let Rk be a route, which consists of n 1 links l01, l12, ... , l(n2)(n1) between n vehicles 0, 1, ..., n1 To compute the Route Expiration Time (RET) we should find the link which expires before the others, hence:

RETk = Min{LETi,(i +1) | i = 0 .. n - 1}

With analytical studies, we compute a, and then the stability function will be:

S = 1 e
6/26/2010

2 LET RET

46

Connecting VANET to Internet: VANETII

If two nodes have the same stability function value introduce a second function to eliminate duplications We will take into account the progress that the packet has made in the opposite direction of the movement:

The second function is as follow: cos( i j ) d ij

P=

Where: i sender, j,k,l receivers (j is the farther).

6/26/2010 47

Connecting VANET to Internet: VANETII

We should combine S and P together. P should not be as effective as S for next hop selection:

F = S + (1 ) P
For the contention in our protocol we select the timer runtime as:

t ( F ) = T (1 F )
Where: T: the maximum forwarding delay. The next hop will be the one with the longest lifetime and the largest progress in the opposite direction of the road.

6/26/2010

48

Conclusion

We presented Security issues of vehicular networks and We proposed: ODAM, a protocol for disseminating alarm messages, CRCCA, a risk aware Mac protocol, VANETII, a protocol for connecting VANET to Internet Still open field in security: Group formations and management of public/private key, group signature Preserving privacy: attacks against privacy in different layers.
6/26/2010 49

Further readings
Securing Vehicle ad hoc networks, M. Raya and J.P. Hubaux, J. of comp. Science, Vol. 15, pp. 39-68, 2007. Secure Vehicular Communication Systems: Design and Architecture, P. Papadimitratos, et al., IEEE Communication Magazine, 2008. A secure and efficient communication scheme with authenticated key establishment and privacy preserving for vehicular ad hoc networks, Computer Communications, 2008. Optimized Dissemination of Alarm messages in Vehicular Ad-Hoc Networks (VANET), A. Benslimane, 7th IEEE HSNMC 2004, LNCS 3079, Springer Publisher, pp.655-666. An Efficient Routing Protocol for Connecting Vehicular Networks to the Internet, S. Barghi, A. Benslimane and C. Assi, 10th IEEE WoWMoM 15-19 June 2009, Greece. Towards an Effective Risk-conscious and Collaborative Vehicular Collision Avoidance System, T. Taleb, Z. Fadlullah, A. Benslimane, and K. Ben Letaief, IEEE Transaction on Vehicular Technology.

6/26/2010

50

Thank you
COCONCLUSIONS AND FUTUREWORKS

6/26/2010

51