Brevet FR2899748A1 — publié le 20071012

SCHEMA DE DIFFUSION HYBRIDE EFFICACE, ADAPTE A UNE FAIBLE BANDE PASSANTE La présente invention concerne notamment un procédé pour diffuser des données à différents utilisateurs enregistrés de façon telle que seuls les utilisateurs autorisés puissent accéder aux informations. Les utilisateurs autorisés ou non peuvent changer à chaque session. Le procédé concerne de manière générale un service de diffusion 10 de données pour des systèmes à faible bande passante. II existe à l'heure actuelle différents schémas de diffusion dénommés BES (de l'anglais Broadcast Encryption Scheme ) permettant de diffuser des données de manière fiable. Le principe d'un BES est le 15 suivant. Chaque utilisateur u possède un ensemble spécifique I(u) contenant plusieurs clés de chiffrement dénommées KEKs (de l'anglais Key Encryption Keys ). A chaque session, les données sont chiffrées avec une clé de session , et la clé de session (et éventuellement de nouvelles clés KEKs) est chiffrée avec des clés KEKs telles que, chaque utilisateur autorisé connaît au 20 moins une des clés utilisées et les utilisateurs non autorisés ou déniés ne connaissent aucune des clés utilisées. Le choix de la méthode de diffusion BES détermine les clés KEKs, leur structure, les possibilités de renouvellement et le choix des clés KEKs utilisées pour le chiffrement pour une session donnée. 25 Trouver un chiffrement réellement efficace lorsque la donnée est transmise par un média à très faible largeur de bande et lorsqu'il y a plusieurs dénis possibles est un problème. Le choix du schéma de diffusion BES peut être critique, par exemple, si la donnée est émise par des satellites. L'art antérieur divulgue plusieurs schémas de chiffrement pour la diffusion des données, en particulier deux grands types de schémas, les schémas stateless et les schémas stateful décrits ci-après. Dans un schéma stateless , toutes les clés de chiffrement KEKs sont distribuées lors de l'initialisation du système. Les clés KEKs sont ensuite statiques pendant toute la durée de vie du système et aucune autre clé n'est ajoutée. Seule la clé de session peut être changée. Cela signifie que, lorsqu'un utilisateur perd la connexion ou que pour d'autres raisons, il manque des paquets de données utilisant des clés KEKs, il ne pourra déchiffrer le contenu utile du message (ne connaissant pas la clé de session en cours), mais, dès qu'il aura accès aux prochains paquets utilisant des clés KEKs, il pourra récupérer les futures clés de la session sans effort supplémentaire. Dans un schéma stateful , les clés de chiffrement KEKs peuvent être mises à jour ou additionnées grâce à des messages de gestion des clés. Cela signifie que, si l'utilisateur manque les paquets de gestion des clés, il peut être impossible pour lui de déchiffrer les clés de session suivantes. Une perte de paquets de données par les utilisateurs étant possible, un schéma stateful doit être complété avec un mécanisme de récupération des paquets. En général, un schéma stateful peut toujours être transformé en un schéma stateless en incluant tous les messages précédents dans chaque nouveau message. Caractéristique : Avantage Principaux Chaque session est-elle principal Inconvénients indépendante de l'état de la session précédente ? Schéma OUI Un utilisateur La taille du stateless Chaque session contient Peut être message toutes les informations du déconnecté augmente toutes les informations du d'une station potentiellement à passé sans perdre chaque session (utilisateurs déniés, l'information utile nouveaux utilisateurs .) pour la prochaine session Schéma NON. La taille du Si un utilisateur Stateful Chaque session contient message est déconnecté seulement l'information n'augmente pas pendant une utile qui est nouvelle par a priori d'une session il peut rapport au passé session à la perdre session suivante l'information utile pour les sessions futures Les articles les plus récents relatifs au schéma de diffusion BES utilisent deux types principaux de structure de clés de chiffrement KEKs. KEKs structure N 1: La première structure de clé de chiffrement est un simple arbre hiérarchique. Les utilisateurs sont représentés par des feuilles d'un arbre T. Cet arbre n'est pas nécessairement binaire ni équilibré. A chaque noeud v; de l'arbre est associée une clé k;. Les feuilles sont considérées comme des noeuds particuliers. Les clés k; sont des clés KEKs utilisées dans un BES. Lors de l'initialisation, chaque utilisateur u (c'est-à-dire chaque feuille u) reçoit le jeu de toutes les clés k; correspondant aux noeuds v; appartenant au plus court chemin entre la racine de T et la feuille u. Ainsi la clé k; est distribuée à chaque feuille du sous-arbre Si dont la racine est le noeud v; et seulement à ces feuilles. Toute donnée chiffrée avec la clé k; est destinée aux feuilles de Si et seulement à ces feuilles. On note ko la clé racine (c'est-à-dire la clé associée à la racine vo de l'arbre T) et {k; } l'ensemble de toutes les clés k;...DTD: KEKs structure N 2: La seconde structure de clé de chiffrement KEKs est aussi basée sur un arbre hiérarchique T tel que, chaque utilisateur est représenté par une feuille d'arbre. L'arbre est binaire et une clé k;,1 est associée à une différence de sous ensembles 5;,j = Si - Sj de façon telle que, le sous arbre Si contient le sous-arbre Si. Chaque clé k;,j est distribuée pour chaque feuille appartenant au sous-ensemble S;,j,(c'est-à-dire appartenant à si mais pas à Si) et cette clé est utilisée pour chiffrer toute donnée destinée à tous les utilisateurs appartenant à Sj et seulement à eux. Une clé ko,__ est associée à l'ensemble de l'arbre T et donnée à chacun des utilisateurs. On note {k;,j } l'ensemble de toutes les clés kid incluant la clé ko,__. De nombreuses méthodes de diffusion BES, stateful ou stateless , utilisent la structure KEKs N 1, comme, par exemple, la méthode CS décrite dans la référence [3] ou LKH décrite dans l'une des références [6], [5], [4-RFC-2627]. Plusieurs méthodes stateless BES efficaces utilisent la structure KEKs N 2, comme la méthode de différence de sous-ensembles SD donnée dans [3] ou des schémas dérivés de SD. L'état de l'art montre que la structure de clé N 1 est adaptée au 25 schéma stateful BESs alors que la structure N 2 est mieux adaptée au schéma stateless BESs . Les auteurs dans la référence [1] proposent deux schémas hybrides qui combinent un algorithme stateful et un algorithme stateless , ayant la même structure de clé KEKs. Schéma hybride basé sur les schémas précédents Un schéma hybride simple mélange la méthode stateless CS décrite, par exemple, dans la référence [3] et la méthode stateful LKH (voir les références [6], [5], [RFC-2627]). Si l'on utilise seulement la méthode CS pour diffuser un message et si le nombre d'utilisateurs déniés devient très important, alors la taille de la session de diffusion devient très importante. L'idée principale du schéma hybride décrit dans [1] est la suivante : généralement, on utilise la méthode stateless CS, mais lorsque le nombre d'utilisateurs déniés est supérieur à un seuil fixé, alors on utilise la méthode stateful LKH pour renouveler les clés connues par les utilisateurs autorisés et les utilisateurs déniés. Ainsi l'ensemble des utilisateurs déniés est remis à jour et l'on utilise à nouveau la méthode CS. La largeur de bande utilisée est ainsi améliorée par rapport à celle obtenue lorsque l'on utilise la seule méthode CS. Les schémas hybrides divulgués dans l'art antérieur ne proposent toutefois pas de solution permettant de mélanger des schémas présentant chacun des structures de clés de chiffrement KEKs différentes. L'idée de la présente invention repose sur un nouveau schéma hybride mélangeant une procédure stateless Al et une procédure stateful A2 utilisant différentes structures de clés. L'invention concerne notamment un procédé de diffusion de données dans un système utilisant un schéma stateless BES (Al) utilisant un arbre binaire T avec une structure de clé KEKs N 2, i.e. telle qu'une clé k1,i est associée à chaque différence de sous-ensembles S1,i , et une clé racine ko,__ associée à l'ensemble de l'arbre T et un schéma stateful BES (A2) utilisant le même arbre binaire T avec une structure de clé KEKs N 1, i.e. telle qu'une clé k; soit associée à chaque sous arbre Si caractérisé en ce que l'on utilise le schéma (Al) pour la session courante de diffusion et mettre à jour les clés connues par les utilisateurs déniés avec un schéma stateful (A2) de temps à autre. Les clés statiques ki, 1 and ko,__ définies par les procédures "stateless" (Al) ayant une longueur en bits notée Ns , les clés dynamiques k; définies par la procédure "stateful (A2) ont une longueur en bits notée Nd , le procédé utilise une fonction F avec des entrées dans {0,1 }Ns x {0,1 }Nd et des sorties dans {0,1 }"S, la fonction F est telle que : • il est facile de calculer z=F(x,y) à partir de tout (x,y) appartenant à {o, l }r's x {0,1 }Nd • pour tout triplet (x,y,z) tel que z=F(x,y), il est impossible de trouver z si l'on ne possède aucune information sur y, même si x est connu. et il comporte au moins les étapes suivantes : a) pour chaque index i d'un noeud v; de l'arbre, et pour chaque index j d'un noeud vi appartenant au sous-arbre Si, on définit les clés variables suivantes : • Lr,1 =F(kr,i , kr) calculé à partir de la clé statique k1,i et la clé dynarnique k; , • Lo __ =F(ko,__ , ko) calculé à partir de la clé statique ko,__ et de la clé dynamique ko . b) chaque session t, on note Mt les données à diffuser vers les utilisateurs autorisés, et on utilise (Al) pour diffuser Mt avec les "clés variables" on envoie : Al [Mt, {L1,j}], c) toutes les T sessions, où T est un paramètre, on utilise (A2) pour renouveler les clés dynamiques partagées par les utilisateurs autorisés et révoqués, et on envoie une information I(D) donnant la date D de la mise en oeuvre opérationnelle du jeu de clés renouvelées, i.e, envoyer A2[M, {k;}, {k';}] et I(D), d) à la date D, l'ensemble de clés dynamiques {k;} est remplacé par le nouveau jeu {k';}. Le procédé est utilisé par exemple pour la diffusion de données comportant un service de radio-navigation par satellite protégé chaque jour t par une clé de trafic KT (t), chaque jour t, un service fournit aux utilisateurs autorisés un message Mt contenant une ou plusieurs clés de trafic futures donnant un accès potentiel au service S pour les jours futurs, et en ce que l'on diffuse le message Mt en exécutant les étapes décrites ci-dessus. Le procédé selon l'invention présente notamment les avantages suivants : pouvoir choisir les méthodes (Al) et (A2) parmi les plus performantes, c'est-à- dire de choisir une méthode stateless Al ayant une structure de clés N 2 et une méthode stateful A2 ayant une structure de clés N 1, et combiner ces deux méthodes. Le schéma stateless (Al) est utilisé pour la session courante de diffusion. Ainsi, entre deux messages A2, un utilisateur peut rater plusieurs 20 messages Al sans échouer dans le déchiffrement du prochain message Al. Le schéma stateful (A2) est utile pour deux raisons : Il renouvelle les clés connues par les utilisateurs révoqués (pour des raisons de sécurité) et il permet de "réinitialiser" l'ensemble des utilisateurs révoqués (raison d'optimisation de largeur de bande). D'autres caractéristiques et avantages de la présente invention apparaîtront mieux à la lecture de la description d'un exemple donné à titre illustratif et nullement limitatif annexé des figures suivantes qui représentent : 25 • la figure 1 un arbre binaire pour Al avec les clés associées, • la figure 2 un arbre binaire pour A2 avec les clés associées. En résumé le procédé selon l'invention comporte, par exemple, les étapes suivantes : 1) choisir deux schémas Al et A2 définis ci-après, 2) calculer des clés de chiffrement variables à partir des clés de chiffrement statistiques et de clés de chiffrement dynamiques , 3) utiliser des schémas Al et A2 avec les clés de chiffrement statiques , dynamiques et variables comme il est exposé ci-après. L'invention permet de mixer deux schémas, l'un stateless l'autre stateful, ayant des structures de clés différentes. Description détaillée d'un mode de réalisation De manière à illustrer le procédé selon l'invention, l'exemple donné se place dans le cas suivant : 1 ù on considère un schéma stateless BES (Al) utilisant un arbre binaire T avec une structure de clé KEKs N 2, i.e. telle qu'une clé k;,i est associée à chaque différence de sous-ensembles 5;,i , et une clé racine ko,__ associée à l'ensemble de l'arbre T. Comme tout schéma stateless , l'utilisation normale de (Al) pour une session donnée consiste à envoyer une donnée M formatée dans le message M', contenant : la donnée M chiffrée par une clé de session et la clé de session chiffrée par plusieurs clés KEKs appartenant à l'ensemble {k;,i} tel que seuls les utilisateurs qui sont autorisés pour la session puissent déchiffer la clé de session (permettant de déchiffrer la donnée M). En particulier, s'il n'y a pas de dénis, la clé de session est chiffrée avec la clé de la racine ko,_. On note M'=A1 [M, {k1à]. 2 ù on considère un schéma stateful BES (A2) utilisant le même arbre binaire T avec une structure de clé KEKs N 1, i.e. telle qu'une clé k; soit associée à chaque sous arbre Si. Comme tout schéma stateful , l'utilisation normale de (A2) pour une session donnée consiste à envoyer une donnée M formatée dans le message M', contenant : plusieurs nouvelles clés KEKs k'; (incluant une nouvelle clé racine k'o) chiffrée avec des clés courantes KEKs, et la donnée M chiffrée par la nouvelle clé de la racine k'o (ayant le rôle de clé de session). Le nouvel ensemble {k'; } renouvelle les clés KEKs partagée par les utilisateurs déniés et les utilisateurs autorisés. Ce sera l'ensemble des clés KEKs courantes pour la prochaine session. Nous notons M'=A2[M, {k;}, {k';}]. Nouveau schéma hybride selon l'invention : L'idée de ce schéma hybride est d'utiliser un schéma stateless (A1) efficace pour la session courante de diffusion, et de mettre à jour les clés connues par les utilisateurs révoqués avec un schéma efficace stateful (A2) de temps à autre, par exemple lorsque le nombre d'utilisateurs révoqués devient important. Les clés k;,; and ko,__ définies par les procédures "stateless" (A1) sont appelées "clés statiques". Leur longueur en bits est notée NS . Les clés k; définies par la procédure "stateful (A2) sont appelées "clés dynamiques". Leur longueur en bits est notée Nd . On note F une fonction avec des entrées dans {0,1 }Ns x {0,1 }Nd et des sorties dans {0,1}NS. La fonction F est telle que : • il est facile de calculer z=F(x,y) à partir de tout (x,y) appartenant à {0,1 }Ns x {0,1 }Nd • pour tout triplet (x,y,z) tel que z=F(x,y), il est impossible de trouver z si l'on ne possède aucune information sur y, même si x est connu. Par exemple, si NS=Nd alors F peut être la fonction XOR, car si z = x XOR y alors la connaissance de x ne donne pas d'information sur z si y est inconnu. Une condition plus forte à vérifier peut être que F est une fonction à sens unique one-way function , i.e. pour tout z donné, il est pratiquement impossible par calcul de trouver un couple (x,y) tel que z=F(x,y). Pour chaque index i d'un noeud v; de l'arbre, et pour chaque index j d'un noeud vi appartenant au sous-arbre Si, on définit les clés suivantes : • L1,i =F(k;,i , k;) calculé à partir de la clé statique k;, et la clé dynamique k; . • Lo __ =F(ko,__ , ko) calculé à partir de la clé statique ko,__ et de la clé dynamique ko . Ces nouvelles clés L;,i et Lo,__ sont appelées "clés variables". Ces clés ont la même longueur que les clés statiques et sont indexées de manière identique. Ces clés variables remplaceront les clés KEKs Ki pour le schéma (A1) dans le schéma hybride selon l'invention. Chaque session t, on note Mt les données à diffuser vers les utilisateurs autorisés. Le schéma hybride mélangeant (A1) et (A2) est le suivant : • Chaque session t, on utilise (A1) pour diffuser Mt avec les "clés variables" comme KEKs, c'est-à-dire on envoie : Al [Mt, {L;,i}]. • Toutes les T sessions, où T est un paramètre (fixé ou pouvant varier), on utilise (A2) pour renouveler les clés dynamiques partagées par les utilisateurs autorisés et révoqués, et on envoie une information I(D) donnant la date D de la mise en oeuvre opérationnelle du jeu de clés renouvelées, i.e, envoyer A2[M, {k;}, {k';}] et I(D) Contrairement à l'utilisation normale de A1, on utilise ici Al avec les clés variables {L1,i} au lieu des clés statiques {k;I de sorte à ce que A2 permettent un renouvellement des clés utilisées par Al. A la date D, l'ensemble de clés dynamiques {k;} est remplacé par le nouveau jeu {k';}. Les clés variables utilisées pour (Al) dépendent des clés dynamiques et des clés statiques. Ainsi, à la date D, l'ensemble des clés variables {14 est remplacé par le nouveau jeu et utilisé pour (Al). Le nouveau schéma hybride selon l'invention repose sur l'idée suivante : utiliser un schéma efficace stateless (Al) pour la session courante de diffusion et mettre à jour les clés connues par les utilisateurs déniés avec un schéma stateful efficace (A2) de temps à autre (toutes les T sessions), par exemple lorsque le nombre d'utilisateurs déniés augmente de manière trop importante. Remarques sur le paramètre T : Remarque 1 : si le temps entre des sessions des messages Al est fixé (une session par jour par exemple), et si le temps entre deux messages A2 est fixé (T jours par exemple) et connus par les utilisateurs, alors l'information I(D) est implicite et il n'est pas nécessaire de la transmettre, - Remarque 2 : Le nombre T de session entre deux messages A2 peut évoluer avec le nombre de personnes révoquées. Par exemple, un message A2 est transmis lorsque le nombre d'utilisateurs révoqués atteint un seuil. Exemple d'utilisation de schéma hybride : Le schéma hybride peut être utilisé par un service OTAR (Over The Air Rekeying) avec contrôle d'accès. Par exemple, si l'on fait l'hypothèse qu'un service de radio-navigation par satellite est protégé chaque jour t par une clé de trafic KT (t). Chaque jour t, un service OTAR fournit aux utilisateurs autorisés un message Mt contenant une ou plusieurs clés de trafic futures donnant un accès potentiel au service S pour les jours futurs. Les satellites ont une très faible largeur de bande. Les utilisateurs doivent donc s'organiser en groupes d'utilisateurs, et les groupes sont organisés comme des feuilles d'un arbre de hiérarchie binaire. Le message Mt peut être diffusé en utilisant le schéma hybride utilisant l'arbre T, par exemple avec la méthode SD décrite par exemple dans la référence [3] pour (Al) et la méthode OFT exposée dans la référence [2] pour (A2). Références [1] Shaoquan Jiang and Guang Gong. Hybrid Broadcast Encryption and Security Analysis. Cryptology ePrint Archive, Report 2003/241, 2003. http://eprint.iacr.org/. [2] David A. McGrew and Alan T. Sherman. Key Establishment in Large Dynamic Groups Using One-Way Function Trees. Manuscript, 1998. [3] Dalit Naor, Moni Naor, and Jeff Lotspiech. Revocation and tracing schemes for stateless receivers. Lecture Notes in Computer Science, 2139:41-62, 2001. [4] : "Key Management for Multicast: Issues and Architectures", RFC 2627, 1999. [5] Debby M. Wallner, Eric J. Harder, and Ryan C. Agee. Key Management for Multicast: Issues and Architectures. Internet 5 Request for Comment RFC 2627, Internet Engineering Task Force, 1999. [6] Chung Kei Wong, Mohamed Gouda, and Simon S. Lam. Secure group communications using key graphs. In Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, pages 68-79. ACM Press, 1998. REVENDICATIONS 1 ù Procédé de diffusion de données dans un système utilisant un schéma stateless (Al) utilisant un arbre binaire T avec une structure de clé de chiffrement KEKs N 2, i.e. telle qu'une clé k;,; est associée à chaque différence de sous-ensembles S;,i , et une clé racine associée à l'ensemble de l'arbre T et un schéma stateful (A2) utilisant le même arbre binaire T avec une structure de clé de chiffrement KEKs N 1, i.e. telle qu'une clé k; soit associée à chaque sous arbre Si, caractérisé en ce que l'on utilise le schéma (Al) pour la session courante de diffusion et mettre à jour les clés connues par les utilisateurs déniés avec un schéma stateful (A2) de temps à autre. 2 - Procédé de diffusion de données selon la revendication 1, les clés de chiffrement statiques k;,; and ko,__ définies par les procédures "stateless" (Al) ayant une longueur en bits notée Ns , les clés de chiffrement dynamiques k; définies par la procédure "stateful (A2) ont une longueur en bits notée Nd , le procédé utilise une fonction F avec des entrées dans {0,1 }Ns x {0,1 }Nd et des sorties dans {0,1 }NS, la fonction F est telle que : • il est facile de calculer z=F(x,y) à partir de tout (x,y) appartenant à 40, 1 }Ns x {0,1 }Nd • pour tout triplet (x,y,z) tel que z=F(x,y), il est impossible de trouver z si l'on ne possède aucune information sur y, même si x est connu, caractérisé en ce qu'il comporte au moins les étapes suivantes : a) pour chaque index i d'un noeud v; de l'arbre, et pour chaque index j d'un noeud v; appartenant au sous-arbre Si, on définit les clés de chiffrement variables suivantes :• L1,i =F(k;,1 , k;) calculé à partir de la clé de chiffrement statique Ki et la clé de chiffrement dynamique k; . • Lo __ =F(ko __ , ko) calculé à partir de la clé statique ko,__ et de la clé dynamique ko . b) chaque session t, on note Mt les données à diffuser vers les utilisateurs autorisés, et on utilise (Al) pour diffuser Mt avec les "clés de chiffrement variables" on envoie : Al [Mt, {L;,i}], c) toutes les T sessions, où T est un paramètre, on utilise (A2) pour renouveler les clés dynamiques partagées par les utilisateurs autorisés et révoqués, et on envoie une information I(D) donnant la date D de la mise en oeuvre opérationnelle du jeu de clés de chiffrement renouvelées, i.e, envoyer A2[M, {k;}, {k';}] et I(D), d) à la date D, l'ensemble de clés de chiffrement dynamiques {k;} est remplacé par le nouveau jeu {k';}. 3 û Procédé de diffusion de données comportant un service de radio-navigation par satellite protégé chaque jour t par une clé de trafic KT (t), chaque jour t, un service fournit aux utilisateurs autorisés un message Mt contenant une ou plusieurs clés de trafic futures donnant un accès potentiel au service S pour les jours futurs, et en ce que l'on diffuse le message Mt en utilisant le procédé selon l'une des revendications 1 ou 2.25