Brevet FR2820914A1 — publié le 20020816

Procédé de sécurisation d'un ensemble électronique mettant en oeuvre un algorithme cryptographique utilisant des opérations booléennes et des opérations arithmétiques, et système embarqué correspondant Introduction Paul Kocher et al. ont introduit en 1998 [5] et publié en 1999 [6] le concept de Differential Power Analysis , connu aussi sous le nom de DPA. La cible initiale était les cryptosystèmes symétriques, tels que le DES ou les candidats AES, mais les cryptosystèmes à clé publique se sont depuis avérés également vulnérables face aux attaques DPA. En 1999, Chari et al. [2] ont suggéré une contre-mesure générique consistant à séparer toutes les variables intermédiaires. Une méthode similaire de duplication a été proposée par Goubin et al. [4], comme cas particulier. Or ces méthodes générales augmentent en général fortement la quantité de mémoire ou le temps de calcul nécessaires, comme l'ont remarqué Chari et al. De plus, il a été montré que même les étapes intermédiaires peuvent être attaquées par DPA, si bien que la séparation des variables doit être effectuée sur toutes les étapes de l'algorithme. Cela rend d'autant plus cruciale la question de la mémoire et du temps de calcul supplémentaires, en particulier pour des systèmes embarqués tels que les cartes à puce. En 2000, Thomas Messerges [8] a étudié les attaques DPA appliquées aux candidats AES. Il a développé une contre-mesure générale, consistant à masquer toutes les entrées et sorties de chaque opération élémentaire exécutée par le microprocesseur. Cette technique générique lui a permis d'évaluer l'impact de ces contre-mesures sur les cinq candidats AES. Néanmoins, pour des algorithmes qui combinent des fonctions booléennes et des fonctions arithmétiques, on est conduit à utiliser deux sortes de masques. On a donc besoin d'une méthode de conversion entre le masquage booléen et le masquage arithmétique. C'est typiquement le cas pour IDEA [7] et pour trois des candidats AES : MARS [1], RC6 [9] et Twofish [10]. T. Messerges [8] a proposé un algorithme pour effectuer cette conversion. Malheureusement, Coron et Goubin [3] ont décrit une attaque spécifique, montrant que l'algorithme BooleanToArithmetic proposé par T. Messerges est insuffisant pour se prémunir contre la DPA. De même, son algorithme ArithmeticToBoolean n'est pas sûr non plus. L'objet de la présente invention est de proposer deux nouveaux algorithmes BooleanToArithmetic et ArithmeticToBoolean , prouvés sûrs contre les attaques DPA. Chacun de ces algorithmes n'utilise que des opérations très simples : XOR (ou exclusif), AND, la soustraction, et le décalage à gauche d'un registre. Notre algorithme BooleanToArithmetic utilise un nombre constant (égal à 7) de telles opérations élémentaires, alors que le nombre d'opérations élémentaires mises en jeu dans notre algorithme ArithmeticToBoolean est proportionnel (il vaut 5K+5) à la taille (i. e. le nombre de bits K) des registres du processeur. Contexte L'attaque Differential Power Analysis La Differential Power Analysis (DPA) est une attaque qui permet d'obtenir des informations sur la clé secrète (contenue dans une carte à puce par exemple), en effectuant une analyse statistique des enregistrements de consommation électrique, mesurés sur un grand nombre de calculs avec la même clé. Cette attaque ne requiert aucune connaissance sur la consommation électrique individuelle de chaque instruction, ni sur la position dans le temps de chacune de ces instructions. Elle s'applique exactement de la même manière dès que l'attaquant connaît les sorties de l'algorithme et les courbes de consommation correspondantes. Elle repose uniquement sur l'hypothèse fondamentale suivante : Hypothèse fondamentale : Il existe une variable intermédiaire, apparaissant au cours du calcul de l'algorithme, telle que la connaissance de quelques bits de la clé (en pratique moins de 32 bits) permet de décider si deux entrées (respectivement deux sorties) donnent ou non la même valeur pour cette variable. La méthode de masquage La présente invention s'intéresse à la méthode de masquage , suggérée par Chari et al. [2]. Le principe de base consiste à programmer l'algorithme de telle sorte que l'hypothèse fondamentale ci-dessus ne soit plus vérifiée (ire. une variable intermédiaire ne dépend jamais de la connaissance d'un sous-ensemble facilement accessible de la clé secrète). Plus précisément, en utilisant un schéma de partage de clé, chacune des variables intermédiaires apparaissant dans l'algorithme cryptographique est séparée en plusieurs parties. De cette manière, un attaquant se trouve obligé d'analyser des distributions de plusieurs points, ce qui rend sa tâche exponentielle en le nombre d'éléments de la séparation. Le problème de conversion Pour des algorithmes qui combinent des fonctions booléennes et des fonctions arithmétiques, deux types de masquage doivent être utilisés : Un masquage booléen : x'= x K Un masquage arithmétique : A = x-r modulo 2. Ici, la variable x est masquée par la valeur aléatoire r, ce qui donne la valeur masquée x' (ou A). Notre objectif est de trouver un algorithme efficace pour passer du masquage booléen au masquage arithmétique et vice versa, tout en faisant en sorte que les variables intermédiaires soient décorrélées des données à masquer, ce qui assure la résistance à la DPA. Dans tout le présent document, on suppose que le processeur utilise des registres de K bits (en pratique K est la plupart du temps égal à 8, 16, 32 ou 64). Toutes les opérations arithmétiques (comme l'addition + , la soustraction - , ou le doublement z 2. z ) sont considérées modulo r. Pour des raisons de simplicité, le modulo 2K sera souvent omis dans la suite. L'invention concerne à cet effet un procédé de sécurisation d'un ensemble électronique comprenant un processeur et une mémoire, mettant en oeuvre un algorithme cryptographique stocké dans la mémoire et utilisant des opérations booléennes et des opérations arithmétiques, dans lequel au moins une variable est séparée en plusieurs parties, selon une séparation booléenne utilisant une opération booléenne, et selon une séparation arithmétique utilisant une opération arithmétique, caractérisé en ce que, pour passer de l'une quelconque de ces séparations à l'autre, on effectue, au moyen du processeur, un nombre prédéterminé d'opérations booléennes et arithmétiques sur lesdites parties et au moins un aléa, de manière à ce, pour chacune des valeurs apparaissant au cours du calcul, il n'y ait aucune corrélation avec ladite variable, le calcul aboutissant à un résultat stocké dans la mémoire. Avantageusement, pour passer de la séparation booléenne à la séparation arithmétique, le procédé comprend les étapes suivantes : - séparer toutes les parties sauf une en au moins deux éléments ; - calculer au moins deux résultats partiels ne dépendant jamais de tous les éléments d'une partie ; - pour obtenir chaque partie sauf une de la séparation arithmétique, regrouper au moins deux desdits résultats partiels. Avantageusement, la séparation desdites parties en au moins deux éléments utilise une opération booléenne. Avantageusement, ledit regroupement de deux desdits résultats partiels s'effectue au moyen d'une opération booléenne. Avantageusement, l'opération booléenne utilisée pour la séparation desdites parties en au moins deux éléments est l'opération "ou exclusif'. Avantageusement, l'opération booléenne utilisée pour le regroupement desdits résultats partiels s'effectue au moyen de l'opération "ou exclusif'. Avantageusement, pour passer de la séparation booléenne à la séparation arithmétique, on utilise uniquement les opérations "ou exclusif'et "soustraction". Avantageusement, la séparation booléenne, en deux parties, utilisant l'opération"ou exclusif et la séparation arithmétique, en deux parties, utilisant l'opération "addition", le procédé est caractérisé en ce que pour passer de la séparation booléenne à l'opération arithmétique, on utilise cinq opérations "ou exclusif'et deux opérations"soustraction". Avantageusement, pour passer de la séparation arithmétique à la séparation booléenne, on définit au moins une variable obtenue au moyen d'un nombre prédéterminé d'itérations successives à partir d'une valeur initiale qui est fonction d'au moins un aléa, par applications successives d'une transformation à base d'opérations booléennes et arithmétiques s'appliquant auxdites parties de la séparation arithmétique et audit au moins un aléa. Avantageusement, ladite transformation est à base des opérations "ou exclusif', "et logique"et"décalage logique d'un bit à gauche". Avantageusement, chaque partie sauf une de la séparation booléenne est obtenue en appliquant des opérations booléennes à ladite ou lesdites variables obtenues par itération successives, auxdites parties de la séparation arithmétique et audit ou auxdits aléas. Avantageusement, les opérations booléennes appliquées pour obtenir toutes les parties sauf une de la séparation booléenne sont l'opération "ou exclusif" et l'opération"décalage logique d'un bit vers la gauche". Avantageusement, pour sécuriser un ensemble électronique utilisant des registres de K bits, la séparation arithmétique, en deux parties, utilisant l'opération"addition"et la séparation booléenne, en deux parties, utilisant l'opération "ou exclusif" caractérisé en ce que pour passer de la séparation booléenne à l'opération arithmétique, on utilise (2K+4) opérations"ou exclusif', (2K+1) opérations"et logique", et K opérations"décalage logique d'un bit à gauche". L'invention concerne aussi un système embarqué comprenant un processeur et une mémoire, et mettant en oeuvre un algorithme cryptographique stocké dans la mémoire et utilisant des opérations booléennes et des opérations arithmétiques, dans lequel au moins une variable est séparée en plusieurs parties, selon une séparation booléenne utilisant une opération booléenne, et selon une séparation arithmétique utilisant une opération arithmétique, caractérisé en ce que, pour passer de l'une quelconque de ces séparations à l'autre, il comprend des moyens de conversion pour effectuer, au moyen du processeur, un nombre prédéterminé d'opérations booléennes et arithmétiques sur lesdites parties et au moins un aléa, de manière à ce, pour chacune des valeurs apparaissant au cours du calcul, il nit y ait aucune corrélation avec ladite variable, le calcul aboutissant à un résultat stocké dans la mémoire. Du masquage booléen au masquage arithmétique Pour calculer A = (x r)-r, on utilise l'algorithme suivant : Algorithme BooleanToArithmetic Entrée : tel que x = x'r. Sortie : (A, r) tel que x = A + r. Initialiser r à une valeur aléatoire y T L'algorithme BooleanToArithmetic utilise 2 variables auxiliaires (T et I), 1 appel au générateur aléatoire, et 7 opérations élémentaires (plus précisément : 5 XOR et 2 soustractions). Du masquage arithmétique au masquage booléen Pour calculer x'= (A + r) (j) r, on utilise l'algorithme suivant : Algorithme ArithmeticToBoolean Entrée : (A, r) tel que x = A + r. Sortie : (x r) tel que x = x'r. Initialiser r à une valeur aléatoire r XP, r xt Prar xi, (- T (DA T (- IA r 2PrAx' '-r4 r L'algorithme ArithmeticToBoolean utilise 3 variables auxiliaires (T, il eut 1), 1 appel au générateur aléatoire, et (5K+5) opérations élémentaires (plus précisément (2K+4) XOR , (2K+1) AND et K décalages à gauche ). En ce qui concerne le nombre des aléas intervenant dans le procédé selon l'invention, on notera qu'il peut y en avoir un ou plusieurs par variable et, dans le cas de plusieurs variables, il y aura en général plusieurs aléas respectivement associés auxdites variables. Bibliographie [1] Carolynn Burwick, Don Coppersmith, Edward D'Avignon, Rosario Gennaro, Shai Halevi, Charanjit Jutla, Stephen M. Matyas, Luke O'Connor, Mohammad Peyravian, David Safford et Nevenko Zunic, MARS-A Candidate Cipher for AES , Proposition pour l'AES, Juin 1998. Disponible sur http : //www. research. ibm. com/security/mars. pdf [2] Suresh Chari, Charantjit S. Jutla, Josyula R. Rao et Pankaj Rohatgi, Towards Sound Approaches to Counteract Power-Analysis Attacks , in Proceedings of Advances in Cryptology- CRYPTO'99, Springer-Verlag, 1999, pp. 398-412. [3] Jean-Sébastien Coron et Louis Goubin, On Boolean and Arithmetic Masking against Differential Power Analysis , in Proceedings of Workshop on Cryptographic Hardware and Embedded Systems, Springer-Verlag, Août 2000. [4] Louis Goubin et Jacques Patarin, DES and Differential Power Analysis-The Duplication Method , in Proceedings of Workshop on cryptographic Hardware and Embedded Systems, Springer-Verlag, Août 1999, pp. 158-172. [5] Paul Kocher, Joshua Jaffe et Benjamin Jun, Introduction to Differential Power Analysis and Related Attacks , http : //www. cryptography. com/dpa/technical, 1998. [6] Paul Kocher, Joshua Jaffe et Benjamin Jun, Differential Power Analysis , in Proceedings of Advances in Cryptology-CRYPTO'99, Springer-Verlag, 1999, pp. 388-397. [7] Xuejia Lai et James Massey, A Proposal for a New Block Encryption Standard , in Advances in Cryptology-EUROCRYPT'90 Proceedings, SpringerVerlag, 1991, pp. 389-404. [8] Thomas S. Messerges, Securing the AES Finalists Against Power Analysis Attacks , in Proceedings of Fast Software Encryption Workshop 2000, Springer- Verlag, Avril 2000. [9] Ronald L. Rivest, Matthew J. B. Robshaw, Ray Sidney et Yiqun L. Yin, The RC6 Block Cipher , vl. l, 20 août 1998. Disponible sur ftp : //ftp. rsasecurity. com/pub/rsalabs/aes/rc6vl 1. pdf [10] Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall et Niels Ferguson, Twofish : A 128-Bit Block Cipher , 15 juin 1998, soumission AES disponible sur : http : //www. counterpane. com/twofish. pdf Revendications 1. Procédé de sécurisation d'un ensemble électronique comprenant un processeur et une mémoire, mettant en oeuvre un algorithme cryptographique stocké dans la mémoire et utilisant des opérations booléennes et des opérations arithmétiques, dans lequel au moins une variable est séparée en plusieurs parties, selon une séparation booléenne utilisant une opération booléenne, et selon une séparation arithmétique utilisant une opération arithmétique, caractérisé en ce que, pour passer de l'une quelconque de ces séparations à l'autre, on effectue, au moyen du processeur, un nombre prédéterminé d'opérations booléennes et arithmétiques sur lesdites parties et au moins un aléa, de manière à ce, pour chacune des valeurs apparaissant au cours du calcul, il n'y ait aucune corrélation avec ladite variable, le calcul aboutissant à un résultat stocké dans la mémoire. 2. Procédé selon la revendication 1, caractérisé en ce que, pour passer de la séparation booléenne à la séparation arithmétique, le procédé comprend les étapes suivantes : - séparer toutes les parties sauf une en au moins deux éléments ; - calculer au moins deux résultats partiels ne dépendant jamais de tous les éléments d'une partie ; - pour obtenir chaque partie sauf une de la séparation arithmétique, regrouper au moins deux desdits résultats partiels. 3. Procédé selon la revendication 2, caractérisé en ce que la séparation desdites parties en au moins deux éléments utilise une opération booléenne. 4. Procédé selon la revendication 2, caractérisé en ce que ledit regroupement de deux desdits résultats partiels s'effectue au moyen d'une opération booléenne. 5. Procédé selon la revendication 3, caractérisé en ce que l'opération booléenne utilisée pour la séparation desdites parties en au moins deux éléments est l'opération "ou exclusif'. 6. Procédé selon la revendication 4, caractérisé en ce que l'opération booléenne utilisée pour le regroupement desdits résultats partiels s'effectue au moyen de l'opération "ou exclusif'. 7. Procédé selon la revendication 6, caractérisé en ce que pour passer de la séparation booléenne à la séparation arithmétique, on utilise uniquement les opérations "ou exclusif'et "soustraction". 8. Procédé selon la revendication 6, la séparation booléenne, en deux parties, utilisant l'opération "ou exclusif'et la séparation arithmétique, en deux parties, utilisant l'opération"addition", caractérisé en ce que pour passer de la séparation booléenne à l'opération arithmétique, on utilise cinq opérations "ou exclusif'et deux opérations"soustraction". 9. Procédé selon la revendication 1, caractérisé en ce que, pour passer de la séparation arithmétique à la séparation booléenne, on définit au moins une variable obtenue au moyen d'un nombre prédéterminé d'itérations successives à partir d'une valeur initiale qui est fonction d'au moins un aléa, par applications successives d'une transformation à base d'opérations booléennes et arithmétiques s'appliquant auxdites parties de la séparation arithmétique et audit au moins un aléa. 10. Procédé selon la revendication 9, caractérisé en ce que ladite transformation est à base des opérations"ou exclusif,"et logique"et"décalage logique d'un bit à gauche". 11. Procédé selon la revendication 9, caractérisé en ce que chaque partie sauf une de la séparation booléenne est obtenue en appliquant des opérations booléennes à ladite ou lesdites variables obtenues par itération successives, auxdites parties de la séparation arithmétique et audit ou auxdits aléas. 12. Procédé selon la revendication 11, caractérisé en ce que les opérations booléennes appliquées pour obtenir toutes les parties sauf une de la séparation booléenne sont l'opération"ou exclusif et l'opération"décalage logique d'un bit vers la gauche". 13. Procédé selon la revendication 12, pour sécuriser un ensemble électronique utilisant des registres de K bits, la séparation arithmétique, en deux parties, utilisant l'opération "addition" et la séparation booléenne, en deux parties, utilisant l'opération "ou exclusif", caractérisé en ce que pour passer de la séparation booléenne à l'opération arithmétique, on utilise (2K+4) opérations"ou exclusif, (2K+1) opérations"et logique", et K opérations"décalage logique d'un bit à gauche". 14. Système embarqué comprenant un processeur et une mémoire, et mettant en oeuvre un algorithme cryptographique stocké dans la mémoire et utilisant des opérations booléennes et des opérations arithmétiques, dans lequel au moins une variable est séparée en plusieurs parties, selon une séparation booléenne utilisant une opération booléenne, et selon une séparation arithmétique utilisant une opération arithmétique, caractérisé en ce que, pour passer de l'une quelconque de ces séparations à l'autre, il comprend des moyens de conversion pour effectuer, au moyen du processeur, un nombre prédéterminé d'opérations booléennes et arithmétiques sur lesdites parties et au moins un aléa, de manière à ce, pour chacune des valeurs apparaissant au cours du calcul, il n'y ait aucune corrélation avec ladite variable, le calcul aboutissant à un résultat stocké dans la mémoire.