Solutions basées sur la diffusion avec adressage implicite 

Télécharger le fichier pdf d’un mémoire de fin d’études

Organisation des relais

Le relais isolé

Dans certains cas [ANZ, Hel95], un unique relais (voir figure 1.4) propose ses ser-vices pour les clients qui veulent communiquer anonymement. Si l’on veut juste établir une connexion unique et qu’on souhaite se protéger d’un attaquant local ou du serveur sur lequel on se connecte, un tel relais offre un anonymat suffi-sant et peut se révéler utile. Cependant, un ffeort de recherche important est fait dans l’étude des systèmes utilisant plusieurs relais. En ffeet ces systèmes peuvent fournir un anonymat de communication de telle sorte que les informations de tra-çage ne soient pas accessibles à un unique relais, qui pourrait les journaliser et les divulguer sans le consentement de l’utilisateur.
On peut remarquer que dans le cas où une seule entreprise contrôle un ensemble de relais, l’utilisation de plusieurs de ses relais successivement dans une même com-munication rend les attaques extérieures plus difficiles, mais présente un risque important de collusion entre les relais, ce pourquoi nous assimilons cette approche à celle d’un relais unique.

Les cascades

Les relais peuvent s’organiser en cascades (voir figure 1.5), ou chaînes de relais fixées au préalable. Ainsi certains systèmes proposent aux utilisateurs d’utiliser de telles cascades de relais (on peut choisir parmi plusieurs cascades mais pour une cascade les relais sont fixes), chaque relais étant géré par une entité ffdiérente (en général une entreprise ou une organisation pour la protection de la vie privée). Nous décrirons plus longuement l’un de ces systèmes dans la section 1.3.5.

Les réseaux de relais

On dit que des relais forment un réseau (voir figure 1.6) quand les chaînes de relais ne sont pas fixées au préalable comme dans le cas des cascades. Si le choix d’un relais en amont limite le choix des relais suivants on dit qu’il s’agit d’un réseau de relais à routage restreint [RR98, FM02]. Si le choix d’un relais ne limite en rien le choix des relais ultérieurs on dit que le réseau est à routage libre [DMS04, GRS99].
L’organisation des relais est une caractéristique importante d’un système visant à protéger l’anonymat de communication. Cependant, le relais étant l’élément de base du protocole, c’est son comportement qui va le plus fortement déterminer le type de protocole utilisé. Nous présentons dans ce qui suit deux exemples de relais qui sont utilisés de nos jours dans des systèmes réels fournissant un anonymat de communication.

Les MIX

Les premiers relais utilisés pour l’anonymat de communication furent décrits par David Chaum en 1981 [Cha81]. Ces relais, qu’il appela MIX, opèrent de la façon suivante :
– ils n’acceptent que des messages de taille fixe ;
– ils déchiffrent les messages entrants avec leur clé privée ;
– ils attendent d’avoir reçu un certain nombre de messages ;
– puis réordonnent les messages avant de les réémettre.
L’objectif est de fournir un anonymat relationnel entre le groupe des utilisateurs émetteurs d’un message, et le groupe des utilisateurs récepteurs d’un message vis-à-vis d’un attaquant qui observerait tous les messages arrivant et sortant du MIX.
Si nous reprenons l’exemple du service d’envoi de lettres fourni par Alice dans la section précédente (exemple 1.2), nous disons qu’Alice se comporte comme un MIX si elle n’accepte de rendre son service que pour des lettres comportant un nombre fixe de pages, attend d’avoir un certain nombre de lettres avant de les envoyer, et elle les mélange aléatoirement avant d’aller les poster. Un attaquant n’a plus aucun moyen de faire le lien entre les messages entrants et sortants, et du coup ne peut faire le lien entre un émetteur et un récepteur (voir figure 1.7).

Fonctionnement d’un MIX

Quand un utilisateur A veut envoyer un message M à un utilisateur E, il ajoute l’adresse de E au message et chiffre le tout avec KMI X la clé publique du MIX. On note ce message chiffréKMI X (RA, M, E), RA étant unnonce6.
Quand le MIX reçoit le message chi ffré, il le déchiffre avec sa clé privée, élimine le nonce RA, et met en attente le résultatM, E. Quand le MIX a mis en attente un nombre donné de messages il les envoie dans un ordre aléatoire aux adresses de destination. La figure 1.8 illustre ces opérations. S’il y a peu de trafic, les délais introduits par un MIX de ce type peuvent être excessifs. Pour diminuer les délais de transit, de faux messages peuvent être en-voyés au MIX, voire insérés par le MIX lui-même pour assurer que les tampons se remplissent assez fréquemment.
En supposant que tous les utilisateurs envoient des messages de même taille, le MIX décrit ci-dessus fournit un anonymat relationnel vis-à-vis d’un attaquant passif qui pourrait observer tous les liens (observateur global). Cependant des at-taques actives sont toujours possibles, et nous décrivons dans les sections 1.3.3.3 et 1.3.3.4 deux des plus connues.

Utilisation de plusieurs MIX

Quand un utilisateur veut utiliser plusieurs MIX les uns après les autres il va ap-pliquer plusieurs couches de chiffrement pour qu’elles soient traitées et retirées à raison d’une par MIX utilisé. Par exemple, un utilisateurA qui veut envoyer un message M à un utilisateur U va chiffrer une première fois le message pour le MIX le plus proche du destinataire, qu’on nomme MI X2 et obtenir KMI X2(RA, M, U). Il va ensuite re-chiffrer ce message à l’intention d’un autre MIX, MI X1 précédant MI X2 dans le chemin de A à U, pour obtenir : KMIX1(RA0 , KMIX2(RA, M, U), MIX2)
Ces MIX peuvent être organisés en cascades (voir figure 1.5) ou en réseau (voir figure 1.6). La figure 1.9 illustre l’exemple donné ci-dessus pour deux MIX en cascade .

Attaque par rejeu

On peut remarquer que le MIX opère de façon déterministe, et donc que si un message entrant X produit un message sortant Y vers un utilisateur U, toute nou-velle réception du messageX provoquera la réémission du même message sortant Y vers l’utilisateur U. Un attaquant peut donc tenter d’envoyer à un MIX un dou-blon d’un message entrant précédent (c’est-à-dire rejouer un message) pour repé-rer les doublons en sortie (voir figure 1.10). Pour cette raison les MIX surveillent l’arrivée de doublons et les éliminent le cas échéant.

Attaque par inondation

Si un MIX attend d’avoir reçu n messages avant de les réémettre, un attaquant peut envoyer n − 1 messages puis analyser la sortie où il peut repérer le message qui n’est pas parmi les siens. Bien sûr cette attaque n’a pas besoin d’être poussée jusqu’aux n − 1 messages, il suffit qu’un attaquant envoie αα−1 × n messages pour réduire la taille des groupes anonymes d’un facteurα.
Pour ce type d’attaques comme pour d’autres, diverses parades ont été élaborées. Pour une présentation plus détaillée des MIX récents, le lecteur est invité à consul-ter l’étude présentée dans [DP04].

Utilisation du nonce

Deux raisons font que l’utilisation de le nonce est indispensable. La première est que si on n’utilise pas le nonce RA, un attaquant pourrait reconstruire KMI X (M, E) à partir du message sortant M et de l’adresse du destinataire E (incluse dans l’en-tête du paquet sortant). Ceci lui permettrait de faire le lien entre le message entrant et le message sortant et donc entre l’émetteur et le destinataire. La deuxième raison est que si RA est différent deRA0 on a : KMIX (RA, M, E) , KMIX (RA0 , M, E) et donc les nonces permettent aux utilisateurs d’envoyer plusieurs fois le même message au même destinataire sans pour autant créer des doublons. Pour détecter les doublons, il suffit que le MIX conserve une table des nonces déjà reçus.
En pratique les nonce sont souvent formés de quelques bits aléatoires plus une estampille permettant de rejeter automatiquement les messages trop vieux et de ne maintenir qu’une liste de nonces récents.

Les Onion Routers

En 1997, des chercheurs du NRL8 ont proposé l’utilisation d’un réseau de relais à routage libre (voir figure 1.6). Ces relais sont en fait des MIX que les auteurs nomment Onion Routers (ORs). Ils maintiennent des connexions chiffrées per-manentes entre eux au sein desquelles ils multiplexent les connexions des utilisa-teurs, et pour éviter l’analyse du trafic à l’intérieur de ces connexions ils utilisent du bourrage chiffré (cf. 1.5.2).
Lors de l’établissement d’une connexion le premier relais, qui est appelé l’Onion Proxy (OP), envoie un paquet le long d’une route qu’il choisit librement parmi les autres relais du réseau. La présence de multiples couches de chiffrement dans ce paquet sont à l’origine du terme oignon le désignant. L’oignon, illustré dans la figure 1.11, est créé par l’OP en ajoutant une couche de chiffrement9 et un message pour chacun des ORs du chemin choisit par l’OP. Chacun des messages contient des informations pour l’établissement d’un canal permanent, et des clés de chiffrement symétrique. Une fois le canal formé le long de la route choisie, toutes les informations entre l’émetteur et le récepteur circulent à travers le canal ainsi créé avec une couche de chiffrement symétrique pour chaque OR traversé.
Pendant quelques années les auteurs ont proposé de façon expérimentale un petit réseau composé de quelques relais, tous exécutés au sein d’une même machine. Actuellement une deuxième génération dénommée Tor [DMS04] est proposée, avec un nombre de différences important.
Premièrement, les OR ne sont plus des MIX. Le réordonnancement des messages à été abandonné dans le but de diminuer le plus possible la latence introduite par le système, ainsi que le bourrage qui a été considéré comme trop coûteux [ADS03].

Attaques par corrélation

Corrélation au sein d’une communication

Les groupes anonymes évoluent dans le temps, et ceci peut avoir un impact im-portant lorsque plusieurs messages sont associables entre eux. Par exemple deux messages appartenant à une même connexion TCP sortant d’un réseau local ont certainement été émis par le même utilisateur. Un attaquant saura que l’émet-teur de ces deux messages est dans l’intersection du groupe anonyme d’émission du premier message et du groupe anonyme d’émission du deuxième message. Si ces groupes sont différents ceci résultera dans une diminution de l’anonymat de l’émetteur. Dans le cas des communications (même unidirectionnelles), des me-sures précises peuvent mener à une perte totale de l’anonymat comme le montre la figure 1.14. Dans cet exemple cinq utilisateurs A, B, C, D, et E se servent d’un MIX pour obtenir des pages Web. Une simple observation ne suffit pas à savoir quel utilisateur parmi A, B, et C à demandé quelle page lors du premier tour. Lors du tour suivant, deux utilisateurs B et C n’envoient pas de message en laissant leur place aux utilisateurs D et E. En corrélant les informations sur les messages de chacun de ces deux tours (ici le destinataire des messages), un attaquant va pouvoir réaliser des intersections entre les groupes anonymes d’émission. Étant donné le grand nombre de sites Web existant et le fait qu’en général un utilisateur réalise plusieurs requêtes au même site, l’attaquant va pouvoir déduire queAest probablement à l’origine des requêtes envoyées au site du LAAS.
Notons que dans cet exemple, deux choses rendent possible l’attaque. La pre-mière est que l’attaquant peut associer deux requêtes envoyées au LAAS comme des requêtes appartenant à une même communication. Dans de nombreux cas l’in-terlocuteur interpellé utilise des protocoles non-anonymisés (par exemple lors de la navigation HTTP), et l’ensemble des messages d’une communication peuvent être associés par n’importe quel attaquant. On supposera que c’est le cas dans le reste de ce mémoire, d’autant plus qu’il est possible d’associer des messages en se basant sur d’autres paramètres comme leur taille, le destinataire, la date d’émis-sion, etc. La deuxième chose rendant possible cette attaque est que l’attaquant est capable de savoir quand un utilisateur émet.
Dans un système possédant des groupes anonymes d’émission il y a deux types d’utilisateurs : les émetteurs et les utilisateurs n’émettant pas. Dans un système possédant des groupes d’émission non-observable un attaquant ne peut pas distin-guer entre les émetteurs et les utilisateurs n’émettant pas. Ainsi, les intersections devront être réalisées sur l’ensemble des utilisateurs connectés (iciA,{B, C, D, E} pour les deux tours), groupe qui est en général beaucoup moins changeant que les groupes anonymes d’émission (ici {A, B, C} le premier tour et {A, D, E} le deuxième), voire pas du tout.
Si un attaquant sait que certains messages sont plus probablement liés aux clients qui sont devenus membres du groupe non-observable récemment, par exemple parce que les clients ne se connectent au FAC que peu de temps avant de démarrer une communication, il pourra réaliser des attaques analogues à celle décrite ci-dessus. Même si ces attaques sont beaucoup moins ffiecaces que dans l’exemple, il est préférable, afin de réduire au maximum les informations qu’un attaquant peut tirer de telles attaques, que les utilisateurs essayent au maximum de décorréler la connexion au FAC et le début de leurs émissions (par exemple en se connectant tous les matins à la même heure, en attendant un délai variable après la connexion au FAC avant de démarrer une communication, etc.).
De la même façon, face à une telle attaque, un groupe anonyme de réception of-frira peu ou pas de protection dans le cadre des communications, et les utilisateurs ont intérêt à ce que leur intégration dans un groupe de réception non-observable et les réceptions des premières communications soient aussi décorrélées que pos-sible. La réception de communications par un utilisateur étant un acte en général involontaire ceci peut présenter des difficultés. Ce problème n’a pas de solution générale et devra être traité au cas par cas lors de l’implémentation d’une solution proposant de l’anonymat de communication.

Corrélation des émissions et réceptions

Dans le cadre des communications bidirectionnelles, les systèmes ne fournissant pas en même temps une non-observabilité d’émission et de réception sont vulné-rables à la corrélation des données qu’un attaquant peut recueillir sur les émissions ou les réceptions. L’exemple suivant illustre ceci.
Soit un FAC tel que les utilisateurs émettant forment un groupe anonyme d’émis-sion et qu’un groupe fixe d’utilisateurs (par exemple les utilisateurs d’un réseau local) forment un groupe de réception non-observable. À un instant donné, un utilisateur se met à émettre en utilisant le FAC. Un attaquant peut (sans rien ap-prendre sur le destinataire), enregistrer l’identité de l’émetteur, le moment où il a commencé à émettre et le moment où il finit d’émettre. Si l’attaquant observe qu’un deuxième utilisateur commence à émettre peu de temps après le premier, et finit en même temps ses émissions, il peut en déduire que probablement ces deux utilisateurs ont communiqué entre eux, brisant l’anonymat relationnel ainsi que la non-observabilité de réception.
De façon similaire, un FAC donnant lieu à un groupe non-observable en émission fixe et à un groupe anonyme en réception variable pourrait subir la même attaque par corrélation des réceptions de messages.
Soit A un attaquant. Soit G1 le groupe d’émission non-observable d’un utilisateur U vis-à-vis de A, et G2 son groupe de réception non-observable vis-à-vis de ce même attaquant. SiA réalise des corrélations entre les émissions et les réceptions des membres de G1 et de G2, les groupes d’émission non-observable et de récep-tion non-observable de U se voient réduits à un même groupe qu’on appelle le groupe non-observable de communication ou (par abus de langage) groupe ano-nyme de communication qui est l’intersection de G1 et G2.

Les attaques par intersection

Les attaques présentés dans les sections 1.4.1 et 1.4.2 sont basées sur des corréla-tions à court terme. Quand les corrélations se font sur des analyses à long terme on parle d’attaques par intersection. Le cas le plus communément utilisé pour illus-trer ces attaques est celui d’un attaquant qui observe comment le comportement d’un système change pendant les périodes de connexion d’un utilisateur donné. Deux modèles d’attaquants sont classiques dans ce cadre : l’observateur global, et l’attaquant suspicieux.
Associer les occurrences d’événements avec la présence d’un utilisateur est une attaque puissante contre laquelle il est difficile de se protéger. Deux solutions sont possibles. La première est que le FAC soit distribué sur l’ensemble de l’Internet de façon à réduire au minimum le nombre d’attaquants qui pourraient observer le système d’un point de vue global. La deuxième est de disposer de FACs associés à des groupes d’utilisateurs stables de telle façon que les intersections seront peu efficaces. Ces deux alternatives et leurs avantages respectifs sont discutés dans la section 1.6.

Primitives pour la non-observabilité

Comme expliqué dans la section précédente, il est important que les utilisateurs puissent recevoir et émettre des messages de façon non-observable. Il n’existe dans la littérature qu’une seule primitive permettant de garantir la non-observabilité en réception : c’est la diffusion. En revanche, il existe deux primitives permettant la non-observabilité en émission : le bourrage chiffré et l’envoi superposé.

La diffusion

L’envoi de messages que tout le monde reçoit (ou peut recevoir) et qui n’est in-terprétable que par le destinataire est un moyen classique pour assurer la nonobservabilité en réception (voir figure 1.15).
En informatique, la diffusion permet d’envoyer un message à toutes les adresses d’un réseau ou d’un sous-réseau. Son utilisation est cependant contraignante puis-que les liens de nombreux utilisateurs se voient encombrés, et même si on peut diffuser au delà d’un réseau local par l’utilisation de réseaux privés virtuels, il est impossible de diffuser des messages à très grande échelle (par exemple, sur l’ensemble de l’Internet). Nous proposons dans le deuxième chapitre de ce mé-moire un système fournissant un service d’anonymat de communication, dérivé des protocoles à di ffusion et avec un impact limité sur la charge réseau.

Table des matières

Introduction générale
1 Problématique et état de l’art 
1.1 L’analyse du trafic
1.2 Les communications anonymes
1.2.1 Notions de base
1.2.1.1 Définitions
1.2.1.2 Remarques
1.2.2 Propriétés d’anonymat
1.2.3 Modèles d’attaquant
1.3 Les relais
1.3.1 Utilisation d’un relais
1.3.2 Organisation des relais
1.3.2.1 Le relais isolé
1.3.2.2 Les cascades
1.3.2.3 Les réseaux de relais
1.3.3 Les MIX
1.3.3.1 Fonctionnement d’un MIX
1.3.3.2 Utilisation de plusieurs MIX
1.3.3.3 Attaque par rejeu
1.3.3.4 Attaque par inondation
1.3.3.5 Utilisation du nonce
1.3.4 Les Onion Routers
1.3.5 État de l’art
1.4 Attaques par corrélation
1.4.1 Corrélation au sein d’une communication
1.4.2 Corrélation des émissions et réceptions
1.4.3 Les attaques par intersection
1.5 Primitives pour la non-observabilité
1.5.1 La diffusion
1.5.1.1 Les adresses implicites
1.5.1.2 Utilisation d’un panneau d’affichage
1.5.2 L’utilisation de bourrage chiffré
1.5.3 L’envoi superposé
1.5.3.1 Principe
1.5.3.2 Justification informelle de la non-observabilité en émission
1.5.3.3 État de l’art
1.5.3.4 Pratique
1.6 Problématique de notre étude
1.6.1 Taille des groupes anonymes
1.6.2 Les groupes ouverts et les groupes fermés
1.6.3 L’Internet et les réseaux locaux
1.6.4 Cadre de travail
1.6.4.1 Modèles d’attaquant
1.6.4.2 Approches possibles
1.6.4.3 Utilisation de serveurs
2 Solutions basées sur la diffusion avec adressage implicite 
2.1 Évaluation des performances d’un EBBS
2.1.1 Utilisation de tours d’appel
2.1.2 Performances
2.2 Serveurs DC-net
2.2.1 L’implémentation d’un serveur DC-net
2.2.1.1 Les clients
2.2.1.2 Le serveur
2.2.2 Protocoles non implémentés
2.2.2.1 La réservation de canaux
2.2.2.2 La réception superposée
2.2.2.3 Occulter le nombre de communications
2.2.3 Les tests réalisés
2.2.3.1 La grappe
2.2.3.2 Le réseau
2.2.3.3 Mesures sur l’Internet
2.2.3.4 Utilisation de mandataires
2.3 Conclusions
3 Le PIR 
3.1 Notions de base
3.2 PIR parfaitement sûr
3.3 PIR sur des bases de données non-répliquées
3.4 Évolution des protocoles PIR
3.5 Comparaison des performances
3.6 Conclusions
4 Le pMIX et ses variantes 
4.1 Le pMIX
4.1.1 De l’EBBS au pMIX
4.1.1.1 Utilisation
4.1.1.2 Anonymat de communication
4.1.1.3 Réduction du nombre de requêtes PIR
4.1.1.4 Version finale
4.1.1.5 Attaques actives des administrateurs
4.1.2 Performances
4.1.2.1 Bande passante utilisable et taille des groupes non-observables
4.1.2.2 Coût des communications
4.1.2.3 Exemple
4.1.2.4 Évaluation
4.2 Les variantes du pMIX
4.2.1 Le apMIX
4.2.1.1 Principe
4.2.1.2 Performances
4.2.2 Les serveurs pDC-net et apDC-net
4.2.2.1 Principe
4.2.2.2 Performances
4.3 Vue globale
Conclusion générale 
A Analyse formelle des protocoles PIR basés sur des systèmes de chiffrement homomorphiques
A.1 Définitions
A.1.1 Systèmes de chiffrement
A.1.2 La récupération d’informations calculatoirement privée
A.1.3 Systèmes de chiffrement homomorphiques
A.2 Protocoles PIR homomorphiques à une dimension
A.3 Protocoles PIR homomorphiques à plusieurs dimensions
A.3.1 Cas à deux dimensions
A.3.2 Cas général
Bibliographie 

Télécharger le rapport complet