Brevet FR2763770A1 — publié le 19981127

PROCEDE DE ROUTAGE SECRET DE MESSAGES La présente invention concerne un procédé pour router des messages dans un réseau de communications, apte à préserver secrète l'adresse des utilisateurs du réseau. Avec la multiplication des réseaux de télécommunication, notamment du type sans fil, un nombre croissant de communications, au sens large, ont lieu en utilisant un terminal de télécommunications mobile, par exemple du type Groupe Special Mobile (GSM). Afin d'établir des communications, l'opérateur du réseau doit suivre en permanence la position du terminal mobile. Il15 existe donc dans les réseaux actuels, un fichier central situé auprès de l'opérateur du réseau, et contenant des informations sur la position instantanée de chacun des utilisateurs. Or dans certaines conditions, les communications électroniques doivent être effectuées d'une manière qui préserve la discrétion des émetteurs et/ou des récepteurs d'informations sur leur position, et sur le trajet suivi par les messages dans le réseau, afin notamment que le message ne puisse pas être intercepté et25 lu. Bien que ce besoin soit plus largement exprimé dans des environnements du type militaire, des besoins similaires peuvent également apparaître dans les communications civiles. Par exemple, comme les réseaux de communications mobiles, notamment cellulaires, sont30 sujets à des écoutes hostiles, il existe un besoin d'assurer les utilisateurs du caractère secret de leur adresse instantanée. Ce besoin de secret peut également être justifié au nom de la liberté de communiquer et de circuler sans être surveillé par une quelconque organisation. Or ce besoin de secret crée un problème technique nouveau, non résolu jusqu'à présent, qui consiste à assurer des communications, notamment à l'aide de terminaux mobiles, sans que ni la localisation de 5 l'utilisateur, ni le chemin suivi par les messages entre un émetteur et un récepteur en passant par une pluralité de noeuds de réseau, ne puisse être déterminé. Rappelons que dans l'état de la technique des communications, un problème voisin mais différent a déjà été abordé: il s'agit du problème d'anonymie, consistant à cacher l'identité réelle d'un utilisateur par rapport à des tentatives d'accès extérieur au réseau. Ce problème a par exemple déjà été abordé dans les articles suivants: D. Chaum, " Security without Identification: Transactions Systens to make Big Borther obsolete ", CACM Vol. 28, No. , Octobre 1985; D. Chaum, " The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability ", Journal of Cryptology, Vol. 1 No. 1, 1988. Mais les solutions à ce problème n'ont pas permis de résoudre le problème de la conservation du secret de la localisation d'un utilisateur de réseau mobile. L'invention a pour but de proposer un procédé de communication entre des émetteurs et des récepteurs de messages, qui permette d'assurer la confidentialité des messages et de leur trajet. L'invention s'applique en particulier, mais pas uniquement, à la préservation de la confidentialité de la position de postes émetteurs/récepteurs dans un réseau de communications mobiles. Bien que l'invention puisse être utilisée dans d'autres cadres, elle sera plus spécifiquement décrite 3 dans son application à un réseau de communications mobiles. Dans ce cas, le problème posé est de portée plus limitée, et consiste à empêcher un observateur de suivre le trajet et de capter les communications d'un 5 utilisateur de terminal de communication mobile. Le principe de l'invention est basé, de façon nouvelle, sur l'utilisation de la théorie des ensembles secrets. Etant donné un ensemble de noeuds de communication dans un réseau de communications, mobile ou10 non, un message émis par un émetteur donné vers un récepteur donné suit un trajet qui passe par une série de noeuds du réseau, appelée route. Cette route constitue donc un sous- ensemble de l'ensemble des noeuds du réseau. Le principe de la solution du problème posé consiste à15 former à partir de cette route un ensemble dit secret. La mise en oeuvre de la solution suppose que l'on sache construire un tel ensemble secret, et plusieurs méthodes à cet effet seront décrites plus loin. Rappelons les caractéristiques d'un ensemble secret. Un ensemble est dit secret si les conditions suivantes sont réalisées: (Cl): toute partie (qu'elle soit membre ou non de l'ensemble secret) peut vérifier son appartenance à l'ensemble secret;25 (C2): personne, à l'exception du créateur de l'ensemble secret, ne peut vérifier l'appartenance d'une autre partie à l'ensemble secret; (C3): personne, à l'exception du créateur de l'ensemble secret, ne peut déterminer avec certitude le nombre d'éléments dans l'ensemble secret (bien qu'une limite supérieure du nombre d'éléments puisse éventuellement être connue). En mettant en oeuvre la théorie des ensembles secrets dans le cadre pratique des communications dans un réseau, il est nécessaire de ne pas perdre de vue les objectifs de sécurité, qui sont tenus grâce au respect 4 des conditions Cl-C3 ci-dessus sur les ensembles secrets, et d'efficacité. Par efficacité, on entend la minimisation de la complexité spatiale et temporelle, à la fois pour construire un ensemble secret, et pour 5 vérifier l'appartenance d'un membre (un noeud du réseau) à l'ensemble secret. La qualité du procédé pourra être évaluée par rapport à la résistance qu'elle peut offrir en cas d'une attaque de la part d'un " adversaire ". Dans ce contexte,10 un adversaire est une entité ayant pour but d'attaquer le système d'une des manières suivantes: (A1): déterminer si une partie donnée est un membre d'un ensemble secret (la route secrète de communication), avec ou sans collusion avec d'autres15 membres de l'ensemble secret; (A2): déterminer le nombre de parties dans un ensemble secret. Dans ce contexte, l'invention concerne un procédé de routage de messages entre au moins un émetteur et au moins un récepteur, chaque message étant routé à travers un réseau de communication comportant un ensemble de noeuds de réseau U = {ST1,... STn}, caractérisé en ce qu'il comporte des étapes consistant à:25 a) pour chaque nouveau message à émettre, déterminer une route entre un émetteur et un récepteur, comportant un sous-ensemble de l'ensemble U des noeuds du réseau; b) construire un ensemble secret S = {STi,... STj...} constitué par les noeuds de ladite route; c) transmettre ledit message d'un noeud déterminé de la route à tous les noeuds adjacents du réseau, sauf le noeud de provenance; d) à chaque nouveau noeud de réseau STi recevant ledit message transmis, vérifier si ce noeud STi appartient à l'ensemble secret S, et dans l'affirmative, transmettre le message à tous les noeuds adjacents au noeud STi, à l'exception du noeud de provenance, et dans la négative, éliminer le message au noeud STi. Selon d'autres caractéristiques de l'invention, pour vérifier l'appartenance d'un noeud STm à l'ensemble secret des noeuds de la route, le procédé de routage comporte les étapes suivantes: a) attribuer à chaque noeud STi du réseau une clé publique PKi et une clé secrète Ski; b) choisir aléatoirement un entier n codé sur p bits, et constituer un bloc de chiffrement de 2p bits en concaténant n et (n+l), ce bloc de chiffrement étant noté txti = nln+l;15 c) calculer un codage SR de la route secrète S, selon l'expression suivante: SR = PK1(txt1),...,PKi(txti),...PKj(txtj),...PKn(tXtn), et transmettre SR avec le message à partir de l'émetteur; d) lors de la réception du message et de SR par un noeud STm, décrypter les composantes de SR pour retrouver le bloc de chiffrement txtm, et si txtm = nln+l, en déduire que le noeud STm appartient à la route secrète, et si txtm = nln, en déduire que le noeud STm n'appartient pas à la route secrète.25 Selon une autre variante du procédé, utilisant le théorème du reste chinois, le procédé comporte des étapes consistant à: a) pour chaque noeud STi, calculer une valeur yi telle que: yi = xi mod Pi (0 Ki ro= gbaqmodp, o b est choisi par la source Stsrc. b) on construit l'ensemble secret en calculant, pour chaque noeud STq appartenant à U, la valeur KrCq = gbaq, et on le représente par: SR = (x1,...,......,x) gbmodP c) pour vérifier si le noeud STi appartient à l'ensemble secret, on compare à ce noeud la valeur de xi avec la valeur MSB(Ksrci), o MSB(a) représente le bit de plus fort poids du codage binaire d'une valeur a donnée, et en cas d'égalité de la comparaison, alors le noeud STi appartient à l'ensemble S, sinon le noeud STi20 n'appartient pas à l'ensemble secret S. - de préférence, certains noeuds ne faisant pas partie de la route d'un message, retransmettent ce message malgré tout à certains noeuds en aval sur la route, de façon à augmenter la résistance à une25 observation non autorisée de la route suivie par le message. L'invention sera mieux comprise à la lecture de la description suivante faite à titre d'exemple non limitatif, et aux dessins ci-annexés, dans lesquels: - la figure 1 représente de façon schématique le trajet d'un message dans une architecture de réseau avec une pluralité de noeuds; On se réfère à la figure 1. On a représenté dans cette figure une pluralité de noeuds d'un réseau de communication. Les noeuds du réseau sont représentés de façon schématique par des rectangles. Un message est émis par un émetteur A, à destination d'un récepteur B. Le10 message est transmis par A à l'agent de B, noté HDA de B, qui le transmet à tous les noeuds (ST1, ST2, ST3) auxquels il est connecté. Les noeuds qui font partie de la route du message, à savoir ST2, ST4, et ST5, sont représentés en grisé. Chacun de ces noeuds transmet le15 message à tous les noeuds auxquels il est connecté, sauf le noeud qui lui a transmis le message. Par exemple, le noeud ST2 transmet le message aux noeuds ST4, ST3 et ST6. Seuls les noeuds qui font partie de la route du message retransmettent le message, les autres noeuds le20 détruisent. Ainsi, ST1 et ST3 qui reçoivent le message mais ne font pas partie de la route de celui-ci, ne le retransmettent pas. De préférence, pour augmenter la difficulté pour un observateur extérieur de retrouver la route utilisée, certains noeuds, comme ST3, qui ne font25 pas partie de la route du message, retransmettent celui- ci malgré tout, de sorte qu'il est plus difficile de suivre le trajet réel. A titre d'exemple non limitatif, on peut considérer que le réseau représenté en figure 1 fait partie d'un réseau de communication mobile, A et /ou B étant alors des terminaux mobiles. Dans une mise en oeuvre typique d'un réseau de communication entre terminaux mobiles, chaque utilisateur de terminal mobile est enregistré auprès d'un domaine d'appartenance, et chaque domaine35 comporte un agent de domaine d'appartenance, encore 8 appelé " Home Domain Agent " en terminologie anglo- saxonne, et noté HDA. La tâche de chaque HDA consiste de façon connue à garder un enregistrement de la position courante de chaque utilisateur de terminal mobile 5 enregistré dans son domaine. Lorsqu'un utilisateur de terminal mobile A appelle un autre utilisateur de terminal mobile B, l'appel de A atteint d'abord le HDA du domaine d'appartenance de B. Ensuite, l'appel de A arrive jusqu'à B sur la base de l'information de localisation10 fournie par le HDA du domaine de B. Afin que le HDA de B puisse conserver une information précise de la localisation de B, B doit informer le HDA de tous ses changements de position. Cette technique de gestion de la mobilité nécessite donc de facon inhérente une entité centrale qui maintient à jour l'information de localisation pour chaque utilisateur. Malgré son utilité comme mécanisme de gestion de réseau, elle constitue une menace potentielle pour le caractère privé et secret des déplacements et des20 communications entre individus. Ainsi, un historique complet du comportement de chaque utilisateur et de son utilisation du réseau, peut être obtenu à partir des enregistrements le concernant, par le HDA. De plus, cette menace est une faiblesse inhérente et jusqu'à présent25 incontournable de toutes les architectures existantes de réseaux de communication mobile bien connus (GSM, CDPD, DECT, Mobile IP, UPT, etc), puisque toutes ces architectures nécessitent une entité centrale similaire au HDA pour garder la trace de l'utilisateur d'un30 terminal mobile. Selon l'invention, le problème décrit plus haut est résolu par le fait que chaque HDA, dans le cas o le réseau en possède, gère un enregistrement à jour d'une information secrète de routage, en lieu et place de35 l'enregistrement de la localisation. L'information 9 secrète de routage est alors utilisée sensiblement de la même manière que l'enregistrement de localisation dans les systèmes existants. La différence essentielle entre l'information secrète de routage et l'enregistrement de 5 localisation des architectures existantes réside dans le fait que l'information secrète de routage ne donne aucune indication sur la position de l'utilisateur. Pour chaque nouvelle position de l'utilisateur d'un terminal mobile, l'information secrète de routage est calculée en utilisant un procédé faisant intervenir un ensemble secret, dans lequel les rôles des différentes entités sont définis comme suit: On désigne par U = {ST1,... STn} l'ensemble connu de tous les membres de l'ensemble secret, c'est-à- dire en l'occurence, l'ensemble connu de tous les noeuds de routage du réseau, par lesquels un message traversant le réseau pourrait passer. On désigne par STsrc l'entité générant l'information secrète de routage. Il peut s'agir soit de l'utilisateur du terminal mobile lui-même, soit d'un noeud de routage " fiable " qui soit le plus proche de la nouvelle position du terminal mobile. On désigne S = {STil,..., STim} c U, l'ensemble secret des noeuds du réseau traversés par un message donné. On désigne par PKj(données) et SKj(données) le résultat crypté d'une donnée, respectivement avec une clé publique et une clé secrète du noeud de rang j dans le réseau.30 Et on désigne par SR la représentation, c'est- à-dire le codage, de l'information secrète de routage, obtenu par l'intermédiaire d'une technique de génération d'ensembles secrets. Pour chaque utilisateur B et chaque nouvelle position de B, une nouvelle valeur de SR est calculée et placée dans le HDA de B, avec l'identification de B. A chaque fois qu'un autre utilisateur A cherche à 5 communiquer avec B, A contacte d'abord le HDA de B. Le message de A est alors annexé à la valeur courante de SR, et le message résultant est transmis à tous les noeuds adjacents au HDA de B dans le réseau. En utilisant un procédé d'ensemble secret du type de ceux qui seront décrits en détail plus loin, chaque noeud de routage détermine s'il est lui-même un membre de l'ensemble secret pour cette communication, c'est-à-dire s'il se trouve sur la route du message et s'il doit le transmettre plus loin. La transmission du15 message d'un noeud donné aux noeuds adjacents (à l'exception du noeud de provenance du message) ressemble initialement à une diffusion généralisée, mais très rapidement, l'effet de diffusion généralisée s'estompe puisque seuls les noeuds de la route réelle du message20 (c'est-à-dire les élements de l'ensemble secret) transmettent le message plus avant. Afin de créer de la confusion pour un observateur extérieur éventuel, et empêcher que la route réelle du message soit découverte, certains noeuds ne25 faisant pas partie de l'ensemble secret peuvent être utilisés pour faire un trajet supplémentaire du message, en parallèle avec la route réelle. De telles routes parallèles sont des leurres, puisqu'au bout il n'y a pas de nouvelle transmission du message. Ainsi, ces routes30 parallèles créent des traces qui disparaissent après quelques sauts élémentaires du message entre des noeuds ne faisant pas partie de la route secrète. Au contraire, seule la trace correspondant à la route réelle atteint en définitive le récepteur B.35 Dans l'exemple représenté en figure 1, la route réelle secrète est constituée par SR = {ST2, ST4, ST5}, 11 alors que les noeuds ST3 et ST7 constituent des noeuds leurres. Après le principe de la solution, basé sur l'utilisation d'un ensemble secret de noeuds constituant la route secrète du message, on va maintenant décrire trois exemples d'algorithmes de routage secrets basés sur la construction et l'utilisation d'un ensemble secret de noeuds. Bien entendu, il ne s'agit là que d'exemples de réalisation, d'autres modes de réalisation pouvant être10 envisagés sans sortir du champ de l'invention. Bien entendu, toutes les méthodes décrites ont en commun une étape de calcul d'appartenance d'un noeud à un ensemble secret. Méthode 1: une méthode simple: Selon cette méthode, on construit un ensemble secret S de noeuds du réseau par o passe un message entre un émetteur et un récepteur, puis on vérifie20 l'appartenance d'un noeud donné STm à l'ensemble secret des noeuds de la route ainsi définie. On attribue d'abord (a) au noeud STi possède une paire de clés: une clé publique PKi, et une clé secrète SKi. La représentation la plus simple d'un ensemble secret S à m éléments est: PKil(txtil),... PKim(txtim), o txtij (pour j compris entre 1 et m) représente une indication claire et univoque que le noeud STij est un membre de l'ensemble secret S. Par exemple, txtij peut être égal à Rj, une quantité aléatoire générée par un noeud source Stsrc. b) on choisit alors aléatoirement un entier n codé sur p bits, et on constitue un bloc de chiffrement de 2p bits en concaténant n et (n+l), ce bloc de chiffrement étant noté txti = nln+l;35 c) on calcule un codage SR de la route secrète S, selon l'expression suivante: SR = PK1(txtl),...,PKi(txti),...PKj(txtj),...PKn(txtn), et on transmet le codage SR avec le message à partir de l'émetteur; d) lors de la réception du message et de SR par un noeud STm, on décrypte les composantes de SR pour retrouver le bloc de chiffrement txtm, et si txtm = nln+l, on en déduit que le noeud STm appartient à la route secrète S, et si tXtm = njn, on en déduit que le noeud STm n'appartient pas à la route secrète.10 Un chiffrement de type PKi(txti) étant par exemple sur 512 bits, l'inconvénient de cette méthode simple réside dans la longueur du codage SR calculé, qui devient problématique lorsqu'il y a beaucoup de noeuds,15 par exemple plus de cent. Méthode 2: utilisation du théorème du reste chinois On rappelle que ce théorème stipule que: étant donnée une séquence de nombres premiers: Pi, p2,... Pn, et n valeurs yi = xi mod pi (0 valeur unique X telle que 0 Dans ce cas, on utilise le théorème du reste chinois pour construire l'ensemble secret S formant la route, puis pour vérifier l'appartenance d'un noeud donné à la route. A cet effet, le procédé comporte les étapes suivantes: a) pour chaque noeud STi, on calcule une valeur yi telle que: yi = xi mod Pi (0 le détruit. Méthode 3: utilisation de vecteurs de bits avec protocole d'échange de clef de Diffie-Hellman Selon cette méthode, chaque récepteur STq appartenant à l'ensemble U des noeuds du réseau doit pré- distribuer son exposant public calculé selon Diffie- Hellman: gaqmodP (o g désigne la base, aq est la clé secrète du noeud STq, et P est l'ordre de groupe). Les étapes sont alors les suivantes: a) chaque noeud STi calcule la clé partagée: Ki src= gbaqmodP, o b est choisi par la source Stsrc. b) on construit l'ensemble secret en calculant, pour chaque noeud STq appartenant à U, la valeur K.Cq = ba g baq, et on le représente par: SR = (xl,..., xi,...,xn) I gbmodP c) pour vérifier si le noeud STi appartient à l'ensemble secret, on compare à ce noeud la valeur de xi 14 avec la valeur MSB(Ksrci), o MSB(a) représente le bit de plus fort poids du codage binaire d'une valeur a donnée. En cas d'égalité de la comparaison, alors le noeud STi appartient à l'ensemble S, (donc il route le message), 5 sinon le noeud Sti n'appartient pas à l'ensemble S (et par conséquent le noeud élimine le message). Il résulte de ce qui précède que l'invention atteint ses objectifs, et permet de communiquer des messages à travers un réseau, notamment de communications10 mobiles entre un émetteur et un récepteur, tout en garantissant que l'utilisateur du terminal ne peut pas être localisé, ni ses communications surveillées. REVENDICATIONS 1. Procédé de routage de messages entre au moins un émetteur et au moins un récepteur, chaque message étant routé à travers un réseau de communication comportant une pluralité de noeuds de réseau U = {ST1,... STn}, caractérisé en ce qu'il comporte des étapes consistant à: a) pour chaque nouveau message à émettre, déterminer une route entre un émetteur et un récepteur, comportant un sous-ensemble de l'ensemble U des noeuds du réseau; b) construire un ensemble secret S = {STi,... STj...} constitué par les noeuds de ladite route; c) transmettre ledit message d'un noeud déterminé de la route à tous les noeuds adjacents du réseau, sauf le noeud de provenance; d) à chaque nouveau noeud de réseau STi recevant ledit message transmis, vérifier si ce noeud STi appartient à l'ensemble secret S, et dans l'affirmative, transmettre le message à tous les noeuds adjacents au noeud STi, à l'exception du noeud de provenance, et dans la négative, éliminer le message au noeud Sti.25 2. Procédé de routage de messages selon la revendication 1, caractérisé en ce que pour vérifier l'appartenance d'un noeud STm à l'ensemble secret des noeuds de la route, il comporte les étapes suivantes:30 a) attribuer à chaque noeud ST du réseau une clé publique PKi et une clé secrète Ski; b) choisir aléatoirement un entier n codé sur p bits, et constituer un bloc de chiffrement de 2p bits en concaténant n et (n+l), ce bloc de chiffrement étant noté35 txti = nln+l; c) calculer un codage SR de la route secrète S, selon l'expression suivante: SR = PKl(txtl),...,PKi(txti),...PKj(txtj),... PKn(txtn), et transmettre SR avec le message à partir de l'émetteur; 5 d) lors de la réception du message et de SR par un noeud STm, décrypter les composantes de SR pour retrouver le bloc de chiffrement txtm, et si txtm = nln+l, en déduire que le noeud STm appartient à la route secrète, et si txtm = nln, en déduire que le noeud STm10 n'appartient pas à la route secrète. 3. Procédé de routage de messages selon la revendication 1, caractérisé en ce que pour vérifier l'appartenance d'un noeud STq à l'ensemble secret des15 noeuds de la route secrète, il comporte les étapes suivantes: a) pour chaque noeud STi, calculer une valeur yi telle que: Yi = xi mod Pi (O le détruit. 4. Procédé de routage de messages selon la revendication 1, caractérisé en ce que pour vérifier l'appartenance d'un noeud STn à l'ensemble secret des noeuds de la route secrète, il comporte les étapes suivantes:35 a) chaque noeud STi calcule la clé partagée: 17 Ki src= gbaqmodP, o b est choisi par la source Stsrc. b) on construit l'ensemble secret en calculant, pour chaque noeud STq appartenant à U, la valeur KSCq = gbaq, et on le représente par: SR = (xl,..., xi,...,xn) I gbmodP c) pour vérifier si le noeud STi appartient à l'ensemble secret, on compare à ce noeud la valeur de xi avec la valeur MSB(K=rci), o MSB(a) représente le bit de plus fort poids du codage binaire d'une valeur a donnée, et en cas d'égalité de la comparaison, alors le noeud STi appartient à l'ensemble S, sinon le noeud ST1 n'appartient pas à l'ensemble secret S. 5. Procédé de routage de messages selon l'une quelconque des revendications précédentes, caractérisé en ce que certains noeuds ne faisant pas partie de la route d'un message, retransmettent ce message malgré tout à certains noeuds en aval sur la route, de façon à augmenter la résistance à une observation non autorisée20 de la route suivie par le message.