Le concept de l'anonymat entre en jeu dans les cas où nous voulons garder le secret sur l'identité des agents qui participent à un certain événement. Il existe un large éventail de situations dans lesquelles cette propriété peut être nécessaire ou souhaitable, par exemple: web de vote surf, les dons anonymes, et l'affichage sur les babillards. L'anonymat est souvent formulées de manière plus générale comme une propriété de dissimulation d'informations, à savoir la propriété qu'une partie des informations relatives à un certain événement est tenu secret. Il faut être prudent, cependant, de ne pas confondre anonymat avec d'autres propriétés que la même description, notamment la confidentialité (secret aka). Laissez-nous insister sur la différence entre les deux concepts en ce qui concerne l'envoi de messages: la confidentialité se réfère aux situations dans lesquelles le contenu du message doit être gardée secrète, dans le cas de l'anonymat, d'autre part, c'est l'identité de l'expéditeur ou du destinataire, qui doit être gardée secrète. De la même façon, en votant, l'anonymat signifie que l'identité de l'électeur associés à chaque vote doit être caché, et non pas le vote lui-même ou le candidat a voté pour. D'autres propriétés remarquables de cette catégorie sont la vie privée et la non-ingérence. Protection des renseignements personnels, il se réfère à la protection de certaines données, telles que le numéro de carte de crédit d'un utilisateur. Non-ingérence signifie qu'un utilisateur bas ne seront pas en mesure d'obtenir des informations sur les activités d'un utilisateur élevés. Une discussion sur la différence entre l'anonymat et d'autres propriétés de dissimulation d'informations peuvent être trouvées dans HO03 [, HO05]. Une caractéristique importante de l'anonymat, c'est qu'il est généralement relative à la capacité de l'observateur. En général, l'activité d'un protocole peut être observé par divers observateurs, di? Vrant dans les informations qu'ils ont accès. La propriété anonymat dépend essentiellement de ce que nous considérons comme observables. À titre d'exemple, dans le cas d'un babillard anonyme, une annonce par un membre du groupe est maintenue anonymes aux autres membres, mais il peut être possible que l'administrateur du conseil d'administration a accès à une information privilégiée qui peut lui permettre de déduire l'identité du membre qui l'a publié. Dans l'anonymat peut être exigée pour un sous-ensemble des agents uniquement. Afin de définir complètement l'anonymat d'un protocole, il est donc nécessaire de préciser ce qui se (s) des membres ont de garder l'anonymat. Une généralisation est le concept de l'anonymat à l'égard d'un groupe: les membres sont divisés en un certain nombre de séries, et nous sommes autorisés à révéler à quel groupe l'utilisateur responsable de l'action appartient, mais pas l'identité de l'utilisateur lui-même. Plusieurs définitions formelles et les cadres d'analyse anonymat ont été développés dans la littérature. Elles peuvent être classifiées en ed approches fondées sur les processus de calculs ([SS96, RS01]), la logique épistémique ([SS99], HO03), et des vues de fonction ([HS04]). La plupart de ces approches sont fondées sur le principe dit de confusion: un système est anonyme si l'ensemble des résultats possibles observable est saturé pour les utilisateurs prévus anonymes. Plus précisément, si dans un calcul le coupable (l'utilisateur qui exécute l'action) est i et le résultat observable est o, alors pour tout autre agent j il doit y avoir un calcul où j est le coupable et l'observable est encore o. Cette approche est aussi appelée possibiliste, et s'appuie sur non-déterminisme. En particulier, les choix probabilistes sont interprétés comme non déterministe. Nous nous référons à RS01] pour plus de détails sur la relation de cette approche à la notion d'anonymat.

La société de l’information dans laquelle nous vivons repose notamment sur notre capacité à échanger des informations de façon sécurisée. Ces échanges sécurisés sont réalisés au moyen de protocoles cryptographiques. Ils explicitent comment les différents agents communicants doivent se comporter et exploitent des primitives cryptographiques (e.g. chiffrement, signature) pour protéger les échanges. Étant donné leur prédominance et leur importance, il est crucial de s’assurer que ces protocoles accomplissent réellement leurs objectifs. Parmi ces objectifs, on trouve de plus en plus de propriétés en lien avec la vie privée (e.g. anonymat, non-traçabilité). Malheureusement, les protocoles développés et déployés souffrent souvent de défauts de conception entraînant un cycle interminable entre découverte d’attaques et amélioration des protocoles.Pour en sortir, nous prônons l’analyse mécanisée de ces protocoles par des méthodes formelles qui, via leurs fondements mathématiques, permettent une analyse rigoureuse apportant des garanties fortes sur la sécurité attendue. Parmi celles-ci, la vérification dans le modèle symbolique offre de grandes opportunités d’automatisation. La plupart des propriétés en lien avec la vie privée sont alors modélisées par l’équivalence entre deux systèmes. Toutefois, vérifier cette équivalence est indécidable dans le cas général. Deux approches ont alors émergé. Premièrement, pour un nombre borné de sessions d’un protocole, il est possible de symboliquement explorer toutes ses exécutions possibles et d’en déduire des procédures de décision pour l’équivalence. Deuxièmement, il existe des méthodes de semi-décision du problème dans le cas général qui exploitent des abstractions, notamment en considérant une forme forte d’équivalence.Nous avons identifié un problème majeur pour chacune des deux méthodes de l’état de l’art qui limitent grandement leur impact en pratique. Premièrement, les méthodes et outils qui explorent symboliquement les exécutions souffrent de l’explosion combinatoire du nombre d’états, causée par la nature concurrente des systèmes étudiés. Deuxièmenent, dans le cas non borné, la forme forte d’équivalence considérée se trouve être trop imprécise pour vérifier certaines propriétés telle que la non traçabilité, rendant cette approche inopérante pour ces propriétés.Dans cette thèse, nous proposons une solution à chacun des problèmes. Ces solutions prennent la forme de contributions théoriques, mais nous nous efforçons de les mettre en pratique via des implémentations afin de confirmer leurs impacts pratiques qui se révèlent importants.Tout d’abord, nous développons des méthodes de réduction d’ordres partiels pour réduire drastiquement le nombre d’états à explorer tout en s’assurant que l’on ne perd pas d’attaques. Nos méthodes sont conçues pour le cadre exigeant de la sécurité et sont prouvées correctes et complètes vis-à-vis de l’équivalence. Nous montrons comment elles peuvent s’intégrer naturellement dans les outils existants. Nous prouvons la correction de cette intégration dans un outil et proposons une implémentation complète. Finalement, nous mesurons le gain significatif en efficacité ainsi obtenu et nous en déduisons que nos méthodes permettent l’analyse d’un plus grand nombre de protocoles.Ensuite, pour résoudre le problème de précision dans le cas non-borné, nous proposons une nouvelle démarche qui consiste à assurer la vie privée via des conditions suffisantes. Nous définissons deux propriétés qui impliquent systématiquement la non-traçabilité et l’anonymat et qui sont facilement vérifiables via les outils existants (e.g. ProVerif). Nous avons implémenté un nouvel outil qui met en pratique cette méthode résolvant le problème de précision de l’état de l’art pour une large classe de protocoles. Cette nouvelle approche a permis les premières analyses de plusieurs protocoles industriels incluant des protocoles largement déployés, ainsi que la découverte de nouvelles attaques. / The information society we belong to heavily relies on secure information exchanges. To exchange information securely, one should use security protocols that specify how communicating agents should behave notably by using cryptographic primitives (e.g. encryption, signature). Given their ubiquitous and critical nature, we need to reach an extremely high level of confidence that they actually meet their goals. Those goals can be various and depend on the usage context but, more and more often, they include privacy properties (e.g. anonymity, unlinkability). Unfortunately, designed and deployed security protocols are often flawed and critical attacks are regularly disclosed, even on protocols of utmost importance, leading to the never-ending cycle between attack and fix.To break the present stalemate, we advocate the use of formal methods providing rigorous, mathematical frameworks and techniques to analyse security protocols. One such method allowing for a very high level of automation consists in analysing security protocols in the symbolic model and modelling privacy properties as equivalences between two systems. Unfortunately, deciding such equivalences is actually undecidable in the general case. To circumvent undecidability, two main approaches have emerged. First, for a bounded number of agents and sessions of the security protocol to analyse, it is possible to symbolically explore all possible executions yielding decision procedures for equivalence between systems. Second, for the general case, one can semi-decide the problem leveraging dedicated abstractions, notably relying on a strong form of equivalence (i.e. diff-equivalence).The two approaches, i.e. decision for the bounded case or semi-decision for the unbounded case, suffer from two different problems that significantly limit their practical impact. First, (symbolically) exploring all possible executions leads to the so-called states space explosion problem caused by the concurrency nature of security protocols. Concerning the unbounded case, diff-equivalence is actually too imprecise to meaningfully analyse some privacy properties such as unlinkability, nullifying methods and tools relying on it for such cases.In the present thesis, we address those two problems, going back and forth between theory and practice. Practical aspects motivate our work but our solutions actually take the form of theoretical developments. Moreover, we make the effort to confirm practical relevance of our solutions by putting them into practice (implementations) on real-world case studies (analysis of real-world security protocols).First, we have developed new partial order reduction techniques in order to dramatically reduce the number of states to explore without loosing any attack. We design them to be compatible with equivalence verification and such that they can be nicely integrated in frameworks on which existing procedures and tools are based. We formally prove the soundness of such an integration in a tool and provide a full implementation. We are thus able to provide benchmarks showing dramatic speedups brought by our techniques and conclude that more protocols can henceforth be analysed.Second, to solve the precision issue for the unbounded case, we propose a new methodology based on the idea to ensure privacy via sufficient conditions. We present two conditions that always imply unlinkability and anonymity that can be verified using existing tools (e.g. ProVerif). We implement a tool that puts this methodology into practice, hence solving the precision issue for a large class of protocols. This novel approach allows us to conduct the first formal analysis of some real-world protocols (some of them being widely deployed) and the discovery of novel attacks.

Cette thèse se situe dans le cadre de l'analyse symbolique des protocoles Les contributions sont représentées par l'obtention de résultats de décidabilité et de transfert dans les directions suivantes qui sont des thèmes majeurs en vérification des protocoles : - traitement des primitives cryptographiques : chiffrement CBC, signatures en aveugle; - propriétés de sécurité : secret fort, existence de cycles de clefs; - approches pour la sécurité : construction de protocoles sûrs. Ainsi, nous avons montré la décidabilité (d'une part) de l'existence de cycles de clefs et (d'autre part) du secret pour des protocoles utilisant le mode de chiffrement CBC ou des signatures en aveugle. Nous avons aussi transféré la sécurité des protocoles d'un cadre faible vers un cadre plus fort dans les sens suivants. D'une part, nous avons montré qu'une propriété de secret faible implique sous certaines hypothèses une propriété de secret plus forte. D'une autre part, nous avons construit des protocoles sûrs à partir de protocoles ayant des propriétés plus faibles. / This thesis is developed in the framework of the symbolic analysis of security protocols. The contributions are represented by decidability and transfer results in the following directions which are major topics in protocol verification: - treatment of the cryptographic primitives: CBC encryption, blind signatures; - security properties: strong secrecy, existence of key cycles; - approaches for protocol security: construction of the secure protocols. Thus, we showed the decidability (on the one hand) of the existence of key cycles for a bounded number of sessions using a generalized constraint system approach, and (on the other hand) of secrecy for protocols using the CBC encryption or blind signatures for an unbounded number of sessions by using a refined resolution strategy on a new fragment of Horn clauses. We also transferred protocol security from a weak framework towards a stronger framework in the following directions. On the one hand, we showed that a weak property of secrecy (i.e. reachability-based secrecy) implies under certain well-motivated assumptions a stronger secrecy property (i.e. equivalence-based secrecy). On the other hand, we built protocols secure against active adversaries considering an unbounded number of sessions, by transforming protocols which are secure in a non-adversarial setting.

L'établissement de la confiance est un problème qui se pose en permanence dans la vie quotidienne. Nous avons toujours besoin d'évaluer la confiance que l'on a en quelqu'un avant de décider d'entreprendre une action avec. Il s'agit bien évidemment d'une question très importante pour les applications de l'Internet où il est de plus en plus rare d'engager une transaction avec des personnes ou des entités que l'on connaîtrait au préalable. La confiance est un élément clé pour le développement et le bon fonctionnement des applications d'e-commerce et par extension de tous les services qui amènent à des interactions avec des inconnus.Le but de cette thèse est de proposer une infrastructure de gestion de la confiance qui permette à chaque participant d'exprimer sa propre politique de confiance ; politique qui guidera le comportement des applications qui fournissent ou qui permettent d'accéder à des services. Cette infrastructure met en œuvre des mécanismes de négociation qui vont permettre d'établir une confiance mutuelle entre les différents participants d'une transaction. Un des points importants de notre proposition est d'offrir un langage d'expression des politiques qui permet d'utiliser toutes les sources d'informations disponibles telles que les qualifications (credentials), la notion de réputation, de recommandation, de risque pour exprimersa politique de confiance.

L'établissement de la confiance est un problème qui se pose en permanence dans la vie quotidienne. Nous avons toujours besoin d'évaluer la confiance que l'on a en quelqu'un avant de décider d'entreprendre une action avec. Il s'agit bien évidemment d'une question très importante pour les applications de l'Internet où il est de plus en plus rare d'engager une transaction avec des personnes ou des entités que l'on connaîtrait au préalable. La confiance est un élément clé pour le développement et le bon fonctionnement des applications d’e-commerce et par extension de tous les services qui amènent à des interactions avec des inconnus.Le but de cette thèse est de proposer une infrastructure de gestion de la confiance qui permette à chaque participant d'exprimer sa propre politique de confiance ; politique qui guidera le comportement des applications qui fournissent ou qui permettent d'accéder à des services. Cette infrastructure met en œuvre des mécanismes de négociation qui vont permettre d'établir une confiance mutuelle entre les différents participants d'une transaction. Un des points importants de notre proposition est d'offrir un langage d'expression des politiques qui permet d'utiliser toutes les sources d'informations disponibles telles que les qualifications (credentials), la notion de réputation, de recommandation, de risque pour exprimersa politique de confiance. / Trust establishment is an important problem which often arises everyday. We need to assess the trust in someone or something before making decisions on their actions. It is also a very important problem for Internet applications where participants of a system are virtual entities. The trust establishment is a key factor for e-commerce applications and services which involve interactions with unknown users.The objective of this thesis is to build an infrastructure for trust management which allows each participant to express his own security policy. The security policy is a way for the participant to define his own access control to his own resources and services. The infrastructure provides a trust negotiation mechanism that allows two participants to establish a mutual trust between them for interactions.The important point of our proposal of an infrastructure for trust management is that we use all available information such as credentials (signed certificates), reputations, recommendations or risk information about the peer to make decisions on trust. All these factors are expressed in the security policy by using our proposed policy language.

Cette thèse se situe dans le cadre de l'analyse symbolique des protocoles Les contributions sont représentées par l'obtention de résultats de décidabilité et de transfert dans les directions suivantes qui sont des thèmes majeurs en vérification des protocoles :<ul><li>traitement des primitives cryptographiques : chiffrement CBC, signatures en aveugle;</li><li>propriétés de sécurité : secret fort, existence de cycles de clefs;</li><li>approches pour la sécurité : construction de protocoles sûrs.</li></ul>Ainsi, nous avons montré la décidabilité (d'une part) de l'existence de cycles de clefs et (d'autre part) du secret pour des protocoles utilisant le mode de chiffrement CBC ou des signatures en aveugle. Nous avons aussi transféré la sécurité des protocoles d'un cadre faible vers un cadre plus fort dans les sens suivants. D'une part, nous avons montré qu'une propriété de secret faible implique sous certaines hypothèses une propriété de secret plus forte. D'une autre part, nous avons construit des protocoles sûrs à partir de protocoles ayant des propriétés plus faibles.

L'Internet des Objets (IdO) permet à des milliards de dispositifs informatiques embarqués de se connecter les uns aux autres. Les objets concernés couvrent la plupart de nos appareils de la vie quotidienne, tels que les thermostats, les réfrigérateurs, les fours, les machines à laver et les téléviseurs. Il est facile d'imaginer l'ampleur du danger, si ces dispositifs venaient à nous espionner et révélaient nos données personnelles. La situation serait encore pire si les applications critiques IdO, par exemple, le système de contrôle des réacteurs nucléaires, le système de sécurité du véhicule ou les dispositifs médicaux, étaient compromis. Afin de garantir la sécurité et lutter contre des menaces de sécurité dans l'IdO, des solutions de sécurité robustes doivent être considérées. Cependant, les appareils pour l’IdO sont limités en mémoire, capacités de calcul et énergie, et disposent de moyens de communication peu fiables, ce qui les rend vulnérables à des attaques variées. Dans ce contexte, nous nous concentrons sur deux défis majeurs, à savoir des protocoles de sécurité légers en termes de calculs et d’infrastructure, et des mécanismes d'établissement de clés légers, les solutions existantes actuellement étant beaucoup trop coûteuses pour les dispositifs IdO. En réponse au premier défi, nous avons, d'une part, proposé ECKSS - un nouveau schéma de signcryption léger qui évite l'utilisation de PKI. Cette proposition permet de chiffrer et signer simultanément des messages en garantissant la confidentialité et la non-falsification du canal de communication. De plus, les échanges de message sont authentifiés sans recourir à des certificats. Par ailleurs, nous avons aussi proposé OEABE qui est un mécanisme de délégation pour le chiffrement à base d’attributs CP-ABE (Ciphertext-Policy Attribute-Based Encryption). CP-ABE est un schéma de chiffrement par attributs qui permet aux utilisateurs de préciser au moment du chiffrement qui pourra déchiffrer leurs données. Notre solution, OEABE, permet à un dispositif contraint en ressources de générer rapidement un chiffré CP-ABE tout en précisant les droits d’accès à ses données. Cette solution est d’autant plus utile que le volume de données générées par les dispositifs IdO est en augmentation exponentielle chaque année. Quant au deuxième défi, nous avons proposé tout d'abord deux modes de distribution de clés pour le protocole standard de gestion de clés MIKEY. Ils s’appuient sur notre schéma de signcryption ECKSS et héritent ainsi de la légèreté d'ECKSS à la fois en termes de calculs et de dispensent d'utilisation de PKI. Les résultats expérimentaux, obtenus à partir d’une plateforme de capteurs Openmote, ont prouvé l'efficacité de nos solutions comparativement aux autres méthodes de MIKEY. Nous avons aussi proposé un schéma d'échange de clés, appelé AKAPR qui est très adapté dans le cas où les deux parties qui participent à la négociation de clés sont très contraintes en ressources / The Internet of Things (IoT) enables billions of embedded computing devices to connect to each other. The smart things cover our everyday friendly devices, such as, thermostats, fridges, ovens, washing machines, and TV sets. It is easy to imagine how bad it would be, if these devices were spying on us and revealing our personal information. It would be even worse if critical IoT applications, for instance, the control system in nuclear reactors, the vehicle safety system or the connected medical devices in health-care, were compromised. To counteract these security threats in the IoT, robust security solutions must be considered. However, IoT devices are limited in terms of memory, computation and energy capacities, in addition to the lack of communication reliability. All these inconvenients make them vulnerable to various attacks, as they become the weakest links of our information system. In this context, we seek for effective security mechanisms in order to establish secure communications between unknown IoT devices, while taking into account the security requirements and the resource constraints of these devices. To do so, we focus on two major challenges, namely, lightweight security protocols in terms of processing and infrastructure and lightweight key establishment mechanisms, as existing solutions are too much resource consuming. To address this first challenge, we first propose ECKSS - a new lightweight signcryption scheme which does not rely on a PKI. This proposal enables to encrypt and sign messages simultaneously while ensuring the confidentiality and unforgeability of the communication channels. In addition, the message exchanges are authenticated without relying on certificates. Moreover, we also propose OEABE which is a delegation-based mechanism for the encryption of the Ciphertext-Policy Attribute-Based Encryption (CP-ABE). CP-ABE is anattribute-based public key encryption scheme that gives users the flexibility to determine who can decrypt their data at runtime. Our solution enables a resource-constrained device to generate rapidly a CP-ABE ciphertext with authorization access rights to its data. This solution is particularly useful as the volume of data issued from IoT devices grows exponentially every year. To solve the second challenge, we first propose two new key distribution modes for the standard key management protocol MIKEY, based on our signcryption scheme ECKSS. These modes inherit the lightness of ECKSS and avoid the use of PKI. The experimental results, conducted in the Openmote sensor platform, have proven the efficiency of our solutions compared with other existing methods of MIKEY. Then, we propose a new key agreement scheme, named AKAPR. In case the two communicating parties are involved in the key negotiation procedure, AKAPR is very suitable in the context of IoT. As such, it can operate even if the two communicating parties are highly resource-constrained