Brevet FR2825542A1 — publié le 20021206

du tissage. PROCEDE FONDE SUR UN ALGORITHME DE CHIFFRAGE PAR BLOC A REPETITION DE RONDES ET DISPOSITIF LE METTANT EN _UVRE La présente invention concerne des perfection- nements apportés aux procédés - et aux dispositifs le mettant en uvre fondés sur un algorithme de chiffrage par bloc à répétition de ronde, propre à fournir, à partir d'une donnce d'entrée de longueur déterminée, un cryptogramme ou donnée de sortie qui dépend de la donnée d'entrée et d'une clé mémorisée inaccessible en lecture depuis l'extérieur. Pour fixer les idées, les perfectionnements que l' invention vise à apporter peuvent concerner des algorithmes à répétition de rondes involutives - tels que l'algorithme DES (Data Enscription Standard, couramment utilisé dans les cartes à puce pour établir un cryptogramme à partir d'une donnée d'entrée de 8 octets et d'une clé maître de 56 éléments binaires ou bits utiles) ou l'algorithme KASUMI (aussi dénommé MITSY) - ou des algorithmes à répét it ion de rondes non involutives - tel que l'algorithme AES -. Parmi les divers types d'attaque qui peuvent être menés contre des moyens algorithmes, l'attaque DFA (Differential Fault Analysis) consiste à provoquer des erreurs durant l'exécution d'un algorithme cryptographique, puis à comparer les résultats obtenus À d'une part, lorsque les calculs ont été exéautés correctement et À d'autre part, lorsque les calauls ont été exécutés avec des erreurs, et enfin à déduire de cette comparaison la clé utilisée. Cette attaque - lorsque sa mise en _uvre est possible - est relativement efficace car elle permet en quelques dizaines d' appels à l' algorithme de retrouver la clé utilisée. Elle est souvent mise en _uvre contre des algorithmes DES implémentés dans des cartes à microcircuit (cartes à puce). L'invention a essentiellement pour but de proposer des moyens - procédé et dispositif - perfectionnés propres à procurer une protection contre ce type d'attaque DFA. A cette fin, selon un premier de ses aspects, l' invention propose un procédé fondé sur un algorithme de chiffrage à répétition de rondes, utilisant une clé maître à partir de laquelle sont générées une ou des sous-clés qui sont injectées dans les rondes, lequel procédé, étant conforme à l' invention, se caractérise en ce que l'algorithme inclut en outre au moins une paire de rondes supplémentaires constituée d'une première et d'une seconde rondes sans utilité dans le déroulement de l'algorithme et auxquelles sont affectées des sous-clés aléatoires respectives et des moyens propres à rendre indétectable la mise en _uvre de ces deux rondes supplémentaires. Ainsi, l'invention propose des moyens purement algorithmes pour parvenir à sécuriser le déroulement de l'algorithme de chiffrage. L' introduction d'une paire de rondes supplémentaires ne pose, dans le principe, aucun problème ni pour la mise en _uvre, ni pour le fonctionnement et l' introduction de plusieurs paires de rondes supplémentaires accroît la séaurité sans introduire de difficulté sensible. Au cours du fonctionnement normal de l'algorithme modifié conformément à l' invention, la ou chaque paire de rondes supplémentaires introduite artificiellement dans l'algorithme est purement transparente et n'a aucune influence sur le cryptogramme obtenu en sortie. Par contre, en présence d'une attaque DFA, l'une des rondes supplémentaires risque d'être modifiée - une telle modification d'une ronde supplémentaire étant d'autant plus probable que le nombre des paires de rondes ajoutées est élevé -, tandis qu'il n'existe qu'une probabilité quasi nulle pour que les deux rondes d'une paire ajoutée soient simultanément modifiées de manière que leurs effets se compensent mutuellement: il devient alors impossible d'effectuer des comparaisons valables entre les calculs algorithmes corrects et ceux volontairement affectés d'erreur, et l' identification de la clé devient impossible. Les moyens proposés par l' invention se révèlent relativement simples à mettre en _uvre, tandis que leur efficacité est élevée. Le profil des rondes supplémentaires pouvant être analogue à celui des rondes de calcul de l'algorithme, ces rondes artificielles peuvent ne pas être décelables par des mesures du type mesure de la consommation électrique instantanée (attaque DPA: analyse différentielle de consommation). En outre, ce procédé peut être utilisé en combinaison avec la mise en _uvre de masques tel qu'enseigné dans le document FR-A 2 802 741. Pour éviter une complication extrême des calculs, il est souhaitable que la paire de rondes supplémentaires soit formée de deux rondes successives, de sorte que les deux rondes de l'algorithme de cryptage entre lesquelles ladite paire de rondes supplémentaires a été ajoutée se transmettent les mêmes informations que dans l'algorithme non modifié. Dans une mise en _uvre avantageuse du procédé de l'invention, la seconde ronde est la ronde inverse de la première ronde et il lul est affecté une sous-clé K' différente de la sous-clé K de la première ronde, mais dépendante de la sous-clé K. Dans une mise en _uvre spécifique, la première ronde est involutive et la même clé K est affectée à la ronde et à son inverse. Dans ce cas, les dispositions de l' invention trouvent une application préférée, bien que non limitative, pour la protection de l'algorithme itératif DES, composé d'une permutation IP, de 16 rondes successives, et de l' inverse de la permutation IP. Selon un second de ses aspects, l' invention propose de perfectionner un dispositif mettant en _uvre un algorithme de chiffrage à répétition de rondes, utilisant une clé maître à partir de laquelle sont générées une ou des sous-clés qui sont injectées dans les rondes, lequel dispositif, étant agencé conformément à l'invention, se caractérise en ce que l'algorithme inclut en outre au moins une paire de rondes supplémentaires constituée d'une première et d'une seconde rondes sans utilité dans le déroulement de l'algorithme et auxquelles sont affectées des sous-clés aléatoires respectives et des moyens propres à rendre indétectable la mise en _uvre de ces deux rondes supplémentaires. De préférence, la paire de rondes supplémentaires est formée de rondes successives. On peut faire en sorte que la seconde ronde est la ronde inverse de la première ronde et qu'il lui est affecté une sous-clé K' différente de la sous-clé K de la première ronde, mais dépendante de la sous-clé K. Lorsque cela est possible, il est avantageux que la première ronde soit involutive et que la même clé K soit affectée à la ronde et à son inverse. Un tel dispositif trouve une application préférée, bien que non exclusive, dans la mise en _uvre de l'algorithme itératif DES, composé d'une permutation IP, de 16 rondes successives, et de l' inverse de la permutation IP. L'invention sera mieux comprise à la lecture de la description détaillée qui suit de certains modes de réalisation donnés à titre d'exemples non limitatifs. Dans cette description, on se réfère aux dessins annexés sur lesquels: - la figure 1A illustre très schématiquement, à titre de référence, deux étapes consécutives d'un algorithme; - la figure 1B illustre très schématiquement la même partie de l'algorithme qu'à la figure 1 après modification conformément à l' invention; - la figure 2 illustre très schématiquement une partie d'un algorithme modifié selon une mise en _uvre avantageuse des dispositions de l' invention; - la figure 3A illustre très schématiquement l'algorithme DES; et - la figure 3B illustre très schématiquement l'algorithme DES modifié selon une mise en _uvre spécifique, préférée, de l' invention. En se référant tout d'abord à la figure 1A, l' invention vise un algorithme de chiffrage à répétition de rondes utilisant une clé maître à partir de laquelle sont générées une ou des sous-clés qui sont injectées dans les rondes. A la figure 1 on a schématisé une ronde de rang i recevant des données di (données d'entrée si la ronde est de rang 1; données de sortie de la ronde précédente de rang i-1 dans les autres cas); à cette ronde de rang i est associée une sous-clé Ki. La ronde de rang i délivre des données di+l à destination de la ronde suivante de rang i+1 gérée par une sous-clé Ki+1. 6 2825542 Conformément à l'invention, on introduit dans l'algorithme au moins une paire derondes supplémentaires r' et r", entre les rondes de rang i et i+ 1, les rondes r' et r" étant respectivement gérces par des sous-clés K' et K". Les rondes r' et r" sont sans utilité dans le déroulement normal de l'algorithme, les clés K' et K" sont arUitraires, et des moyens sont prévus qui sont propres à rendre indécelables la mise en _uvre de ces deux rondes supplémentaires, notamment en présence d'une attaque DPA. De ce fait, la ronde de rang i émet touj ours des données di+1 et la ronde de rang i+1 reçoit touj ours des données di+1 lorsque l'algorithme fonctionne normalement, de la même manière qu'illustré à la figure 1A. Par contre, en présence d'une attaque DFA, si une des rondes artificielles r' ou r" est modifiée, l'attaquant récupère des inconnues provenant de la sous-clé aléatoire - K' ou K" respectivement - associée à la ronde modifiée. Comme il existe une probabilité quasiment nulle pour que les deux rondes supplémentaires r' et r" soient modifiées simultanément de manière que leurs effets se compensent, le travail de cryptoanalyse de l'attaquant DFA est rendu très compliqué, voire impossible. Éiefficacité des dispositions de l' invention est d'autant meilleure que le nombre de paires de rondes supplémentaires introduites dans l'algorithme est accru. On peut ainsi multiplier les paires de rondes supplémentaires introduites chacune entre deux rondes conséautives, voire introduire plusieurs paires de rondes supplémentaires successives entre deux rondes conséautives. Toutefois, pour ne pas compliquer outre mesure le fonctionnement de l'algorithme, il est préférable de ne pas séparer les deux rondes d'une paire supplémentaire et 7 2825542 de constituer la paire de rondes supplémentaires de deux rondes conséautives r' et r" comme illustré à la figure 1B. Dans un mode de mise en _uvre préféré illustré à la figure 2, la seconde ronde est la ronde inverse r1 de la première ronde r et il est affecté à cette ronde inverse r1 une sous-clé K' qui est différente de la sous- clé K de la première ronde, mais qui est dépendante de cette sous-clé K (notée K'(K) à la figure 2). Les dispositions qui viennent d'être exposées ne tiennent pas compte du caractère involutif ou non involutif des rondes de l'algorithme et s'appliquent donc à tout algorithme de chiffrage à répétition de rondes gérées chacune par une sous-clé générée à partir d'une clé maître. Toutefois, dans le cas o les rondes sont involutives, on peut simplifier la mise en _uvre de l' invention en donnant la même sous-clé aléatoire K à la ronde supplémentaire r et à son inverse r1. Les dispositions de l' invention qui viennent d'être exposées trouvent une application particulièrement intéressante, bien que non exclusive, dans la protection de l'algorithme DES couramment mis en _uvre dans les cartes à puce. Comme illustré à la figure 3A, l'algorithme DES comporte un étage d'entrée constitué d'un permutateur d'entrée ou permutateur initial IP fournissant, à partir d'une donnée d'entrée E, une partie gauche de 32 bits et une partie droite de 32 bits, les 32 bits constituant des opérandes. Chaque étage i comporte: - un élément d' expansion ad augmentant la taille de la partie droite, - un ensemble bd ayant en cascade un opérateur ou EXCLUSIF ou XOR sur l'opérande droit expansé et 8 2825542 une sous-clé Ki de même longueur dérivée de la clé maître et des tables de substitution ou "S boxes" ci affectées chacune à un groupe de bits et à lecture dans un ordre arbitraire, - et un opérateur XOR di sur le contenu lu dans les tables ci et l'opérande gauche expansé ag pour donner naissance à une partie de gauche de 32 bits constituant la sortie de droite de l'étage, l'autre sortie - sortie de gauche - de l'étage étant constituée par l'opérande droit expansé ad. L'algorithme de chiffrage DES met en _uvre un nombre de n = 16 étages en cascade constitués comme il vient d'être expliqué, le dernier étage étant suivi d'un permutateur effectuant l'opération inverse IP1 et délivrant le cryptogramme de sortie S. Conformément à l'invention, on introduit, entre les étages de rang i et i+1, une ronde r et son inverse r consécutives et gérées par la même sous-clé K aléatoire, comme illustré à la figure 3B, les rondes r et r1 n'ayant individuellement aucune utilité dans le déroulement de l'algorithme. 9 2825542 REVENDICATIONS 1. Procédé fondé sur un algorithme de chiffrage à répétition de rondes, utilisant une clé maître à partir de laquelle sont générées une ou des sous-clés (Ki) qui sont injectées dans les rondes (i), caractérisé en ce que l'algorithme inclut en outre au moins une paire de rondes supplémentaires constituée d'une première et d'une seconde rondes (r', r") sans utilité dans le déroulement de l'algorithme et auxquelles sont affectées des sous-clés aléatoires respectives (K', K") et des moyens propres à rendre indétectable la mise en _uvre de ces deux rondes supplémentaires. 2. Procédé selon la revendication l, caractérisé en ce que la paire de rondes supplémentaires est formée de rondes successives. 3. Procédé selon la revendication l ou 2, caractérisé en ce que la seconde ronde est la ronde inverse (rl) de la première ronde (r) et en ce qu'il lui est affecté une sous-clé K' différente de la sous-clé K de la première ronde, mais dépendante de la sous-clé K. 4. Procédé selon la revendication 3, caractérisé en ce que la première ronde est involutive et en ce que la même clé K est affectée à la ronde et à son inverse. 5. Procédé selon la revendication 4, caractérisé en ce que l'algorithme de chiffrage est l'algorithme itératif DES, composé d'une permutation IP, de 16 rondes successives, et de l' inverse de la permutation IP. 6. Dispositif mettant en _uvre un algorithme de chiffrage à répétition de rondes, utilisant une clé maître à partir de laquelle sont générces une ou des sous-clés (Ki) qui sont injectées dans les rondes (i), caractérisé en ce que l'algorithme inclut en outre au moins une paire de rondes supplémentaires constituce d'une première et d'une seconde rondes (r', r") sans utilité dans le déroulement de l'algorithme et auxquelles sont affectées des sous-clés aléatoires respectives (K', K") et des moyens propres à rendre indétectable la mise en _uvre de ces deux rondes supplémentaires. 7. Dispositif selon la revendication 6, caractérisé en ce que la paire de rondes supplémentaires est formée de rondes successives. 8. Dispositif selon la revendication 6 ou 7, caractérisé en ce que la seconde ronde est la ronde inverse (rl) de la première ronde (r) et en ce qu'il lui est affecté une sous-clé K' différente de la sous-clé K de la première ronde, mais dépendante de la sous-clé K. 9. Dispositif selon la revendication 8, caractérisé en ce que la première ronde est involutive et en ce que la même clé K est affectée à la ronde et à son inverse. lO. Dispositif selon la revendication 9, caractérisé en ce que l'algorithme de chiffrage est l'algorithme itératif DES, composé d'une permutation IP, de 16 rondes successives, et de l' inverse de la