Brevet FR2969789A1 — publié le 20120629

PROCEDE D'AUTHENTIFICATION MULTIMODALE ET GENERATION DE CLE CRYPTOGRAPHIQUE UTILISANT LES SECURE SKETCHES GENERALISES La présente invention concerne un procédé d'authentification multimodale utilisant notamment des systèmes possédant une phase d'enrôlement et une phase de recouvrement plus connus sous l'expression anglo-saxonne « secure sketches généralisés » (brevet FR 09 /03699). L'invention s'applique notamment dans les domaines d'authentification des personnes ou des supports, tels que des composants électroniques, des étiquettes, etc. Elle est utilisée dans tous les domaines mettant en oeuvre des techniques d'extraction de données à partir de données floutées. Elle trouve son application pour l'authentification de constituants physiques d'équipements, la détection d'une substitution d'un composant, d'une altération physique d'un composant, d'une altération d'un support physique. Elle est utilisée pour le contrôle d'accès des utilisateurs, par 20 exemple sur des sites sensibles, pour des équipements ou des comptes d'utilisateurs. Elle permet l'authentification conjointe d'utilisateurs et d'équipements. Le mot « donnée biométrique », dans la suite de la description, 25 couvre les empreintes digitales, l'iris, ... toutes les données biométriques possibles. Le terme « modalité » est utilisé dans la présente description pour désigner une donnée biométrique, la réponse d'un PUF ou toute autre donnée susceptible d'être bruitée associée à un individu ou à un objet que 30 l'on souhaite authentifier. Dans le domaine de l'authentification, le problème posé est de savoir extraire une donnée connue à partir d'une donnée floutée et de générer des données d'authentification ou des clés cryptographiques. Dans un souci d'augmenter la sécurité au niveau de la reconnaissance biométrique, la tendance actuelle est d'utiliser plusieurs modalités pour authentifier un individu. On effectuera ainsi l'authentification à partir de données floues d'une source possédant de multiples modalités, pouvant être différentes en taille, en type et/ou en métrique. Une modalité dans le domaine de la biométrie représente par exemple une empreinte digitale, la main, le visage, la voix, l'iris, la rétine, la signature dynamique ou tout autre caractéristique biométrique. La modalité peut aussi bien être la réponse d'un PUF ou toute autre donnée susceptible d'être bruitée. L'article principal connu dans ce domaine est celui publié par Dodis et al., intitulé « Fuzzy extractors : How to generate strong keys from biometrics and other noisy data » Eucrocypt 2004, LCNS, vol 3027, pp 523-540 qui traite du problème du caractère non uniforme des données mesurées et de la présence de bruit. Pour rendre les données stables malgré la présence de bruit, les auteurs de cet article proposent l'utilisation d'un extracteur flou. Une possibilité pour construire un extracteur flou est l'utilisation de deux primitives. Un premier module, désigné par l'expression anglo-saxonne « secure sketch » permet la conciliation de l'information, c'est-à-dire le rétablissement d'une valeur systématiquement identique en sortie pour une même donnée d'entrée, et un second module permet de rendre uniforme la sortie de l'extracteur flou par application d'une fonction d'extraction d'aléa sur ladite sortie, préalablement stabilisée. L'extracteur flou fonctionne en deux phases : l'enrôlement et la correction. La phase d'enrôlement peut n'être exécutée qu'une seule fois ; elle produit à partir d'une donnée de référence, notée w, issue d'une mesure d'une donnée confidentielle W fournie en entrée, une donnée publique, notée s et qualifiée dans la plupart du temps de « sketch ». Classiquement, la donnée de référence w peut être obtenue via une première mesure issue d'un traitement d'une donnée confidentielle W reçue par un capteur ou un composant électronique. A titre illustratif, la donnée confidentielle W est une empreinte digitale et la donnée de référence w est la donnée caractéristique obtenue par une première mesure de cette empreinte par un capteur. Seule la donnée publique s est enregistrée, la donnée de référence w étant confidentielle. La donnée publique joue donc un rôle de reconstruction de la mesure confidentielle de référence w à partir d'une donnée bruitée w'. Les figures 1A et 1B schématisent respectivement les phases d'enrôlement et de recouvrement. Sur ces figures, w est la donnée d'origine, s est le sketch, et w' la seconde donnée floue ou bruitée. Plus formellement, dans l'article précité, un secure sketch est défini de la façon suivante : soit M correspondant à un espace métrique muni d'une opération de mesure de distance entre w et w' qui sont des mesures des données et m, m' des paramètres d'entropie, un secure sketch de paramètres (M,m,m',t) est une paire de procédures 'sketch' ou enrôlement (Enrol) et 'recover' ou recouvrement (Rec) telles que : a) la procédure Enrol 100 prend en entrée wE M et retourne une chaîne de bits s E {0;1}* . b) la procédure de recouvrement Rec 101 prend en entrée un élément 20 w'E M et une chaîne de bits s E {0;11*. La propriété de correction du secure sketch garantit que si dis(w,w') t, aucune garantie n'est donnée sur la sortie de Rec. c) la propriété de sécurité garantit que pour toute distribution W sur M de min-entropie m, la valeur de W ne peut être retrouvée par l'adversaire 25 qu'avec une probabilité inférieure à 2'' : HL(W,SS(W))>_ m' où H~(.) est la min-entropie. Classiquement, la donnée de référence w peut être obtenue via une première mesure issue d'un traitement d'une donnée confidentielle W reçue par un capteur ou un composant électronique. A titre illustratif, la 30 donnée confidentielle W est une empreinte digitale et la donnée de référence w est la donnée caractéristique obtenue par une première mesure de cette empreinte par un capteur. Par la suite, la phase de correction est exécutée à chaque fois que l'on souhaite retrouver la donnée de référence w. A cette fin, une donnée bruitée w' provenant d'une mesure issue d'un traitement de la donnée confidentielle W - par exemple, une seconde mesure de la même empreinte digitale - est combinée à la donnée publique s. La donnée publique s joue donc un rôle dans la reconstruction de la mesure confidentielle de référence w à partir d'une donnée bruitée w'. Si la donnée bruitée w' est trop éloignée de la donnée de référence w, cette donnée de référence w ne peut être reconstruite. C'est le cas, par exemple, lorsque la donnée bruitée w' est obtenue par une mesure d'un traitement d'une donnée X différente de la donnée confidentielle W. Un des problèmes du secure sketch classique est que la donnée en entrée (w ou w') est d'une certaine taille et il n'est alors pas toujours possible de la traiter. Souvent, lorsque l'on utilise des codes correcteurs, les données physiques imposent des contraintes sur les paramètres du code. Il se peut dans certains cas que ces contraintes soient antagonistes ce qui fait qu'il n'existe pas de codes correcteurs d'erreurs capables à la fois de corriger correctement la donnée w' et de maintenir un bon niveau de sécurité. Pour remédier à ce problème, l'idée est donc la suivante : on allonge de façon déterministe la taille des données ce qui permet de les adapter à la longueur du code utilisé. La position et la valeur des bits à ajouter pour effectuer cette élongation sont stockées dans une clé secrète Sk = [(post...,posk) ;(vali,...,valk)] ; où les val; sont des bits et les pos; représentent les positions des bits de valeur val; à ajouter dans la donnée pour effectuer son élongation. La clé secrète Sk sert donc à augmenter la taille des données. Le secure sketch généralisé ainsi défini est schématisé sur les figures 2A et 2B, où l'on retrouve pour la phase d'enrôlement 200 la donnée w et la clé secrète Sk qui permettent de générer le sketch s et pour la phase de recouvrement 201, la donnée bruitée w', le sketch s et la clé secrète Sk qui permettent de retrouver la donnée w. Une façon de construire des secure sketches est, par exemple, donnée dans la demande de brevet déposée par le Demandeur sous la référence FR 0903699 ou FR 1005115 ayant pour titre « Procédé de reconstruction d'une mesure de référence d'une donnée confidentielle à partir d'une mesure bruitée de cette donnée, notamment pour la génération de clés cryptographiques ». Les solutions existantes connues du Demandeur pour authentifier des individus, des objets ou conjointement des individus et des objets ne permettent pas l'interopérabilité des différents types de modalités utilisées. Les solutions biométriques multimodales actuelles utilisent en effet la combinaison des solutions dédiées à chaque type de biométrie. L'objet de l'invention concerne un procédé d'authentification multimodale d'individus ou d'objets ou conjointement d'individus et d'objets, lesdits individus ou lesdits objets étant caractérisés ou associés à une ou plusieurs modalités modi avec i allant de 1 à n caractérisé en ce qu'il comporte au moins les étapes suivantes : a) la connaissance d'un ensemble de mesures des n modalités et des sketches correspondant à chacune des modalités s(mod1), 20 s(mod1,mod2), ..., s(mod1,...,modi), ..., s(mod1,...,modn), b) une étape de mesure d'une donnée floue ou bruitée w'(mod1) (310) correspondant à une première modalité mod1, c) la correction de la mesure de la première modalité w'(mod1) au moyen d'un secure sketch SS1 qui prend en entrée la mesure bruitée 25 w'(mod1) et le sketch s(mod1) correspondant à la modalité 1 mod1, afin d'obtenir une mesure corrigée ou débruitée w(mod1), d) transformer la donnée w(mod1) en utilisant une fonction de transformation non inversible afin de trouver une première clé secrète Sk('), c'est-à-dire qu'à partir de la connaissance de Sk(l) il n'est pas possible de 30 retrouver de l'information concernant la donnée w, e) effectuer une mesure d'une ième modalité w'(modi) avec i supérieur ou égal à 2 et inférieur ou égal à n, f) corriger ladite ième modalité w'(modi) avec i supérieur ou égal à 2 et inférieur ou égal à n le nombre de modalités choisies pour 5 l'authentification en exécutant les étapes suivantes : g) utiliser la clé Sk('-l) obtenue en appliquant la fonction d'élongation sur la modalité w'(mod;) afin de générer une donnée étendue w'e(modi) en augmentant la taille de la donnée de référence avec les k valeurs composant la clé Sk('-'), 10 h) déterminer à partir de la donnée étendue w'e(modi) et du sketch s(mod1,..., modi) la valeur débruitée étendue we(mod1,..., modi), i) réitérer les étapes e) à h) tant que i est inférieur ou égal à n, nombre de modalités fixé initialement, j) utiliser le mot we(mod1,...modn) afin d'authentifier l'utilisateur ou 15 l'objet correspondant aux n modalités mesurées ou afin de générer une clé cryptographique. De manière générale, la fonction de transformation `T' peut prendre, en entrée une donnée w et génère une clé Sk .II y a, par exemple, trois types de données possibles en entrées (distance de Hamming, 20 différence symétrique ou distance d'édition) ; pour le cas des distances d'entrée autres que la distance de Hamming on effectue un prétraitement sur les données afin d'obtenir une chaîne de caractères de longueur fixe (on note C la chaîne obtenue par prétraitement). La clé générée par la fonction de transformation est de la forme Sk = Rpos,; ...; posk); (vals; ...; valk)] dans 25 le cas de la distance de Hamming et de la distance d'édition et Sk = ((éléments; ...; élémentk)] dans le cas de la différence symétrique. La fonction de transformation présente une propriété commune quelle que soit la distance utilisée : la propriété de non-inversibilité : il n'est pas possible de retrouver l'entrée à partir de la sortie de la fonction. 30 Dans le cas où les données en entrée et en sortie sont dans un espace de Hamming, le procédé utilise une fonction de transformation `T' qui prend, par exemple, en entrée une donnée w = et génère une clé Sk = [(pose; ...; posé); (vals; ...; valk)] où les val; sont des bits et les pos; représentent les positions des bits de valeur val; à ajouter, les k positions étant choisies parmi n emplacements et en ce que ladite fonction de transformation `T' présente les propriétés suivantes : a) Non-inversibilité, c'est-à-dire qu'à partir de la connaissance de Sk = [(pose; ...; posé); (vals; ...; valk)] il n'est pas possible de retrouver de l'information concernant la donnée w, soient we {0 ;1}m et Sk E Pk x {0;1}k tels que Sk = T(w), alors V Sk, H(w) = m; b) Probabilités de distributions uniformes sur les valeurs de val, de pos et sur l'union de ces deux valeurs avec : - Vie {1;...;klVVALE {0;1}k,P[val, =VAL] = Zk - b'i E {1;...; k}, b'POS E P, P[pos; = POS] = 1 n - b'i E {1;4 k}, /VAL e {0;1}k, `dPOS E P, P[val; = VAL, pos; = POS] = n * 2k Le procédé peut utiliser une fonction de transformation 'T' définie de la manière décrite ci-après. A partir d'une donnée w=wl...wm, le procédé va déduire une « clé secrète » Sk =[(posi,...,posk) ;( vali,...,valk)] uniforme en exécutant les étapes suivantes : Phase 1 : choisir les val; choisir une fonction de hachage h :{0 ;1}*->{0 ;1}k', cE N* l'ensemble des entiers naturels non nuls, pour i=1 à k, val;=(h(w));. Phase 2: déterminer les pos; en se basant sur, l'algorithme KSA de 25 génération de permutation du RC4, connu de l'Homme du métier, S est un tableau de n cases indexées de 0 à n-1, 1 choisir une fonction de hachage h et poser K=h(w). Découper ensuite K en paquets de rlogz ni bits (ici [1 désigne le plus petit entier supérieur ou égal à x), si le dernier paquet ne contient pas exactement rlogz ni bits, ne pas conserver ledit paquet, poser ensuite key[0] le premier paquet en base 10, key[1 ] le deuxième, etc. soit keylength le nombre de paquets, pour i=0 à n-1 S[i] .=i p:=0 pour i=0 à n-1 j:=(j+S[i]+key[i mod keylength]) mod n Inverser les valeurs de S[i] et de SU] S représente une permutation de {0,...,n-1}, prendre ensuite une liste publique de k indices (par exemple {0,...,k-1}) et l'image de chacun de ces éléments par S contient une des k positions cherchées. Le procédé utilise, par exemple, pour le premier secure sketch SS1, un secure sketch généralisé composé d'une fonction permettant 20 d'étendre la donnée mesurée suivie d'un secure sketch. Un secure sketch généralisé peut être remplacé par un extracteur flou généralisé (un extracteur flou généralisé est composé d'un secure sketch généralisé et d'une fonction de hachage). Un certain nombre de secure sketches parmi le premier secure 25 sketch SS1 et certains des secure sketches généralisés suivants sont remplacés par des extracteurs flous généralisés. Le procédé peut comporter l'utilisation d'un secure sketch généralisé recentré composé d'un secure sketch généralisé auquel il a été ajoutée une fonction ExtendSk-' à la sortie, ledit secure sketch généralisé 30 recentré étant disposé au niveau de la mesure de la n-1+1 ième modalité, les n-1 modalités précédentes mesurées utilisant des secure sketches généralisés. Selon un mode de mise en oeuvre, le procédé comporte au moins les étapes suivantes : SOit n : nombre total de secure sketches classiques notés SS, généralisés notés SSg ou recentrés notés SSgr utilisés, seul le premier de la chaîne peut être un secure sketch classique, 1 : la limite, correspond à la plus longue chaîne de SSg en partant de 10 la fin et en incluant le premier SSgr, C : chaîne de n-I+1 bits qui représentent les n-I premiers SS, SSg ou SSgr (2 bits pour le premier SS (celui ci peut être un secure sketch classique, un SSg ou un SSgr) et 1 bit pour chacun des SSg ou SSgr placés aux positions 2 à n-I), 15 positionner un SSgr en position n-1+1 et pour tous les autres blocs des SSg, récupérer la donnée en sortie du SSgr,. Cette donnée récupérée ne dépend alors que des 1 dernières modalités; SSgr, un SSg positionné à la place n, ainsi l'indice désigne la position de l'outil utilisé. Le procédé peut aussi récupérer une donnée qui dépend d'un 20 certain nombre de modalités l' et ce avant la limite 1 et qui nécessite l'authentification multimodale des m premières modalités. Pour cela, on place un SSgr en position m-l'+1 et des SSg aux positions m-l'+2, ..., m. Selon une variante de réalisation, le procédé récupère m modalités en sortie de m secure sketches (SS, SSg ou SSgr) prédéfinis pour 25 créer une donnée dépendant de cette liste de modalités. Cette donnée peut par exemple servir à la génération d'un clé cryptographique qui dépend des m modalités choisies. Un exemple est de générer une clé crytographique en appliquant une fonction de hachage sur la concaténation des mesures « défloutées » 30 des m modalités. Selon une variante de réalisation, le procédé comporte pour obtenir une donnée qui ne dépend que de la modalité m, mais qui nécessite l'authentification des m premières modalités au moins les étapes suivantes: on dispose un secure sketch généralisé recentré (SSgr) en position m, le type des autres blocs (SSg ou SSgr) n'a alors aucune influence sur la dépendance de cette donnée. Le procédé met par exemple en oeuvre un principe d'authentification croisée comprenant au moins les étapes suivantes : passer d'abord dans le premier secure sketch SS1, afin d'en déduire une première clé secrète Sk(l), appliquer ladite première clé secrète à la deuxième modalité mod2, puis dériver une seconde clé secrète à appliquer à la première modalité mod1 afin d'obtenir la valeur de w(2)(mod1, mod2). L'exposant (2) signifie que c'est la deuxième fois que le SS1 est utilisé par le procédé. Le procédé décrit précédemment et ci-après est utilisé, par exemple, pour authentifier un individu à partir de plusieurs modalités choisies parmi la liste suivante : la voix, les empreintes digitales, l'iris, la rétine, le visage..., la réponse de PUFs, la combinaison des biométries et des réponses de PUFs ou toute autre données floues D'autres caractéristiques et avantages du dispositif selon l'invention apparaîtront mieux à la lecture de la description qui suit d'un exemple de réalisation donné à titre illustratif et nullement limitatif annexé des figures qui représentent : - Les figures 1A et 1B, la notion de secure sketch, - Les figures 2A et 2B, la notion de secure sketch généralisé, - La figure 3A, l'étape d'initialisation du système prenant en compte deux modalités et permettant la génération des sketches utilisés lors de la phase d'authentification, ^ La figure 3B, le schéma d'une phase d'authentification dans le cas d'une application prenant en compte deux modalités, - La figure 3C, une illustration pour le secure sketch généralisé, - La figure 4A, et la figure 4B, deux exemples de répercussion d'erreurs dans la chaîne de traitement, - La figure 5A, un exemple de généralisation du procédé selon l'invention à une pluralité de modalités, les figures 5B et 5C, des étapes d'un exemple de construction d'une fonction de transformation, - Les figures 6A, 6B, deux exemples d'utilisation avec ajout de fonctions de hachage, - La figure 7, un exemple de gestion des différentes modalités : il n'est pas obligatoire d'associer une modalité à un secure sketch, les différentes modalités peuvent être réparties à convenance sur les différents secure sketches. - Les figures 8 et 9 un exemple de la mise en oeuvre du procédé selon l'invention réalisant de l'authentification croisée et la figure 10, la phase d'enrôlement correspondante, - La figure 11, un schéma pour une définition d'un secure sketch généralisé recentré, - La figure 12, une comparaison entre le secure sketch généralisé et le secure sketch généralisé recentré, - La figure 13, une représentation d'un schéma d'authentification mettant en oeuvre un secure sketch généralisé recentré, - La figure 14A, un schéma d'authentification mettant en oeuvre plusieurs secure sketches généralisés recentrés, - La figure 14B, un schéma d'enrôlement correspondant à la figure 14A, ^ Les figures 15A, 15B, 15C des exemples de mise en oeuvre du procédé dans lesquels la donnée du sortie ne dépend que d'un nombre donné de modalités, - Les figures 16A, 16B, des exemples chiffrés de mise en oeuvre du procédé de la figure 15A, et ^ La figure 17, un exemple de dispositif selon l'invention. L'idée sur laquelle repose le procédé selon l'invention est l'authentification multimodale, c'est-à-dire que le procédé utilise plusieurs types de modalités pour effectuer l'authentification d'un individu ou d'un composant, par exemple, associé à un PUF ou tout autre support ou conjointement d'individus et de supports. La description qui va suivre, donnée à titre illustratif afin de comprendre le principe mis en oeuvre dans l'invention, met en oeuvre dans un premier temps deux modalités désignées mode et mode, les deux modalités étant dans cet exemple des réponses de PUFs ou encore des données biométriques et elle sera généralisée au cas où le procédé utilise n modalités pour authentifier un ou plusieurs individus et/ou objets. La figure 3A représente un exemple de schéma d'initialisation du système qui va permettre d'obtenir une base de données comprenant pour une modalité donnée, le sketch qui lui correspond. Les notations utilisées sur cette figure 3A seront conservées pour désigner des éléments identiques sur plusieurs figures. Dans cet exemple, la procédure exécutée par les secure sketches est la procédure de recouvrement. Au préalable, l'étape d'enrôlement génère pour i=1 à n des sketches s(mod1, ..., modi). Chaque sketch dépend à la fois de la modalité i et des modalités précédentes (mod1, ..., modi-1). Cette dépendance est due aux clés secrètes Sk(1), ..., Sk(i-1) générées par la fonction de transformation T détaillée ci-après. Le principe consiste à effectuer l'enrôlement pour le premier secure sketch SS1 car le second enrôlement nécessite la clé secrète Sk(l) qui est dérivée de w(modi) : notons que chaque clé Sk est propre à une modalité. Une fois le premier enrôlement terminé, le procédé dispose de s(modi) et transforme la donnée w(modi) en la clé secrète Sk('). Ensuite, une mesure de la deuxième modalité mode est effectuée pour obtenir w(mod2) puis s(modi,mod2). L'étape d'enrôlement ou d'initialisation est représentée à la figure 3A. En entrée du premier secure sketch SS1, le procédé effectue une mesure 300 de la modalité w(mod1) qu'il transmet ensuite au secure sketch SS1, 301, afin de déterminer la valeur du sketch s(mod1), 302, associée à la modalité mod1. La valeur w(mod1) est aussi envoyée vers la fonction de transformation `T' afin de générer une clé Sk(l) qui va être utilisé pour étendre 304 la mesure w(mod2). Ensuite, grâce à la clé secrète Sk(l), et la fonction d'enrôlement du secure sketch généralisé 305 on obtient s(modi,mod2) 306, le sketch qui est associé à la modalité mod2 et aussi à la modalité mod1 via la clé secrète Sk(l). L'étape de correction ou de recouvrement est schématisée à la figure 3B dans un exemple d'authentification à deux modalités. En entrée du premier secure sketch le procédé réalise une mesure w'(modi), 310, de la modalité mode qui, si elle est assez proche de w(modi), pourra être corrigée grâce au sketch s(modi) 302. Ensuite, la valeur de w(modi) 303 obtenu est transformée 'T' en une clé secrète Sk(l) qui donne l'emplacement des bits à ajouter dans la donnée issue du secure sketch suivant, sur la figure le secure sketch généralisé SSg2. La procédure de transformation en la clé secrète est détaillée plus loin dans la description. Au niveau du deuxième secure sketch généralisé SSg2, 305, le procédé prend en entrée une mesure bruitée w'(mod2) 306 de la modalité mod2 qui sera corrigée grâce au sketch s(modi,mod2) si elle est assez proche de la donnée initiale pour générer la mesure we(mod1, mod2) 307 qui est représentative des deux modalités mod1 et mod2 et qui permet l'authentification d'un individu, d'un composant ou d'un individu et d'un composant à partir de ces deux modalités. Ce schéma permet d'authentifier un composant électronique, par exemple, ou une personne, etc. par deux modalités car si l'une des deux 30 mesures de modalités n'est pas satisfaisante, l'authentification échoue. Ce système permet de ne pas stocker de données sensibles : seuls sont gardés en mémoires les sketches s(modi) et s(modi, mode) qui ne révèlent pas d'information sur les données initiales. Dans le cas d'un échec de l'authentification, il n'est pas possible 5 de savoir quelle modalité en est responsable ce qui est un avantage du point de vue de la sécurité. La figure 3C présente un exemple de secure sketch généralisé qui consiste en l'extension de la donnée w en une donnée we grâce à Sk puis l'application d'un secure sketch standard (un exemple de secure sketch : le 10 code offset). Le secure sketch généralisé comprend une phase d'enrôlement et une phase de reconstruction. Au cours de la phase d'enrôlement, on traite la donnée w grâce à une « clé » Sk, la donnée w est alors étendue en we de taille n+k : la fonction qui réalise cette « élongation » ou extension de taille 15 est appelée Extend. A partir de là, le procédé décrit met en oeuvre un secure sketch classique connu de l'Homme du métier et le tout forme le secure sketch généralisé qui permet d'obtenir la donnée étendue we. Lors de la phase d'enrôlement, on applique le secure sketch généralisé sur w pour obtenir la donnée s. La phase de reconstruction consiste à traiter la donnée 20 bruitée w' mesurée proche de w avec la clé secrète Sk 320 pour obtenir une valeur étendue w'e. On applique ensuite un secure sketch standard 321, 322, 323, sur w'e pour obtenir we. Dans certains cas, il est possible d'inverser l'élongation des données pour retrouver w, c'est ce que l'on appelle un « secure sketch généralisé recentré » détaillé dans le brevet déposé sous le 25 numéro FR 1005115 par le Demandeur intitulé « Procédé de reconstruction d'une mesure de référence d'une donnée confidentielle à partir d'une mesure bruitée de cette donnée, notamment pour la génération de clés cryptographiques ». Il y a donc en sortie du système, après correction de la donnée w', 30 la donnée we qui correspond à la donnée w étendue avec Sk : we=Extend(w,Sk) où Extend est une fonction qui sera définie plus loin et qui peut être vue comme une fonction de Sk et de la variable w permettant l'élongation des données : elle sera notée Extend(w,Sk). La donnée we est de taille n+k>n, donc tant que Sk est secret la sécurité sur we est augmentée par rapport à w. Lorsque l'on a besoin que ce soit une fonction de w paramétrée par Sk, nous la noterons Extendsk(w). Lorsque l'on souhaite retrouver la donnée d'origine à partir de la donnée étendue, nous noterons w=Extendsk 1(we) Cette manière de procéder permet de résoudre notamment les problèmes liés aux contraintes sur les codes correcteurs d'erreurs et de retrouver une donnée de la même taille que la donnée originelle indépendante de Sk. Lorsque la deuxième modalité est valide et que la première ne l'est pas, il en découle que la clé Sk(l) est erronée puisque w(modi) est faux comme il est illustré sur la figure 4A par le signe d'une croix sur la valeur . Il en est de même lorsque c'est la seconde modalité Mod2 qui n'est pas valide, voir la figure 4B. Généralisation à n secure sketches La figure 5A schématise le procédé selon l'invention où le nombre 20 de modalités choisies pour authentifier un utilisateur ou un objet est au nombre de n. II peut parfois être nécessaire d'utiliser plus de deux modalités pour identifier une personne, des objets, ou conjointement des personnes et des objets (par exemple plusieurs empreintes digitales, la voix, l'iris, 25 différents types de PUFs, combinaison des biométries et des PUFs...) ce qui conduit à cette généralisation. On retrouve toujours une étape d'enrôlement telle que celle décrite à la figure 3A, en prenant en compte les n modalités, ce qui conduit à la génération des secures sketches à partir de SS1 , SS2 généralisé, ....SS' 30 généralisé, aux clés Sk('), _Sel) correspondant à : 2969789' 16 Mod1 Modi Modn SS1 SS;généralisé SS~ généralisé s(mod1) s(mod1,...,modi) s(mod1, ...,modn) Sur la figure 5A, les étapes concernant la phase d'authentification mise en oeuvre par le procédé selon l'invention sont les suivantes : 1 ère étape 5 Mesure de la modalité mode qui donne la mesure bruitée w'(modi), 310, puis correction de la mesure bruitée en utilisant le sketch s(modl) et le secure sketch SS1, 301, on obtient la valeur w(modi) débruitée 311. 2ème étape 10 Transformation de la valeur w(modi) 311 débruitée pour obtenir une clé Sk(l) associée à la donnée w(modi), via la fonction de transformation `T'. Sème étape Mesure de la valeur bruitée w'(mod2) 312 correspondant à la 15 modalité 2, puis on corrige la valeur étendue en utilisant un secure sketch généralisé dans sa phase de correction avec la clé Sk(l) pour obtenir w(modi, mode) qui est fonction des deux modalités mode, mode, donc de la modalité à traiter et des modalités précédentes (ici mod1 seulement), 4eme étape On transforme par une fonction de tranformation 'T' la valeur w(modi, mode) en une clé Sk(2) qui va être utilisée notamment pour étendre la valeur mesurée pour la modalité 3 et ainsi de suite. Etape finale dans le cas d'une authentification multimodale On mesure la modalité modn, on obtient une valeur bruitée w'(modn) 317; on étend cette valeur bruitée en utilisant la clé Sk(n-l) obtenue pour la modalité précédente mod(n-1), puis on corrige la valeur w'(modn) étendue en utilisant le sketch s(modi, ...,modn) 318 pour obtenir la valeur débruitée w(modi ,...,modn) 320 qui correspond à un individu ou une chose que l'on cherche à authentifier en utilisant les n modalités. La référence 319 contient la fonction du secure sketch généralisé qui comporte le traitement pour « étendre » la taille de la donnée, et l'étape de recouvrement de la donnée we. Dans les exemples précédents, toutes les clés Sk font la même taille. Pour avoir un système simple on peut prendre toutes les modalités de la même taille sauf la première qui est plus longue de k bits. Pour remédier à ce problème, car dans certains cas on préférerait que toutes les données fassent la même taille, on prend la première donnée de la même taille que les autres et on lui ajoute k bits de façon déterministe ou bien on transforme le premier secure sketch en un secure sketch généralisé. Dans le cas où l'on voudrait que les tailles des modalités ne soient pas les mêmes sur chaque secure sketch, on peut adapter la taille des clés secrètes pour obtenir les tailles souhaitées. Il est aussi possible d'utiliser des fonctions de transformation différentes en fonction de leur position dans la chaîne. La fonction de transformation sera choisie notamment selon la taille des clés. Rem lacement du SS1 -ar un SS -énéralisé : Sans sortir du cadre de l'invention, il est possible pour exécuter la première étape d'utiliser un secure sketch généralisé. Pour cela, le procédé demande l'utilisation d'une seconde clé secrète que l'on notera S'k qui servira à l'extension des données w(modi) et w'(modi). Cette clé secrète devra être stockée contrairement à Sk qui peut être retrouvée chaque fois qu'elle est nécessaire. Cette action à pour effet d'augmenter la sécurité liée à w(modi) en augmentant sa taille grâce à l'extension. Description de la fonction de transformation La suite donne plusieurs exemples de fonctions de transformation pouvant être mises en oeuvre par le procédé selon l'invention à titre illustratif 30 et nullement limitatif. La fonction de transformation dépend notamment des types de données possibles en entrée et en sortie. Il y a trois types de données possibles en entrées (distance de Hamming, différence symétrique ou distance d'édition), pour le cas des distances autres que la distance de Hamming on effectue un prétraitement sur les données afin d'obtenir une chaîne de caractères de longueur fixe (on note C la chaîne obtenue par prétraitement). II y a aussi les trois même types de données possibles en sortie. La clé générée par la fonction de transformation est de la forme Sk = [(pose; ...; posé); (vals; ...; valk)] dans le cas où les distances de sortie sont des distances de Hamming et d'édition et Sk = [(éléments; , élémentk)] dans le cas de la différence symétrique. Dans le cas où les espaces d'entrée et de sortie sont munis de la distance de Hamming, la donnée w utilisée en entrée de la fonction de transformation est toujours une chaîne de bits de longueur constante et la sortie est une clé secrète qui constitue un ensemble de positions et de valeurs . Si l'on considère les trois distances précitées, distance de Hamming, différence symétrique ou distance d'édition, il y a donc 9 cas à considérer, 3 possibilités pour le type de données en entrée (distance de Hamming, différence symétrique ou distance d'édition) et 3 en sortie. Nous commencerons donc par décrire les deux cas restants avec la distance de Hamming en entrée puis nous verrons ensuite un exemple montrant comment modifier les données en entrée (prétraitement) pour que les méthodes décrites dans le cas de la distance de Hamming fonctionnent aussi pour des espaces d' entrée munis de la différence symétrique ou de la distance d'édition. Première variante de réalisation pour la fonction de transformation avec des données en entrée et en sortie qui sont dans un espace de Hamming La fonction de transformation, 'Transformation' ou 'T', prend en entrée une donnée notée pour la définition w = et elle en tire une clé Sk = [(pose; ..,; posk); (vals; ...; valk)] où les val; sont des bits et les pos; représentent les positions des bits de valeur val;. II faut donc choisir k positions parmi n emplacements. Plus formellement, soit P l'ensemble des n positions possibles (que l'on peut identifier à 10;1P'l où r.1 est la fonction 5 qui associe à un nombre x le plus petit entier naturel supérieur ou égal à x), on veut T : {0;lr -> Pk x {0;1}k . Propriétés de la fonction Cette fonction possède les propriétés suivantes : 1. Non-inversibilité. C'est-à-dire qu'à partir de la connaissance de Sk = 10 [(pose; ...; posk); (vals; ...; valk)] il n'est pas possible de retrouver de l'information concernant la donnée w. Soient wE {0 ;1 }m et Ske Pk x {0;1}k tels que Sk=T(w). Alors V Sk, H(w) = m. 2. Probabilités de distributions uniformes sur les valeurs de val, de pos et sur l'union de ces deux valeurs. On souhaite donc : 15 -Vi E 11;...;klVVALE 10;1}k,P[val; =VAL] = Zk - Vi E {1;...; k}, `dPOS E P, P[pos; = POS] = 1 n - Vi E {1;...; k},`dVAL E 10;lr,VPOS E P, P[val; = VAL, pas, = POS] = n * 2k Exemples Une méthode pour construire cette fonction de Transformation est 20 la suivante. Elle consiste en deux étapes, la première permettant de trouver les valeurs val; et la seconde les positions pos; associées à ces valeurs. Phase 1 : trouver les val; 25 On a en entrée une donnée w = W~...Wm et on veut en déduire k bits uniformes pour représenter les k valeurs de val;. 1. La première solution proposée est de choisir une fonction de hachage h dont l'ensemble d'arrivée est {0 ;1}k" avec e E N* (l'ensemble des entiers 2969789- 20 naturels non nuls) puis pour i = 1 ,...,k; val; _ (h(w));, c'est-à-dire que vali prend la valeur du ième bit du haché de w. 2. Une autre solution, un peu plus complexe à mettre en oeuvre, est de poser H = {1-11E , une famille de fonctions de hachage où 1 est un ensemble fini qui 5 possède au moins k éléments. Ensuite, pour i El, calculer: val; = $kj=, (h, (w))i où (h;(w))i représente le jiè' bit de h;(w). Phase 2 : trouver les pos; Le but de cette phase est de trouver uniformément k positions parmi n possibles et ce en utilisant w = wl...wm. La solution proposée dans cet 10 exemple est d'utiliser des registres à décalage à rétroaction linéaire plus connus sous l'abréviation anglo-saxonne « LFSR » (Linear Feedback Shift Register) pour générer une suite pseudo aléatoire de longueur supérieure à L = krlog2 ni. En ce qui concerne le LFSR, il faut choisir : a. Un polynôme de rétroaction de degré assez grand et qui permet 15 d'avoir une période très grande (supérieure au nombre de bits générés de façon pseudo-aléatoire dont nous avons besoin : L). b. Une graine (seed) égale à h(w) où h est une fonction de hachage. On obtient une séquence pseudo-aléatoire SEQ de longueur L = krlog2 nl . On découpe cette séquence en k sous-séquences de longueur l = [loge ni : 20 SEQ = seglII -.-Ilsegk. On pose post = seg1 mod n ; pour simplifier les notations, on met les seq; en base 10. Ensuite, pour trouver pos;, on part de pos;_ et on avance de seq; cases libres : pos; = f(pos;l; seqi). On sous-entend par « case libre » les cases qui ne sont pas encore occupées et, lorsque l'on arrive à la nième case, on repart à la première selon le schéma 25 de la figure 5B. Remarque 1 (choix de 1) A chaque fois que l'on se déplace pour trouver une nouvelle valeur de pos; on veut que ce déplacement soit compris entre 1 et au moins n cases. Il faut donc 1= r1og2 ni bits pour caractériser ce déplacement. 30 Exemple 1 Un LFSR est composé de registres à décalages qui sont initialisés (avec la graine) et qui évoluent grâce à des fonctions booléennes entre ces bascules dont la sortie est réinjectée à l'entrée des bascules. Sur l'exemple suivant, les fonctions booléennes sont des Xor et on modélise le LFSR avec des polynômes représenté à la figure 5C. A chaque cran d'horloge, tous les bits sont décalés vers la droite et le bit numéro 1 est remplacé par le Xor des bits 11, 13, 14 et 16. La modélisation avec des polynômes donne : 1. La graine (seed) : T(X) = X16 +X11 + X1° + X9 + X6 + X5 + X3 + X 10 2. Le polynôme de rétroaction : P(X) = X16 + X14 + X13 + X11 + 1 La graine correspond à l'état initial du système et le polynôme P permet de caractériser la rétroaction. De plus, nous avons besoin de polynômes de rétroaction qui permettent d'avoir des périodes très grandes pour le LFSR pour que la suite soit 15 pseudo-aléatoire. Il existe de nombreux polynômes qui ont les bonnes propriétés, comme par exemple P(X) = X19 +X16 +X1' +X14 +1 qui possède une période de 524287. Deuxième variante pour la fonction de transformation La méthode proposée maintenant est plus facile à implémenter 20 que celle utilisant les LFSR. Cette fonction possède toutes les propriétés souhaitées à savoir choisir les val; et les pos; en fonction de w et que ces choix semblent être le fruit du hasard. Rappel du problème à résoudre : 25 La fonction Transformation doit, à partir d'une donnée w=w1...wm, déduire une « clé secrète » Sk =[(pos1,...,posk) ;( val1,...,valk)] uniforme. Pour les val; : trouver k bits qui semblent être pris au hasard. Pour les pos; : trouver k positions parmi les n possibles de façon à ce que les positions semblent avoir été tirées au hasard. 30 Phase 1 : les val; Cette phase est exactement la même que la fonction de Transformation précédente : choisir une fonction de hachage h :{0 ;1}*->{0 ;Ire, EE N*. Pour i=1 à k, val;=(h(w));. Phase 2 : les pos; Cette phase se base sur KSA, l'algorithme de génération de la permutation de l'algorithme de chiffrement RC4. KSA de RC4 : Soit S un tableau de 256 cases. pour i=0 à 255 S[i] .=i 1a p :=0 pour i= 0 à 255 j :=(j+S[i]+ key[i mod keylength]) mod 256 inverser les valeurs de S[i] et de S[j] Adaptation de cet alqorithme au problème posé dans la présente invention 15 Ici S est un tableau de n cases indexées de 0 à n-1. On choisit une fonction de hachage h et on pose K=h(w). On découpe ensuite K en paquets de Iongueurrlog2 nl. Si le dernier paquet ne contient pas exactement r1og2 ni bits, on le jette : dans le cas contraire il y aurait la création d'un biais statistique. 20 On pose ensuite key[0] le premier paquet (en base 10), key[1 ] le deuxième, etc. Soit keylength le nombre de paquets. pour i=0 à n-1 S[i] .=i 25 p :=O pour i= 0 à n-1 j :=(j+S[i]+ key[i mod keylength]) mod 256 inverser les valeurs de S[i] et de SU] S contient maintenant n entiers de 0 à n-1 dans un ordre qui semble aléatoire 30 (c'est une permutation de {0,...,n-1}). On prend ensuite une liste publique de k indices (par exemple 0,...,k-1) et l'image de chacun de ces éléments par S contient une des k positions cherchées. Notations : Une notation supplémentaire est introduite lors du prétraitement 5 de la donnée en entrée pour les distances symétrique et d'édition : soit C la donnée une fois prétraitée. Distance de Hamming en entrée : w => méthode 1 ou 2 => sortie Différence symétrique ou distance d'édition en entrée : w => prétraitement => C => méthode 1 ou 2 => sortie 10 Récapitulatif : prétraitement/clé secrète Entrée / Hamming Différence Edition sortie Symétrique Hamming Non Non Non [(pose; ...; posé); Relemi; ...; Rpos,; ...; posé); (vals; ...; valk)] elemk)] (vals; ...; valk)] Différence Oui Oui Oui Symétrique [(pose; ...; posé); Relemi; ...; [(pose; ...; posk); (vals; ...; valk)] elemk)] (vals; ...; valk)] Edition Oui Oui Oui Rpos,; ...; posé); Relemi; ...; [(pose; ...; posé); (vals; ...; valk)] elemk)] (vals; ...; valk)] Dans la suite de la description, seront décrits les cas avec la distance de Hamming en entrée (différence symétrique ou distance d'édition en 15 sortie), puis nous verrons ensuite un exemple montrant comment modifier les données en entrée (prétraitement qui permet d'obtenir C) pour que les méthodes décrites dans le cas de Hamming fonctionnent aussi pour des données en entrées de type différence symétrique ou édition. Pour la distance symétrique en sortie avec une distance de Hamming en entrée(Hamming/ différence symétrique) Rappel de la distance appelée différence symétrique Soit M l'ensemble des parties d'un univers U de taille n, la différence symétrique entre deux éléments w et w' de M est le nombre d'éléments de U qui sont dans l'union mais pas dans l'intersection de w et w' : do(w,w')=l{xewuw', xewnw'}I Le but de la fonction Transformation est de trouver de façon déterministe k éléments de U à partir de w = Ces k éléments doivent sembler être pris au hasard et ils ne doivent pas révéler d'information sur w. Méthode 1 On se base sur l'algorithme KSA du RC4. Rappel de KSA du RC4 : Soit S un tableau de 256 cases. pour i=0 à 255 S[i] =i p:=0 pour i=0 à 255 j:=(j+S[i]+key[i mod keylength]) mod 256 Inverser les valeurs de S[i] et de S[j] Adaptation de cet algorithme au problème résolu dans la présente demande de brevet : Ici S est un tableau de n cases indexées de 0 à n-1 dans lesquelles on met 25 les éléments de U. - On choisit une fonction de hachage h et on pose K=h(w). - On découpe ensuite K en paquets de Ilog2 ni bits (ici I.1 désigne « partie entière supérieure »). - Si le dernier paquet ne contient pas exactement (loge n1 bits, on le 30 jette : dans le cas contraire il y aurait la création d'un biais statistique. - On pose ensuite key[0] le premier paquet (en base 10), key[1 ] le deuxième, etc. Soit keylength le nombre de paquets. pour 1=0 à n-1 S[i] .=i p:=0 pour 1=0 à n-1 j:=(j+S[i]+key[i mod keylength]) mod n Inverser les valeurs de S[i] et de SU] ~o S contient maintenant les n éléments de U indexés de 0 à n-1 dans un ordre qui semble aléatoire (c'est une permutation de {0,...,n-1}). - On prend ensuite une liste publique de k indices (par exemple 0,...,k-1) et l'image de chacun de ces éléments par S contient un des k éléments cherchés. 15 Méthode 2 Le but est de trouver uniformément k éléments parmi n possibles et ce en utilisant w = w~ ...wm. On indexe les n éléments de U. La solution proposée ici est d'utiliser des registres à décalage linéaires à rétroaction ou en abrégé anglo- 20 saxon LFSR (Linear Feedback Shift Register) pour générer une suite pseudo aléatoire de longueur supérieure à L = kllog2 nI. En ce qui concerne le LFSR, on choisit : 1. Un polynôme de rétroaction de degré assez grand et qui permet d'avoir une période très grande (supérieure au nombre de bits générés de façon 25 pseudo-aléatoire dont nous avons besoin : L). 2. Une graine (seed) égale à h(w) où h est une fonction de hachage. Nous obtenons avec ce LFSR une séquence pseudo-aléatoire SEQ de longueur L = kllog2 nI. On découpe cette séquence en k sous-séquences de longueur 1 = 30 Ilog2 nl : SEQ = seg1 II - - -Ilsegk. On pose post = seg1 mod n ; pour faciliter les choses, on met les seq; en base 10. Ensuite, pour trouver post, on part de posi_1 et on avance de seq; cases libres : pos; = f(posi_1; seqi). On sous-entend par « case libre » les cases qui ne sont pas encore occupées et lorsque l'on arrive à la nième case on repart à la première. Remarque 1 (choix del) ; à chaque fois que l'on se déplace pour trouver une nouvelle valeur de pos; on veut que ce déplacement soit compris entre 1 et au moins n cases. II faut donc 1 = Ilog2 nl bits pour caractériser ce déplacement. Dans chacune des n cases on met les éléments de U dans leur ordre d'indexation. Les cases « prises » (colorées) correspondent aux 1 o éléments cherchée. Exemple 1 de LFSR. Un LFSR est composé de registres à décalages qui sont initialisés (avec la graine) et qui évoluent grâce à des fonctions booléennes entre ces bascules dont la sortie est réinjectée à l'entrée des bascules. Sur l'exemple 15 suivant, les fonctions booléennes sont des Xor et on modélise le LFSR avec des polynômes. A chaque cran d'horloge, tous les bits sont décalés vers la droite et le bit numéro 1 est remplacé par le Xor des bits 11, 13, 14 et 16. La modélisation avec des polynômes donne : 20 1. La graine (seed) : T(X) = X16 + X" + X10 + X9 + X6 + X5 + X3 + X 2. Le polynôme de rétroaction : P(X) = X16 +X14 +X13 +X11 + 1 La graine correspond à l'état initial du système et le polynôme P permet de caractériser la rétroaction. De plus, nous avons besoin de polynômes de rétroaction qui 25 permettent d'avoir des périodes très grandes pour le LFSR pour que la suite soit pseudo-aléatoire. II existe de nombreux polynômes qui ont les bonnes propriétés et qui sont faciles à trouver, comme par exemple P(X) = X19 +X16 +X17 +X14 +1 qui possède une période de 524287. Pour la distance d'édition en sortie avec une distance de Hamming en entrée: (Hamming/édition) Rappel de la distance d'édition :la distance d'édition entre les chaines de caractères w,w'E M c F* (F un alphabet) est le nombre minimum de suppressions et d'insertions nécessaires pour passer d'une chaîne à l'autre. Le but de la fonction Transformation est de trouver de façon déterministe k valeurs (de F) à ajouter à k positions. Les k positions sont choisies parmi les n+k positions possibles où n est la taille de la plus petite chaîne de caractères de M. La clé secrète sera de la forme Sk =[(posi,...,posk) ;( vali,...,valk)]- Méthode 1 Phase 1 : trouver les val; On a en entrée une donnée w = wl...wm et on veut en déduire k 15 bits uniformes pour représenter les k valeurs de val;. 1. La première solution que nous proposons est de choisir une fonction de hachage h dont l'ensemble d'arrivée est {0 ;Ir avec EE N* puis pour 1 i = 1 ,...,k; val; _ (h(w));, c'est-à-dire que vali prend la valeur du ième bit du haché de w. 20 2. Une autre solution, un peu plus complexe à mettre en oeuvre, est de poser H = {h;};E , une famille de fonctions de hachage puis de calculer pour i E 1 : val; = XORk =1(hi(w))i où (h;(w))i représente de jème bit de h;(w). On utilise ici une fonction Xor mais on peut tout aussi bien utiliser n'importe quelle fonction booléenne dont la sortie est uniforme si l'entrée l'est. 25 Phase 2 : trouver les pos; Cette phase se base sur l'algorithme KSA du RC4. Rappel de KSA du RC4 : Soit S un tableau de 256 cases. pour i=0 à 255 30 S[i] .=i p:=0 pour i=0 à 255 j:=(j+S[i]+key[i mod keylength]) mod 256 Inverser les valeurs de S[i] et de SU] Adaptation de cet algorithme au problème posé dans ce cas : Ici S est un tableau de n+k cases indexées de 0 à n+k-1. - On choisit une fonction de hachage h et on pose K=h(w). - On découpe ensuite K en paquets de 1log2 n+k 1 bits (ici 1.1 désigne « partie entière supérieure »). - Si le dernier paquet ne contient pas exactement 11og2 n+k 1 bits, on le jette : dans le cas contraire il y aurais la création d'un biais statistique. - On pose ensuite key[0] le premier paquet (en base 10), key[1 ] le deuxième, etc. Soit keylength le nombre de paquets. pour i=0 à n+k -1 S[i] =i p:=0 pour i=0 à n+k -1 j:=(j+S[i]+key[i mod keylength]) mod n+k Inverser les valeurs de S[i] et de SU] S contient maintenant n+k entiers de 0 à n+k -1 dans un ordre qui semble aléatoire (c'est une permutation de {0,...,n+k-1}). - On prend ensuite une liste publique de k indices (par exemple 0,...,k-1) et l'image de chacun de ces éléments par S contient une des k positions cherchées. Méthode 2 Cette méthode consiste en deux étapes, la première permettant de trouver les valeurs val; et la seconde les positions pos; associées à ces valeurs. Phase 1 : trouver les val; (c'est la même que pour la méthode 1 de la 30 distance d'édition) 2969789. 29 On a en entrée une donnée w = wl...wm et on veut en déduire k bits uniformes pour représenter les k valeurs de val;. 1. La première solution que nous proposons est de choisir une fonction de hachage h dont l'ensemble d'arrivée est {0 ;Ir avec EE N* puis pour 1 i = 1 5 ,...,k; val; _ (h(w));, c'est-à-dire que vali prend la valeur du ième bit du haché de w. 2. Une autre solution, un peu plus complexe à mettre en ceuvre, est de poser H = {1-11E ; une famille de fonctions de hachage puis de calculer pour i E 1 : val; = XORk =1(hi(w))i où (h;(w))i représente de jème bit de h;(w). On utilise ici 10 une fonction Xor mais on peut tout aussi bien utiliser n'importe quelle fonction booléenne dont la sortie est uniforme si l'entrée l'est. Phase 2 : trouver les pos; Le but de cette phase est de trouver uniformément k positions parmi n+k possibles et ce en utilisant w = w~ ...wm. La solution que nous 15 proposons est d'utiliser des LFSR (Linear Feedback Shift Register) ou registres à décalage linéaires à rétroaction pour générer une suite pseudo aléatoire de longueur supérieure à L = kllog2 (n+k)I. En ce qui concerne le LFSR, nous choisissons : 1. Un polynôme de rétroaction de degré assez grand et qui permet d'avoir 20 une période très grande (supérieure au nombre de bits générés de façon pseudo-aléatoire dont nous avons besoin : L). 2. Une graine (seed) égale à h(w) où h est une fonction de hachage. Nous obtenons avec ce LFSR une séquence pseudo-aléatoire SEQ de longueur L = kllog2 (n+k)I. 25 On découpe cette séquence en k sous-séquences de longueur 1 = Ilog2 (n+k)I SEQ = segl II - - -Ilsegk. On pose post = seg1 mod (n+k) ; pour faciliter les choses, on met les seq; en base 10. Ensuite, pour trouver pos;, on part de pos;_ et on avance de seq; cases libres : pos; = f(pos;_1; seqi). On sous-entend par « case libre » les cases qui ne sont pas encore occupées et lorsque l'on arrive à la nième case on repart à la première. Les cases « occupées » correspondent aux positions pos;. La notation D1/D2 où D1 et D2 représentent la distance de Hamming, la différence symétrique ou la distance d'édition signifie que l'espaceen entrée est muni de la distance D1 et l'espace en sortie de la distance D2. Nous considérons les différents cas que nous regroupons lorsqu'il peuvent être traités suivant la même méthode. Différence symétrique/distance de Hamming, Différence symétrique/Différence symétrique, Différence symétrique/édition Dans les solutions décrites précédemment (c'est-à-dire avec la distance de Hamming en entrée et l'une des trois autres distances en sortie), la donnée en entrée en une chaîne de m bits avec m un entier fixé. Il est donc nécessaire pour utiliser les méthodes précédemment décrites d'effectuer une prétransformation de la donnée en entrée : nous en donnons ici un exemple. Lorsque la donnée en entrée est un ensemble de 1 éléments parmi m, la solution que nous proposons ici est d'indexer ces éléments et de créer une chaîne de caractères C de longueur m qui possède en position i un 1 si l'élément i est présent, un 0 sinon. Il est ensuite possible avec C d'utiliser les méthodes décrites lorsque la donnée en entrée est une chaîne de caractères. Distance d'édition/distance de Hamming, Distance d'édition/Différence symétrique, Distance d'édition/Distance d'édition Il en est de même pour la distance d'édition : on donne ici un 25 exemple de prétraitement possible pour pouvoir utiliser les méthodes décrites avec la distance de Hamming. Le problème avec une entrée dans un espace muni de la distance d'édition est que sa taille n'est pas fixe. Pour remédier à ce problème, nous proposons d'appliquer une fonction de hachage h :10;1Y ---> {0;1}m sur la 30 donnée w. On obtient alors une chaîne de caractères C=h(w) de taille fixe avec laquelle il est possible d'utiliser les méthodes décrites pour la distance de Hamming. Le système et le procédé décrits précédemment peuvent être généralisés à plusieurs types d'applications illustrées aux figures 6A à 8 5 Rem - lacement du SS1 - ar un extracteur flou fi - ure 6A: Sur la figure 6A, en sortie du premier secure sketch, au lieu d'appliquer w(modi) en entrée de la fonction Transformation on applique h(w(modi)) 600 où h est une fonction de hachage. Ceci a pour effet que l'entrée de Transformation est uniforme. De plus, si un attaquant possède la 10 clé secrète et qu'il réussi à inverser la fonction Transformation, il n'aura pas accès à la donnée w(modl). Il est possible d'appliquer une fonction de hachage sur tous les w(mod1,...,modi) pour i=1 à n-1. Remplacement du SS2 par un extracteur flou fiqure 6B: Dans le cas représenté à la figure 6B, on applique une fonction de 15 hachage h à la sortie w(modi,mod2) 601 du secure sketch. De cette façon, il est possible de vérifier grâce au haché que la réponse du système correspond à une donnée biométrique valide sans avoir à stocker cette donnée ce qui est un bon point pour la sécurité. De plus, ce haché permet d'associer à chaque personne physique une clé cryptographique utilisable 20 dans de nombreuses applications. Sans ce haché la donnée w(modi,mod2) est inutilisable en tant que clé cryptographique car elle n'est pas uniforme. Notons que si lh(w(modi,mod2))l Remplacement des deux secure sketches par des extracteurs flous : II est possible de remplacer à la fois le premier secure sketch par un extracteur flou et le deuxième par un extracteur flou généralisé. Ceci est également valable pour la généralisation à n quelconque plus grand que 2. Troncature des mesures : II est possible de tronquer directement les mesures biométriques effectuées pour que leurs tailles d'adaptent à un secure sketch qui est contraignant au niveau de la taille de ses entrées. Exemple : pour chaque modalité modi, si la modalité contient y bits et que le SS en prend x en entrée, alors on ne conserve par exemple que les x premiers bits de la modalité. D'autres solutions sont possibles, comme par exemple enlever les y-x premiers bits en position paire. L'essentiel est de conserver x bits de 15 façon connue et déterministe. n extracteurs flous : Selon un mode de mise en ceuvre du procédé selon l'invention, il est possible de généraliser les n secure sketches généralisés en n extracteurs flous généralisés ou extracteurs flous généralisés recentrés. 20 Secure sketches et extracteurs flous : Dans la même idée que précédemment, il est possible de laisser k secure sketches (généralisés ou recentrés) et convertir les n-k restants en extracteurs flous(généralisés ou recentrés). Les étapes du procédé décrites précédemment sont applicables à 25 des PUFs (Physical Unclonable Functions) : Un PUF est une fonction réalisée sur un circuit électronique qui envoie des challenges et reçoit les réponses. Une ou plusieur de ces réponses forme la sortie du PUF. Ces challenges sont basés sur des éléments physiques aléatoires choisis de telle sorte qu'un PUF donnera des 30 réponses similaires sur un même circuit et des réponses différentes sur deux circuits distincts. On utilise par exemple le temps de parcours sur des chemins différents, l'initialisation des transistors, des propriétés optiques... Ces réponses peuvent faire office de modalités pour authentifier des composants sur des circuits électroniques. Les modalités en entrée des secure sketches peuvent sans problème être des données biométriques comme par exemple la voix, les empreintes digitales, l'iris, la rétine, le visage... il est possible, par exemple, d'authentifier une unique personne en mesurant plusieurs de ses données biométriques mais il est aussi possible d'authentifier plusieurs personnes simultanément grâce à ce système. De plus, le procédé selon l'invention permet d'éviter que l'on trouve quelle modalité est erronée lorsque l'authentification échoue. Les données pouvant être de différentes tailles et le procédé pouvant mettre en oeuvre différentes métriques ce qui peut impliquer des codes correcteurs ou des secure sketches différents. Le procédé permet de résoudre ce genre de problèmes car les secure sketches sont indépendants les uns des autres. Traitement des modalités : Quel que soit le type de modalités que l'on utilise (données biométriques ou PUFs), la taille de ces modalités n'est pas forcément adaptée à l'entrée des secure sketches. Pour combler cette lacune, nous proposons le schéma suivant représenté sur la figure 7 : on concatène toutes les modalités que l'on possède puis, pour chaque secure sketch, on prend des données de la taille souhaitée. Les figures 8, 9 et 10 schématisent un exemple de procédé selon l'invention mettant en oeuvre une authentification croisée. Authentification croisée : Le principe de base est le suivant. On passe d'abord dans le secure sketche 1 SS1 pour en déduire une première clé secrète Sk(l) que l'on applique avec la modalité 2 au secure sketch SSg2 puis, de là, on dérive une seconde clé secrète que l'on applique avec la première modalité pour obtenir la sortie. L'exposant (i) indique que c'est la ième fois que l'on passe dans le secure sketch. Les numéros entourés sur les figures représentent l'ordre de passage, la figure 9 étant une vision développée de la figure 8 et la figure 10, l'exemple dans le cas de la phase d'enrôlement. En ce qui concerne la phase d'enrôlement, on a besoin ici de trois sketches. Un pour la première utilisation de SS1, un pour celle de SS2 et un pour la deuxième utilisation de SS1 qui dépend de la deuxième clé secrète. La figure 8 montre qu'après l'étape 1, le SS1 est un secure sketch standard, alors que lors du deuxième passage, c'est-à-dire après l'étape 3, celui-ci est un secure sketch généralisé car il prend une clé secrète en entrée. La première solution, qui est la plus simple, est d'utiliser deux secures sketches différents SS1 et SS3. Lorsque le procédé utilise pour la deuxième fois mod1 (avec SSg3), une solution consiste à garder la première mesure car cela permet de ne faire qu'une seule mesure pour chacune des modalités. En notant w(2)(mod1)= w(')(mod1) si les mesures de mod1 sont correctes, si la mesure de la modalité 2 est fausse, alors la valeur de w(2)(mod1) sera différente de celle de w(')(mod1). Le système global permet donc de retrouver la valeur de la mesure effectuée sur mod1 lors de l'enrôlement en fonction de la mesure de mod1 et mod2. Sans sortir du cadre de l'invention, il est possible au lieu d'utiliser un secure sketch généralisé SSg3 lors de la phase de l'enrôlement d'utiliser le premier secure sketch que l'on peut généraliser. Lors de la première utilisation, il est nécessaire d'avoir un secure sketch standard, la solution est alors de définir une clé Ski) qui peut être publique et qui sera utilisée lors de la première utilisation du SSgi. Selon un autre mode de réalisation, le procédé selon l'invention peut mettre en oeuvre des secure sketches généralisés recentrés définis en résumé de la manière suivante. Des détails et des explications sont donnés dans la demande de brevet déposée le même jour que la présente demande de brevet et explicité en relation avec les figures 11 à 17B. Un « secure sketch généralisé recentré » permet de retrouver toutes les propriétés du secure sketch standard sans les contraintes liées aux codes. Le principe mis en oeuvre de créer un secure sketch généralisé recentré qui consiste en un secure sketch généralisé suivit de la fonction Extendsk-1 (800 figure 11) obtenue à partir de la fonction Extendsk. La fonction Extendsk-' permet notamment à la donnée en sortie du système de retrouver sa taille d'origine et de perdre sa dépendance en la clé Sk. Une des applications possibles des secure sketches généralisés recentrés (abrégés SSgr dans la suite) est l'utilisation dans un système qui requiert un renouvellement régulier de la clé Sk car, étant donné que la sortie du système est indépendante de Sk, le renouvellement est possible sans modifier la donnée en sortie du système. Cette application a un avantage certain lorsque la donnée en sortie sert à générer une clé cryptographique : il est alors possible de modifier Sk sans modifier la clé cryptographique. La figure 12 représente schématiquement un diagramme montrant la différence entre les étapes mises en ceuvre pour un secure sketch généralisé et les étapes mises en ceuvre pour un secure sketch généralisé recentré. Propriétés de la fonction Extend : - Enrôlement : Extend(w,Sk)=we - Correction : soit d la distance, on veut que d(we,we') = d(Extend(w,Sk), Extend(w',Sk)) = d(w,w'). Si d(Extend(w,Sk), Extend(w',Sk)) = d(w,w') et distance d'édition (dE). Ces distances correspondent aux secure sketches classiques existants. Les fonctions Extend associées à ces distances seront respectivement notées ExtendH, Extendo et ExtendE. Définition : secure sketch qénéralisé recentré (SSgr) : Comme il a été vu précédemment, la fonction Extend utilisée dans la définition des secure sketches généralisés est utilisée pour définir la fonction Extendsk. La définition de la fonction Extend dépend de la métrique utilisée. La fonction Extendsk est inversible pour les distances de Hamming et d'édition. II est alors possible d'appliquer son inverse Extendsk-' à la sortie du système pour inverser l'élongation de la donnée et perdre ainsi la dépendance en la clé Sk. Nous obtenons alors ce que nous appelons un secure sketch généralisé recentré (SSgr). La donnée en sortie d'un secure sketch généralisé recentré est 15 indépendante de la clé Sk et possède la même taille que la donnée en entrée ce qui n'est pas le cas pour un secure sketch généralisé. Rappel: Extendsk(w)=Extend(w,Sk) et Extend-'sk(w) est l'inverse de Extendsk(w). Un secure sketch généralisé recentré est un secure sketch 20 généralisé auquel on a ajouté la fonction Extendsk-' à la sortie. La donnée en sortie est exactement w (si w' assez proche de w) et ce indépendamment de la clé Sk. Dans le cas du secure sketch généralisé recentré deux possibilités peuvent se présenter: 25 Sk publique : il n'est dans ce cas pas nécessaire d'avoir une clé Sk de bonne qualité du point de vue de la sécurité (elle sert juste à s'affranchir des contraintes liées aux codes correcteurs) et on peut la stocker sans se soucier de sa protection. Sk privée : le sortie du système reste indépendante de Sk mais il n'est 30 pas possible de corriger w' en w pour un attaquant qui ignore Sk. De plus, la sécurité du secure sketch généralisé recentré est la même que celle d'un secure sketch, laquelle est maîtrisée. Construction du secure sketch qénéralisé recentré dans le cas d'un espace muni de la distance de Hamminq Le secure sketch généralisé dans un espace de Hamming a sa fonction Extend {sk,H} qui est inversible. Il est donc possible de dériver de ce secure sketch généralisé un secure sketch généralisé recentré SSgr. Pour inverser cette fonction Extend (Un, il suffit de supprimer les bits qui ont été rajoutés aux positions que l'on connaît grâce à Sk. 7o Définition : (Extend -'{sk,H}) On définit la fonction Extend -'{sk,H) qui prend en entrée we E F" et un paramètre Sk de la forme Sk =[(pos,,...,posk),(val,,...,valk)], en sortie on a wE F"' où n=n'+k, qui a les propriétés suivantes : Pour i=1 à k, supprimer les bits en position pos;. 15 - Concaténer les bits restants dans leur ordre d'apparition. Construction du secure sketch qénéralisé recentré dans le cas où l'espace est muni de la distance d'édition La fonction Extend {sk,E} est parfaitement inversible pour les mêmes raisons que dans le cas de la distance de Hamming. Il est donc 20 possible de fabriquer un SSgr avec la distance d'édition. Il faut noter que cette fonction se base sur la chaîne de caractères la plus courte dans l'ensemble des chaînes possibles. II est donc préférable que la chaîne la plus courte ait quand même une certaine longueur sinon on ne peut pas beaucoup jouer sur les pos;. Dans le pire des cas, celui ou n=0, les pos; sont 25 tous prédéterminés (pos;=i ; il n'y a pas d'autre possibilité) mais il reste encore IAlk façons de réaliser l'extension sur les O+k=k premiers bits. Définition : (Extend "I{sk,E}) On définit la fonction Extend "I{sk,E) qui prend en entrée we E F"+k et Sk un paramètre de la forme Sk = [(pos,,..., posé ),(val,,...,valk )], en sortie on a 30 wE F" , qui a les propriétés suivantes : Pour i=1 à k, supprimer les bits en position post. Concaténer les bits restants dans leur ordre d'apparition. Quelques exemples de secure sketches généralisés recentrés ayant été donnés, la figure 13 montre un exemple de procédé d'authentification tel que décrit précédemment dans lequel un secure sketch généralisé est remplacé par un secure sketch généralisé recentré noté SSgr. On remarque que la donnée en sortie d'un « étage » par exemple en sortie de SS2gr 900 ne dépend que la dernière modalité, Le dans l'exemple, la modalité mode. Cependant le sketch s(modi, mode) dépend toujours des deux modalités mode et mode car il corrige w'e(modi, mode). La modalité mode ne peut être corrigée que si la modalité mode était valide et la donnée en sortie est w(mod2), c'est-à-dire une donnée qui ne dépend que de la seconde modalité. Pour cela, on a appliqué la fonction Extend-'sk à la donnée we(mod2)=w(modi,mod2) ce qui a eu pour effet de supprimer les l'élongation dépendant de mod1 (qui était la seule dépendance en mod1 de la donnée). On retombe alors sur w(mod2), mesure corrigée de la modalité 2. Sur la figure 14, les sketches ont aussi une perte de dépendance : le sketch du secure sketch généralisé associé à la modalité i ne dépend plus que de mod; et de mod;_I. En effet, il dépend de mod; et de Sk('-l) avec Sk(") qui ne dépend plus désormais que de mod;_ (contrairement à la construction précédente où seuls des secure sketches généralisés étaient utilisés, le sketch dépendait alors de mode, ..., mod;). Ce schéma peut être caractérisé avec le triplet (n,I,C) où n est le nombre total de secure sketches utilisés (secures sketches généralisés, secure sketches généralisés recentrés, secure sketch « classique » en position 1) et 1 est le nombre de secure sketches généralisés SSg comptés à partir de la fin du système immédiatement précédés par un SSgr. C est une chaîne de n-1+1 bits qui spécifie sur 2 bits pour le secure sketch 1 si c'est un SS (bits 11), un SSg (bits 00) ou un SSgr (bits 01) et sur 1 bit pour les secure sketches 2 à n-I si ce sont des SSg (bit à 0) ou des SSgr (bit à 1). Ce système correspond au triplet (n, 1, 11 1...1). Les figures 14A et 14B schématisent l'enrôlement associé à l'utilisation de secure sketches généralisés recentrés. La figure 15A schématise un exemple de mise en oeuvre du procédé avec un certain nombre de modalités à authentifier dans le cas d'une utilisation d'une chaîne de traitement dans laquelle on utilise un secure sketch SS., 901 comme premier élément, suivi de plusieurs secure sketches généralisés SSg2 à SSgr_,, 902, suivi d'un secure sketch généralisé recentré SSgr'.1+1, 903, suivi de plusieurs secure sketches généralisés SSgr,_I.2 à SSgr, 904. Problématique : un certain nombre de modalités doivent être authentifiées, n en l'occurrence, mais avec la condition que la donnée en sortie du système ne dépende que des 1 dernières modalités. Lorsque l'on souhaite que la donnée en sortie ne dépende que des 1 dernières modalités (1 pour limite), il suffit de perdre la dépendance sur la n-1+1 ième modalité en utilisant un secure sketch généralisé recentré SSgr à la n-1+1 ème place. Ceci peut être schématisé sur les figures 15A et 15B, en représentant les secure sketches généralisés SSg et les secure sketches généralisés recentrés SSgr. On remarque que jusqu'à la modalité n-1 les dépendances s'accumulent puis au niveau de la modalité n-1+1 on perd toutes les dépendances en les modalités précédentes. Cela est dû à la présence du secure sketch généralisé recentré sur la modalité n-1+1. Remarque : 1=n correspond au cas d'utilisation classique (la donnée en sortie du système dépend de toutes les modalités, i.e. les n dernières) et 1=1 correspond au cas où la sortie du système ne dépend que de la dernière modalité. Caractérisation : Le cas présenté sur la figure 15B est le cas optimal d'utilisation, il correspond au triplet (n, I, 00 0...0) que l'on pourra noter 30 simplement (n,l). Les figures 16A et 16B représentent un exemple de généralisation de l'utilisation de secure sketches généralisés et de secure sketches généralisés recentrés. Le cas le plus général en utilisant à la fois des SSg et des SSgr est la 5 possibilité que chaque secure sketch soit : soit un SSg soit un SSgr. Pour n secure sketches il y a donc 2" possibilités. Cas particuliers : tous les SS sont des SSg : on est dans un premier cas de d'application 10 tous les SS sont des SSgr : on est dans un deuxième cas d'utilisation un SSgr et les autres SS sont des SSg : on est dans le cas avec limite de dépendance (notée I) . Il est possible de modéliser ce cas général de la façon représentée à la figure 15C. La donnée en sortie du système dépend de la 15 dernière modalité qui est en entrée d'un SSgr ainsi que toutes les modalités suivantes (les 4 derniers blocs sur le schéma). Une autre façon de voir les choses est que la donnée en sortie du système dépend de toutes les modalités en partant de la dernière tant que des SSg sont utilisés (en partant de la fin du système). Lorsque en partant de la fin du système on tombe sur 20 un SSgr, la donnée en sortie en dépend mais ne dépendra pas des modalités qui ont un indice inférieur (ou une numérotation inférieure). Ainsi, si la i-ème modalité est utilisée avec un SSgr et que les modalités suivantes notées 1+1 à n sont toutes utilisées avec un SSg, alors la sortie du système va dépendre des modalités i à n. 25 Avec la caractérisation choisie précédemment, le système (n,I,C) peut être représenté à la figure 16A. Les figures 16A et 16B représentent un exemple dans le cas d'un triplet (n, I, C). Rappel : on définit le système par les trois paramètres suivants : n : nombre de secure sketches (SS, SSg ou SSgr) utilisés 30 1 : la limite, correspond à la plus longue chaîne de SSg en partant de la fin et en incluant le premier SSgr. C : chaîne de n-1+1 bits qui représentent les n-I premiers SS (sur 2 bits pour le premier SS et 1 bit pour chacun des SSi pour i=2 à n-()(voir description complète plus haut). Dans le cas d'utilisation que nous définissons comme optimal, 5 C=00 0...0, c'est-à-dire qu'il y a un SSgr en position n-1+1 et que tous les autres blocs sont des SSg. Il est cependant possible d'avoir à la fois des SSg et des SSgr avant la limite (1). Par exemple si on souhaite extraire une donnée qui ne dépend 10 que des modalités 4 et 5 avec authentification des 5 premières modalités, on place un SSgr en position 4 et un SSg en position 5. On récupère ensuite la donnée en sortie du SSg5 figure 16A. Plus généralement, figure 16B, pour récupérer une donnée avant la limite qui dépend de l' modalités et qui nécessite l'authentification 15 multimodale des m premières modalités, on place un SSgr en position m-l'+1 et des SSg aux positions m-l'+2, ..., m. On peut réitérer le processus sur les modalités qui précèdent la limiter. Dans le cas extrême où l'on souhaite obtenir une donnée qui ne dépend que de la modalité m mais qui nécessite l'authentification des m 20 premières modalités, il suffit de placer un secure sketch généralisé recentré (SSgr) en position m. Le type des autres blocs (SSg ou SSgr) n'a alors aucun influence sur la dépendance de cette donnée. La variante de mise en oeuvre qui consiste à utiliser uniquement des secure sketches généralisés recentrés (SSgr) offre notamment les 25 avantages suivants : - Chaque donnée intermédiaire ne dépend que de la modalité courante, - Chaque sketch dépend de la modalité courante ainsi que de la modalité précédente, - La donnée en sortie du système ne dépend que de la dernière 30 modalité : préférable si on est susceptible de changer une modalité (sauf la dernière) sans changer la donnée en sortie du système, et - En cas de modification/remplacement d'une modalité : refaire l'enrôlement de la modalité suivante, les autres restes inchangés. La figure 17 représente un exemple de dispositif permettant la 5 mise en oeuvre du procédé selon l'invention. Le dispositif d'authentification selon l'invention comprend une unité de calcul 20 qui contient les différents SS implémentés pour les deux phases (enrôlement et correction) ainsi que la fonction `T' et une fonction de hachage si on souhaite générer une clé cryptographique. 10 Dans la phase d'initialisation, les modalités issues des capteurs 21 sont traitées dans l'unité de calcul 20 avec les SS en phase d'enrôlement puis les sketches sont stockés dans une mémoire de stockage 22. Les clés secrètes Sk calculées sont enregistrées sur un support d'enregistrement 23 et sont effacées dès qu'elles ne sont plus nécessaires. 15 Dans la phase de fonctionnement de l'invention, l'unité de calcul 20 se sert des modalités mesurées et des sketches stockés pour générer à nouveau les Sk, débruiter les modalités et retourner w(mod1,...,modn) ou bien une clé cryptographique. Le procédé et le système selon l'invention présentent notamment 20 les avantages suivants : - Une indépendance vis-à-vis des moyens techniques générant les modalités, - La taille des modalités et les métriques utilisées pouvant être différentes, utilisation de codes correcteurs différents, 25 - Intégrable dans un système multimodal existant, - En cas d'échec de l'authentification, l'erreur est propagée en fin de chaîne.