Thèse de Doctorat de lUniversité Paris 6 UPMC Schémas de sécurité pour le protocole OLSR pour les réseaux ad hoc Daniele Raffo Directeur de Thèse: Paul

Thèse de Doctorat de l’Université Paris 6 UPMC

Schémas de sécurité pour le protocole OLSR pour les réseaux ad hoc

Daniele Raffo

Directeur de Thèse: Paul Mühlethaler

Jury:François Baccelli Ana Cavalli François MorainPaul Mühlethaler Guy Pujolle Ahmed Serhrouchni

Membres invités: Daniel Augot Philippe Jacquet

15 Septembre 2005

Thèse de Doctorat de l’Université Paris 6 UPMC

2 / 55

Plan de la présentation

•Introduction•Les réseaux sans fil

•Les réseaux ad hoc et le routage - OLSR

•Les problématiques de la thèse: ma contribution

•Attaques

•Hypothèse et modèle

•Architecture de sécurité de base (SIGNATURE)•Timestamps et signatures

•Distribution des clés•PKI pour OLSR

•Identity-Based Signatures

•Modèle noeuds compromis: parades•Signatures multiples (ADVSIG)

•Position géographique des noeuds (SIGLOC)

•Accusations et modèle du flot

•Conclusion

Schémas de sécurité pour le protocole OLSR pour les réseaux ad hoc Daniele Raffo

3 / 55

Les réseaux sans fil

Fréquences radio: 2.4 GHz (ISM), 5 GHz (U-NII)

Standards: IEEE 802.11[a|b|g], IEEE 802.16, HiperLAN, Bluetooth...

Architectures: BSS (avec AP), IBSS (sans AP), ad hoc


BSS

IBSS (P2P)

Introduction ∙ Problématiques ∙ Attaques ∙ Modèle ∙ Sécurité de base ∙ Distribution des clés ∙ Noeuds compromis ∙ Conclusion

4 / 55

Les réseaux ad hoc et le routage

Un réseau ad hoc nécessite que dans tout noeud soit actif un protocole de routage

Protocoles: réactifs (AODV, DSR), proactifs (OLSR, OSPF), hybrides (CBRP)


AD HOC


5 / 55

OLSR

OLSR (Optimized Link State Routing): protocole proactif à état de lien, développé par INRIA HIPERCOM.

Inondation (flooding) optimisée par Relais Multipoint (MPRs): tout noeud sélectionne ses MPRs parmi ses voisins symétriques pour qu’un message émis par le noeud et relayé par ses MPRs soit reçu par tous ses voisins à 2 sauts


Inondation pure Inondation par MPRs


6 / 55

OLSREchange périodique de messages de contrôle:

HELLO état de lien (voisinage), sélection MPR 1 sautTC liens symétriques et MPR relayéMID interfaces multiples relayéHNA association host-network non-OLSR relayé


Entête du paquet OLSR

Entête du message

Message

Entête du message

Message

Entête UDP

Entête IP


7 / 55

Problématiques de la thèse


Identification des attaques contre les réseaux ad hoc et OLSR

Idéation et développement d’architectures de sécurité

Analyse des modifications spécifiques au protocole OLSR

Protection du système de routage dans un réseau ad hoc

Non traités: écoute et intrusion dans les réseaux ad hoc

(car problèmes déjà traités dans les réseaux classiques)


8 / 55

Ma contribution


Identification des attaques contre OLSR

Mise en place d’une architecture OLSR sécurisée

Noeuds non compromis(sécurité de base)

Noeuds compromis(sécurité avancée)

•Signatures•Timestamps

•Signatures multiples•Localisation GPS•Accusations

Architecture pour le prototype CELAR

PKIpourOLSR

Modèle de sécurité pour les réseaux ad hoc


9 / 55

Attaques contre OLSRButs de l’adversaire: s’insérer dans le protocole de routage, perturber la topologie du réseau


Génération incorrecte du trafic Relayage incorrect du trafic

HELLO incorrect

attaque ANSN

TC incorrect

IDspoof

linkspoof

linkspoof

IDspoof

MID/HNA incorrect Modification Blackhole

Wormhole

attaque MPR

Rejeu

DoS

Attaques sur le trafic de contrôle dans OLSR


10 / 55

Attaques contre OLSR

Génération incorrecte des HELLOs

identity spoofing: X envoie des messages avec C comme origine ⇒ A et B vont annoncer leur voisinage avec C

X choisit A et/ou B comme ses MPRs avec l’identité de C ⇒ ces MPRs vont déclarer qu’il peuvent fournir connectivité vers C

⇒ conflits des routes vers C, perte de connectivité



11 / 55


Génération incorrecte des HELLOs

link spoofing: X déclare un lien sym avec A ⇒ C choisit comme son MPR set probablement {X, D} au lieu de {X, B, D}

⇒ les messages de E ne vont pas joindre A

Autre attaque: X ne déclare pas tous ses voisins ⇒ possible perte de connectivité des voisins ignorés



12 / 55


Génération incorrecte des TCs

identity spoofing: X envoie un message avec l’identité de C déclarant A comme voisin ⇒ topologie erronée

link spoofing: X envoie un message déclarant D voisin ⇒ topologie erronée

Non-envoi de TC, ou TC incomplets ⇒ topologie non diffusée



13 / 55


Génération incorrecte des MIDs/HNAs

⇒ problèmes à joindre les interfaces sélectionnées

Attaque ANSN

X envoie un TC avec origine Y falsifié et un ANSN élevé ⇒ tout message TC de Y ayant un ANSN inférieur est ignoré (cf. Topology Set)



14 / 55


Modification des messages pendant le rélayage

⇒ mêmes conséquences de l’identity/link spoofing

Blackhole attack (non-relayage des messages)

⇒ perte de messages, topologie non diffusée

Replay attack ou Attaque de rejeu

Nécessite de changer MSN (HELLO ou TC) et/ou ANSN (TC) ⇒ engendre une perte des messages selon leurs MSN/ANSN



15 / 55


Wormhole attack

X (ou X-X’) relaye les messages entre A et B:

création d’un faux lien «optimal» sous le contrôle de X (blackhole)

⇒ lien compromis, possible perte de messages, topologie fausse



16 / 55


Attaque MPR

B = MPR de A C = MPR de B X = non MPR

A envoie un message à X et B

X relaye ce message à C, même s’il n’est pas censé le faire

B relaye ce message à C

C ne relaye pas le message car il l’a déjà reçu de X ⇒ perte de messages



17 / 55

Hypothèses et modèle


Modèle sans cryptographie Modèle avec cryptographie

Noeud compliant

Noeud malveillant

Noeud compliant

Noeud compromisNoeud malveillant

noeud compromis: noeud dont la clé privée (ou le noeud lui-même) est tombé en main d’un adversaire, qui peut donc envoyer de faux messages correctement signés

crypto sym crypto asym


18 / 55

Idée de base d’une architecture

Isoler les noeuds adversaires en utilisant un système de signature



19 / 55

Technique

Un dévoilement de la clé symétrique (noeud compromis) abouti à la compromission du réseau entier...



20 / 55

Technique

... tandis que avec des clés asymétriques on peut encore identifier le noeud coupable (et éventuellement l’éliminer du réseau)



21 / 55

Signature

Ajout d’une signature avec timestamp au trafic de contrôle OLSR.

Deux possibilités:


Signature du paquet

•Signature ajoutée à chaque paquet

•Contrôle hop-by-hop (end-to-end impossible car le paquet change)

•Taille du paquet plus petite

•Identification difficile des noeuds compromis (à cause du relayage)

Signature du message

•OLSR message de type SIGNATURE

•Contrôle end-to-end

•Impossible signer le TTL et Hop Count (⇒ attaques). Solution: utiliser Timestamp à la place du TTL

•Meilleure identification de l’émetteur; signatures asym utiles!

•Meilleure intéroperabilité (signatures on/off)


22 / 55

Signature

Format du SIGNATURE:

0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Sign. Method | Reserved | MSN Referrer |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Timestamp |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Signature |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Associé à chaque message HELLO/TC/MID/HNA, il le précède dans le même paquet. (Une version précédente utilisait un réfèrent MSN pour permettre la non-agrégation; abandonnée car engendrait un délai important)

Fragmentation possible pour respecter le Maximum Transfert Unit

Système de signature intégré avec les fonctions de base d’OLSR



23 / 55

Signature


Time To Live Hop Count Message Sequence Number

Originator Address

Message Type Vtime Message Size

HELLO/TC/MID/HNA MESSAGE

Time To Live Hop Count Message Sequence Number

Originator Address

Message Type Vtime Message Size

Timestamp

Signature

La Signature est calculée sur tous les champs non mutables

SIGNATURE MESSAGE


24 / 55

Signature

Fonctionnement principal du protocole

Création d’un message:

•écrire le Timestamp

•générer la Signature

•envoyer la SIGNATURE et le message de contrôle dans le même paquet

Vérification d’un message signé:

•contrôler la Timestamp

•vérifier la Signature par rapport au message de contrôle

•si ok, traiter le message de contrôle; sinon, écarter les deux messages Schémas de sécurité pour le protocole OLSR pour les réseaux ad hoc Daniele Raffo


25 / 55

Signature

Modification du Duplicate Tuple dans le Duplicate Set:

<D_addr, D_seq_num, D_timestamp, D_retransmitted, D_iface_list, D_time>

Un message est donc identifié par: D_addr, D_seq_num, D_timestamp.

L’algorithme sécurisé de traitement des paquets tient compte de cette modification



26 / 55

Signature

Condition de traitement (modifications pour la sécurité), étape 3b du RFC 3626:

Traiter le message selon le Message Type.

Si le message est une SIGNATURE

•si la Timestamp est valide

•garder le SIGNATURE (entête incluse) en mémoire

•sinon

•écarter le message et effacer sa Duplicate Tuple

Sinon, si le message est d’une autre type implémenté

•si (MSN message = MSN SIGNATURE + 1) et (Signature est valide)

•effacer la SIGNATURE de la mémoire et traiter le message de contrôle

•sinon

•écarter le message et effacer sa Duplicate Tuple



27 / 55

Timestamps

Utilisées pour parer les attaques de rejeu + attaques de modifications du TTL

Options pour les timestamps:

•Timestamps en temps réel (horloge embarqué)

•Timestamps logiques (incrémentées à chaque événement)

•Protocole d’échange des timestamps (Needham-Schroeder)



28 / 55

Timestamps

Utilisation des mécanismes OLSR sous-jacents. Une synchronisation stricte n’est pas nécessaire: l’identification d’un message dans le Duplicate Set est faite par adresse + MSN + Timestamp

Le Duplicate Set est effacé à chaque DUP_HOLD_TIME (=30 sec)

Message accepté si le Timestamp est entre DUP_HOLD_TIME/2



29 / 55

Architecture du prototype CELAR

Implémentation du prototype CELAR: horloges BIOS, synchronisation manuelle au démarrage et resynchronisation par régression linéaire

Dérive Resync pour précision de 15 sec

sans resync 1 sec/j 15 j

avec resync, cas moyen: 30 msec/j 500 j

avec resync, pire cas: 0.2 sec/j 75 j


diff

ére

nce

de t

em

ps

(sec)

, ré

fére

nce

route

r 1

temps (jours) temps (jours)

sans resynchronisation avec resynchronisation


30 / 55

Architecture du prototype CELAR


Vitesse de signature/vérification (msec/op):

Une possibilité:

•HMAC pour signatures sym•EC pour signatures asym


31 / 55

Etude de l’overhead

Taille des messages: doublée au max

Calcul théorique de l’overhead d’OLSR en fonction des timers des messages de contrôle, du facteur d’optimisation d’OLSR et de l’algorithme de signature choisi



32 / 55

Signature

Attaques parées par cette architecture:



33 / 55

Distribution des clés

Alternatives possibles pour la distribution des clés dans un environnement ad hoc:

•PKI standard avec Certification Authority

•Cryptographie à seuil (threshold cryptography)

•Imprinting

•Web of Trust (PGP)

•Identity-Based Signatures

•PKI pour l’architecture de sécurisation OLSR



34 / 55


PKI pour OLSR

Certification Authority (CA): clé publique connue à priori

Pour un noeud donné, on a des

Noeuds untrusted - non fiables: clé publique non connue

Noeuds trusted - fiables: clé publique connue

Un noeud:

•sélectionne comme MPR seulement des noeuds fiables

•accepte comme MPR Selectors seulement des noeuds fiables

•accepte seulement les TCs qui ont comme origine des noeuds fiables

•relaye seulement les messages qui viennent de voisins fiables



35 / 55


PKI pour OLSR

Problème d’interblocage: pas de sélection de MPR ⇔ pas de distribution de certificats!

Solution: considérer les liens MPR avec les noeuds non fiables comme liens simples symétriques

Construction de la topologie et distribution des clés sont simultanés



36 / 55

PKI pour OLSR

Certification Authority Noeud sans clé Noeud avec clé MPR

Etape 1




37 / 55

PKI pour OLSR


Etape 2




38 / 55

PKI pour OLSR


Etape 3




39 / 55

PKI pour OLSR


Etape 4




40 / 55

PKI pour OLSR


Etape 5




41 / 55

Cas des noeuds compromis

Parades dans le cas des noeuds compromis:

Principe 0: utiliser l’architecture précédente (protocole SIGNATURE)

Principe 1: prévention - Inclure de l’information redondante dans les messages de contrôle au fin de vérifier ceux-ci

•Signatures multiples relatives à l’état de lien (ADVSIG)

•Position géographique des noeuds (SIGLOC)

et/ou

Principe 2: détection – Déceler les comportements malveillants

•Système d’accusations

•Modèle de conservation du flot



42 / 55

Cas des noeuds compromis

Protection offerte en cas de noeuds compromis:



43 / 55

Signatures multiples

La topologie du réseau change étape par étape



44 / 55


On pourrait donc réutiliser l’information topologique au moment ti-1 pour prouver la validité de l’information à un moment successif ti


t1

t2

t3

t4

BA

(vide)

A: ASYM_LINK

B: SYM_LINK

A: SYM_NEIGH ou MPR_NEIGH


45 / 55


Cette information est le Link Code transmis dans un HELLO


t1

t2

t3

t4

BA

(vide)

A: ASYM_LINK

B: SYM_LINK

A: SYM_NEIGH ou MPR_NEIGH

A: ASYM_LINK

B: SYM_LINK


(vide)

46 / 55


Etat de lien Preuve nécessaire


SYM_LINK ou SYM_NEIGHSYM_NEIGH ou MPR_NEIGH

ASYM_LINK ou SYM_LINK

« le paquet a été entendu »

SYM_LINK

ASYM_LINK

voisinage (dans les TCs) SYM_NEIGH ou MPR_NEIGH


47 / 55

Signatures multiples 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Reserved | Htime | Willingness |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Link Code | Reserved | Link Message Size |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Neighbor Interface Address |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Neighbor Interface Address |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Link Code | Reserved | Link Message Size |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Neighbor Interface Address |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+: :: :

Chaque information d’état de lien est signée et incluse dans un ADVSIG, qui est couplé et envoyé avec tout message HELLO/TC


0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Global Timestamp |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Global Signature |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Signature of Certificate #0 |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Signature of Certificate #1 |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Signature of Certificate #2 |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Signature of Certificate #3 |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+: :: :+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Link Code #1 | Reserved |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Timestamp of Proof #1 |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Signature of Proof #1 |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Link Code #2 | Reserved |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Timestamp of Proof #2 |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Signature of Proof #2 |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Link Code #3 | Reserved |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Timestamp of Proof #3 |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Signature of Proof #3 |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+: :: :


48 / 55


Protection contre les fausses informations topologiques fournie par: un noeud malveillant ou par noeuds malveillants multiples disjoints

Wormhole et DoS sont encore possibles

Taille importante, plusieurs signatures dans le HELLO: faisable?



49 / 55

Position géographique

Information géographique (GPS) incluse dans la signature et diffusée

Cette information est la dernière position connue du noeud

But: contrôler la vraisemblance des informations topologiques diffusées dans les HELLOs/TCs (position du noeud et existence du lien)

L’information est distribuée dans un message SIGLOC

Tout noeud maintient en mémoire la dernière position connue d’un noeud: < adresse, position, timestamp >



50 / 55


rmax portée maximale de transmission

dSR distance entre les noeuds émetteur S et receveur R

pS , pR position actuelle des noeuds S et R

TS , TR timestamps d’envoi et de réception du message

t erreur max dans la synchronisation des horloges

d erreur max dans le positionnement des noeuds

vmax vitesse max des noeuds

Si formule fausse ⇒ S et R trop lointains ⇒ transmission suspecteSchémas de sécurité pour le protocole OLSR pour les réseaux ad hoc Daniele Raffo


51 / 55


Protection contre le wormhole:

Si formule fausse par rapport à dAB ⇒ Possible wormhole A-B

Protection contre le link spoofing (X déclare un lien avec N):

Si formule fausse (par A) par rapport à dXN ⇒ Lien X-N inexistant



52 / 55


Une détection plus détaillée est obtenue par une antenne sectorielle: le noeud receveur vérifie que la direction θS de provenance du signal est conforme au secteur [θ, θ+θ ] dans lequel le signal est reçu



53 / 55


Overhead limité par rapport au système avec signatures multiples

Toutefois, il est nécessaire de pourvoir un dispositif GPS embarqué dans chaque noeud



54 / 55

Détection des malveillances

Etat de l’art: Watchdog/Pathrater, CONFIDANT, WATCHERS

Système des accusations:

•tout noeud vérifie le comportement de ses voisins

•en cas de malveillance, une accusation est envoyée en broadcast

•les noeuds avec un “trust level” inférieur à un certain seuil sont éliminés du réseau

Contrôle sur la conservation du flot:

“Tous donnée envoyé à un noeud et non destiné à lui y doit sortir”

Mise en place d’un système de compteurs



55 / 55

Résultats obtenus•Analyse détaillée des attaques contre OLSR et définition d’un cadre d’étude

•Conception d’une architecture sécurisée pour OLSR et détails des

modifications du protocole pour l’implémentation

•PKI pour OLSR sécurisé

•Architectures avancées de sécurité pour les attaques particulières:

wormhole ou noeuds compromis

Perspectives•Etude sur les performances des architectures définies (test réels)

•Affinage de la protection offerte par les différentes techniques

•Recherche d’algorithmes de signature appropriés: ex. ESIGN, RW

Conclusion



Documents

Thèse de Doctorat de lUniversité Paris 6 UPMC Schémas de sécurité pour le protocole OLSR pour les réseaux ad hoc Daniele Raffo Directeur de Thèse: Paul