Quelques propositions de solutions pour la sécurité des réseaux de capteurs sans fil

Wassim Znaidiwassim.znaidi@insa-lyon.fr

Directeurs de thèse: Marine Minier, Stéphane UbédaLaboratoire CITI

INRIA SWING / CITI INSA de Lyon

Date : 19 Octobre 2010

2

Réseau de capteurs Pas d’infrastructure fixe Forte densité Topologie aléatoire – Env. ouvert Routage multi-sauts

Capteurs

Capture/ traitement de données physiques Transmission sans fil Energie (batterie)

Station de base (BS)

Réseau de capteurs (RdCs)

Contraintes

• Mémoire limitée• Energie limitée• Capacité de calcul limitée• Faible portée radio• Communication radio sans fil WSN430:

Ti MSP430 (8 MHz) 1Mo Flash, 10 Ko de RAM Batterie 2xAA

3

Réseau de capteurs

Applications: besoin de sécurité

Surveillance environnementale

Industrie

Médical-BodyNet

Surveillance industrielle

Moniteur d’inventaire

4

Contremesures

Externe: cryptographie secrets efficacité dans un environnement contraint ?

Interne: solution algorithmique, car une partie des secrets sont connus.

Attaquant

Externe: l’attaquant ne fait pas partie du réseau pas d’accès aux nœuds.

Interne: l’attaquant compromet des nœuds accès à une partie des nœuds

Sécurité dans les RdCs

5

Attaques dans les RdCs

Physique

Liaison

Routage

Application

Réplication SinkholeSybileCollision

brouillage, extraction de données,débordement de tampon,…

collision, épuisement, link jamming, …

Selective forwarding, sinkhole, Sybile, hello flood, wormhole, réplication des nœuds,…

inondation, désynchronisation, localisation,Faux paquet de contrôle, …

6

Approches Algorithmiques: solutions pour la couche de routage Détection de l’attaque wormhole

Détection de l’attaque par réplication des nœuds

Durant cette thèse

Attaque wormhole

Coefficient de clustering des arêtes

Algorithme de détection basé sur le coefficient de clustering

Performance et comparaisonApproches Cryptographiques: solutions pour la couche application

Gestion de clés et de contrôle d’accès

Authentification des messages pour l’agrégation et le codage réseau

[Znaidi et al. 2008]

[Znaidi et al. 2009 et 2010]

7

Attaque wormhole

Conséquences Selective forwarding Déni de service Fausse découverte de voisinage

8

Etat de l’art

Protocole Description Inconvénient

Perrig et al. 2003 Utilisation des paquets leaches pour des données

géographiques et temporelles

exige la synchronisation des horloges et l’utilisation

d’un GPS

L. Hu et al. 2004 Utilisation de la direction des antennes des voisins

utilisation d’antennes directionnelles

R. Maheshwari et al. 2007

Recherche des structures interdites

Grande complexité de calcul

Shokri et al. 2009 Estimation des distances à l’aide d’ondes ultrasons et

recherche des formes géométriques interdites

Besoin de la technologie ultrason et d’horloges très

précises

MotivationBesoin d’une solution distribuée ne

nécessitant pas de composants spéciaux

9

Observation de l’attaque wormhole

Observation

2 communautés distinctes ont l’impression d’être proche grâce au lien wormhole

les voisins des nœuds malicieux n’ont aucun voisin commun

Piste

Etude de voisinage pour vérifier la consistance des liens et détecter une attaque wormhole

10

Coefficient de clustering des arêtes (CCA)

CCA [Radicchi 2004]

• Mesure de la vraisemblance que g-nœuds associés à une arête soient bien associés entre eux.

• Coefficient de clustering:

Proposition de CCA modifié

• Motivation: étudier l’impact de suppression d’un lien sur la connectivité des voisins

ba

d

c

i j

ba

d

c

i j

3i,j

2

4C =

3i,j\d

1

3CS =

lien existantlien possible

gi,j\Xg

i,j\X gi,j\X

zCS =

s• Coefficient clustering modifié:

gi,jg

i,j gi,j

zC =

s

11

Wormhole détecté à l’aide du CCA modifié

Extrémité de wormhole

Pour deux nœuds a et b, b est déclaré malicieux si:

\1 1 2( ) (( ( ) ( )) \G bk V b et k V a V a

(3) (4), \ , \0 0a k b a k bCS et CS

YX

a

b

m

n

j

(3) (4), \ , \0, 0a Y X a Y XCS CS

Intuition

Dans un réseau de capteurs dense, un couple de noeuds possède au moins

1-2 noeuds voisins en commun(3) (4).,.\. .,.\.0 et 0CS CS

Algorithme de détection

1. Découverte de voisinage: les nœuds s’échangent leurs tables de voisinage de 1-2 sauts, construites à l’aide des messages Hello.

2. Phase de calcul: chaque nœud calcule S’ils sont nuls, le voisin est déclaré comme étant un nœud malicieux.

(3) (4).,.\. .,.\.etCS CS

12

Faux positifs

Limitations

Faux positifs: des nœuds honnêtes sont déclarés comme malicieux

YX

a

b

m

n

j

(3) (4), \ , \0, 0j b a j b aCS CS

Solution proposée

Technique de vote: un nœud est déclaré malicieux si une majorité de nœuds le considère malicieux

Algorithme de détection

1. Découverte de voisinage: les nœuds s ’échangent leurs tables de voisinage de 1-2 sauts, construites à l’aide des messages Hello.

2. Phase de calcul: chaque nœud calcule le CS d’ordre 3 et 4. S’ils sont nuls, le nœud est désigné un nœud suspect.

3. Phase d’isolation: un nœud diffuse une alerte chaque fois qu’il détecte un nœud suspect. Si le nombre d’alertes dépasse un seuil , le nœud est déclaré malicieux.

amT

13

Intégration à un protocole d’auto-organisation

QLoP [Heurtefeux et al. 2008]

Echange de messages Hello périodiques

Echange des tables de voisinage à 1-saut

Calcul d’indice de proximité

Classification des voisins en 3 classes

Intégration à QLoP

1. Exécution de QLoP: adaptation de QLoP pour pouvoir échanger les tables de voisinage à 1-2 sauts.

2. Phase de calcul: chaque nœud calcule le CCA modifié d’ordre 3 et 4. Pour optimiser les calculs, on calcule ce coefficient que pour les nœuds de classe 2 et 3

3. Phase d’isolation: un nœud diffuse une alerte chaque fois qu’il détecte un nœud suspect. Si le nombre d’alertes dépasse un seuil , une attaque est déclarée.

amT

14

Etude de performance

Hypothèses

Topologie aléatoire

Pas de mobilité

Simulations Simulateur WSNet Modèle radio réaliste Comparaison avec l’approche [Shokri 2009]

Probabilité de détection de 1/plusieurs attaques wormhole aléatoires de faux positifs avec/sans les nœuds sur les bords

UDGRéel

15

Résultats

Observations Forte probabilité de détection variant (entre 80% et 98%). 1% - 7% de faux positifs. Pour moitié dû aux bordures.

Gain de l’ordre de 15% par rapport à [Shokri 2009]

16

[Zna

idi 2

008]

[Sho

kri 2

009]

Résultats

17

Conclusion wormhole

Résumé

Algorithme distribué utilisant uniquement des informations de voisinage local Introduction du coefficient CCA modifié Définition d’un wormhole à l’aide du coefficient CCA modifié Intégration dans QLoP

Perspectives

Ne fonctionne plus si les voisins des nœuds wormhole mentent de façon consistante sur leur voisinage [Boucetta 2010] Etude de plusieurs attaquants wormhole qui collaborent entre eux

18

Sécurisation contre l’attaque wormhole

Authentification des messages pour le codage réseau

Définition de l’attaque de pollution dans le contexte de codage réseau

Les fonctions de hachage universelles

Mode d’opérations de la vérification de l’intégrité des données

2ème partie de la présentation

19

Codage réseau et attaque par pollution

Problème

Alice

Bob

Attaque par pollution: injecter de fausses données

inutilisables dans les messages transformés

Question ?

Comment prévenir l’attaque par pollution dans un RdC (en étant efficace en énergie) ?

Codage réseau

1x 2x1t

1 2x x 1 2x x2t

Alice Eve Bob

Le codage réseau est une méthode de transmission de données multipoint par combinaison de flux permettant d’augmenter le débit et d’améliorer la robustesse

20

Méthode de vérification de l’authenticité

3 grandes classes de Message Authentication Codes (MACs)

MACs basés sur les fonctions de hachage cryptographiques: HMAC et MDx-MAC

MACs basés sur les algorithmes de chiffrement par blocs: CBC-MAC

MACs basés sur les fonctions de hachage universelles FHU (FMAC)

Identité + Intégrité

Codes MACs: crypto symétrique

MA

C

MAC Taille fixe

Clé secrète

Signature digitale: crypto asymétrique exemples: RSA, DSA, ECDSA

hash

h

Clé privée

encencsignature

Trop gourmande en ressources

21

FHU [Carter et al. 1978]

Définition 1: faible probabilité de collision

Définition 2: linéarité

22

FMAC linéaire [Krawczyk 1994]

Les FHU permettent de construire un schéma de MAC sûr si les résultats sont cachés à l’aide d’une autre fonction

Conception de MAC à l’aide de FHU

La conception d’un code MAC est possible en suivant le scénario suivant: les deux parties échangent une clé secrète k les deux parties connaissent une valeur aléatoire r l’empreinte d’un message M est égale à: ( )ktag f M r

Exemples

La valeur r peut être obtenue à l’aide d’une fonction pseudo-aléatoire (AES) [Krawczyk 1994]: xor linéaire – CRC cryptographique

2( ) ( ). mod ( ), ( )ntag M M x x q x où M x F x

Questions ?

Quels MACs choisir dans la pratique pour faire du codage réseau ?

23

Etude de la consommation

Simulations et paramètres WSIM + eSimu Ti MSP430f1611

Algorithme Energie (10-4J) Délai (ms)

SHA1AES-128

0.6230.473

4.643.53

HMAC 2 14.48

CBC-MAC 1.476 11.045

FMAC (Toeplitz) 1.201 8.976

Résultats pour des données de 20 octets

24

Exploiter la linéarité

4 modes d’opération

AXMF

fonctionne avec toutes les primitives MACs

AXF

fonctionnent uniquement avec les FMACs linéaires

nécessitent la propriété de linéarité

méthode classique

XAF

XF

Mode d’opération: définir la démarche que le relais doit suivre pour vérifier la validité des données

25

Authenticate-Xor-Mac-Forward (AXMF)Mode classique qui fonctionne avec HMAC, CBC-MAC et FMAC

1 1,dx 2 2,dx

1 2m=x x

Alice Eve Bob

1 1' ,d'x 2 2' ,d'x

a am ,d b bm ,d

3 k 1 2d =h ( )x x

? ?

k 1 1 k 2 2h ( ) = d et h ( ) = dx x

?

k a ah (m ) = d

2 1 amx x

?

k b bh (m ) = d

1 2 bx x m

1

2

3

A

X M

FF

26

Authenticate-Xor-Forward (AXF)

fonctionne uniquement avec FMAC car besoin de la linéarité

1 1,dx 2 2,dx

Alice Eve Bob

1 1' ,d'x 2 2' ,d'x

a am ,d b bm ,d

?

k 2 2h ( '' ) = d"x

2 1 a 2 a 1'' = m / d'' =d dx x

1

2

3

1 2 b 1 b 2'' = m / d'' =d dx x

?

k 1 1h ( '' ) = d"x

X 1 2 3 k 1 k 2m= / d =h ( ) h ( )x x x x

? ?

k 1 1 k 2 2h ( ) = d et h ( ) = dx x Aréduit le calcul

FF

27

Modes d’opérations

XF ne permet pas au relais de détecter

l’attaque par pollution

Xor-Authenticate-Forward (XAF)

1 1,dx 2 2,dx

Alice Eve Bob1 1' ,d'x 2 2' ,d'x

a am ,d b bm ,d

?

k 2 2h ( '' ) = d"x

2 1'' ax x m

2 a 1d'' =d d1 2'' bx x m

1 b 2d'' =d d?

k 1 1h ( '' ) = d"x

1 2 3 1 2m= / d =d' d'x x ?

k 3h (m) = d

X

A

Xor-Forward (XF)

1 1,dx 2 2,dx

1 2m x x

Alice Eve Bob1 1' ,d'x 2 2' ,d'x

a am ,d b bm ,d

3 1 2d =d' d'

?

k 2 2h ( '' ) = d"x

2 1'' ax x m

2 a 1d'' =d d1 2'' bx x m

1 b 2d'' =d d?

k 1 1h ( '' ) = d"x

Xréduit l’authentification relais

FF FF

28

Résultats (WSNet-WSIM-eSimu)

TE =14.7 TE =13.1 TE =11.2

TE =19.1 TE =16.4

R: réception, V:vérification, T:tranformation, E:émission, TE :energie totale

29

Energie moyenne

p: la probabilité qu’une attaque par pollution se produise, M: le mode utilisé

( ) ( ) (1 ) ( )attack noattackS M p E M p E M

En pratique

Conclusion

Combiner les modes XAF et XF pour économiser l’énergie et contrer l’attaque par pollution

30

Conclusion agrégation de MACs

MAC pour l’agrégation et le codage réseau

Agrégation de MACs

Pour les schémas d’agrégation de données, seule la station de base est capable de vérifier la validité des données

Mise en place d’un mécanisme de vérification à la volée

Extension des travaux: utilisation des codes FMACs pour

le mécanisme de l’agrégation des données.

1

0 l-1M(x) = M +...+ M et tag(M) = M(x). mod q( ) + r mod pl nx x x

Généralisation de CRC Cryptographique sur pF

31

Conclusion Générale

Aussi

Proposition d’une ontologie d’attaques pour les RdCs

Défense contre l’attaque de réplication de nœuds dans un RdC: Utilisation d’une architecture hiérarchique Utilisation des filtres de Bloom

Proposition d’un mécanisme de gestion de clé Schéma de Blundo modifié Utilisation des chaînes de hachages

32

Perspectives

Analyse formelle des politiques de sécurité dans un RdC

Plusieurs mécanismes de sécurité possibles pour chaque couche

Différents niveaux de sécurité possibles selon le besoin de l’application et de QoS

Proposition d’une étude utilisant un modèle formel permettant de choisir la meilleure politique de sécurité en fonction de l’énergie restante dans le capteur et de la QoS souhaitée

33

Merci pour votre attention

Questions ?

“Key management and access control scheme for WSNs”. To appear in the Telecommunication Systems Journal, 2010.

“Energy Friendly Integrity for Network Coding in Wireless Sensor Networks”. In NSS 2010, Melbourne, Australia. “Hierarchical Node Replication Attacks Detection in Wireless Sensors Networks”. In PIMRC 2009, Tokyo, Japan. “Aggregated authentication (AMAC) using universal hash functions”. In SecureComm 2009 , Athènes, Grèce. “Detecting Wormhole Attacks in Wireless Networks Using Local Neighborhood Information”. In PIMRC 2008, Cannes, France. “Worst-case lifetime computation of a Wireless Sensor Network by model-checking”. In PE-WASUN 2007, Grèce

“Problèmes d'allocation dynamique d'adresses”. Dans AlgoTel 2010, Belle Dunes, France. “Une proposition d'agrégation de MACs pour les réseaux de capteurs utilisant des fonctions de hachage universelles”. Dans SAR-SSI 2009, Luchon, France. “Proposition de gestion des clés et de contrôle d'accès dans un réseau de capteurs”. Dans JDIR 2009, Belfort, France.

Publications:

Journal

Conférences Nationaux

Conférences Internationaux

Quelques propositions de solutions pour la sécurité des réseaux de capteurs sans fil

Wassim Znaidiwassim.znaidi@insa-lyon.fr

Directeurs de thèses: Marine Minier, Stéphane UbédaLaboratoire CITI

INRIA SWING / CITI INSA de Lyon

Date: 19 Octobre 2010

35

Attaque wormhole

Lien wormhole

• Radio plus sophistiqué ou un câble

• longueur du lien > 4-5 sauts

36

• Combine [Cas 05] and our approach• A node i:

– two key kai and kei

– The Sink verifies:

i j

k

)),,...,(,( 1 iliii tagccIV )),,...,(,( 1 jljjj tagccIV

)

,...,

,,,

),(111

(

kji

lkljlikji

kji

tagtagtag

cccccc

IVIVIV

)mod,...,mod(

:

1100 prMprM

rMC

where

il

il

ii

iii

s

s

ss Mtag ?

)mod,...,mod( 1100 prhprh

rhtagi

lil

ii

iii

37

38

39

j

i

Base station

Cluster head node

Sensor node

BFi

BF’i

=?

CHj checks if any of its cluster node is in BFi

If one node success, a double check with CHiis requested

Attaque nœud répliqué