PROCEDE HYBRIDE DE DISTRIBUTION DE CLES POUR LA DIFFUSION DE DONNEES CHIFFREES

5 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.

Il 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 l(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.

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 nœud v, de l'arbre est associée une clé k,. Les feuilles sont considérées comme des nœuds 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 nœuds 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 S, dont la racine

est le nœud v, et seulement à ces feuilles. Toute donnée chiffrée avec la clé k, est destinée aux feuilles de S ₁ et seulement à ces feuilles. On note k ₀ la clé racine (c'est-à-dire la clé associée à la racine v ₀ de l'arbre T) et {k, } l'ensemble de toutes les clés k,. 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, _j est associée à une différence de sous ensembles S _1J = S ₁ - S _j de façon telle que, le sous arbre S ₁ contient le sous-arbre S _j .

Chaque clé k, _j est distribuée pour chaque feuille appartenant au sous- ensemble S _1J , (c'est-à-dire appartenant à S ₁ mais pas à S _j ) et cette clé est utilisée pour chiffrer toute donnée destinée à tous les utilisateurs appartenant à S _1J et seulement à eux. Une clé k _o ,~ 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 k, _j 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 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 » A1 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 (A1 ) utilisant un arbre binaire T avec une structure de clé KEKs N°2, i.e. telle qu'une clé k,, _j est associée à chaque différence de sous-ensembles S _1J = S ₁ - S _j où S ₁ et S _j sont deux sous-arbres tels que S ₁ contient S _j ,, 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 S, caractérisé en ce que l'on utilise le schéma (A1 ) 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, le jeu de clés permettant la diffusion des messages de la session courante avec le schéma (A1 ) étant un autre jeu {L, _j } déterminé à partir des deux jeux {k, _j } et {k,}.

Les clés statiques k,, _j and k _o ,~ définies par les procédures "stateless" (A1 ) ayant une longueur en bits notée N _s , les clés dynamiques k, définies par la procédure "stateful (A2) ont une longueur en bits notée N _d , 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 à {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. et il comporte au moins les étapes suivantes : a) pour chaque index i d'un nœud v, de l'arbre, et pour chaque index j d'un nœud V _j appartenant au sous-arbre S ₁ , on définit les clés variables suivantes :

• L _N =F(k, _j , k,) calculé à partir de la clé statique k, _, , et la clé dynamique k, ,

• L ₀ ,- =F(k ₀ ,- , k ₀ ) calculé à partir de la clé statique ko,- et de la clé dynamique k ₀ . b) chaque session t, on note M _t les données à diffuser vers les utilisateurs autorisés, et on utilise (A1 ) pour diffuser M _t avec les "clés variables" on envoie : AI [Mt ₁ (UjJ],

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 œuvre opérationnelle du jeu de clés renouvelées, i.e, envoyer A2[M, {k,}, {k ¹ ,}] et I(D), d) à la date D, le nouveau jeu de clés {k',}, et en conséquence l'ensemble des clés {L, _j } est remplacé par le nouveau jeu {!_',,,} tel que U _1J = F (k,,, 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 K _τ (t), chaque jour t, un service fournit aux utilisateurs autorisés un message M _t 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 M _t 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 (A1 ) et (A2) parmi les plus performantes, c'est-à- dire de choisir une méthode stateless A1 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 (A1 ) est utilisé pour la session courante de diffusion. Ainsi, entre deux messages A2, un utilisateur peut rater plusieurs messages A1 sans échouer dans le déchiffrement du prochain message A1.

Le schéma stateful (A2) est utile pour deux raisons : II 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 :

• la figure 1 un arbre binaire pour A1 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 A1 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 A1 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 (A1 ) utilisant un arbre binaire T avec une structure de clé KEKs N°2, i.e. telle qu'une clé k, _j est associée à chaque différence de sous-ensembles S _1J , et une clé racine ko,- associée à l'ensemble de l'arbre T.

Comme tout schéma « stateless », « l'utilisation normale » de (A1 ) 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,, _j } 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,-

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 S ₁ .

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,, _j and k _o ,~ définies par les procédures "stateless" (A1 ) sont appelées "clés statiques". Leur longueur en bits est notée N _s .

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 N _d .

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 N _s =N _d 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 nœud v, de l'arbre, et pour chaque index j d'un nœud v, appartenant au sous-arbre S ₁ , on définit les clés suivantes : • L _1J =F(k, _j , k,) calculé à partir de la clé statique k _u et la clé dynamique k, .

• L ₀ ,- =F(k ₀ ,- , k ₀ ) calculé à partir de la clé statique ko,- et de la clé dynamique k ₀ .

Ces nouvelles clés L _1J et L _0, - 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 k _u pour le schéma (A1 ) dans le schéma hybride selon l'invention.

Chaque session t, on note M _t 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 M _t avec les "clés variables" comme KEKs, c'est-à-dire on envoie : A1 [M _t , {L, _j }].

• 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 œuvre opérationnelle du jeu de clés renouvelées, i.e, envoyer A2[M, {k,}, {k' }] et l(D)

Contrairement à l'utilisation « normale » de A1 , on utilise ici A1 avec les clés variables {!_,,} au lieu des clés statiques {k, _j }, de sorte à ce que A2 permettent un renouvellement des clés utilisées par A1.

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 (A1 ) dépendent des clés dynamiques et des clés statiques. Ainsi, à la date D, l'ensemble des clés variables {L,, _j } est remplacé par le nouveau jeu et utilisé pour (A1 ).

Le nouveau schéma hybride selon l'invention repose sur l'idée suivante : utiliser un schéma efficace stateless (A1 ) 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 A1 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 K _τ (t). Chaque jour t, un service OTAR fournit aux utilisateurs autorisés un message M _t 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 M _t 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 (A1 ) 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. Agée. Key

Management for Multicast: Issues and Architectures. Internet

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 conférence on Applications, technologies, architectures, and protocols for computer communication, pages 68-79. ACM Press, 1998.