Brevet FR2782431A1 — publié le 20000218

La présente invention concerne un procédé d'authentification à algorithme symétrique présentant la caractéristique principale que, à chaque authentification de deux parties entre elles, appelées communément A et B, un calcul cryptographique avec une clé variable, appelée K', est effectué. L'invention concerne plus précisément les calculs cryptographiques cités ci-dessus lors d'une authentification des deux parties, appelées A et B, indépendantes l'une de l'autre dans le cadre d'échange de données. Cela peut être entre un PC et un serveur, un lecteur et un serveur, une carte à puce et un lecteur de carte à puce comme, par exemple, un distributeur de billets de banque dans le cadre de l'utilisation d'une carte à puce appelée A par un utilisateur qui, souhaitant se procurer quelques billets de banque, se rend sur un lieu comportant un distributeur de billets, appelé B. Plus particulièrement, les deux parties A et/ou B peuvent être considérées comme une carte à puce et/ou un lecteur. Il est connu de l'homme du métier que les problèmes de sécurité sont cruciaux pour un bon fonctionnement d'appareils du type distributeurs de billets et carte à puce. Ces soucis sont l'objet de protections continues et toujours plus efficaces pour rendre une attaque de plus en difficile à commettre. Pour expliquer cet état de fait, dans le domaine technologique de la cryptologie, il est connu de dénommer les deux parties devant communiquer entre elles A et B. D'une manière plus technique et scientifique, le procédé consiste en un certain nombre d'étapes. Dans le détail, A, qui possède une clé secrète K, choisit un aléa R ou nombre aléatoire appelé aussi message. A envoie cet aléa R à B, qui possède également la même clé secrète K. B calcule un résultat, à l'aide d'un algorithme symétrique de chiffrement ALG, appelé r par la formule suivante: r = ALG[K] (R), r est le résultat du chiffrement du message R avec l'algorithme ALG et la clé secrète K. L'algorithme dénommé ALG est un algorithme de chiffrement symétrique. Cela peut être le DES (Data Encryption Message), le triple DES, l'IDEA, etc. Cette opération est réalisable car la clé secrète K est connue des deux parties A et B et seulement par A et B. Ensuite, B envoie le résultat r à A. Ce dernier, A, calcule alors le résultat r' par la formule suivante: r' = ALG [K] (R). Si le nombre r est égal au résultat r' alors B est authentifié. L'authentification de B par A est réalisée de cette manière. Cependant, cette opération n'est pas suffisante car elle est vulnérable aux mesures de courant donc aux attaques d'un possible piratage. Un attaquant, ou pirate, mesure la consommation de courant électrique de la puce. Suivant la courbe obtenue, il peut déduire de l'information sur les opérations et les données utilisées par le processeur. Afin de réaliser des mesures précises, l'attaquant doit réaliser plusieurs mesures et les filtrer. Plus précisément, le problème réside dans le calcul de r, c'est à dire sur la formule: r = ALG[K](R). En effet, des mesures de courant sont faciles à réaliser à ce niveau et il est par conséquent possible de connaître les données par le calcul, en particulier du fait que la clé K est constante. Pour obtenir une mesure pertinente, le pirate doit effectuer plusieurs mesures et les filtrer pour en extraire l'information pertinente. Du fait de l'utilisation d'une même clé K constante, toutes les mesures utilisent la même clé K et donc le résultat du filtrage est caractéristique de la clé K. L'invention propose une première particularité qui consiste en une modification succincte qui est réalisée dans la formule du calcul de r du protocole d'authentification, objet de l'invention. La partie A, qui possède la clé secrète K, envoie un aléa ou nombre choisi aléatoirement R1, à la partie B. Cette dernière possède également la même clé secrète K. B choisit un nombre aléatoire R2, puis calcule le nombre K', qui est aussi une clé secrète à partir de la formule suivante: K' = R2 xor K, xor étant le "ou exclusif" mathématique. Ensuite, B calcule un résultat r issu de la formule: r = ALG[K'] (R1) B envoie ensuite r et R2 à A. Ce dernier calcule, à l'aide du même algorithme symétrique de chiffrement ALG, K' et r' à partir des formules suivantes: K' = R2 xor K et r' = ALG[K'] (R1) Dans l'hypothèse o r est égal à r', alors B est authentifié par A. L'impossibilité d'attaque à ce jour provient du fait que, puisque K' change à chaque authentification, la consommation de courant du calcul de r et r' est différente à chaque exécution de l'authentification. Cependant, le calcul de K' reste vulnérable aux attaques en consommation de courant. L'invention propose donc une seconde particularité non liée à la première ci-dessus décrite, concernant le calcul de K' En effet, l'invention utilise un système de chiffrement indépendant et/ou dépendant du système d'authentification ci-dessus décrit. Il consiste en un calcul de K' qui est rendu aléatoire. Pour cela, on décompose la clé secrète K en un ensemble de n sous clés ki, i étant l'indice de sous clés par la formule: K = k1 xor k2 xor... xor kn. Ainsi, le calcul de K' est possible comme étant, sous une autre formulation: K' = R2 xor k1 xor... xor kn. Du fait de la commutativité de l'opérateur xor, il est possible de changer l'ordre de calcul pour obtenir un calcul variable à chaque authentification. Pour qu'un lien soit établi entre K et K' l'algorithme utilisé comprend une phase d'initialisation et un sous-ensemble de boucles. L'initialisation de l'algorithme doit être expliquée, de manière générale d'abord, et ensuite en prenant un cas particulier d'explication, transposable ensuite à la généralité. L'initialisation a pour explication les propos suivants. D'une manière générale, un premier tableau k, dénommé ci-après dans la description par k[], est utilisé; ce tableau contient les valeurs des n sous clés ki. Un second tableau appelé afaire, dénommé ci-après par a_faire[], contient n booléens. Chaque booléen contient la valeur vraie appelée "True" ou "T", ci- après et sur la figure 2. Les tableaux k[] et a faire[] contiennent le même nombre n d'éléments, représentant les n sous clés ki et les n booléens Il est affecté la valeur R2 à K', plus précisément K' = R2 La boucle de l'algorithme est décrite ci-dessous et représentée à la figure 1: La première étape, ou étape a, consiste en ce que tant qu'il reste un élément du tableau a faire[] à la valeur "T", alors un nombre aléatoire i, compris entre 1 et n, est choisi. L'étape suivante, étape b, est le test d'égalité de l'élément i du tableau a faire[] et de la valeur "T", dénommée ci-après dans la description et sur la figure. Si le précédent test d'égalité est vrai, deux opérations sont effectuées: - La première, étape c, est l'affectation à la variable K' du résultat du "ou exclusif" mathématique entre K' et le ième élément du tableau k[] qui est en fait le calcul de la formule suivante: K' = K' xor k[i] - La deuxième, étape d, est l'affectation à l'élément d'indice i du tableau afaire[] de la valeur "False", dénommée ci-après dans la description et sur la figure par "F": afaire[i] = "F". Si le test d'égalité de l'étape b est faux, alors le système de calcul revient à l'étape première, ou étape a. Cet algorithme n'est pas en temps constant car il est possible d'exécuter plus de boucles qu'il y a de sous-clés ki. L'invention concerne également un système d'authentification à algorithme de chiffrement symétrique entre deux entités ou parties A et B, possédant une même clé secrète K, qui met en oeuvre le procédé ci-dessus décrit. L'invention va être maintenant décrite avec un exemple de réalisation précis qui est le cas pour lequel n, nombre de sous clés, est égal à deux, n = 2, en relation avec la figure 2, figure ne décrivant que deux boucles. L'initialisation reste identique au cas général ci- dessus décrit; elle est mentionnée sur la figure 2 par la référence A ou 10. La boucle de l'algorithme est réalisée de la manière suivante: Deux calculs de l'algorithme sont possibles. Soit l'opération suivante sera effectuée: K' = R2 xor k1 xor k2; Soit l'opération suivante sera effectuée: K' = R2 xor k2 xor k1; Ainsi, le pirate ne sait pas quel est le calcul qui va être effectué en premier lieu et donc ne peut pas utiliser plusieurs mesures pour effectuer des filtrages. La probabilité de remplir les deux éléments en un tour de boucle ou premier essai est nulle, ou bien de manière plus explicite et visuelle (cf. figure 2), la probabilité de mettre à la valeur "F" les deux éléments du tableau afaire[] en un seul essai est nulle. Il est donc impossible d'obtenir en un seul bouclage les deux valeurs identiques "F", "F". Ensuite, la probabilité de mettre à la valeur "F" les deux éléments du tableau a faire[] en deux boucles ou essais est égale à un demi, ou 1/2. En effet, lors de la première boucle, un nombre aléatoire i égal à 1 (20) ou 2 (21), i=l ou 2, est choisi; alors la valeur "F" est mise dans un des deux éléments du tableau afaire[]; cette première boucle est mentionnée figure 2 par la référence B. Lors d'une seconde boucle (cf. figure 2), un nombre aléatoire i égal à 1 ou 2, i=1 ou 2, est choisi; alors la valeur "F" est mise dans un des deux éléments du tableau afaire[], selon le nombre aléatoire choisi; cette seconde boucle est mentionnée figure 2 par la référence C. Ainsi, on a deux cas terminés (31, 32), c'est à dire deux valeurs "F" dans deux éléments et deux cas non terminés (30, 33); le calcul de K' n'est pas terminé. La probabilité d'obtenir ce résultat est de un demi. En outre, la probabilité de remplir deux éléments en trois boucles ou essais est égale à un quart, ou 1/4 (non représentée sur la figure 2). En effet, un nombre aléatoire i égal à 1 ou 2 est choisi; la valeur "F" est mise soit dans le premier élément, soit dans le second élément du tableau a faire[]. Ainsi, comme lors du second bouclage, on a deux cas terminés, c'est à dire deux valeurs "F"I dans deux éléments et deux cas non terminés, Le calcul de K' n'est pas terminé. De manière très générale, la probabilité de remplir les deux éléments en k boucles est égale à 1/2k-1. Il est intéressant de connaître une moyenne S de boucles à réaliser pour tomber sur deux éléments comprenant chacun la valeur "F". Pour cela, l'espérance mathématique est calculée et est formulée de la manière suivante: E x S i 2iJ1 i=2 Cette espérance mathématique est la somme pondérée des probabilités. Elle est égale, une fois calculée, à trois. La conclusion est donc: S = 3 Le calcul de K' est réalisé en trois boucles en moyenne. REVENDI CATIONS 1. Procédé d'authentification à algorithme de chiffrement symétrique entre deux entités ou parties A et B, possédant une même clé secrète K, caractérisé en ce qu'il effectue les étapes suivantes pour l'authentification: a) la partie A, possédant la clé secrète K, envoie un aléa, ou nombre choisi aléatoirement R2 à la partie B, cette dernière possédant également la même clé secrète K; b) la partie B choisit un nombre aléatoire R2, et calcule le nombre K', qui est aussi une clé secrète, à partir de la formule suivante: K' = R2 xor K, xor étant l'équivalent du "ou exclusif" mathématique; c) ensuite, B calcule, à l'aide d'un algorithme symétrique de chiffrement ALG un résultat r issu de la formule: r = ALG[K'] (R1); d) ladite partie B envoie ensuite r et R2 à ladite partie A; e) ladite partie A calcule, à l'aide du même algorithme symétrique de chiffrement ALG, K' et r' à partir des formules suivantes: K' = R2 xor K et r' = ALG[K'] (R1); f) si r est égal à r', alors ladite partie B est authentifié par ladite partie A. 2. Procédé selon la revendication 1 caractérisé en ce que la clé K est décomposée en un ensemble de n sous clés ki, i étant l'indice de sous clés, par la formule: K = k1 xor k2 xor... xor kn. 3. Procédé selon la revendication 1 ou 2 caractérisé en ce qu'il comprend un système de calcul de la clé K' rendu aléatoire par l'ordre d'utilisation des sous clés ki i étant l'indice de sous clés, dans la formulation: K' = R2 xor kl xor... xor kn. 4. Procédé selon la revendication 3 caractérisé en ce que la clé secrète K' est calculée au moyen d'un algorithme qui comprend une phase d'initialisation et un ensemble de boucles. 5. Procédé selon la revendication 4 caractérisé en ce que la phase d'initialisation comprend: - un premier tableau k, ou k[], contenant les n sous clés ki et - un second tableau appelé a faire, ou afaire[], contenant n booléens, chaque booléen contenant la valeur vraie appelée "True" ou "T", et caractérisé en ce que les tableaux k[] et afaire[] contiennent le même nombre n d'éléments, représentent les n sous clés ki et les n booléens. 6. Procédé selon la revendication 4 caractérisé en ce que la boucle de l'algorithme comprend les étapes suivantes a) la première étape consiste en ce que tant qu'il reste un élément du tableau afaire[] à la valeur "T", un nombre aléatoire i, compris entre 1 et n, est alors choisi; b) la seconde étape consiste au test de l'élément i du tableau a faire[] à la valeur "T"; c) si le résultat de la seconde étape est vrai, alors la troisième étape consiste en deux opérations: - la première est l'affectation, à la variable K', du résultat du "ou exclusif" mathématique entre K' et le ième élément du tableau k[] qui est le calcul de la formule suivante: K' = K' xor k[i]. - La deuxième est l'affectation à l'élément d'indice i du tableau afaire[] de la valeur "False", dénommée ci-après dans la description et sur la figure par "F": afaire[i] = "F". 7. Procédé selon la revendication 4 caractérisé en ce que la boucle de l'algorithme comprend les étapes suivantes a) la première étape consiste en ce que tant qu'il reste un élément du tableau afaire[] à la valeur "T", un nombre aléatoire i, compris entre 1 et n, étant alors choisi; b) la seconde étape consiste au test de l'élément i du tableau a faire[] à la valeur "T"; c) si le résultat de la seconde étape est faux alors le système de calcul revient à l'étape première. 8. Système d'authentification à algorithme de chiffrement symétrique entre deux entités ou parties A et B, possédant une même clé secrète K caractérisé en ce qu'il met en oeuvre le procédé d'authentification selon l'une quelconque des revendications 1 à 7.