Brevet FR2786346A1 — publié le 20000526

Procédé de traitement aléatoire de la clé dans un chiffrement à clé secrète Le procédé objet de la présente invention est du domaine de la protection de données par algorithme cryptographique. Il concerne plus particulièrement un procédé de traitement aléatoire de clé dans le cadre d'un chiffrement à clé secrète. Cette invention s'applique notamment aux données contenues dans des mémoires de dispositifs dits "cartes à puce". Récemment, des chercheurs en cryptographie ont montré que les cartes à puce étaient vulnérables à certaines attaques du matériel. Ceci est dû au fait que des informations peuvent fuir d'un calcul cryptographique sur carte, par exemple au travers de la consommation de courant nécessaire à une opération, des radiations électromagnétiques engendrées par des fluctuations de charge, ou encore des différences de temps de calcul. Les informations observées peuvent alors faire l'objet de tests statistiques, et induire des attaques qui permettent de retrouver la clé du cryptosystème (système de chiffrement). Les attaques évoquées ci-dessus peuvent devenir plus faciles lorsque la clé secrète du système est traitée dans un ordre déterministe. En particulier quand elle est utilisée de l'octet le plus significatif à l'octet le moins significatif, ou inversement. L'invention a donc pour but de remédier à l'inconvénient précité, en proposant un procédé de traitement aléatoire d'une permutation donnée f sur une clé secrète IK, ledit procédé étant utilisé dans le cadre d'un algorithme de chiffrement à clé secrète, caractérisé en ce que il comporte l'utilisation de deux permutations pseudo aléatoires sur la clé secrète IK : l'une sur les octets, et l'autre sur les bits à l'intérieur de chaque octet. Selon un mode de réalisation préféré, le procédé comporte les étapes suivantes : 1/ Création d'une permutation pseudo-aléatoire dans un premier tableau (permutation sur les octets de IK). 2/ Création d'une permutation pseudo-aléatoire dans un second tableau, comportant 8 éléments (permutation sur les huit bits de chaque octet de IK). 3/ Initialisation des octets de la clé permutée PK=f(IK) à 0. 4/ Permutation des octets de clé initiale IK selon le premier tableau et des 8 bits de chacun de ces octets selon le second tableau. Selon un mode particulier de réalisation, la clé initiale IK a une longueur de 64 bits, la clé permutée PK une longueur de 56 bits, et le premier tableau comporte huit éléments. Selon un mode encore plus particulier de réalisation, la création d'une permutation pseudo-aléatoire dans un tableau de permutation comporte des sous- étapes de : a/ Génération de 8 aléas de trois bits, bl Initialisation de chacun des 8 octets du tableau de permutation à la valeur hexadécimale FF, c/ Création d'une permutation pseudo-aléatoire dans le tableau de permutation à partir des aléas générés à l'étape a/ La génération de 8 aléas de 3 bits est préférentiellement réalisée par génération de quatre octets d'aléas par deux appels à une fonction de création de deux octets pseudo-alétoires, puis par transformation des quatre octets obtenus en huit aléas de trois bits par appel à une fonction de masquage. Encore plus particulièrement, la fonction de création de deux octets pseudo-aléatoires est la fonction qui associe un double octet Xn+1 à un double octet Xn selon l'équation modulaire : Xn+1 = a Xn mod b, Xo, a E [1, b-1 ], a étant un nombre entier, choisi de préférence, mais pas obligatoirement, premier, et b étant de préférence égal à 216+1 Ces différentes dispositions correspondent à une mise en oeuvre simple et efficace de l'invention. L'invention vise également tout dispositif comportant des moyens adaptés à mettre en #uvre le procédé exposé brièvement ci-dessus. La description et les dessins qui suivent permettront de mieux comprendre les buts et avantages de l'invention. Il est clair que cette description est donnée à titre d'exemple, et n'a pas de caractère limitatif. Dans les dessins : - la figure 1 illustre schématiquement le fonctionnement d'une permutation PC-1, - la figure 2 schématise le procédé de création d'aléas de 3 bits. La description de l'invention est ici faite dans le cadre de l'implantation du chiffrement DES (de l'anglais Data Encryption Standard) sur une carte à puce de type traditionnel, non décrite ici en détails, mais l'invention ne se limite pas à cette seule application. Dans cet algorithme, une clé initiale, (de 64 bits avec 8 bits de parité aux positions 8,16, 24,32 , 40,48, 56, et 64) est d'abord permutée par une permutation PC-1 (figure 1), avant de servir à la dérivation de 16 sous-clés. La permutation PC-1 ne permute que les bits significatifs de la clé initiale (et non les bits de parité), c'est-à-dire que le résultat de PC-1 est sur 56 bits. Il s'agit donc, dans le contexte du DES, d'appliquer la permutation f = PC-1 à la clé initiale, de manière pseudo-aléatoire et non pas déterministe. On note, pour la suite de la description, IK (de l'anglais Initial Key) la clé initiale avant permutation, et PK (de l'anglais Permuted Key) la clé permutée par la permutation PC-1. On note IK~0 ,..., IK~7, les octets de clé initiale IK, IK~0 étant le plus significatif, IK[1] à IK[64] les bits de la clé initiale IK, IK[1] étant le bit le plus significatif. On indique par l'indice m le quartet (groupe de quatre bits) le plus significatif de l'octet, et par l'indice 1 le quartet le moins significatif. On numérote de 0 à 7 les bits des octets, 7 étant le bit le plus significatif. La permutation PC-1 peut, de façon classique, être décomposée en une boucle à 7 passages, suivie d'un cycle de transpositions. Comme le montre la figure 1, la boucle a pour effet de déplacer les bits n 7 (les plus significatifs) de chaque octet de la clé initiale IK vers l'octet le plus significatif (octet n 0) de la clé permutée PK, les bits n 6 de chaque octet de la clé initiale IK vers l'octet n 1 de la clé permutée PK, et ainsi de suite... A l'intérieur de l'octet n j de la clé permutée PK, les bits n (7-j) des octets de la clé initiale IK sont rangés de telle sorte que le bit n (7-j) de l'octet n 0 (le plus significatif) de la clé initiale IK se trouve en position 0 dans l'octet n j de la clé permutée PK, le bit n (7-j) de l'octet n 1 de la clé initiale IK se trouve en position 1 dans l'octet n j de la clé permutée PK, etc... En résumé : le bit de rang (7-j) de l'octet k de la clé initiale IK devient, par la permutation PC-1, le bit de rang k de l'octet j dans la clé permutée PK, ou, sous une autre forme : le bit de rang i' de l'octet j' de la clé initiale IK (ce bit est également noté IK~j'~ i' ) devient, par la permutation PC-1, le bit de rang j' de l'octet (7-i') dans la clé permutée PK (ce bit est également noté PK- (7-i') J'). L'algorithme de la permutation PC-1 est décrit ci-dessous en pseudocode. Il comporte d'abord une boucle ("boucle k"): index := 0 Pour k de 57 à 63 faire : i:= k tant que i > 0 faire : index :=index + 1 PK[index]:= IK[i] i := i- 8 fin fin PK[index] désignant le bit de rang "index" de la clé permutée PK, et IK[i] désignant le bit de rang i de la clé initiale IK. Puis l'algorithme de la permutation PC-1 comporte une série de transpositions : (PK~3J PK~6~I PK~4~m PK~5~IPK~5~m PK~4~IPK~6~m) La notation (a b c) signifiant que a prend la place de b, qui prend celle de c, qui prend celle de a, et la notation IK~3~Ireprésentant le quartet de poids le plus faible (le moins représentatif) du troisième octet de la clé initiale IK. Une méthode simple pour réaliser cette permutation est de vider bit par bit les octets de la clé initiale IK - de l'octet le plus significatif à l'octet le moins significatif, et, à l'intérieur d'un octet, du bit le plus significatif au bit le moins significatif - et de les ranger dans l'ordre convenable dans la clé permutée PK, la clé permutée PK étant au préalable remplie de zéros. Cette méthode, de type général connu en soi, comme d'autres méthodes déterministes, présente l'inconvénient d'être vulnérable aux attaques mentionnées plus haut. L'invention a pour but de pallier cette faiblesse due à la façon déterministe et systématique de procéder à la permutation des bits, en décomposant chaque opération unitaire de permutation d'un bit et en effectuant ces opérations dans un ordre aléatoire. Il s'agit donc de faire intervenir les bits de la clé dans un ordre aléatoire à l'intérieur d'un calcul cryptographique. Ainsi l'idée de permutation de bits de l'algorithme de base, qui consiste à prendre un bit donné dans un mot en entrée et à le positionner à un endroit donné dans le mot en sortie, est conservée, mais l'algorithme est remanié pour qu'il soit possible de choisir chacun de ces bits à titre individuel. A partir de là, il est possible de définir un ordre aléatoire selon lequel procéder à ces repositionnements. Cet ordre aléatoire devant bien sûr prendre en compte tous les bits, il faut donc définir une permutation sur les positions de départ. Il y a 64 bits dans un mot en entrée (dont seulement 56 bits participent au résultat, puisqu'il y a huit bits de parité, mais à des fins de généralisation, on considérera les 64 bits), il faut donc définir une permutation de 64 éléments (codée en 64 octets). Si ceci requiert un volume de stockage incompatible avec l'application envisagée, ce qui peut être le cas pour une carte à puce, une décomposition en deux permutations distinctes est préférée, l'une sur les 8 octets du mot et l'autre sur les 8 bits de chaque octet, soit un stockage de 2 permutations de 8 éléments, codée chacune en 4 octets, soit 8 octets au total. C'est ce cas qui est décrit dans ce qui suit. Dans le cas du remplacement de la "boucle k" de la permutation PC-1 par une procédure selon l'invention (voir description en pseudo-code), on applique deux permutations pseudo aléatoires sur la clé initiale IK: l'une sur les octets, et l'autre sur les bits à l'intérieur de chaque octet. Dans la suite de la description, on représentera une permutation de 8 éléments par un tableau de 8 octets contenant chacun l'un des 8 chiffres de 1 à 8 (sans répétition). Dans cette représentation le tableau {7,4, 2,1, 3,8, 5,6} définit la permutation consistant à mettre le 7ème objet en 1ère position, le 4ème en 2ème position, etc.. Dans le procédé, une étape consiste à définir une permutation pseudo aléatoire, notée perm, sur 8 positions (octets ou bits) à partir d'un générateur pseudo aléatoire. Ceci est de la manière suivante : Initialement perm est initialisé à la valeur {OxFF, OxFF, OxFF, OxFF, OxFF, OxFF, OxFF, OxFF}, le préfixe Ox indiquant une valeur hexadécimale. Puis on applique au tableau initialisé perm une procédure create-perm définie ci-dessous en pseudo-code : create-perm: Pour index de 1 à 8 faire : choisir un aléa noté rand de 3 bits tant que perm[rand] <> OxFF faire rand := rand + 1 modulo 8 perm[rand]:= index fin perm [rand] désignant l'élément de rang "rand" de la permutation perm. A la fin de cette procédure, la permutation perm contient effectivement une permutation pseudo aléatoire. Le fonctionnement du générateur pseudo aléatoire qui fournit les aléas rand de 3 bits utilisés dans create-perm est décrit ci-dessous La première phase est la génération d'un pseudo-aléa de longueur deux octets à partir de l'équation modulaire : Xn+1 = a Xn mod b avec Xo, a # [1, b-1], a étant de préférence choisi premier, et b étant de préférence égal à 216 +1 ; on note par la suite create-rand la fonction qui associe Xn+1 à Xn selon cette équation. Soit d'autre part trans-rand une fonction qui transforme quatre octets d'aléas rand[1],...,rand[4] (obtenus en exécutant 2 fois la fonction create-rand, et donc en obtenant un pseudo-aléa X1 = (rand[1],rand[2]) de longueur 2 octets à partir de Xo, puis un pseudo-aléa X2 = (rand[3], rand[4]) de longueur 2 octets à partir de Ni) en huit aléas rand[11, rand[21,...,rand[81 de 3 bits chacun (ces aléas étant nécessaires à la fonction create-perm). Une telle fonction trans-rand est définie par exemple par le pseudocode ci-dessous: trans-rand : Pour index de1 à 4 faire rand' [index] := rand [index] and 00000111 Pour index de 5 à 8 faire rand' [index] : = 2-3((rand [index - 4] and 00111000) (où and est la fonction logique "ET') L'utilisation de la fonction ET avec le masque 00000111 permet de sélectionner les trois derniers bits d'un mot de huit bits pour l'index compris entre 1 et 4, et avec le masque 00111000, la fonction ET permet de sélectionner trois autres bits du mot de huit bit pour index compris entre 5 et 8. La figure 2 schématise le passage de Xo à Xi puis X2 par la procédure create-rand, avec X, d'une longueur de 2 octets, puis le passage de Xi et X2 (d'une longueur totale de quatre octets) par la procédure trans-rand à 8 aléas de 3 bits rand'[1 ], rand'[2], rand'[8]. Les éléments qui ont été définis ci-dessus permettent alors de réaliser un traitement aléatoire de la clé dans la permutation PC-1, dans le but de remplacer la "boucle k" de l'algorithme classique. La procédure qui remplace la "boucle k" est décrite ci-dessous. Dans cette procédure, on utilise deux tableaux, l'un noté o-perm contenant une permutation sur les octets, l'autre noté b-perm contenant une permutation sur les bits. On définit également un masque de 8 octets noté MASK défini par : MASK= {Ox01, Ox02, Ox04, Ox08, Ox 10, Ox20, Ox40, 0x80}. Ce masque permettant d'extraire sélectivement l'un des 8 bits d'un octet.(à compléter) On rappelle que l'on note IK~r, l'octet n r de la clé initiale IK, et de même PK~r, l'octet n r de la clé permutée PK. La procédure qui transforme une clé initiale IK en une clé permutée PK comporte les 8 étapes suivantes : 1. Génération de 4 octets d'aléa par deux appels à la fonction createrand, et transformation de ces 4 octets en 8 aléas de trois bits par la fonction trans-rand (tel que schématisé figure 2 et détaillé ci-dessus). 2. Initialisation des 8 octets du tableau o-perm à OxFF. 3. Création d'une permutation pseudo-aléatoire dans o-perm par la fonction create-perm à partir des aléas générés à l'étape 1. 4. Répétition de l'étape 1 5. Initialisation des 8 octets du tableau b-perm à OxFF. 6. Création d'une permutation pseudo-aléatoire dans b-perm par la fonction create-perm à partir des aléas générés à l'étape 4. 7. Initialisation des 7 octets de clé permutée PK à 0. 8. Permutation des 8 octets de clé initiale IK selon o-perm et des 8 bits de chacun de ces octets selon b-perm, selon la procédure ci-dessous: Pour i de 7 à 0 faire i' = b-perm[i] Pour} de 7 à 0 faire j' = o-perm[j]. courant ;= IKj' AND MASKi' k' :=j'-i' Si k' <> 0 alors courant := 2-k'.courant modulo 256 PK~i':= courant OR PK~i' fin fin On comprend qu'on effectue une boucle sur les 8 bits i, dans laquelle est réalisée pour chaque bit i une boucle sur les huit octets j. On réalise par l'utilisation de l'octet n i' du masque MASK l'extraction du bit i' de l'octet j' de la clé initiale IK, dans lequel i' et j' sont obtenus par utilisation des permutations b-perm et o-perm respectivement, puis on donne à k' la valeur j'-i', et on procède à un décalage vers la gauche (pour former l'octet n i' de la clé permutée PK) si j'> i', et vers la droite si j' Après cette étape, on effectue le cycle classique de transpositions terminant la permutation PC-1. (PK 3 I PK 6 PK~4~m PK~5~I PK~5~m PK~4~I PK~6~m). Il est clair que les étapes 1 à 8 ci-dessus donnent le même résultat que la "boucle k" initiale, c'est à dire qu'à la fin de l'étape 8, pour 0 # r#7, les bits n (7r) de chaque octet de la clé initiale IK se trouvent dans l'octet n r de la clé permutée PK, et à l'intérieur de l'octet n r de la clé permutée PK, le bit n (7-r) de l'octet n 0 de la clé initiale IK se trouve en position 0, le bit n (7-r) de l'octet n 1 de la clé initiale IK se trouve en position 1, etc... Dans une variante avantageuse d'implémentation, pour optimiser la taille du code, au lieu d'initialiser deux tableaux de 8 octets à OxFF (étapes 2 et 5), de générer deux permutations pseudo-aléatoires, et de stocker ces permutations dans les tableaux préalablement initialisés à OxFF (étapes 3 et 6), le procédé est réalisé de la manière suivante : 1'- Etape 1 inchangée (génération des 8 aléas de 3 bits) 2'- Initialisation des 8 octets du tableau b-perm à OxFF. 3'- Création d'une permutation pseudo aléatoire dans b-perm par la fonction create-perm à partir des aléas générés à l'étape 1'. 4'- Copie de b-perm dans o-perm. 5'- Répétition des étapes 1' à 3' 6'/7'- Ce sont les étapes 7 et 8 inchangées. L'intérêt de cette variante est de pouvoir utiliser deux fois le même code réalisant les étapes 1' à 3', pour remplir les deux tableaux o-perm et b-perm de permutations convenables. La spécificité de l'implantation sur carte à puces réside dans l'utilisation, comme aléa Xo servant de "graine" au générateur pseudo aléatoire create-rand, d'une donnée aléatoire mémorisée dans la carte au moment de sa personnalisation, et différente pour chaque carte. Le procédé de traitement aléatoire de la clé, exposé ci-dessus dans le cadre du DES, s'applique à tout chiffrement à clé secrète. La manière dont les permutations sur les octets et sur les bits de la clé initiale est agencée dépend évidemment de la fonction f qui fait intervenir la clé (ici la permutation PC-1), mais la méthode décrite est aisément adaptable à tout autre contexte où la clé intervient dans une fonction f quelconque. Le procédé décrit plus haut est dédié à des composants 8 bits. Les fonctions create-perm, create-rand, et trans-rand sont néanmoins aisément transposables au contexte 16 ou 32 bits. La portée de la présente invention ne se limite pas aux détails des formes de réalisation ci-dessus considérés à titre d'exemple, mais s'étend au contraire aux modifications à la portée de l'homme de l'art. REVENDICATIONS 1. Procédé de traitement aléatoire d'une permutation donnée f sur une clé secrète IK pour obtenir une clé permutée PK, ledit procédé étant utilisé dans le cadre d'un algorithme de chiffrement à clé secrète, caractérisé en ce que il comporte l'utilisation de deux permutations pseudo aléatoires sur la clé secrète IK : l'une sur les octets, et l'autre sur les bits à l'intérieur de chaque octet. 2. Procédé selon la revendication 1, caractérisé en ce qu'il comporte les étapes suivantes : 1/ Création d'une permutation pseudo-aléatoire dans un premier tableau (o-perm, permutation sur les octets de IK). 2/ Création d'une permutation pseudo-aléatoire dans un second tableau (b-perm), comportant 8 éléments (permutation sur les huit bits de chaque octet de IK). 3/ Initialisation des octets de clé permutée PK=f(IK) à 0. 4/ Permutation des octets de clé initiale IK selon le premier tableau (o-perm) et des 8 bits de chacun de ces octets selon le second tableau (b-perm). 3. Procédé selon la revendication 2, caractérisé en ce que la clé initiale IK a une longueur de 64 bits, la clé permutée PK une longueur de 56 bits, et en ce que le premier tableau o-perm comporte huit éléments. 4. Procédé selon la revendication 3, caractérisé en ce que la création d'une permutation pseudo-aléatoire dans un tableau perm (étapes 1/, 2/) comporte des sous-étapes de : a/ Génération de 8 aléas de trois bits (rand'[1 ], rand'[2],..., rand'[8]), b/ Initialisation de chacun des 8 octets du tableau perm à OxFF (OxFF désignant la valeur hexadécimale FF), c/ Création d'une permutation pseudo-aléatoire dans perm à partir des aléas générés à l'étape a/ (rand'[1], rand\2],..., rand'[8]). 5. Procédé selon la revendication 4, caractérisé en ce que la génération de 8 aléas de 3 bits (étape a/) (rand'[1], rand'[2], rand'[8]) est réalisée par génération de quatre octets d'aléas par deux appels à une fonction (create-rand) de création de deux octets pseudo-alétoires, puis par transformation des quatre octets obtenus (rand[1], rand[2], rand [3], rand [4]) en huit aléas de trois bits (rand'[1], rand'[2], rand'[8]) par appel à une fonction de masquage (trans-rand). 6. Procédé selon la revendication 5, caractérisé en ce que la fonction (create-rand) de création de deux octets pseudo-aléatoires est la fonction qui associe un double octet Xn+1 à un double octet Xn selon l'équation modulaire : Xn+1 = a Xn mod b, Xo, a E [1, b-1], a étant un nombre entier. 7. Procédé selon la revendication 6, caractérisé en ce que a est un nombre premier. 8. Procédé selon la revendication 6, caractérisé en ce que b est égal à 216+1. 9. Procédé selon la revendication 5, caractérisé en ce que la transformation (trans-rand) de quatre octets (rand[1], rand [2], rand [3], rand [4]) en huit aléas de trois bits (rand'[1], rand'[2], rand'[8]) est définie par le pseudo-code ci-dessous : Pour index de 1 à 4 faire rand' [index] : = rand [index] and 00000111 Pour index de 5 à 8 faire rand' [index] : = 2-3((rand [index - 4] and 00111000) où and est la fonction logique "ET". 10. Procédé selon l'une quelconque des revendications 4 à 9, caractérisé en ce que l'étape de création d'une permutation pseudo-aléatoire dans perm (étape cI) à partir de huit aléas de trois bits (rand'[1], rand'[2], rand'[8]) comprend l'utilisation d'une procédure create-perm définie ci-dessous en pseudocode : Pour index de 1 à 8 faire : rand := rand[index] tant que perm [rand] <>OxFF faire rand := rand + 1 (modulo 8) perm [rand] index fi n perm[rand] désignant l'élément de rang "rand" de la permutation perm, rand étant un aléa prenant la valeur rand'[index], pour index valant de 1 à 8. 11. Procédé selon la revendication 4, caractérisé en ce que l'étape de permutation des 8 octets de clé initiale IK selon o-perm et des 8 bits de chacun de ces octets selon b-perm (étape 4/), est réalisée selon la procédure ci-dessous: Pour i de 7 à 0 faire i' = b-perm[i] Pour j de 7 à 0 faire j' = o-perm[j]. courant := IKJ' AND MASK~i' k' :=j'-i' Si k' <> 0 alors courant := 2 -k'.courant (modulo 256) PK~i':= courant OR PK~i' fi n fin où MASK est un masque de 8 octets défini par : MASK= {Ox01, Ox02, Ox04, Ox08, Ox10, Ox20, Ox40, Ox80} Et où PK~i'désigne le i'-ième octet de la clé permutée PK, et IK~i' le j'ième octet de la clé initiale IK. 12. Dispositif caractérisé en ce que il comporte des moyens adaptés à mettre en #uvre le procédé selon l'une quelconque des revendications 1 à 11.