FR2995110A1

FR2995110A1 - Method for optimizing use of e.g. memory, of electronic device i.e. smart card, involves protecting smart card from physical attacks by masking from substitution box and inverse substitution box upon implementing cryptographic algorithm

Info

Publication number: FR2995110A1
Application number: FR1258234A
Authority: FR
Inventors: Cyrille Pepin; Francois Lecocq; Victor Servant
Original assignee: Morpho SA
Current assignee: Idemia Identity & Security France Fr
Priority date: 2012-09-04
Filing date: 2012-09-04
Publication date: 2014-03-07
Anticipated expiration: 2032-09-04
Also published as: FR2995110B1

Abstract

The method involves protecting an electronic device i.e. smart card from physical attacks by masking from a substitution box (SBOX) and an inverse substitution box (INV SBOX) when the smart card implements a cryptographic algorithm. An inverse function (INV F) of the substitution box is closely followed by a closely connected function (AFF F), and a closely connected reciprocal function (R AFF F) of the inverse substitution box is followed by the inverse function. A masked inverse function (MSK INV F) is generated. Independent claims are also included for the following: (1) a computer program for optimizing the use of the memory of an electronic device (2) a non-transitory computer readable storage medium storing a program for optimizing the use of the memory of an electronic device (3) an electronic device.

Description

OPTIMISATION MEMOIRE CRYPTOGRAPHIQUE L'invention concerne l'optimisation mémoire de dispositifs électroniques mettant en oeuvre des algorithmes cryptographiques (tels que l'AES) et leur protection contre des attaques physiques telles que des attaques par canal auxiliaire. Les dispositifs électroniques mettant en oeuvre des algorithmes cryptographiques ont souvent des capacités mémoire très restreintes. En particulier, la mémoire vive (RAM) disponible se limite parfois à quelques milliers voire quelques centaines d'octets. C'est le cas notamment des cartes à puces cryptographiques, et en particulier des modèles les plus simples de telles cartes à puce. Les attaques par canaux auxiliaires exploitent des propriétés physiques du dispositif électronique attaqué lorsqu'il met en oeuvre un algorithme cryptographique (la mise en oeuvre pouvant être logicielle, matérielle, voire mixte : logicielle et matérielle). Le fait que l'algorithme cryptographique soit sécurisé d'un point de vue purement mathématique (c'est-à-dire en théorie) ne garantit pas nécessairement que la mise en oeuvre pratique de cet algorithme cryptographique par un dispositif électronique donné soit sécurisée.The invention relates to memory optimization of electronic devices implementing cryptographic algorithms (such as AES) and their protection against physical attacks such as auxiliary channel attacks. Electronic devices implementing cryptographic algorithms often have very limited memory capacity. In particular, the available random access memory (RAM) is sometimes limited to a few thousand or even a few hundred bytes. This is particularly the case of cryptographic smart cards, and in particular the simplest models of such smart cards. Auxiliary channel attacks exploit physical properties of the attacked electronic device when it implements a cryptographic algorithm (the implementation can be software, hardware, or even mixed: software and hardware). The fact that the cryptographic algorithm is secure from a purely mathematical point of view (that is, in theory) does not necessarily guarantee that the practical implementation of this cryptographic algorithm by a given electronic device is secure.

Il est ainsi connu d'attaquer un dispositif électronique de façon non- invasive en procédant à une observation extérieure de certains de ces paramètres de fonctionnement. Un attaquant peut par exemple se livrer à une cryptanalyse acoustique consistant à étudier le bruit éventuellement généré par le dispositif électronique lorsqu'il met en oeuvre l'algorithme cryptographique. En effet, le dispositif électronique peut émettre un bruit (ou des vibrations éventuellement inaudibles) variant en intensité et en nature selon les opérations effectuées. Des condensateurs qui se chargent ou se déchargent peuvent notamment émettre des claquements qui peuvent être mesurables.It is thus known to attack an electronic device in a non-invasive manner by making an external observation of some of these operating parameters. An attacker can for example engage in acoustic cryptanalysis consisting of studying the noise possibly generated by the electronic device when it implements the cryptographic algorithm. Indeed, the electronic device can emit a noise (or possibly inaudible vibrations) varying in intensity and nature depending on the operations performed. Capacitors that load or discharge can in particular emit clicks that can be measurable.

Il est également connu d'analyser les émanations électromagnétiques du dispositif électronique, ou d'analyser son image thermique. En effet, le rayonnement électromagnétique d'un dispositif électronique, par exemple d'un processeur, dépend de ce que ce dispositif est en train d'effectuer, par exemple d'une instruction que le processeur est en train d'exécuter ou d'une donnée que le processeur est en train de manipuler.It is also known to analyze the electromagnetic emanations of the electronic device, or to analyze its thermal image. Indeed, the electromagnetic radiation of an electronic device, for example a processor, depends on what this device is performing, for example an instruction that the processor is executing or a piece of data that the processor is manipulating.

Les attaquants peuvent également analyser la consommation électrique du dispositif électronique lors de l'exécution de l'algorithme cryptographique. Différentes parties de l'algorithme cryptographique peuvent engendrer des consommations caractéristiques. Il est donc possible d'analyser la consommation électrique instantanée d'un dispositif électronique, et de distinguer ainsi les tâches accomplies en fonction de la consommation électrique qu'elles requièrent. Ces attaques peuvent être combinées pour obtenir des informations secrètes telles qu'une clé de chiffrement utilisée par l'algorithme cryptographique. La mise en ceuvre de ces attaques est généralement étroitement liée au dispositif électronique attaqué. Ainsi, ces attaques peuvent le cas échéant permettre, via l'utilisation d'un canal auxiliaire (non envisagé ou non suffisamment protégé par le concepteur du dispositif électronique), tel qu'un canal d'ondes acoustiques, un canal électromagnétique, ou encore un canal thermique (les exemples de canaux donnés ne sont nullement limitatifs) d'affecter la sécurité de la mise en ceuvre considérée de l'algorithme cryptographique. Un algorithme cryptographique est un algorithme qui vise à protéger une information, en assurant par exemple sa confidentialité, son authenticité, ou son intégrité, grâce aux mathématiques. Un algorithme cryptographique s'appuie souvent sur une ou plusieurs clés, qui peuvent être notamment secrètes, privées, ou publiques. Certains algorithmes cryptographiques n'utilisent pas de clé, c'est le cas notamment de certaines fonctions de hachage (telles que les fonctions SHA-1, MD5, SHA-256, RIPEMD-160, etc.). Parmi les algorithmes cryptographiques on trouve notamment des algorithmes de chiffrement (qui permettent de rendre une information inintelligible) et des algorithmes de déchiffrement (qui permettent de récupérer l'information d'origine à partir d'une information chiffrée), des algorithmes de signature électronique, de vérification de signature, d'authentification, de vérification d'authentification, etc. Parmi les algorithmes cryptographiques s'appuyant sur des clés, certains sont dits symétriques (par exemple les algorithmes DES, 3DES, AES, RC4, HMAC, etc.). Certains algorithmes symétriques sont spécialisés (par exemple l'algorithme HMAC sert pour la signature/vérification de signature mais pas pour le chiffrement/déchiffrement). Les algorithmes symétriques tirent leur nom du fait qu'ils utilisent la même clé (on parle généralement de clé secrète) pour chiffrer et pour déchiffrer, ou encore pour signer et vérifier une signature, etc. Ainsi, les algorithmes cryptographiques symétriques imposent ils à deux parties les utilisant pour sécuriser leurs communications de partager des clés. L'algorithme AES (« Advanced Encryption Standard ») est notable car il est l'algorithme qui a été choisi en 2000 par le National Institute of Standards and Technology (ou « NIST ») afin de devenir l'algorithme de chiffrement symétrique standard pour le gouvernement des Etats-Unis d'Amérique. D'autres algorithmes cryptographiques sont qualifiés d'asymétriques (par exemple les algorithmes DSA, RSA, les courbes elliptiques, etc.) car une clé différente est utilisée par les parties à une communication. Chaque partie dispose d'une clé privée (on parle plutôt de clé privée que de clé secrète en pareil cas, même si l'on rencontre parfois des abus de langage) et d'une clé publique associée. Par exemple une partie peut utiliser une de ses clés privées pour signer une information, et c'est une clé publique correspondante qui est utilisée par l'autre partie pour vérifier la signature, ou encore une partie peut utiliser une clé publique appartenant à une autre partie pour chiffrer une information, et l'autre partie peut alors utiliser sa clé privée correspondante pour déchiffrer l'information. Les algorithmes cryptographiques sont souvent décrits de façon très précise dans des spécifications accessibles à tous, la sécurité d'un algorithme cryptographique n'étant généralement pas liée au caractère secret ou non de son fonctionnement (les algorithmes qui ne sont présumés sûrs qu'en raison de leur caractère secret finissent souvent par être cassés par ingénierie inverse). Les spécifications permettent de déterminer ce qu'un algorithme doit produire en sortie lorsqu'on lui donne une certaine information en entrée. Ceci permet de s'assurer de l'interopérabilité de l'algorithme cryptographique, c'est-à-dire que des implémentations distinctes doivent pouvoir fonctionner entre elles. Par exemple, on peut légitimement s'attendre à ce qu'une information chiffrée par toute implémentation d'un algorithme de chiffrement puisse être déchiffrée par toute implémentation de l'algorithme de déchiffrement correspondant. Cependant, ceci ne signifie pas qu'il n'existe qu'une implémentation possible de chaque algorithme cryptographique. Au contraire, il existe des multitudes d'implémentations possibles pour chaque algorithme cryptographique, de même qu'il existe des multitudes de manières différentes d'effectuer un même calcul. Par exemple, pour calculer X2+2X+1, on peut notamment calculer X*X, puis 2*X, puis ajouter les deux termes puis ajouter 1, ou bien calculer X+1, multiplier le résultat par X, puis ajouter 1, ou encore calculer X+1 et élever le résultat au carré.Attackers can also analyze the power consumption of the electronic device while executing the cryptographic algorithm. Different parts of the cryptographic algorithm can generate characteristic consumptions. It is therefore possible to analyze the instantaneous power consumption of an electronic device, and thus distinguish the tasks performed according to the power consumption they require. These attacks can be combined to obtain secret information such as an encryption key used by the cryptographic algorithm. The implementation of these attacks is usually closely related to the attacked electronic device. Thus, these attacks may, where appropriate, allow, via the use of an auxiliary channel (not envisaged or not sufficiently protected by the designer of the electronic device), such as an acoustic wave channel, an electromagnetic channel, or a thermal channel (the examples of given channels are in no way limiting) to affect the security of the implementation of the cryptographic algorithm considered. A cryptographic algorithm is an algorithm that aims to protect information, for example by ensuring its confidentiality, authenticity, or integrity through mathematics. A cryptographic algorithm often relies on one or more keys, which can be secret, private, or public. Some cryptographic algorithms do not use a key, such as some hash functions (such as SHA-1, MD5, SHA-256, RIPEMD-160, etc.). Among the cryptographic algorithms are in particular encryption algorithms (which make it possible to make information unintelligible) and decryption algorithms (which make it possible to recover the original information from an encrypted information), electronic signature algorithms , signature verification, authentication, authentication verification, etc. Some key-based cryptographic algorithms are called symmetric (eg DES, 3DES, AES, RC4, HMAC, etc.) algorithms. Some symmetric algorithms are specialized (for example the HMAC algorithm is used for signature / signature verification but not for encryption / decryption). Symmetric algorithms get their name from the fact that they use the same key (usually called a secret key) to encrypt and decrypt, or to sign and verify a signature, and so on. Thus, symmetric cryptographic algorithms require two parties using them to secure their communications from sharing keys. The Advanced Encryption Standard (AES) algorithm is notable because it is the algorithm that was chosen in 2000 by the National Institute of Standards and Technology (or "NIST") to become the standard symmetric encryption algorithm for the Government of the United States of America. Other cryptographic algorithms are called asymmetric (eg DSA, RSA, elliptic curves, etc.) because a different key is used by the parties to a communication. Each party has a private key (we speak rather of private key than secret key in such a case, even if one sometimes encounters abuse of language) and of an associated public key. For example, a party may use one of his private keys to sign information, and it is a corresponding public key that is used by the other party to verify the signature, or a party may use a public key belonging to another party. part to encrypt information, and the other party can then use his corresponding private key to decrypt the information. Cryptographic algorithms are often described very precisely in specifications accessible to all, the security of a cryptographic algorithm is generally not related to the secret nature or not of its operation (the algorithms that are only presumed safe because their secret character often end up being broken by reverse engineering). The specifications are used to determine what an algorithm should output when given some input information. This ensures the interoperability of the cryptographic algorithm, that is to say that separate implementations must be able to work between them. For example, it can legitimately be expected that information encrypted by any implementation of an encryption algorithm can be decrypted by any implementation of the corresponding decryption algorithm. However, this does not mean that there is only one possible implementation of each cryptographic algorithm. On the contrary, there are multitudes of possible implementations for each cryptographic algorithm, just as there are multitudes of different ways to perform the same calculation. For example, to calculate X2 + 2X + 1, we can calculate X * X, then 2 * X, add the two terms, add 1, or calculate X + 1, multiply the result by X, and add 1, or else calculate X + 1 and raise the result squared.

On aurait pu penser que la sécurité d'un algorithme cryptographique ne dépend que de sa définition mathématique (et des éventuelles clés qui sont utilisées, lorsque ces dernières sont secrètes ou privées), telle qu'elle ressort d'une spécification, et non de la façon exacte dont il calcule le résultat défini dans la spécification. En réalité, il n'en est rien, en général, comme cela a été illustré plus haut à l'aide de l'exemple des attaques par canaux auxiliaires. Il s'avère que la sécurité d'une mise en oeuvre particulière d'un algorithme cryptographique ne dépend pas seulement de l'algorithme cryptographique lui-même, mais également de la façon dont il est implémenté, et d'autres facteurs tels que les caractéristiques du dispositif électronique chargé de l'exécuter.One would have thought that the security of a cryptographic algorithm depends only on its mathematical definition (and any keys that are used, when they are secret or private), as it appears from a specification, and not from the exact way in which it calculates the result defined in the specification. In reality, it is not, in general, as was illustrated above using the example of attacks by auxiliary channels. It turns out that the security of a particular implementation of a cryptographic algorithm does not only depend on the cryptographic algorithm itself, but also on the way it is implemented, and other factors such as characteristics of the electronic device responsible for executing it.

Il est notamment bien connu que lorsqu'un dispositif électronique non protégé exécute un logiciel mettant en oeuvre un algorithme cryptographique de manière « naïve » c'est-à-dire d'une manière qui se contente de produire le résultat numérique attendu selon la spécification (tel qu'un résultat de chiffrement) à partir d'une entrée donnée, il est souvent possible d'effectuer une écoute passive du dispositif électronique et d'obtenir des informations critiques sur le déroulement de l'algorithme cryptographique. L'écoute passive présente l'avantage d'être non invasive. Le dispositif électronique n'est pas endommagé, et son propriétaire ne se rend pas nécessairement compte qu'il a été attaqué. Ainsi, le dispositif a pu être subtilisé et rendu sans que son propriétaire ne le soupçonne, ou simplement utilisé en l'absence du propriétaire, voire espionné en présence du propriétaire, sans que ce dernier ne le remarque (par exemple par un module dissimulé entre le dispositif électronique et son alimentation électrique). Ainsi, le propriétaire d'un dispositif électronique dont une clé AES a été extraite par un attaquant n'est pas amené à révoquer sa clé AES (il n'a aucune raison de penser qu'il a été attaqué). L'attaquant peut ensuite utiliser librement la clé AES jusqu'à ce que le propriétaire finisse par se rendre compte que des opérations qu'il n'a pas effectuées (par exemple des transferts de fonds électroniques), lui sont prétendument attribuées, ou qu'un tiers a manifestement eu accès à des informations confidentielles (par exemple un concurrent répondant à plusieurs reprises à de mêmes appels d'offres en étant de très peu le moins disant).It is notably well known that when an unprotected electronic device executes software implementing a cryptographic algorithm in a "naive" manner, that is to say in a manner that merely produces the expected numerical result according to the specification (Such as an encryption result) from a given input, it is often possible to perform a passive listening of the electronic device and to obtain critical information on the progress of the cryptographic algorithm. Passive listening has the advantage of being non-invasive. The electronic device is not damaged, and its owner does not necessarily realize that it has been attacked. Thus, the device could be stolen and returned without its owner suspecting it, or simply used in the absence of the owner, or even spied in the presence of the owner, without the latter noticing (eg by a module hidden between the electronic device and its power supply). Thus, the owner of an electronic device whose AES key has been extracted by an attacker is not required to revoke his AES key (he has no reason to believe that he has been attacked). The attacker can then freely use the AES key until the owner finally realizes that transactions he has not made (eg electronic funds transfers), are allegedly attributed to him, or that a third party obviously had access to confidential information (for example, a competitor repeatedly responding to the same calls for tenders by being the lowest bidder).

Une écoute passive élémentaire peut consister simplement à identifier une caractéristique donnée en fonction d'une mesure donnée sur le dispositif électronique ciblé. C'est le cas par exemple des attaques dites SPA (de l'anglais « Simple Power Analysis »). Par exemple, lors d'une exponentiation modulaire effectuée dans une implémentation « naïve » de l'algorithme RSA, la consommation électrique est très différente lorsqu'un bit de l'exposant est égal à 1 (forte consommation) et lorsque ce bit est égal à 0 (consommation plus faible). En effet, dans les implémentations communes, un bit à 1 implique à la fois une opération d'élévation au carré et une opération de multiplication (dite « square and multiply » en anglais, la traduction française pouvant être : « élève au carré et multiplie »), alors qu'un bit à 0 n'implique qu'une opération d'élévation au carré. On peut ainsi, en observant la trace de la consommation électrique lors de l'exponentiation modulaire, repérer les séries de 1 et de 0 de l'exposant, qui correspondent à des fluctuations de consommation électrique. Or l'exposant RSA, dans le cas où il s'agit d'un exposant privé, est une donnée extrêmement confidentielle constitutive de la clé privée RSA, qui en général n'est pas censée être connue de quiconque en dehors du dispositif électronique. Obtenir la clé privée de signature d'une personne permet ainsi de signer en son nom, obtenir sa clé privée de déchiffrement permet de déchiffrer ses messages. Cependant, ces écoutes (simples à mettre en oeuvre) ne sont pas toujours efficaces. On connaît des écoutes plus élaborées, telles que les attaques dites DPA (de l'anglais « Differential Power Analysis »), durant lesquelles un attaquant exécute un algorithme cryptographique à de multiples reprises, et enregistre à chaque fois les traces produites (par exemple les traces de consommation de courant). Par la suite l'attaquant effectue des calculs statistiques sur la base des multiples enregistrements, et obtient des informations d'une façon plus fiable et plus difficile à empêcher. Afin de se prémunir contre ces attaques, il est possible de sécuriser le dispositif électronique lui-même. Par exemple, on peut superposer un bruit sur l'alimentation électrique afin de rendre son exploitation plus difficile, lisser la consommation électrique (par exemple avec des condensateurs), limiter les émissions électromagnétiques par des blindages adéquats, etc. On peut aussi utiliser une horloge interne particulière, ayant pour caractéristique d'avoir une fréquence de fonctionnement variable de manière aléatoire, ce qui rend les mesures difficiles à exploiter (les opérations de l'algorithme cryptographique étant alors effectuées à une cadence qui ne cesse de varier, et qui est a priori inconnue de l'attaquant). Il existe également d'autres techniques, consistant par exemple à contrôler l'accès physique et/ou l'accès logique au dispositif électronique. Par exemple, les cartes à puce mettant en oeuvre des algorithmes cryptographiques à clé privée protègent généralement les opérations concernées par un code PIN. Ainsi, une personne qui volerait temporairement la carte à puce en espérant en extraire la clé privée puis rendre la carte à son propriétaire sans qu'il ne s'en rende compte, ne pourrait exécuter l'algorithme concerné sans présenter le bon code PIN (qu'un utilisateur averti apprend par coeur et ne communique à personne), et ne serait donc pas nécessairement en mesure d'effectuer l'attaque.Basic passive listening may simply consist in identifying a given characteristic according to a given measurement on the targeted electronic device. This is the case, for example, of so-called SPA (Simple Power Analysis) attacks. For example, during a modular exponentiation carried out in a "naïve" implementation of the RSA algorithm, the electrical consumption is very different when a bit of the exponent is equal to 1 (high consumption) and when this bit is equal at 0 (lower consumption). Indeed, in common implementations, a bit at 1 implies both a squaring operation and a multiplication operation (called "square and multiply" in English, the French translation being able to be: "pupil squared and multiplies ), While a 0 bit implies only a squaring operation. It is thus possible, by observing the trace of the electrical consumption during the modular exponentiation, to identify the series of 1 and 0 of the exponent, which correspond to fluctuations in electrical consumption. However, the RSA exhibitor, in the case of a private exhibitor, is an extremely confidential datum constituting the RSA private key, which in general is not supposed to be known to anyone outside the electronic device. Obtaining a person's private signature key allows you to sign on your behalf, so getting your private decryption key decrypts your messages. However, these plays (simple to implement) are not always effective. We know more sophisticated tapping, such as attacks called DPA (Differential Power Analysis), during which an attacker runs a cryptographic algorithm multiple times, and records each time the traces produced (eg traces of current consumption). Subsequently the attacker performs statistical calculations on the basis of multiple records, and obtains information in a more reliable and more difficult way to prevent. In order to guard against these attacks, it is possible to secure the electronic device itself. For example, a noise can be superimposed on the power supply in order to make its operation more difficult, to smooth the power consumption (for example with capacitors), to limit the electromagnetic emissions by adequate shielding, etc. It is also possible to use a particular internal clock, whose characteristic is to have a frequency of operation which varies randomly, which makes the measurements difficult to exploit (the operations of the cryptographic algorithm being then carried out at a rate which does not stop vary, and which is a priori unknown to the attacker). There are also other techniques, for example to control physical access and / or logical access to the electronic device. For example, smart cards implementing private key cryptographic algorithms generally protect the operations concerned by a PIN code. Thus, a person who temporarily steals the smart card hoping to extract the private key and then return the card to its owner without him realizing it, could not execute the algorithm concerned without presenting the correct PIN code ( that an informed user learns by heart and does not communicate to anyone), and therefore would not necessarily be able to perform the attack.

Ces techniques de contremesure sont utiles, mais généralement insuffisantes à elles seules, car elles ne protègent pas contre tous les scénarios d'attaques. Une autre méthode de protection consiste à utiliser un procédé de sécurisation de l'algorithme cryptographique, consistant à implémenter l'algorithme d'une manière telle qu'il génère le minimum de fluctuations (électriques ou autres). Par exemple, il est possible de modifier l'implémentation d'un algorithme RSA utilisant une clé privée de façon à ce qu'il effectue des opérations ayant la même signature (électrique, électromagnétique, etc.) lors d'un bit 1 ou lors d'un bit 0 dans l'exposant privé de la clé privée. Par exemple on peut effectuer un « square and multiply » quoi qu'il en soit, le résultat de l'opération de multiplication n'étant utilisé que dans le cas où le bit est à 1. Il faut évidemment être très vigilant, et s'arranger pour que l'implémentation soit aussi symétrique que possible. Par exemple s'il y a un test vérifiant que le résultat de la multiplication doit ou non être utilisé, il faut que ce test se comporte de la même manière quelle que soit son issue (ou du moins d'une manière aussi proche que possible), sinon une écoute passive pourrait cibler ce test afin de déterminer s'il s'agissait d'un bit à 0 ou d'un bit à 1. Un autre procédé de sécurisation (qui peut être complémentaire du précédent) consiste à masquer les données sensibles. Les données sensibles peuvent être par exemple des clés cryptographiques, et/ou un message d'entrée devant par exemple être chiffré par l'algorithme cryptographique, et/ou certaines données intermédiaires manipulées durant l'exécution de l'algorithme cryptographique. En effet, dans certains cas l'attaquant peut connaître voire choisir un message d'entrée à traiter par l'algorithme cryptographique, et faire des prédictions bien plus précises sur le calcul en cours. Le fait que le message d'entrée et/ou les données intermédiaires soient masqués d'une manière a priori imprévisible par l'attaquant lui retire ainsi une partie de l'information et peut ainsi compliquer singulièrement l'attaque. De plus, pour peu que le masquage soit différent lors de chaque utilisation de l'algorithme cryptographique, l'analyse statistique peut être compliquée. Par exemple, plusieurs procédés de protection par masquage de l'algorithme AES ont été proposés pour se prémunir des attaques par canaux cachés. Une solution traditionnelle est un masquage du type additif où les données manipulées x sont remplacées par des données masquées x + m (+ désignant 2 9 9 5 1 1 0 8 ici le « ou exclusif »). Cela permet de passer facilement à travers les opérations linéaires de l'algorithme. Les tables (non-linéaires) de substitution S[] sont alors remplacées par des tables masquées générées à la volée après le tirage d'un nouveau masque (ou toutes pré-stockées en mémoire, si la 5 quantité de mémoire le permet). Ainsi, une opération non linéaire masquée correspondant à une boîte de substitution masquée S'[], appliquée à une donnée x masquée par un masque aléatoire ml peut s'écrire sous la forme: y'= + mil = y + m2 = S[x] + m2 m2 étant un masque correspondant. En fin d'algorithme, on démasque le 10 résultat pour obtenir le résultat final (donnée originale chiffrée et non masquée). Il existe d'autres attaques contre lesquelles il peut être utile de se protéger telles que par exemple les attaques invasives (attaques par introduction de fautes, attaques DFA, etc.). 15 Un point commun courant des contremesures proposées contre diverses attaques existantes est leur consommation souvent accrue de mémoire. Ceci pose problème dans le cadre de dispositifs électroniques à mémoire contrainte. De plus, la technique de re-calcul et masquage de la boîte de substitution 20 communément employée, telle que décrite dans l'article « An AES Smart Card Implementation Resistant to Power Analysis Attacks » (Herbst, C., Oswald, E., Mangard, S., In: Zhou, J., Yung, M., Bao, F. (eds.) ACNS 2006. LNCS, vol. 3989, pp. 239-252, Springer, Heidelberg 2006) réduit l'intérêt d'une version plus légère en mémoire de l'AES spécifiée dans le standard concerné (AES 25 Proposal: Rijndael, Document version 2, Date: 03/09/99, Joan Daemen, Vincent Rijmen, disponible à l'adresse suivante, comprenant deux m dans le mot « amended » : csrc.nist.gov/archive/aes/rijndael/Rijndael-ammended.pdf) Plusieurs attaques sont susceptibles de compromettre les schémas de protection existants de l'AES, qui impliquent pourtant déjà souvent une mise 30 en oeuvre de l'AES exigeant une consommation mémoire plus importante ainsi qu'un temps d'exécution plus long qu'un AES non modifié. De plus, les 2 9 9 5 1 10 9 composants dédiés (solutions purement matérielles) à cet algorithme AES ne sont pas toujours disponibles et une implémentation logicielle est alors nécessaire, ce qui peut ralentir encore davantage l'exécution de l'algorithme (et dégrader ses performances du point de vue de l'utilisateur final). 5 L'AES opère sur une entrée appelée tableau d'état, qui contient 16 octets (4x4). Il peut employer des clés de 128, 192 ou 256 bits. Pour simplifier, les exemples donnés s'appuieront sur le cas 128 bits sauf mention contraire. La structure de l'opération de chiffrement par AES est celle qui est illustrée sur la figure 1 (les noms de fonctions originaux sont conservés). La fonction de 10 déchiffrement AES, structurellement similaire, est bien connue de l'homme du métier. Afin de mettre en oeuvre la fonction de chiffrement ou de déchiffrement AES, il est nécessaire de procéder préalablement à une expansion de clé. A partir de la clé AES, on crée ainsi (via la procédure d'expansion) une clé 15 étendue de taille nettement supérieure à la taille de la clé. Par exemple la clé étendue pour l'AES-128 occupe 176 octets, la clé étendue pour l'AES-192 occupe 208 octets et la clé étendue pour l'AES-256 occupe 240 octets. Ceci est souvent prohibitif pour des dispositifs électroniques à mémoire limitée tels que des cartes à puce. Afin de restreindre l'utilisation de la 20 mémoire, il est possible de tirer partie du fait que la clé étendue n'est utilisée qu'au fur et à mesure du déroulement du chiffrement (ou du déchiffrement). Ainsi, pour l'AES-128, on utilise la clé étendue par groupes de 16 octets consécutifs. Il est ainsi possible de ne réaliser l'expansion de la clé que progressivement (au fur et à mesure) par bloc de 16 octets, chaque nouveau 25 bloc de 16 octets de clé étendue écrasant le bloc de 16 octets précédent déjà utilisé, et ainsi de n'utiliser que 16 octets de mémoire (typiquement de la RAM) au lieu de 176 octets pour la clé étendue complète. Cependant, la procédure d'expansion s'appuie sur une fonction dite boîte (ou table) de substitution (souvent abrégée par les acronymes SBOX ou 30 S-BOX issus de l'anglais, voire par la notation S[]). Comme rappelé précédemment, une méthode de protection classique contre les attaques physiques consiste à masquer la boîte de substitution. Cette méthode nécessite typiquement l'utilisation d'une table de 256 octets en mémoire RAM (pour l'AES-128). Ainsi, la procédure d'expansion progressive, une fois protégée, consomme (pour l'AES-128), 16 octets courants plus 256 octets pour protéger la boîte de substitution, soit 272 octets. Ceci constitue un moindre mal dans le cadre d'une procédure de chiffrement, car la procédure de chiffrement elle-même nécessite de toute façon l'utilisation de la boîte de substitution (et donc les 256 octets supplémentaires sont de toute façon consommés si l'on sécurise cette boîte de substitution). Cependant, dans le cas d'une procédure de déchiffrement, la boîte de substitution est nécessaire pour l'expansion de la clé, mais le déchiffrement utilise, au lieu cette boîte de substitution, une boîte de substitution inverse (en toute rigueur on devrait plutôt parler de boîte de substitution réciproque, inverse étant un anglicisme, mais ce n'est pas le vocabulaire retenu en pratique). Cette boîte de substitution inverse, si elle est sécurisée par masquage, consomme elle aussi 256 octets. On a donc besoin de 16+256+256 = 528 octets, ce qui annule complètement le bénéfice de l'expansion progressive. Il est plus « rentable » en termes d'optimisation de la mémoire de réaliser une expansion complète, qui consomme 176+256 = 432 octets (176 octets pour la clé étendue et 256 octets pour la boîte de substitution masquée), puis après expansion complète, de récupérer les 256 octets occupés par la boîte de substitution masquée pour les réallouer à la boîte de substitution inverse masquée nécessaire pour le déchiffrement (opéré sur la base de la clé étendue). Cependant, 432 octets représentent une quantité de mémoire qui peut être prohibitive.These countermeasure techniques are useful, but generally insufficient, because they do not protect against all attack scenarios. Another method of protection is to use a method of securing the cryptographic algorithm, consisting in implementing the algorithm in such a way that it generates the minimum of fluctuations (electrical or otherwise). For example, it is possible to modify the implementation of an RSA algorithm using a private key so that it performs operations with the same signature (electrical, electromagnetic, etc.) during a bit 1 or when a 0 bit in the private exponent of the private key. For example one can perform a "square and multiply" anyway, the result of the multiplication operation being used only in the case where the bit is 1. It is obviously necessary to be very vigilant, and s arrange for the implementation to be as symmetrical as possible. For example, if there is a test verifying that the result of the multiplication should be used or not, the test must behave the same regardless of its outcome (or at least as close as possible) ), otherwise a passive listening could target this test to determine whether it was a 0 bit or a 1 bit. Another method of securing (which may be complementary to the previous one) is to hide the sensitive data. The sensitive data may be for example cryptographic keys, and / or an input message to for example be encrypted by the cryptographic algorithm, and / or some intermediate data manipulated during the execution of the cryptographic algorithm. Indeed, in some cases the attacker can know or even choose an input message to be processed by the cryptographic algorithm, and make much more accurate predictions on the current calculation. The fact that the input message and / or the intermediate data are masked in a manner unpredictable by the attacker thus withdraws a portion of the information and can thus singularly complicate the attack. Moreover, as long as the masking is different at each use of the cryptographic algorithm, the statistical analysis can be complicated. For example, several methods of masking protection of the AES algorithm have been proposed to guard against hidden channel attacks. A traditional solution is an additive type masking where the manipulated data x is replaced by masked data x + m (+ hereinafter denoting the "exclusive" or "exclusive"). This makes it easy to go through the linear operations of the algorithm. The (non-linear) substitution tables S [] are then replaced by hidden tables generated on the fly after the drawing of a new mask (or all pre-stored in memory, if the amount of memory permits). Thus, a masked non-linear operation corresponding to a masked substitution box S '[], applied to a datum x masked by a random mask ml can be written in the form: y' = + mil = y + m2 = S [ x] + m2 m2 being a matching mask. At the end of the algorithm, the result is unmasked to obtain the final result (original data encrypted and not masked). There are other attacks against which it can be useful to protect oneself such as for example the invasive attacks (attacks by introduction of faults, DFA attacks, etc.). A common common feature of proposed countermeasures against various existing attacks is their often increased memory consumption. This is problematic in the context of electronic devices with constrained memory. In addition, the technique of re-calculating and masking the commonly used substitution box as described in the article "An AES Smart Card Implementation Resist to Power Analysis Attacks" (Herbst, C., Oswald, E., Mangard, S., In: Zhou, J., Yung, M., Bao, F. (eds.) ACNS 2006. LNCS, vol 3989, pp. 239-252, Springer, Heidelberg 2006) reduces the interest of 'a lighter version in memory of the AES specified in the relevant standard (AES 25 Proposal: Rijndael, Document version 2, Date: 03/09/99, Joan Daemen, Vincent Rijmen, available at the following address, including two m in the word "amended": csrc.nist.gov/archive/aes/rijndael/Rijndael-ammended.pdf) Several attacks are likely to compromise the existing protection schemes of the AES, which already often imply a 30 implementation of the AES requiring a higher memory consumption and a longer execution time than an unmodified AES. In addition, the dedicated components (purely hardware solutions) to this AES algorithm are not always available and a software implementation is then required, which may further slow down the execution of the algorithm (and degrade its performance from the point of view of the end user). 5 The AES operates on an input called a status table, which contains 16 bytes (4x4). It can use 128, 192 or 256 bit keys. For simplicity, the examples given will be based on the 128-bit case unless otherwise stated. The structure of the AES encryption operation is that which is illustrated in FIG. 1 (the original function names are retained). The structurally similar AES decryption function is well known to those skilled in the art. In order to implement the AES encryption or decryption function, it is necessary to carry out a key expansion beforehand. From the key AES, one thus creates (via the expansion procedure) an extended key of size much larger than the size of the key. For example, the extended key for the AES-128 is 176 bytes, the extended key for the AES-192 is 208 bytes, and the extended key for the AES-256 is 240 bytes. This is often prohibitive for electronic devices with limited memory such as smart cards. In order to restrict the use of memory, it is possible to take advantage of the fact that the extended key is used only as the encryption (or decryption) proceeds. Thus, for the AES-128, the extended key is used in groups of 16 consecutive bytes. It is thus possible to carry out the expansion of the key only progressively (as and when) in a block of 16 bytes, each new block of 16 bytes extended key overwriting the previous block of 16 bytes already used, and so to use only 16 bytes of memory (typically RAM) instead of 176 bytes for the full extended key. However, the expansion procedure relies on a so-called substitution box (or table) function (often abbreviated as SBOX or S-BOX acronyms from English, or even by S [] notation). As mentioned above, a traditional method of protection against physical attacks is to hide the substitution box. This method typically requires the use of a 256 byte table in RAM memory (for the AES-128). Thus, the progressive expansion procedure, once protected, consumes (for the AES-128), 16 current bytes plus 256 bytes to protect the substitution box, ie 272 bytes. This is a lesser evil in the context of an encryption procedure, because the encryption procedure itself anyway requires the use of the substitution box (and therefore the additional 256 bytes are anyway consumed if the we secure this box of substitution). However, in the case of a decryption procedure, the substitution box is necessary for the expansion of the key, but the decryption uses, instead of this substitution box, a box of inverse substitution (in all rigor one should rather talk of reciprocal substitution box, inverse is an anglicism, but this is not the vocabulary used in practice). This reverse substitution box, if secured by masking, also consumes 256 bytes. We need 16 + 256 + 256 = 528 bytes, which completely cancels the benefit of the progressive expansion. It is more "cost-effective" in terms of memory optimization to perform a full expansion, which consumes 176 + 256 = 432 bytes (176 bytes for the extended key and 256 bytes for the hidden substitution box), and then after full expansion , to recover the 256 bytes occupied by the hidden substitution box to reallocate them to the hidden inverse substitution box necessary for decryption (operated on the basis of the extended key). However, 432 bytes represent a quantity of memory that can be prohibitive.

L'invention vient améliorer la situation. Un aspect de l'invention concerne un procédé d'optimisation de l'utilisation de la mémoire d'un dispositif électronique, lorsque le dispositif 30 électronique met en ceuvre un algorithme cryptographique en le protégeant contre des attaques physiques par masquage d'une boîte de substitution et d'une boîte de substitution inverse, la boîte de substitution comprenant une fonction inverse suivie d'une fonction affine, la boîte de substitution inverse comprenant la fonction réciproque de la fonction affine suivie de la fonction inverse, le procédé générant une fonction inverse masquée.The invention improves the situation. One aspect of the invention relates to a method of optimizing the use of the memory of an electronic device, when the electronic device implements a cryptographic algorithm by protecting it against physical attacks by masking a box of substitution and an inverse substitution box, the substitution box comprising an inverse function followed by an affine function, the inverse substitution box comprising the inverse function of the affine function followed by the inverse function, the method generating an inverse function hidden.

Ce procédé est avantageux en ce qu'il permet de protéger, pour le même coût mémoire, à la fois la boîte de substitution et la boîte de substitution inverse. Ceci permet d'optimiser l'utilisation de la mémoire, en particulier dans le contexte d'une expansion de clé progressive utilisée pour une opération de déchiffrement. Par exemple, dans le cas de l'AES-128, le procédé ne nécessite que 272 octets (aussi bien pour un chiffrement que pour un déchiffrement), plutôt que 432 pour une expansion masquée complète séparée (antérieure au chiffrement ou déchiffrement proprement dit) selon l'état de l'art. L'expansion masquée progressive de l'état de l'art consomme quant à elle 272 octets également dans le cas d'un chiffrement (pas de gain), mais 528 octets dans le cas d'un déchiffrement (et nécessite alors de surcroît le calcul de deux masquages, celui de la boîte de substitution et celui de la boîte de substitution inverse), ce qui illustre là encore un avantage du procédé proposé. La quantité de mémoire nécessaire indiquée ci-dessous (par exemple 272 octets au lieu de 528 octets) ne tient pas compte de certaines exigences qui sont sensiblement identiques quel que soit le procédé mis en oeuvre. Par exemple la donnée à chiffrer et le résultat du chiffrement sont généralement stockés en mémoire, et ce indépendamment du procédé utilisé pour la mise en oeuvre de l'algorithme cryptographique. D'une manière plus rigoureuse, on pourrait donc affirmer que le procédé proposé requiert, dans l'exemple considéré, 272+X octets de mémoire au lieu de 528+X octets de mémoire. Un aspect de l'invention concerne un programme d'ordinateur comprenant une série d'instructions, qui, lorsqu'elle est exécutée par un processeur d'un dispositif électronique, conduit le processeur à mettre en oeuvre un procédé selon un aspect de l'invention.This method is advantageous in that it makes it possible to protect, for the same memory cost, both the substitution box and the inverse substitution box. This makes it possible to optimize the use of the memory, in particular in the context of a progressive key expansion used for a decryption operation. For example, in the case of AES-128, the method requires only 272 bytes (for both encryption and decryption), rather than 432 for separate full masked expansion (prior to encryption or decryption itself) according to the state of the art. The progressive masked expansion of the state of the art consumes for its part 272 bytes also in the case of an encryption (no gain), but 528 bytes in the case of a decryption (and then requires moreover the calculation of two masks, that of the substitution box and that of the inverse substitution box), which again illustrates an advantage of the proposed method. The amount of memory required indicated below (for example 272 bytes instead of 528 bytes) does not take into account some requirements that are substantially identical regardless of the method implemented. For example, the data to be encrypted and the result of the encryption are generally stored in memory, regardless of the method used for implementing the cryptographic algorithm. In a more rigorous way, one could therefore say that the proposed method requires, in the example considered, 272 + X bytes of memory instead of 528 + X bytes of memory. One aspect of the invention relates to a computer program comprising a series of instructions, which, when executed by a processor of an electronic device, causes the processor to implement a method according to an aspect of the invention.

Un aspect de l'invention concerne un support de stockage non transitoire lisible par ordinateur, le support stockant un programme d'ordinateur selon un aspect de l'invention.One aspect of the invention relates to a computer-readable non-transit storage medium, the medium storing a computer program according to one aspect of the invention.

Un aspect de l'invention concerne un dispositif électronique comprenant une mémoire et un circuit d'optimisation de mémoire, le circuit étant agencé, lorsque le dispositif électronique met en oeuvre un algorithme cryptographique en le protégeant contre des attaques physiques par masquage d'une boîte de substitution et d'une boîte de substitution inverse, la boîte de substitution comprenant une fonction inverse suivie d'une fonction affine, la boîte de substitution inverse comprenant la fonction réciproque de la fonction affine suivie de la fonction inverse, pour générer une fonction inverse masquée. D'autres aspects, buts et avantages de l'invention apparaîtront à la lecture de la description de quelques uns de ses modes de réalisation. L'invention sera également mieux comprise à l'aide des dessins, sur lesquels : - la figure 1 illustre l'algorithme cryptographique de chiffrement AES ; - la figure 2 illustre des procédés selon des modes de réalisation de l'invention ; - la figure 3 illustre un dispositif électronique selon un mode de réalisation de l'invention. La figure 1 montre de façon schématique la structure connue de l'algorithme cryptographique de chiffrement AES, et en particulier une première étape AddRoundKey, suivie d'une séquence de neuf tours effectuant chacun les étapes SubBytes (l'application de la boîte de substitution à chacun des octets du tableau d'état de l'AES), ShiftRows, MixColumns, puis à nouveau AddRoundKey, et enfin, à l'issue des neuf tours, les étapes SubBytes, ShiftRows, et AddRoundKey. La figure 1 ne montre pas l'étape préliminaire d'expansion de clé qui doit être réalisée avant de pouvoir chiffrer.One aspect of the invention relates to an electronic device comprising a memory and a memory optimization circuit, the circuit being arranged, when the electronic device implements a cryptographic algorithm by protecting it against physical attacks by masking a box. substitution and an inverse substitution box, the substitution box comprising an inverse function followed by an affine function, the inverse substitution box comprising the inverse function of the affine function followed by the inverse function, to generate an inverse function hidden. Other aspects, objects and advantages of the invention will appear on reading the description of some of its embodiments. The invention will also be better understood with the aid of the drawings, in which: FIG. 1 illustrates the cryptographic encryption algorithm AES; FIG. 2 illustrates methods according to embodiments of the invention; FIG. 3 illustrates an electronic device according to one embodiment of the invention. FIG. 1 schematically shows the known structure of the AES cryptographic encryption algorithm, and in particular a first AddRoundKey step, followed by a sequence of nine rounds each performing the SubBytes steps (the application of the substitution box to each byte of the AES status table), ShiftRows, MixColumns, then AddRoundKey again, and finally, after the nine rounds, the SubBytes, ShiftRows, and AddRoundKey steps. Figure 1 does not show the preliminary key expansion step that needs to be performed before it can be encrypted.

La figure 2 illustre de façon schématique le fonctionnement de procédés selon deux modes de réalisation possibles. Sur la gauche, un premier procédé commence par masquer (étape MSK), à l'aide d'un aléa, la fonction inverse INV_F de l'AES afin de produire une fonction inverse masquée MSK_INV_F. L'aléa peut être issu d'un générateur pseudo aléatoire du dispositif électronique s'appuyant sur des éléments matériels tels qu'un convertisseur analogique numérique numérisant un bruit analogique mesuré dans le dispositif électronique et lui appliquant un traitement mathématique (par exemple à l'aide d'un cryptoprocesseur du dispositif électronique). Un moyen possible de masquer la fonction inverse est de mettre en oeuvre cette fonction inverse sous forme de table INV_F et de générer une table de fonction inverse masquée MSK_INV_F selon l'algorithme suivant (pour une table à 256 éléments), dans lequel m et w sont des octets aléatoires et le symbole `+' désigne l'opération de « ou exclusif » : Pour i de 0 à 255: MSK_INV_F[i] = INV_F[i + m] + w Dans un deuxième temps, le procédé applique une boîte de substitution SBOX masquée à des données d'entrée INPUT, et génère une sortie correspondante OUTPUT. La mise en oeuvre de la boîte de substitution masquée consiste à appliquer la fonction inverse masquée MSK_INV_F aux données d'entrée INPUT, puis à appliquer au résultat de cette inversion masquée la fonction affine AFF_F de l'AES (non masquée). On obtient ainsi une boîte de substitution globalement masquée.Figure 2 schematically illustrates the operation of methods according to two possible embodiments. On the left, a first method starts by masking (step MSK), using a random error, the inverse function INV_F of the AES in order to produce a masked inverse function MSK_INV_F. The hazard may be derived from a pseudo-random generator of the electronic device based on hardware elements such as an analog digital converter digitizing an analog noise measured in the electronic device and applying to it a mathematical treatment (for example to the using a cryptoprocessor of the electronic device). One possible way of masking the inverse function is to implement this inverse function in the form of table INV_F and to generate a hidden inverse function table MSK_INV_F according to the following algorithm (for a table with 256 elements), in which m and w are random bytes and the symbol `+ 'designates the operation of" or exclusive ": For i from 0 to 255: MSK_INV_F [i] = INV_F [i + m] + w In a second step, the process applies a box masked SBOX substitution to INPUT input data, and generates a corresponding OUTPUT output. The implementation of the masked substitution box consists of applying the masked inverse function MSK_INV_F to the input data INPUT, then applying the affine function AFF_F of the AES (not masked) to the result of this hidden inversion. This gives a globally masked substitution box.

De façon similaire, sur la droite de la figure 2, un deuxième procédé commence par masquer (étape MSK identique à l'étape MSK du procédé précédent) la fonction inverse INV_F de l'AES afin de produire une fonction inverse masquée MSK_INV_F. Dans un deuxième temps, le procédé applique une boîte de substitution inverse INV_SBOX masquée à des données d'entrée INPUT, et génère une sortie correspondante OUTPUT. La mise en oeuvre de la boîte de substitution inverse masquée consiste à appliquer la fonction réciproque R_AFF_F de la fonction affine AFF_F de l'AES (non masquée) aux données d'entrée INPUT, puis à appliquer au résultat de cette fonction la fonction inverse masquée MSK_INV_F. On obtient ainsi une boîte de substitution inverse globalement masquée.Similarly, on the right of FIG. 2, a second method starts by masking (step MSK identical to step MSK of the preceding method) the inverse function INV_F of AES in order to produce a masked inverse function MSK_INV_F. In a second step, the method applies a masked inverse substitution box INV_SBOX to input data INPUT, and generates a corresponding output OUTPUT. The implementation of the masked inverse substitution box consists in applying the inverse function R_AFF_F of the affine function AFF_F of the AES (not masked) to the input data INPUT, then in applying to the result of this function the inverse function masked MSK_INV_F. This gives a globally masked inverse substitution box.

La figure 3 montre une carte à puce SCARD (de l'anglais « smartcard ») selon un mode de réalisation de l'invention. Cette carte à puce est équipée d'un microprocesseur MP, d'une mémoire MEM (qui est une mémoire vive de type RAM) et d'une mémoire morte de type ROM. La mémoire morte ROM stocke une table correspondant à une fonction inverse INV_F (non masquée), une table correspondant à une fonction affine AFF_F et une table correspondant à la fonction réciproque R_AFF_F de la fonction affine AFF_F. La mémoire MEM stocke une table correspondant à une fonction inverse masquée MSK_INV_F. La mémoire morte ROM enregistre un logiciel agencé, lorsqu'il est exécuté par le microprocesseur MP, pour mettre en oeuvre un procédé selon un mode de réalisation. Une carte à puce est un exemple possible de dispositif électronique pour lequel l'invention est particulièrement avantageuse, compte tenu de ses nombreuses applications dans le domaine de la cryptographie (cartes SIM authentifiant un utilisateur de téléphone portable vis-à-vis d'un opérateur, carte bancaire authentifiant le porteur lors d'une transaction financière, cartes de santé, etc.). Cependant l'invention s'applique à tout autre dispositif électronique, tel qu'un passeport électronique, un visa électronique, un permis de conduire électronique, une clé USB sécurisée, une carte secure MMC, un token (jeton sécurisé), etc. L'invention peut également être mise en oeuvre dans un serveur, un accélérateur SSL, un HSM, etc. La majorité des serveurs est moins sécurisée contre les attaques physiques qu'un dispositif sécurisé tel qu'une carte à puce. Ceci peut rendre ces serveurs vulnérables à des attaques beaucoup plus simples à mettre en oeuvre (que les attaques contre lesquelles l'invention permet de se protéger), telles que des attaques purement logicielles. Ces attaques logicielles (par virus, chevaux de Troie, etc.) peuvent potentiellement être menées à bien à distance sans nécessiter aucun accès physique. Il pourrait sembler saugrenu de chercher à se protéger contre des attaques complexes et contraignantes de type canaux auxiliaires alors qu'un attaquant situé sur un autre continent pourrait prendre le contrôle du serveur à distance et extraire des informations critiques de manière bien plus simple et bien moins dangereuse pour lui (pas d'intrusion, pas de vol de dispositif, etc.). Cependant certains serveurs ayant une vocation sécuritaire sont fortement sécurisés contre les attaques purement logicielles, et dans ce contexte les protéger également contre des attaques par canal auxiliaire est avantageux. De plus, l'optimisation de leur mémoire peut être utile, en particulier lorsqu'ils effectuent des très nombreuses opérations cryptographiques en parallèle (HSMs, accélérateurs SSL/TLS, etc.).Figure 3 shows a smart card SCARD ("smartcard") according to one embodiment of the invention. This smart card is equipped with a microprocessor MP, a memory MEM (which is a random access memory type RAM) and a read-only memory type ROM. The read-only memory ROM stores a table corresponding to a inverse function INV_F (not masked), a table corresponding to an affine function AFF_F and a table corresponding to the reciprocal function R_AFF_F of the affine function AFF_F. The memory MEM stores a table corresponding to a hidden inverse function MSK_INV_F. ROM ROM stores software arranged, when executed by the microprocessor MP, to implement a method according to one embodiment. A smart card is a possible example of an electronic device for which the invention is particularly advantageous, given its many applications in the field of cryptography (SIM cards authenticating a mobile phone user vis-à-vis an operator , bank card authenticating the bearer during a financial transaction, health cards, etc.). However, the invention applies to any other electronic device, such as an electronic passport, an electronic visa, an electronic driver's license, a secure USB key, a secure MMC card, a token (secure token), etc. The invention can also be implemented in a server, an SSL accelerator, an HSM, etc. The majority of servers are less secure against physical attacks than a secure device such as a smart card. This can make these servers vulnerable to attacks that are much simpler to implement (than the attacks against which the invention makes it possible to protect themselves), such as purely software attacks. These software attacks (by viruses, Trojans, etc.) can potentially be carried out remotely without requiring any physical access. It might seem absurd to try to protect against complex and constraining auxiliary channel attacks while an attacker on another continent could take control of the remote server and extract critical information in a much simpler and less dangerous for him (no intrusion, no device theft, etc.). However, some servers with a security vocation are highly secure against purely software attacks, and in this context also protect them against attacks by auxiliary channel is advantageous. In addition, the optimization of their memory can be useful, in particular when they perform a large number of cryptographic operations in parallel (HSMs, SSL / TLS accelerators, etc.).

Selon un mode de réalisation, un procédé optimise l'utilisation de la mémoire MEM (qui est une mémoire réinscriptible) d'un dispositif électronique SCARD (par exemple une carte à puce), lorsque le dispositif électronique met en oeuvre un algorithme cryptographique en le protégeant contre des attaques physiques. La protection résulte notamment d'un masquage d'une boîte de substitution SBOX et d'une boîte de substitution inverse INV_SBOX. Selon un mode de réalisation, l'algorithme cryptographique est l'AES. Cependant, l'algorithme cryptographique peut être plus généralement tout algorithme Rijndael autre que les algorithmes Rijndael retenus pour l'AES, et même tout algorithme cryptographique mettant en oeuvre une boîte de substitution SBOX comprenant une fonction inverse INV_F suivie d'une fonction affine AFF F et une boîte de substitution inverse INV_SBOX comprenant la fonction réciproque R_AFF_F de la fonction affine AFF_F suivie de la fonction inverse INV_F.According to one embodiment, a method optimizes the use of the memory MEM (which is a rewritable memory) of an electronic device SCARD (for example a smart card), when the electronic device implements a cryptographic algorithm by protecting against physical attacks. The protection results in particular from a masking of an SBOX substitution box and a reverse substitution box INV_SBOX. According to one embodiment, the cryptographic algorithm is the AES. However, the cryptographic algorithm may be more generally any Rijndael algorithm other than the Rijndael algorithms selected for the AES, and even any cryptographic algorithm implementing an SBOX substitution box comprising an inverse function INV_F followed by an affine function AFF F and an inverse substitution box INV_SBOX comprising the reciprocal function R_AFF_F of the affine function AFF_F followed by the inverse function INV_F.

Dans le cas de l'AES, la fonction inverse est l'inverse multiplicatif dans le groupe fini GF(28) défini dans l'AES, et la fonction affine est la fonction affine de l'AES, à savoir la fonction qui à l'octet B associe l'octet B' tel que : 16 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 o 0 1 1 1 1 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 Le procédé génère une fonction inverse masquée MSK_INV_F en masquant la fonction inverse INV_F (ce qui permet de sécuriser aussi bien la boîte de substitution que la boîte de substitution inverse). Selon un mode de réalisation, le procédé ne masque ni la fonction affine AFF_F, ni la fonction réciproque R_AFF_F de la fonction affine AFF_F. La fonction inverse INV_F masquée ne peut être stockée en mémoire non réinscriptible (telle que de la ROM) puisque par définition elle est définie de manière aléatoire lors de l'utilisation du procédé. Elle est donc générée (à partir de la fonction inverse INV_F) puis stockée dans la mémoire MEM, qui est une mémoire réinscriptible. Selon un mode de réalisation, la fonction inverse INV_F, la fonction affine AFF_F et la fonction réciproque R_AFF_F de la fonction affine AFF_F sont, quant à elles, enregistrées dans une mémoire du dispositif électronique autre que sa mémoire MEM. Par exemple, elles sont enregistrées en mémoire non réinscriptible (par exemple en mémoire ROM). En effet, selon un mode de réalisation, ces fonctions sont constantes et peuvent donc être définies lors de la fabrication (une fois pour toutes, en ROM). Elles peuvent également être enregistrées dans une mémoire réinscriptible non volatile (telle qu'une mémoire Flash ou EEPROM par exemple) autre que la mémoire MEM. Elles peuvent alors être enregistrées lors d'une configuration (et éventuellement d'une reconfiguration) du dispositif électronique. Il est en effet de plus en plus courant d'utiliser pour le système d'exploitation et les données constantes de certains dispositifs électroniques (tels que les cartes à puce) non plus une mémoire ROM, mais une mémoire réinscriptible non volatile (souvent une 2 9 9 5 1 1 0 17 mémoire Flash) afin d'augmenter la flexibilité de la fabrication du dispositif électronique (il n'est pas nécessaire de faire masquer un composant ROM chez un fondeur à chaque fois que l'on modifie un élément qui est situé en ROM et n'est pas modifiable par softmask). 5 Le procédé peut ainsi utiliser la fonction affine AFF_F et la fonction réciproque R_AFF_F de la fonction affine AFF_F (lors de la mise en oeuvre d'une boîte de substitution ou d'une boîte de substitution inverse) sans consommer de mémoire MEM supplémentaire, ou le cas échéant en consommant une quantité de mémoire MEM marginale par rapport à 10 l'optimisation mémoire obtenue. Cette éventuelle quantité de mémoire marginale « perdue » peut être liée par exemple à l'appel d'une fonction (AFF_F ou R_ AFF _F) qui peut, par exemple, selon sa mise en oeuvre, entraîner l'enregistrement dans une pile de la mémoire MEM de certaines informations (par exemple deux octets codant l'adresse de retour à utiliser 15 pour poursuivre l'exécution une fois AFF_F ou R_AFF_F exécutée, etc.). L'équivalent de ces informations n'aurait pas nécessairement été requis (en tant qu'enregistrement dans la mémoire MEM) dans une implémentation de l'état de l'art masquant la totalité de la boîte de substitution sous forme de table. Mais en tout état de cause, les quelques octets éventuellement perdus 20 (par exemple deux octets dans l'exemple ci-dessus) sont négligeables par rapport aux 160 voire 256 octets de mémoire MEM économisés grâce au procédé pour un déchiffrement en AES-128 par rapport aux procédés sécurisés de déchiffrement connus. Les données manipulées par la fonction affine AFF_F (et par la fonction 25 affine réciproque R_AFF_F) sont de préférence masquées. Il n'est pas pour autant nécessaire de modifier la fonction affine ni la fonction affine réciproque pourtant initialement conçues pour des données non masquées. En effet, ces fonctions sont linéaires. Il est donc possible de déterminer, à partir du résultat de la fonction affine (respectivement de la fonction affine réciproque) appliquée à une donnée masquée et de la valeur du masque, le résultat de la fonction affine (respectivement de la fonction affine réciproque) appliquée à la donnée non masquée. En effet, pour une fonction linéaire L, une donnée x et un masque m, on a L(x+m)=L(x)+L(m) et donc L(x)=L(x+m)+L(m) (l'opération `+' désignant le « ou exclusif »). Selon un mode de réalisation, la mémoire MEM est une mémoire volatile, telle qu'une RAM, ou plus précisément une SRAM, une DRAM, une MRAM, une DDRAM, une SDRAM, une RDRAM, une DDR SDRAM, une DDR2 SDRAM, une DDR3 SDRAM, une XDR DRAM, etc. La mémoire volatile du dispositif électronique est souvent la mémoire la plus critique car peu disponible (il y en a beaucoup moins que de mémoire non volatile). Par exemple il n'y a souvent que quelques centaines ou milliers d'octets de RAM contre plusieurs dizaines de milliers d'octets d'EEPROM dans une carte à puce. De même il n'y a souvent que quelques gigaoctets de RAM dans un serveur contre des téraoctets dans un disque dur de serveur. La mémoire RAM est généralement très rapide aussi bien en lecture qu'en écriture, mais nécessite une alimentation électrique permanente, l'interruption de l'alimentation conduisant à une perte des données enregistrées. Selon un autre mode de réalisation, la mémoire MEM comprend, aux fins de la mise en oeuvre de l'algorithme cryptographique, une mémoire non volatile réinscriptible (telle qu'une mémoire EEPROM ou Flash) pour le stockage d'informations temporaires telles que la clé étendue, ou telles que la fonction inverse masquée. Cependant l'écriture dans de telles mémoires est beaucoup plus complexe et lente que l'écriture en mémoire volatile de type RAM. Ceci conduit à des performances substantiellement réduites en termes de vitesse d'exécution. C'est également susceptible de donner lieu plus facilement à des attaques par canaux auxiliaires. De plus, le nombre d'écritures dans une mémoire non volatile réinscriptible est généralement limité. Par exemple, le fonctionnement de certaines mémoires EEPROM n'est garanti que pour 100000 écritures. Ce nombre d'écritures (100000) pourrait être atteint pour certaines applications, imposant la non utilisation des zones ayant atteint le seuil d'utilisation, qui se trouveraient ainsi perdues. Ceci accroîtrait d'autant la consommation de mémoire non volatile. Selon un mode de réalisation, l'utilisation d'une mémoire MEM non volatile complète donc l'utilisation d'une RAM comprise dans la mémoire MEM, RAM qui peut s'avérer être de taille insuffisante (en fonction des applications en cours d'exécution, etc.). La mémoire MEM peut ainsi combiner une mémoire RAM et (pour le cas où la RAM serait pleine) de la mémoire non volatile (par exemple EEPROM ou Flash). A cette fin, le procédé peut utiliser par exemple une technique similaire aux techniques connues dites SWAP entre la mémoire vive et le disque dur d'un ordinateur personnel conventionnel (une page de mémoire vive peu utilisée étant recopiée temporairement sur le disque dur pour libérer cette page). Selon le cas, il peut être possible, au lieu de réaliser un SWAP, d'utiliser simplement la mémoire non volatile comme une extension (plus lente et plus contraignante) de la mémoire volatile. Selon un mode de réalisation, la mémoire non volatile de la mémoire MEM peut être une mémoire magnétique (par exemple un disque dur) et peut alors mettre en ceuvre une technique de SWAP conventionnelle. Selon un mode de réalisation, la mémoire MEM comprend un composant de mémoire non volatile physique. Selon un mode de réalisation, la mémoire MEM comprend une mémoire non volatile logique qui constitue un sous ensemble logique d'une mémoire non volatile physique donnée. Par exemple, une puce mémoire EEPROM de 64Ko du dispositif électronique peut être divisée en trois parties. Une première partie de 4Ko peut être allouée à la mémoire MEM. Une deuxième partie de 16Ko peut être allouée à des softmasks (correctifs de bugs éventuels apportés à un système d'exploitation stocké en mémoire ROM, désactivation de certaines fonctions du système d'exploitation, ou fonctionnalités supplémentaires pour ce système d'exploitation). Une troisième partie de 44Ko (la partie principale) peut être allouée à une fonction de mémoire de stockage utilisateur du dispositif électronique (équivalent d'un disque dur sur un ordinateur conventionnel) dans lequel il est possible par exemple de créer des répertoires et sous répertoires (par exemple selon la norme IS0-7816-4), ou encore d'enregistrer des applets Javacard, ou des fichiers de données. Les tailles des trois parties peuvent évidemment être quelconques.In the case of the AES, the inverse function is the inverse multiplicative in the finite group GF (28) defined in the AES, and the affine function is the affine function of the AES, namely the function that 'byte B associates byte B' such that: 16 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 o 0 1 1 1 1 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 The process generates a masked inverse function MSK_INV_F by masking the inverse function INV_F (which also makes it possible to secure well the substitution box as the inverse substitution box). According to one embodiment, the method does not mask the affine function AFF_F nor the inverse function R_AFF_F of the affine function AFF_F. The inverse function INV_F masked can not be stored in non-rewritable memory (such as ROM) since by definition it is defined randomly during the use of the method. It is thus generated (from the inverse function INV_F) then stored in the memory MEM, which is a rewritable memory. According to one embodiment, the inverse function INV_F, the affine function AFF_F and the inverse function R_AFF_F of the affine function AFF_F are, in turn, recorded in a memory of the electronic device other than its memory MEM. For example, they are stored in non-rewritable memory (for example in ROM). Indeed, according to one embodiment, these functions are constant and can therefore be defined during manufacture (once and for all, in ROM). They can also be recorded in a non-volatile rewritable memory (such as a flash memory or EEPROM for example) other than the MEM memory. They can then be recorded during a configuration (and possibly a reconfiguration) of the electronic device. It is indeed more and more common to use for the operating system and the constant data of certain electronic devices (such as smart cards) not a ROM memory, but a non-volatile rewritable memory (often a 2). 9 9 5 1 1 0 17 Flash memory) in order to increase the flexibility of the manufacture of the electronic device (it is not necessary to hide a ROM component in a melter each time an element that is located in ROM and can not be modified by softmask). The method can thus use the affine function AFF_F and the reciprocal function R_AFF_F of the affine function AFF_F (during the implementation of a substitution box or an inverse substitution box) without consuming additional memory MEM, or if necessary by consuming a marginal amount of MEM memory with respect to the memory optimization obtained. This possible amount of "lost" marginal memory can be linked for example to the call of a function (AFF_F or R_ AFF _F) which can, for example, according to its implementation, cause the recording in a stack of the MEM memory of certain information (for example two bytes encoding the return address to use to continue the execution once AFF_F or R_AFF_F executed, etc.). The equivalent of this information would not necessarily have been required (as a record in the MEM memory) in an implementation of the state of the art masking the entire box of substitution in table form. But in any case, the few bytes possibly lost (for example two bytes in the example above) are negligible compared to the 160 or 256 bytes of MEM memory saved by the method for decryption in AES-128 by related to the known secure decryption methods. The data manipulated by the affine function AFF_F (and by the reciprocal affine function R_AFF_F) are preferably masked. It is not necessary to modify the affine function or the inverse affine function, however, initially designed for unmasked data. Indeed, these functions are linear. It is therefore possible to determine, from the result of the affine function (respectively of the reciprocal affine function) applied to a masked datum and the value of the mask, the result of the affine function (respectively of the reciprocal affine function) applied. to the data not masked. Indeed, for a linear function L, a datum x and a mask m, we have L (x + m) = L (x) + L (m) and therefore L (x) = L (x + m) + L (m) (the `+ 'operation designates the" exclusive or "). According to one embodiment, the memory MEM is a volatile memory, such as a RAM, or more precisely an SRAM, a DRAM, an MRAM, a DDRAM, an SDRAM, a RDRAM, a DDR SDRAM, a DDR2 SDRAM, a DDR3 SDRAM, an XDR DRAM, etc. The volatile memory of the electronic device is often the most critical memory because little available (there is much less than nonvolatile memory). For example, there are often only a few hundred or thousands of bytes of RAM against several tens of thousands of bytes of EEPROM in a smart card. Similarly, there are often only a few gigabytes of RAM in a server against terabytes in a server hard drive. The RAM memory is generally very fast both for reading and writing, but requires a permanent power supply, the interruption of power leading to a loss of recorded data. According to another embodiment, the memory MEM comprises, for the purposes of implementing the cryptographic algorithm, a rewritable non-volatile memory (such as an EEPROM or Flash memory) for the storage of temporary information such as the extended key, or such as the hidden inverse function. However, writing in such memories is much more complex and slow than writing in RAM type volatile memory. This leads to substantially reduced performance in terms of speed of execution. It is also likely to give rise more easily to attacks by auxiliary channels. In addition, the number of writes in a rewritable non-volatile memory is generally limited. For example, the operation of some EEPROMs is only guaranteed for 100,000 writes. This number of writes (100000) could be reached for certain applications, imposing the non-use of the areas having reached the threshold of use, which would thus be lost. This would increase the consumption of non-volatile memory. According to one embodiment, the use of a nonvolatile memory MEM thus completes the use of a RAM included in the memory MEM, RAM which may prove to be of insufficient size (depending on the applications in progress). execution, etc.). The memory MEM can thus combine a RAM memory and (for the case where the RAM is full) of the non-volatile memory (for example EEPROM or Flash). For this purpose, the method can use, for example, a technique similar to the so-called SWAP techniques between the random access memory and the hard disk of a conventional personal computer (a page of used random access memory being temporarily copied to the hard disk to release this page). Depending on the case, it may be possible, instead of performing a SWAP, to simply use the non-volatile memory as an extension (slower and more constraining) of the volatile memory. According to one embodiment, the non-volatile memory of the memory MEM can be a magnetic memory (for example a hard disk) and can then implement a conventional SWAP technique. According to one embodiment, the memory MEM comprises a physical nonvolatile memory component. According to one embodiment, the memory MEM comprises a logical nonvolatile memory which constitutes a logical subset of a given physical nonvolatile memory. For example, a 64KB EEPROM memory chip of the electronic device can be divided into three parts. A first part of 4Ko can be allocated to the MEM memory. A second part of 16K can be allocated to softmasks (possible bug fixes to an operating system stored in ROM, disabling certain operating system functions, or additional features for this operating system). A third part of 44K (the main part) can be allocated to a user storage function of the electronic device (equivalent of a hard disk on a conventional computer) in which it is possible for example to create directories and subdirectories (for example according to IS0-7816-4), or to record Javacard applets, or data files. The sizes of the three parts can obviously be any.

Selon un mode de réalisation, le procédé comprend une phase d'expansion de clé utilisant la boîte de substitution SBOX. La phase d'expansion de clé est mise en ceuvre au fur et à mesure d'un chiffrement ou d'un déchiffrement (chiffrement ou déchiffrement effectué à l'aide de la mise en ceuvre de l'algorithme cryptographique). Ceci maximise l'optimisation résultant du masquage de la fonction inverse (à l'exclusion des fonctions affine et réciproque de la fonction affine, qui ne sont pas masquées) en particulier dans le cas où le procédé met en ceuvre une opération de déchiffrement. Une comparaison entre deux techniques connues et un procédé selon une mise en ceuvre particulière du mode de réalisation qui vient d'être décrit est représentée sur le tableau suivant : Mémoire occupée Mémoire occupée Nombre de (chiffrement) (déchiffrement) masquages Expansion masquée 432 octets 432 octets 1 complète (séparée) Expansion masquée 272 octets 528 octets 2 progressive (parallèle) Mode de réalisation 272 octets 272 octets 1 (expansion masquée progressive, parallèle) La première technique connue commence par procéder à une expansion complète (ce qui requiert 176 octets) puis réalise un chiffrement complet à l'aide d'une boîte de substitution masquée (256 octets) soit un total de 176+256=432 octets. La première technique permet également un déchiffrement dans lequel on commence par procéder à une expansion complète (ce qui requiert 176 octets) puis réalise un déchiffrement complet à l'aide d'une boîte de substitution inverse masquée (256 octets) soit un total de 176+256=432 octets. La deuxième technique connue effectue en parallèle une expansion de la clé et un chiffrement. A chaque itération, l'expansion requiert 16 octets (pour les 16 octets parmi 176 que l'on est en train de générer), plus 256 octets pour la boîte de substitution masquée soit un total de 16+256=272 octets. En parallèle, la deuxième technique effectue un chiffrement sur la base des 16 octets de clé qui viennent d'être générés, ce qui requiert 256 octets pour la 2 9 9 5 1 1 0 21 boîte de substitution chiffrée (cependant ces 256 octets étaient déjà alloués donc cela ne change pas les besoins en mémoire). La deuxième technique connue permet également d'effectuer en parallèle une expansion de la clé et un déchiffrement. A chaque itération, l'expansion requiert 16 octets (pour les 5 16 octets parmi 176 que l'on est en train de générer), plus 256 octets pour la boîte de substitution masquée soit un total de 16+256=272 octets. En parallèle, la deuxième technique effectue un déchiffrement sur la base des 16 octets de clé qui viennent d'être générés, ce qui requiert 256 octets pour la boîte de substitution inverse chiffrée. Ces 256 octets s'ajoutent aux 272 octets 10 requis pour l'expansion, ce qui implique un besoin de mémoire de 272+256 = 528 octets. Enfin, la mise en oeuvre particulière du mode de réalisation précité consiste à l'appliquer à l'AES-128. On opère ainsi une expansion masquée progressive, et en parallèle un chiffrement (ou un déchiffrement) à l'aide d'une 15 boîte de substitution (ou d'une boîte de substitution inverse) masquée grâce au masquage de la fonction inverse. Ceci ne nécessite que 272 octets. Selon un mode de réalisation, la fonction inverse masquée MSK_INV_F, la fonction affine AFF_F et la fonction réciproque R_AFF_F de la fonction 20 affine AFF_F sont mises en oeuvre sous forme de tables. Selon un mode de réalisation, ces trois fonctions s'appliquent à un octet et renvoient un octet. Il peut s'agir par exemple de tables de 256 octets chacune, dont le premier octet contient le résultat de la fonction considérée appliquée à l'octet 00, le deuxième octet le résultat de la fonction considérée appliquée à l'octet 01, et ainsi de suite jusqu'au 256ème octet, contenant le résultat de la fonction considérée appliquée à l'octet FF (255 en hexadécimal). Selon un mode de réalisation, le procédé est mis en oeuvre sous forme d'un logiciel stocké ailleurs que dans la mémoire MEM (par exemple dans une mémoire non volatile telle qu'une EEPROM ou une Flash, voire une mémoire non réinscriptible, tel qu'une ROM). Le procédé peut prévoir des adresses fixes pour les trois tables (ou pour certaines d'entre elles seulement). Par exemple, le procédé peut prévoir deux adresses prédéterminées en ROM (ou dans une EEPROM ou Flash autre que celle éventuellement comprise dans la mémoire MEM) pour les tables représentant la fonction affine AFF_F et la fonction réciproque R_AFF_F de la fonction affine AFF_F, et une adresse prédéterminée dans la mémoire MEM pour stocker la table correspondant à la fonction inverse masquée MSK_INV_F. Ceci économise la mémoire MEM qui serait éventuellement nécessaire pour stocker la valeur de ces adresses. De plus le recours à une table constitue une possibilité permettant de s'affranchir d'un appel de fonction. Le logiciel mettant en oeuvre le procédé peut par exemple lire le résultat de la fonction inverse masquée appliquée à un octet quelconque en lisant directement la mémoire MEM à l'adresse prédéfinie de la table représentant cette fonction inverse masquée à laquelle on ajoute la valeur de l'octet. Par exemple, si la table est stockée à l'adresse $12F0, le procédé peut obtenir l'inverse masqué de l'octet ayant pour valeur B7 en lisant le contenu de l'adresse $13A7.According to one embodiment, the method comprises a key expansion phase using the SBOX substitution box. The key expansion phase is implemented as and when encryption or decryption (encryption or decryption performed using the implementation of the cryptographic algorithm). This maximizes the optimization resulting from the masking of the inverse function (excluding the affine and reciprocal functions of the affine function, which are not masked), particularly in the case where the method implements a decryption operation. A comparison between two known techniques and a method according to a particular implementation of the embodiment which has just been described is shown in the following table: Memory occupied Memory occupied Number of (encryption) (decryption) masks Masking Expansion 432 bytes 432 bytes 1 complete (separate) Masked expansion 272 bytes 528 bytes 2 progressive (parallel) Embodiment 272 bytes 272 bytes 1 (progressive masked expansion, parallel) The first known technique starts with a full expansion (requiring 176 bytes) then performs full encryption using a hidden substitution box (256 bytes) for a total of 176 + 256 = 432 bytes. The first technique also allows a decryption in which one starts by carrying out a complete expansion (which requires 176 bytes) then realizes a complete decryption using a masked inverse substitution box (256 bytes) that is a total of 176 + 256 = 432 bytes. The second known technique performs in parallel an expansion of the key and an encryption. At each iteration, the expansion requires 16 bytes (for the 16 bytes out of 176 that are being generated), plus 256 bytes for the hidden substitution box that is a total of 16 + 256 = 272 bytes. In parallel, the second technique performs an encryption based on the 16 key bytes that have just been generated, which requires 256 bytes for the encrypted substitution box (however these 256 bytes were already allocated so it does not change the memory requirements). The second known technique also allows parallel expansion of the key and decryption. At each iteration, the expansion requires 16 bytes (for the 5 16 bytes out of 176 that are being generated), plus 256 bytes for the masked substitution box that is a total of 16 + 256 = 272 bytes. In parallel, the second technique decrypts on the basis of the 16 key bytes that have just been generated, which requires 256 bytes for the encrypted inverse substitution box. These 256 bytes add to the 272 bytes required for expansion, which implies a memory requirement of 272 + 256 = 528 bytes. Finally, the particular implementation of the aforementioned embodiment is to apply it to the AES-128. Thus, a gradual masked expansion is performed, and in parallel encryption (or decryption) using a substitution box (or a reverse substitution box) masked by masking the inverse function. This only requires 272 bytes. According to one embodiment, the masked inverse function MSK_INV_F, the affine function AFF_F and the inverse function R_AFF_F of the affine function AFF_F are implemented in the form of tables. According to one embodiment, these three functions apply to one byte and return one byte. They may be, for example, tables of 256 bytes each, the first byte of which contains the result of the function considered applied to byte 00, the second byte the result of the function considered applied to byte 01, and so on. immediately until the 256th byte, containing the result of the function considered applied to the FF byte (255 in hexadecimal). According to one embodiment, the method is implemented in the form of software stored elsewhere than in the memory MEM (for example in a non-volatile memory such as an EEPROM or Flash, or even a non-rewritable memory, such as a ROM). The method can provide fixed addresses for the three tables (or for some of them only). For example, the method can provide two predetermined addresses in ROM (or in an EEPROM or Flash other than that possibly included in the memory MEM) for the tables representing the affine function AFF_F and the inverse function R_AFF_F of the affine function AFF_F, and a predetermined address in the memory MEM to store the table corresponding to the hidden inverse function MSK_INV_F. This saves the MEM memory that might be needed to store the value of these addresses. In addition the use of a table is a possibility to get rid of a function call. The software implementing the method can for example read the result of the masked inverse function applied to any byte by reading the memory MEM directly to the predefined address of the table representing this masked inverse function to which the value of the memory is added. 'byte. For example, if the table is stored at the address $ 12F0, the method can obtain the hidden inverse of the byte having the value B7 by reading the contents of the address $ 13A7.

Selon un mode de réalisation, un procédé met en oeuvre plusieurs procédés de chiffrement ou de déchiffrement de données dans le cadre d'une même session à l'aide d'un procédé selon l'un des modes de réalisations précédents.According to one embodiment, a method implements several methods of encrypting or decrypting data in the context of the same session using a method according to one of the preceding embodiments.

La session peut correspondre à l'intervalle qui sépare la mise sous tension et la mise hors tension du dispositif électronique (par exemple introduction d'une carte à puce dans un lecteur, transaction, puis retrait de la carte à puce). La session peut également être une session logique, par exemple une session consécutive à la commande PKCS#11 C_OpenSession() qui permet d'ouvrir une session cryptographique avec un dispositif électronique compatible PKCS#11 (qu'il s'agisse d'une carte à puce ou d'un ordinateur plus important, par exemple un serveur ou un HSM, de l'anglais « Hardware Security Module »). Les opérations de chiffrement et de déchiffrement peuvent être mises en oeuvre dans un environnement multitâche. Il peut s'agir d'un multitâche coopératif (« faux multitâche ») ou d'un multitâche préemptif (« vrai multitâche »). Dans un système multitâche coopératif, un dispositif électronique met à disposition différentes fonctions (en l'espèce des fonctions cryptographiques), et l'appel à plusieurs fonctions est possible en parallèle si les différentes fonctions rendent la main. Dans une multitâche préemptif, un système d'exploitation (plutôt que la fonction elle-même) alloue des portions de temps disponible du processeur (voir des processeurs distincts, dans le cas d'un dispositif électronique multiprocesseur) à chaque fonction (tâche). Certains dispositifs électroniques, bien que disposant d'une grande quantité de mémoire MEM (par exemple une mémoire RAM importante), peuvent se trouver limités en raison du grand nombre de calculs parallèles mettant en oeuvre l'algorithme cryptographique. Cela peut être le cas par exemple d'un HSM, ou encore d'un accélérateur TLS/SSL. Bien qu'en pareil cas il soit envisageable de ne masquer la fonction inverse qu'une fois pour toutes les instances en cours, il peut s'avérer préférable du point de vue de la sécurité d'utiliser un masquage différent pour chaque instance, le procédé étant alors avantageux par l'économie mémoire qu'il confère. Selon un mode de réalisation, un programme d'ordinateur comprend une série d'instructions, qui lorsqu'elle est exécutée par un processeur MP d'un dispositif électronique SCARD, conduit le processeur MP à mettre en oeuvre un procédé selon un mode de réalisation. Le dispositif électronique peut ainsi être une carte à puce SCARD, comprenant un microcontrôleur, le microcontrôleur comprenant un processeur MP relié à d'autres composants tels qu'une ou plusieurs mémoires (RAM, EEPROM, Flash, ROM, etc.), des composants d'entrées-sorties, etc. Le programme d'ordinateur peut être écrit en langage assembleur, ou éventuellement en langage de haut niveau (tel que le langage C par exemple) compilé et dont le code assembleur résultant est éventuellement retouché à des fins d'optimisation et/ou de sécurisation.The session may correspond to the interval between the power-on and the power off of the electronic device (eg introduction of a smart card into a reader, transaction, and removal of the smart card). The session can also be a logical session, for example a session following the PKCS # 11 C_OpenSession () command that allows you to open a cryptographic session with a PKCS # 11 compatible electronic device (whether it is a card smart or a larger computer, for example a server or an HSM, the English "Hardware Security Module"). Encryption and decryption operations can be implemented in a multitasking environment. It can be cooperative multitasking ("false multitasking") or preemptive multitasking ("true multitasking"). In a cooperative multitasking system, an electronic device provides different functions (in this case cryptographic functions), and the call to several functions is possible in parallel if the various functions make the hand. In a preemptive multitasking, an operating system (rather than the function itself) allocates portions of the processor's available time (see separate processors, in the case of a multiprocessor electronic device) to each function (task). Some electronic devices, although having a large amount of MEM memory (for example a large RAM), may be limited because of the large number of parallel calculations implementing the cryptographic algorithm. This may be the case, for example, with an HSM or with a TLS / SSL accelerator. Although in such cases it is possible to hide the inverse function only once for all the instances in progress, it may be preferable from the point of view of security to use a different masking for each instance. method being then advantageous by the memory saving it confers. According to one embodiment, a computer program comprises a series of instructions, which when executed by a processor MP of an electronic device SCARD, causes the processor MP to implement a method according to an embodiment . The electronic device can thus be an SCARD chip card, comprising a microcontroller, the microcontroller comprising an MP processor connected to other components such as one or more memories (RAM, EEPROM, Flash, ROM, etc.), components input-output, etc. The computer program can be written in assembler language, or possibly in high level language (such as C language for example) compiled and whose resulting assembly code is possibly retouched for optimization and / or securing purposes.

Selon un mode de réalisation, un support de stockage non transitoire lisible par ordinateur stocke un programme d'ordinateur selon un mode de réalisation. Ce support de stockage peut être notamment une mémoire (par exemple EEPROM, Flash ou ROM), éventuellement intégrée à un système tel qu'une clé USB, une carte à puce, une carte mémoire, etc. Selon un mode de réalisation, un dispositif électronique SCARD comprend une mémoire MEM et un circuit MP d'optimisation de mémoire. Le circuit MP est agencé, lorsque le dispositif électronique SCARD met en oeuvre un algorithme cryptographique en le protégeant contre des attaques physiques par masquage d'une boîte de substitution SBOX et d'une boîte de substitution inverse INV_SBOX (la boîte de substitution SBOX comprenant une fonction inverse INV_F suivie d'une fonction affine AFF_F, la boîte de substitution inverse INV_SBOX comprenant la fonction réciproque R_AFF_F de la fonction affine AFF_F suivie de la fonction inverse INV_F), pour générer une fonction inverse masquée MSK_INV_F par masquage de la fonction inverse INV_F. Le circuit de protection MP peut être un processeur du dispositif électronique utilisateur associé à une mémoire non volatile stockant un logiciel adapté pour la mise en oeuvre du procédé par le processeur. Mais il peut également s'agir d'un circuit électronique dédié intégré au dispositif électronique, tel qu'un ASIC, un FPGA (ou les variantes PAL, EPLD, PLD, CPLD, PLA, etc.) convenablement configuré (par exemple en VHDL), voire de l'électronique dédiée conçue sur mesure. Il est ainsi possible de sécuriser une mise en oeuvre matérielle d'un algorithme cryptographique. Selon un mode de réalisation, le dispositif électronique est agencé pour mettre en oeuvre une phase d'expansion de clé (par exemple par le circuit MP), utilisant la boîte de substitution SBOX, au fur et à mesure de la mise en oeuvre d'un chiffrement ou d'un déchiffrement à l'aide de l'algorithme cryptographique. Selon un mode de réalisation, le dispositif électronique est agencé pour mettre en oeuvre (par exemple par le circuit MP) la fonction inverse masquée MSK_INV_F, la fonction affine AFF_F et la fonction réciproque R_AFF_F de la fonction affine AFF_F sous forme de tables. Selon un mode de réalisation, le dispositif électronique est agencé pour mettre en oeuvre (par exemple par le circuit MP) plusieurs procédés de chiffrement ou de déchiffrement de données dans le cadre d'une même session en minimisant la consommation de mémoire MEM (grâce à la mise en oeuvre d'un procédé selon l'invention). Bien entendu, la présente invention ne se limite pas aux formes de réalisation décrites ci-avant à titre d'exemples ; elle s'étend à d'autres variantes. De plus, le procédé selon l'invention n'est pas exclusif de l'utilisation d'autres procédés. Par exemple il est possible de combiner le procédé selon l'invention avec d'autres contremesures ou optimisation de l'utilisation de la mémoire.According to one embodiment, a non-transitory computer readable storage medium stores a computer program according to one embodiment. This storage medium can be in particular a memory (for example EEPROM, Flash or ROM), possibly integrated into a system such as a USB key, a smart card, a memory card, etc. According to one embodiment, an electronic device SCARD comprises a memory MEM and a memory optimization circuit MP. The circuit MP is arranged when the electronic device SCARD implements a cryptographic algorithm by protecting it against physical attacks by masking an SBOX substitution box and an inverse substitution box INV_SBOX (the substitution box SBOX comprising a inverse function INV_F followed by an affine function AFF_F, the inverse substitution box INV_SBOX comprising the reciprocal function R_AFF_F of the affine function AFF_F followed by the inverse function INV_F), to generate a masked reverse function MSK_INV_F by masking the inverse function INV_F. The protection circuit MP may be a processor of the user electronic device associated with a non-volatile memory storing software adapted for the implementation of the method by the processor. But it can also be a dedicated electronic circuit integrated in the electronic device, such as an ASIC, an FPGA (or PAL, EPLD, PLD, CPLD, PLA variants, etc.) suitably configured (for example in VHDL ), or dedicated dedicated electronics. It is thus possible to secure a hardware implementation of a cryptographic algorithm. According to one embodiment, the electronic device is arranged to implement a key expansion phase (for example by the MP circuit), using the substitution box SBOX, as and when the implementation of encryption or decryption using the cryptographic algorithm. According to one embodiment, the electronic device is arranged to implement (for example by the MP circuit) the masked inverse function MSK_INV_F, the affine function AFF_F and the inverse function R_AFF_F of the affine function AFF_F in the form of tables. According to one embodiment, the electronic device is arranged to implement (for example by the MP circuit) several methods of encrypting or decrypting data in the context of the same session by minimizing the memory consumption MEM (thanks to the implementation of a method according to the invention). Of course, the present invention is not limited to the embodiments described above as examples; it extends to other variants. In addition, the method according to the invention is not exclusive of the use of other methods. For example, it is possible to combine the method according to the invention with other countermeasures or optimization of the use of the memory.

Claims

REVENDICATIONS1. A method for optimizing the use of the memory (MEM) of an electronic device (SCARD), when the electronic device (SCARD) implements a cryptographic algorithm (AES) by protecting it against physical attacks by masking a substitution box (SBOX) and an inverse substitution box (INV SBOX), the substitution box (SBOX) comprising an inverse function (INV_F) followed by an affine function (AFF_F), the inverse substitution box ( INV_SBOX) comprising the reciprocal function (R_AFF_F) of the affine function (AFF_F) followed by the inverse function (INV_F), the method generating a hidden inverse function (MSK_INV_F).

2. Method according to claim 1, comprising a key expansion phase using the substitution box (SBOX), the key expansion phase being implemented as and when implementing encryption or decryption using the cryptographic algorithm (AES).

3. Method according to claim 1 or 2, the hidden inverse function (MSK_INV_F), the affine function (AFF_F) and the reciprocal function (R_AFF_F) of the affine function (AFF_F) being implemented in the form of tables.

4. A method implementing several methods of encryption or decryption of data in the context of the same session using a method according to one of the preceding claims.

A computer program comprising a series of instructions, which when executed by a processor (MP) of an electronic device (SCARD), causes the processor (MP) to implement a method according to the one of the preceding claims.7

6. Non-transitory computer-readable storage medium, the medium storing a computer program according to claim 5.

7. Electronic device (SCARD) comprising a memory (MEM) and a memory optimization circuit (MP), the circuit (MP) being arranged, when the electronic device (SCARD) implements a cryptographic algorithm (AES) in protecting against physical attacks by masking a substitution box (SBOX) and an inverse substitution box (INV SBOX), the substitution box (SBOX) comprising an inverse function (INV_F) followed by an affine function (AFF_F), the inverse substitution box (INV_SBOX) including the inverse function (R_AFF_F) of the affine function (AFF_F) followed by the inverse function (INV_F), to generate a hidden inverse function (MSK_INV_F).

8. Electronic device (SCARD) according to claim 7, arranged to implement a key expansion phase, using the substitution box (SBOX), as and when implementing encryption or encryption. decryption using the cryptographic algorithm (AES).

9. electronic device (SCARD) according to claim 7 or 8, arranged to implement the masked inverse function (MSK_INV_F), the affine function (AFF_F) and the inverse function (R_AFF_F) of the affine function (AFF_F) in the form of tables.

10. Electronic device (SCARD) according to one of claims 7 to 9, arranged to implement several methods of encryption or decryption of data in the context of the same session by minimizing memory consumption (MEM).