La coloration de graphes est un problème central de l'optimisation combinatoire. C'est un domaine très attractif par ses nombreuses applications. Différentes variantes et généralisations du problème de la coloration de graphes ont été proposées et étudiées. La coloration d'arêtes d'un graphe consiste à attribuer une couleur à chaque arête du graphe de sorte que deux arêtes ayant un sommet commun n'ont jamais la même couleur, le tout en utilisant le moins de couleurs possibles. Dans la première partie de cette thèse, nous étudions le problème de la coloration d'arêtes ℓ-distance, qui est une généralisation de la coloration d'arêtes classique. Nous menons une étude combinatoire et algorithmique du paramètre. L'étude porte sur les classes de graphes suivantes : les chaines, les grilles, les hypercubes, les arbres et des graphes puissances. Le paramètre de la coloration d'arêtes ℓ-distance permet de modéliser des problèmes dans des réseaux assez grands. Cependant, avec la multiplication du nombre de nœuds, les réseaux sont de plus en plus vulnérables aux défaillances (ou pannes). Dans la deuxième partie, nous nous intéressons aux algorithmes tolérants aux pannes et en particulier les algorithmes auto-stabilisants. Nous proposons un algorithme auto-stabilisant pour la coloration propre d'arêtes. Notre solution se base sur le résultat de vizing pour utiliser un minimum de couleurs possibles. Par la suite, nous proposons un algorithme auto-stabilisant de clustering destine a des applications dans le domaine de la sécurité dans les réseaux mobiles Ad hoc. La solution que nous proposons est un partitionnement en clusters base sur les relations de confiance qui existent entre nœuds. Nous proposons aussi un algorithme de gestion de clés de groupe dans les réseaux mobiles ad hoc qui s'appuie sur la topologie de clusters préalablement construite. La sécurité de notre protocole est renforcée par son critère de clustering qui surveille en permanence les relations de confiance et expulse les nœuds malveillants de la session de diffusion.

Dans le monde des systèmes qui utilisent des communications sous forme de diffusion de groupes, le critère de sécurité devient un facteur de plus en plus important. Le choix des mécanismes pour la protection de cette communication, mécanismes basés sur des échanges de clés symétriques et asymétriques, influe sur l'efficacité du système. Nous avons procédé à l'analyse des besoins et nous avons défini un modèle qui permet de représenter la dynamique des groupes et la communication entre leurs membres. Nous avons défini l'architecture d'un système dont l'élément central est la fonction de création, d'échange et de mise en place correcte des clés. La modélisation de ce système dans un environnement UML 2.0 a permis son analyse en termes de garantie de propriétés temporelles et de sécurité. L'approche suivie pour l'étude des exigences temporelles est généralisable à de nombreux systèmes distribués. La valorisation de nos études a été faite dans le cadre du projet national RNRT SAFECAST.

La convergence des réseaux fixes et des réseaux mobiles est une réalité. Les couvertures de ces réseaux sont de plus en plus confondues. Leur intégration dans une architecture commune est une priorité pour les opérateurs et fournisseurs de services. Cela afin de mieux répondre aux problématiques introduites par cette convergence en termes d'interopérabilité, de performance, de qualité de service, de sécurité, d'exploitation et également de réactivité liée au déploiement de nouveaux services. Concernant la sécurité, beaucoup de travaux et d'efforts ont été consentis ces dernières années afin d'aboutir à des solutions immédiates pour sécuriser les échanges dans les réseaux fixes. Ces solutions, telles que TLS (Transport Layer Security) et IPSec ont été ainsi conçues dans un contexte où les équipements et les entités sont fixes, elles sont opérationnelles à grande échelle. Malgré leur diversité, ces solutions sont encore limitées, génériques et répondent insuffisamment aux besoins spécifiques des applications de communication dans les environnements mobiles. Nous avons donc opté pour des solutions d'adaptation qui permettent d'adapter les mécanismes de sécurité conçus au départ pour les réseaux fixes aux réseaux mobiles. Ce choix est appuyé par deux raisons principales. La première est que les réseaux sans fil sont opérationnels et reliés de plus en plus aux réseaux fixes et la seconde réside dans le fait que la réutilisation de ces solutions nous permet de réduire leurs coûts d'exploitation. Notre contribution dans cette thèse est donc de faire avancer les solutions de la sécurisation des échanges sans fil tout en prenant en compte les contraintes précédemment citées. Notre travail de recherche est structuré en quatre parties : La première partie traite de TLS, de ses performances et de sa charge protocolaire. Dans le but d'étudier son adéquation aux réseaux mobiles, nous expérimentons TLS avec les réseaux GSM, en utilisant la pile protocolaire WAP, et avec les réseaux 802.11 sans fil. Les résultats de cette étude nous amènent à proposer des extensions plus performantes et plus appropriées que les mécanismes standard définis dans WAP et les réseaux 802.11 sans fil. La deuxième partie est une contribution qui consiste à l'extension et l'enrichissement de TLS pour répondre à des besoins de sécurité dans le contexte du sans fil. Nous avons ainsi proposé de nouvelles architectures pour la convergence avec les réseaux fixes. Dans la troisième partie, nous proposons d'enrichir la sécurité dans les réseaux WLAN en fournissant des services additionnels comme l'anonymat des échanges, la protection d'identité et la protection contre certains types d'attaques (passives, par dictionnaires, etc.). Nous définissons un mécanisme basé sur l'utilisation d'une clé partagée et de TLS. Cette contribution consiste à ajouter une extension sur le premier message du client TLS tout en respectant la norme "TLS extensions". Ce mécanisme ne nécessite pas l'utilisation des certificats et des PKIs pour l'authentification; il est mieux adapté pour certains réseaux sans fil et à petite échelle où les clients sont pré configurés ou personnalisés. Nous terminons cette partie en présentant une implantation de EAP-TLS couplée avec une carte à puce. La dernière partie consiste essentiellement à intégrer les différentes contributions. Ceci pour mettre en exergue une méthode d'authentification couplant "architecture" et "secret partagé". Nous montrons ainsi comment, avec une telle approche, nous dérivons des services de sécurité non supportés jusqu'à présent par TLS tels que le PFS et la protection de l'identité.

Cette thèse traite des problèmes et des défis de sécurité dans l’Internet des Objets (IdO). L’évolution de l’Internet classique vers l’Internet des Objets crée de nombreux challenges dans la manière de sécuriser les communications et soulève des problèmes liés au contraintes de l’internet des objets à savoir : objets à faibles ressources d’énergie et de calculs, hétérogénéité nuisant à l’interopérabilité des objets, taille du réseau de plus en plus grande, ... etc. En effet, Internet s’est développé d’un réseau d’ordinateurs personnels et de serveurs vers un immense réseau connectant des milliards d’objets intelligents communicants. Ces objets seront intégrés dans des systèmes complexes et utiliseront des capteurs et actionneurs pour observer et interagir avec leur environnement physique. Les exigences des interactions entre objets communicants en termes de sécurité dépendent du contexte qui évolue dans l’espace et le temps. Par conséquent, la définition de la politique de sécurité doit être adaptative et sensible au contexte. Un des problèmes auxquels nous nous sommes intéressés est le contrôle d’accès efficace à base de cryptographie d’attributs : « Attributes Based Encryption (ABE) ». Les schémas ABE (CP-ABE et KP-ABE) présentent plusieurs atouts pour l’implémentation d’un contrôle d’accès cryptographique. Par contre, ces schémas posent des défis opérationnels à cause de leurs complexités et leur surcoût élevé en termes de temps d’exécution et consommation énergétique. Pour pallier cet inconvénient, nous avons exploité l’hétérogénéité d’environnement Internet des Objets pour proposer des versions collaboratives et distribuées de ces schémas de contrôle d’accès cryptographique. Nos solutions réduisent considérablement le coût en termes d’énergie nécessaire à l’exécution. Le deuxième inconvénient des schémas ABE est l’inexistence de mécanismes efficaces de gestion de clés. Nous avons proposé des solutions pour le problème de révocation d’attributs dans le schéma CP-ABE, Ces solutions, en plus de leur efficacité, répondent à des exigences de sécurité différentes selon le cas d’applications. Nous avons proposé également, une solution à base de CP-ABE pour le problème du « grouping proof ». Le « grouping proof » consiste à fournir une preuve sur la coexistence, dans le temps et l’espace, d’un ensemble d’objets. Parmi les applications de notre solution, on peut citer le payement NFC et la sécurisation de l’accès aux locaux sensibles. / In this thesis, we deal with security challenges in the Internet of Things. The evolution of the Internet toward an Internet of Things created new challenges relating to the way to secure communications given the new constraints of IoT, namely: resource constrained objects, heterogeneity of network components, the huge size of the network, etc. Indeed, the Internet evolved from a network of computers and servers toward a huge network connecting billions of smart communicating objects. These objects will be integrated into complex systems and use sensors and actuators to observe and interact with their physical environment. The security requirements of the interactions between smart objects depend on the context which evolves in time and space. Consequently, the definition of the security policies should be adaptive and context-aware. In this thesis, we were interested in the problem of access control in IoT relying on Attribute based Encryption (ABE). Indeed, ABE schemes present many advantages in implementing a cryptographic fine-grained access control. However, these schemes raise many implementation challenges because of their complexity and high computation and energy overheads. To overcome this challenge, we leveraged the heterogeneity of IoT to develop collaborative and distributed versions of ABE schemes. Our solutions reduce remarkably the overhead in terms of energy consumption and computation. The second limitation of ABE schemes is the absence of efficient attribute/key revocation techniques. We have proposed batch based mechanisms for attribute/key revocation in CP-ABE. We demonstrated the efficiency of the proposed solutions through simulations. Finally, we have proposed a CP-ABE based solution for the problem of grouping proof. This problem consists of providing the proof that a set of objects are present simultaneously (same time and same location). The propose solution has many applications such as enforcing the security of NFC based payments and the access to sensitive locations.

De nombreux mécanismes de sécurité ont été proposés pour les réseaux fixes et mobiles. Bien que ces mécanismes aient pu répondre à un ensemble d'exigences de sécurité, ils demeurent uniquement efficaces dans un contexte spécifique lié aux hypothèses et aux exigences restrictives qui ont été émises lors de la conception. Dans un premier temps, nous définissons une liste d'exigences en sécurité qui permet d'analyser les solutions de sécurité les plus déployées. Dans un second temps, nous proposons d'étendre le protocole SSL/TLS avec de nouveaux services. SSL/TLS est une solution de sécurité générique et transparente aux applications. Ainsi, il ne couvre pas les besoins spécifiques à certaines classes d'application telles que les applications de paiement sur Internet. Notre propositions d'intégrer le protocole d'échange des clés ISAKMP avec SSL/TLS permet de fournir, entre autres, la protection d'identité des utilisateurs et l'unification des associations de sécurité. Afin d'étendre l'utilisation de SSL/TLS vers les systèmes de paiement sur Internet, nous intégrons un module générique pour la génération d'une preuve de non répudiation dans le protocole SSL/TLS. Par ailleurs, toutes ces propositions restent, cernées par le problème d'interopérabilité avec les anciennes versions de chaque protocole. Ce qui rend la satisfaction de tous les besoins à travers un des protocoles existants irréalisables. Pour cela, nous proposons finalement de concevoir et de valider un nouveau protocole de sécurité qui intègre nativement l'évolution des protocoles de sécurité des échanges et des réseaux d'une manière performante. Nous avons appelé ce protocole SEP (Secure and Extensible Protocol)

Les Réseaux de Capteurs Sans Fils (RCSFs) et les réseaux véhiculaires sont de plus en plus répandus, et déployés dans des domaines d’applications variés tels que la santé, la surveillance environnementale, les applications d’alerte d’accident, et les applications militaires. Cependant, ces réseaux peuvent être sujets à des attaques, ce qui empêche leur utilisation à grande échelle. Cette thèse étudie la sécurité des communications pour les réseaux de capteurs sans fils, et les communications inter-véhiculaires. Dans ce but, nous abordons quatre aspects importants. La première étude porte sur l’authentification des messages diffusés dans les réseaux de capteurs. Nous nous concentrons sur les principaux schémas à base de divulgation de clés d’authentification. Nous démontrons que le délai de divulgation de clé induit un délai d’authentification, ce qui pourrait conduire à une attaque de mémoire de déni de service. Nous proposons ensuite deux protocoles d’authentification de la source dans les RCSFs, pour surmonter la vulnérabilité des solutions existantes. Les schémas proposés garantissent la gestion efficace de la mémoire tampon du récepteur, en utilisant un mécanisme d’authentification par niveau, et une structure de Filtre de Bloom afin de réduire le coût de communication. Ensuite, nous validons nos protocoles en utilisant l’outil de vérification AVISPA, et nous les évaluons avec des expérimentations dans l’environment TinyOS. Nous confirmons que ces protocoles fournissent un service d’authentification de la source tout en respectant les contraintes de RCSFs. La seconde étude porte sur le problème de stockage au niveau des capteurs. Nous considérons en particulier l’attaque d’authentification différée “Delayed Authentication Compromise” (DAC) dans les RCSFs, qui permet à un attaquant d’utiliser une clé déjà divulguée pour signer d’autres messages. Nous montrons d’abord que les systèmes récemment proposés qui sont résistants également à l’attaque DAC sont vulnérables aussi à deux types d’attaques: attaque de permutation de commandes (où un adversaire prétend “permuter” deux messages au fil du temps), et l’attaque de rejet de commandes (où un adversaire semble “cacher” un message envoyé par la station de base). Nous proposons ensuite une nouvelle solution d’authentification. Notre analyse montre que notre solution est efficace pour détecter à la fois l’attaque de permutation de commandes et l’attaque de rejet de commandes, — et en même temps — est plus efficace (en termes de communication et de calcul) que les solutions existantes. xxiDans la troisième étude, nous considérons le problème de la sécurité de la gestion des clés dans les réseaux de capteurs. Nous présentons de nouveaux schémas d’authentification à base de clés symétriques qui présentent un faible coût d’authentification et de communication. Nos systèmes sont construits en intégrant un mécanisme de réputation, un filtre de Bloom, et un arbre binaire de clés pour la distribution et la mise à jour des clés d’authentification. Nos schémas d’authentification sont efficaces en matière de communication et de consommation de l’énergie. La quatrième étude porte sur la sécurité des communications véhiculaires. Nous nous concentrons sur les applications d’alerte d’accident. Nous analysons les menaces pour un ensemble d’algorithmes. Nous démontrons que ces systèmes sont vulnérables à l’attaque d’injection d’une fausse position, à l’attaque de rejeu de message d’alerte, et à l’attaque d’interruption de message d’alerte. Ensuite, nous proposons des contre-mesures à ces menaces. Nous avons donc proposé une solution qui est à la fois rapide et sécurisée pour les applications d’alerte d’accident : Un algorithme rapide et sécurisé pour la diffusion des messages en multi-saut (FS-MBA). Enfin, nous confirmons l’efficacité et la faisabilité des différents protocoles en effectuant un ensemble de simulations sous le simulateur NS-2. / Wireless sensor and vehicular networks play an important role in critical military and civil applications, and pervade our daily life. However, security concerns constitute a potential stumbling block to the impeding wide deployment of sensor networks and vehicular communications. This dissertation studies communication security for Wireless Sensor Networks (WSNs), and vehicular communication. To this aim, we address four important aspects. The first study addresses broadcast authentication in WSNs. We focus on key disclosure based schemes. We demonstrate that key disclosure delay induces an authentication delay, which could lead to a memory DoS attack. We then propose two broadcastauthentication protocols for WSNs, which overcome the security vulnerability of existingsolutions. The proposed schemes guarantee the efficient management of receiver’s buffer, by employing a staggered authentication mechanism, and a Bloom filter data structure to reduce the communication overhead. We also validate our protocols under the AVISPA model checking tool, and we evaluate them with experiments under TinyOS. Our findings are that these protocols provide source authentication service while respecting the WSN constraints.The second study addresses the storage issue in WSNs, in particular the Delayed AuthenticationCompromise attack (DAC). We first demonstrate that recently proposed schemes, which also address the DAC issue are vulnerable to two kinds of attacks: switch command attack (where an adversary pretends to “switch” two messages over time), and drop command attack (where an adversary just pretends to “hide” a message sent from the broadcaster). As a countermeasure against these attacks, we propose a new solution for broadcast authentication. Our analysis shows that our solution is effective in detecting both switch command and drop command attack, and—at the same time—is more efficient (in terms of both communication and computation) than the state of the art solutions.In the third study, we address key management security in WSNs. We present novel symmetric-key-based authentication schemes which exhibit low computation and communication authentication overhead. Our schemes are built upon the integration of a reputation mechanism, a Bloom filter, and a key binary tree for the distribution and updating of the auxviii thentication keys. Our schemes are lightweight and efficient with respect to communication and energy overhead. The fourth study addresses security in vehicular communications. We focus on fast multi hop broadcast applications. We analyze the security threats of state of the art vehicular based safety applications. We demonstrate that these schemes are vulnerable to the position cheating attack, the replay broadcast message attack, and the interrupting forwarding attack. Then, we propose countermeasures for these threats. We hence propose a complete solution which is both fast and secure in broadcasting safety related messages: Fast and Secure Multi-hop Broadcast Algorithm (FS-MBA). Finally, we confirm the efficiency and feasibility of our proposals using an extensive set of simulations under NS-2 Simulator.

La coloration de graphes est un problème central de l’optimisation combinatoire. C’est un domaine très attractif par ses nombreuses applications. Différentes variantes et généralisations du problème de la coloration de graphes ont été proposées et étudiées. La coloration d’arêtes d’un graphe consiste à attribuer une couleur à chaque arête du graphe de sorte que deux arêtes ayant un sommet commun n’ont jamais la même couleur, le tout en utilisant le moins de couleurs possibles. Dans la première partie de cette thèse, nous étudions le problème de la coloration d’arêtes ℓ-distance, qui est une généralisation de la coloration d’arêtes classique. Nous menons une étude combinatoire et algorithmique du paramètre. L’étude porte sur les classes de graphes suivantes : les chaines, les grilles, les hypercubes, les arbres et des graphes puissances. Le paramètre de la coloration d’arêtes ℓ-distance permet de modéliser des problèmes dans des réseaux assez grands. Cependant, avec la multiplication du nombre de nœuds, les réseaux sont de plus en plus vulnérables aux défaillances (ou pannes). Dans la deuxième partie, nous nous intéressons aux algorithmes tolérants aux pannes et en particulier les algorithmes auto-stabilisants. Nous proposons un algorithme auto-stabilisant pour la coloration propre d’arêtes. Notre solution se base sur le résultat de vizing pour utiliser un minimum de couleurs possibles. Par la suite, nous proposons un algorithme auto-stabilisant de clustering destine a des applications dans le domaine de la sécurité dans les réseaux mobiles Ad hoc. La solution que nous proposons est un partitionnement en clusters base sur les relations de confiance qui existent entre nœuds. Nous proposons aussi un algorithme de gestion de clés de groupe dans les réseaux mobiles ad hoc qui s’appuie sur la topologie de clusters préalablement construite. La sécurité de notre protocole est renforcée par son critère de clustering qui surveille en permanence les relations de confiance et expulse les nœuds malveillants de la session de diffusion. / Graph coloring is a famous combinatorial optimization problem and is very attractive for its numerous applications. Many variants and generalizations of the graph-coloring problem have been introduced and studied. An edge-coloring assigns a color to each edge so that no two adjacent edges share the same color. In the first part of this thesis, we study the problem of the ℓ-distance-edge-coloring, which is a generalization of the classical edge-coloring. The study focuses on the following classes of graphs : paths, grids, hypercubes, trees and some power graphs. We are conducting a combinatorial and algorithmic study of the parameter. We give a sequential coloring algorithm for each class of graph. The ℓ-distance-edge-coloring is especially considered in large-scale networks. However, with the increasing number of nodes, networks are increasingly vulnerable to faults. In the second part, we focus on fault-tolerant algorithms and in particular self-stabilizing algorithms. We propose a self-stabilizing algorithm for proper edge-coloring. Our solution is based on Vizing’s result to minimize number of colors. Subsequently, we propose a selfstabilizing clustering algorithm for applications in the field of security in mobile ad hoc networks. Our solution is a partitioning into clusters based on trust relationships between nodes. We also propose a group key-management algorithm in mobile ad hoc networks based on the topology of clusters previously built. The security of our protocol is strengthened by its clustering criterion which constantly monitors trust relationships and expels malicious nodes out of the multicast session.

Les réseaux de capteurs sans fil (RCSF) sont devenus un thème porteur aussi bien pour la recherche académique que pour les activités des services de R&D en raison de leur simplicité de déploiement et de leur potentiel applicatif dans des domaines très variés (militaire, environnemental, industriel). Un RCSF est composé d'un ensemble de noeuds devant être opérationnels et autonomes énergétiquement pour de longues périodes. De ce fait ils sont limités en capacité mémoire et de calcul, et contraint à exploiter une faible puissance de transmission, ce qui en limite leur portée et rend leur débit modeste. Le besoin de sécuriser les communications dans un RCSF dépend de la criticité des données échangées pour l'application supportée. La solution doit reposer sur des échanges sûrs, confidentiels et fiables. Pour assurer la sécurisation des échanges, des techniques de cryptographie existent dans la littérature. Conçues à l'origine pour des réseaux informatiques majoritairement câblés, elles se basent généralement sur des algorithmes complexes et gourmands en ressource. Dans le cadre de cette thèse, nous avons proposé, implémenté et évalué une architecture sécurisée et dynamique adaptée aux communications des RCSF. Elle permet de garantir et de maintenir la sécurité des communications durant toute la durée de vie d'un réseau multi-saut. Nous avons utilisé et adapté des algorithmes standards de cryptographie, tels que AES-CTR et la suite d'algorithmes basée sur ECC, qui permettent à notre architecture de résister à la majorité d'attaques. Nous avons quantifié le surcoût en temps de calcul et en occupation mémoire de notre solution. Les résultats d'implémentation de notre proposition sont issus de mesures réelles faites sur une maquette réalisée à partir de cartes TelosB.

Les réseaux de capteurs sans fil (RCSF) sont devenus un thème porteur aussi bien pour la recherche académique que pour les activités des services de R&D en raison de leur simplicité de déploiement et de leur potentiel applicatif dans des domaines très variés (militaire, environnemental, industriel). Un RCSF est composé d'un ensemble de noeuds devant être opérationnels et autonomes énergétiquement pour de longues périodes. De ce fait ils sont limités en capacité mémoire et de calcul, et contraint à exploiter une faible puissance de transmission, ce qui en limite leur portée et rend leur débit modeste. Le besoin de sécuriser les communications dans un RCSF dépend de la criticité des données échangées pour l'application supportée. La solution doit reposer sur des échanges sûrs, confidentiels et fiables. Pour assurer la sécurisation des échanges, des techniques de cryptographie existent dans la littérature. Conçues à l'origine pour des réseaux informatiques majoritairement câblés, elles se basent généralement sur des algorithmes complexes et gourmands en ressource. Dans le cadre de cette thèse, nous avons proposé, implémenté et évalué une architecture sécurisée et dynamique adaptée aux communications des RCSF. Elle permet de garantir et de maintenir la sécurité des communications durant toute la durée de vie d'un réseau multi-saut. Nous avons utilisé et adapté des algorithmes standards de cryptographie, tels que AES-CTR et la suite d'algorithmes basée sur ECC, qui permettent à notre architecture de résister à la majorité d'attaques. Nous avons quantifié le surcoût en temps de calcul et en occupation mémoire de notre solution. Les résultats d’implémentation de notre proposition sont issus de mesures réelles faites sur une maquette réalisée à partir de cartes TelosB. / Wireless sensor networks (WSNs) have become an attractive topic for both academic research and the activity of R&D services due to their simple deployment and their potential of application in varied fields (military, environmental, industrial). A WSN is composed of a set of nodes that are supposed to operate and to be energetically autonomous for long durations. Thus, they are limited in memory and computing capacities, and constrained to function in a low-power transmission mode which limit their communication range and leave them with low data rates.The need to secure communications in a WSN depends on the criticality of the exchanged data for the supported application. The solution must be based on safe, confidential and reliable exchanges. To ensure the security of exchanges, cryptographic techniques exist in the literature. Originally designed for mostly wired computer networks, they are usually based on complex and resource-consuming algorithms. In this thesis, we have proposed, implemented and evaluated a secure and dynamic architecture suitable for WSNs communications. It ensures and maintains secured communications throughout the lifetime of a multi-hop network. We have used and adapted standard cryptographic algorithms, such as AES-CTR and algorithms based on ECC cipher suites, which allow our architecture to resist against most attacks. We have quantified the overhead of our solution in terms of computation time and memory occupancy. The results of implementation of our proposal are obtained through real measurements on testbeds using TelosB motes.