Method and system for protecting a cryptography device

0001The present invention relates to a method for protecting a cryptography circuit from attacks aiming to discover a secret datum used during execution by the circuit of a cryptography algorithm comprising the application of at least one cryptographic operation to the data, said data belonging to a first mathematical structure having at least one group structure and provided with at least one binary operation.

0002The purpose of cryptography is to allow to entities to communicate in complete security using an unsafe communication channel, i.e. a channel that may be spied on by a third entity, hereafter called “adversary,”

0003To that end, cryptography in particular makes it possible to protect the confidentiality of a piece of information, through encryption of that information and the dual operation, decryption, or to protect only the authenticity of a piece of information, using complementary signature and signature verification operations.

0004Cryptographic protection of a given message is generally implemented by a microcircuit, by applying one or more mathematical operations to that message, operations which depend on a key, called secret key in symmetrical cryptography and public or private in asymmetrical cryptography.

0005Such a protection method is, however, subject to attack by an adversary, seeking to access the content of the message or the key itself.

0006A standard adversary model, at the root of the use of cryptography to protect communications, is that where the adversary is only an observer, passive and/or active, acting via the transmission channel. In this model, the adversary can access all communications, interrupt them or even alter them. Cryptographic protocols resistant to these categories of adversaries exist, and in some cases perform very well.

0007Due in particular to the widening of the fields of application of cryptography, new adversary and attack models have appeared. In particular, microcircuit devices implementing cryptography algorithms are sometimes subject to attacks aiming to determine the secret data they manipulate such as the key(s) used and possibly, in certain cases, information on the messages themselves.

0008This is for example the case of so-called side channel attacks, which exploit certain properties of software or material implementations of the cryptography algorithms.

0009In particular, certain types of attacks exploit the fact that each mathematical operation of a cryptographic computation has a different energy signature from another one. For example, the energy consumption generated by the transition of an information bit from value ‘<b>1</b>’ to value ‘<b>0</b>’ is different from that generated by the transition of a bit from ‘<b>0</b>’ to ‘<b>1</b>’

0010Thus, SPA (Simple Power Analysis) or DPA (Differential Power Analysis) attacks consist of measuring the power consumption generated by a cryptographic calculation, for example the currents and voltages entering and leaving the microcircuit during execution of the cryptographic algorithm, and deducing the series of operations performed, or even the key used, from those currents or voltages.

0011Furthermore, measuring the electromagnetic field created by the electric current during a cryptographic computation may lead to electromagnetic attacks (EMA), the principle of which is identical to attacks relating to the energy consumption.

0012Furthermore, “time attacks” make it possible to find the key(s) used during a cryptographic computation from simple measurements of execution times, i.e. by analyzing the duration of the mathematical computation units, which can depend on the values of the data.

0013These new types of attacks, based on simple passive observation of the cryptographic computations, can be implemented to fraudulently access paid television services, for example. Such services use encryption and decryption algorithms to safely transmit audiovisual content to subscribers, who have decoders able to decrypt the encrypted content using a key. The power consumption of these decoders can thus be monitored and analyzed to access that key, and thereby give the attacker the ability to decrypt the audiovisual content fraudulently.

0014Furthermore, another type of element, having access to the cryptography circuit, can also be considered. This type of adversary would in particular have access to the register at all times, and be able to monitor access to the different variables at any time, and observe the operations carried out. This is then called “white-box” cryptography.

0015The aim of the invention is therefore to provide a cryptographic protection method offering increased resistance to attacks of the aforementioned type.

0016To that end, the invention relates to a protection method of the aforementioned type, characterized in that it comprises a step for protecting said cryptographic operation, comprising:

0017applying to said data at least one first reversible homomorphism, compatible with said binary operation, before applying said cryptographic operation, and

0018applying at least one second homomorphism, opposite the first homomorphism, after applying said cryptographic operation.

0019The method according to the invention also comprises the following features, considered separately or in combination:

0020said cryptographic operation is applied to the result of said first homomorphism,

0021said second homomorphism is applied to the result of said cryptographic operation,

0022said second homomorphism is applied after applying at least two cryptographic operations to the result of said first homomorphism,

0023said cryptography algorithm comprises applying at least two cryptographic operations to the data, and at least one reversible hornornorphisrn is applied before at least two of said cryptographic operations,

0024at least two distinct homomorphisms are applied to said data,

0025said homomorphism is an application of said first mathematical structure toward a second mathematical structure distinct from said first structure, provided with at least one binary operation different from said at least one binary operation of said first structure,

0026said homomorphism is a homomorphic encryption,

0027said cryptographic operation is applied using a correlation map indicating the result of said operation as a function of the input variable of that operation,

0028said homomorphism and said cryptographic operation are applied using a single correlation map indicating the result of the composition of at least said homomorphism and said operation as a function of the input variable of said homomorphism.

0029The invention also relates to a device for protecting a cryptography circuit against attacks aiming to discover a secret datum used during the execution by said circuit of a cryptography algorithm comprising the application of at least one cryptographic operation to data, said data belonging to a first mathematical structure having at least one group structure and provided with at least one binary operation, characterized in that it comprises means for applying to said data at least a first reversible hornornorphisrn, compatible with said binary operation, before applying said cryptographic operation, and at least one second homornorphisrn, opposite said first homomorphism, after applying said cryptography operation.

0030The invention will be better understood using the following description, provided only as an example, and done in reference to the appended drawings, in which:

0031<figref idref="DRAWINGS">FIG. 1</figref> diagrammatically illustrates the structure of a protection device according to one embodiment of the invention,

0032<figref idref="DRAWINGS">FIG. 2</figref> is a summary diagram illustrating the successive steps of the protection method according to one embodiment of the invention,

0033<figref idref="DRAWINGS">FIG. 3</figref> is a detailed illustration of a step of the protection method shown in <figref idref="DRAWINGS">FIG. 2</figref>,

0034<figref idref="DRAWINGS">FIG. 4</figref> is a summary diagram illustrating the successive steps of the protection method according to another embodiment of the invention, and

0035<figref idref="DRAWINGS">FIG. 5</figref> is a summary diagram illustrating the successive steps of the protection method according to another embodiment of the invention,

0036<figref idref="DRAWINGS">FIG. 1</figref> shows a protection device <b>1</b> according to a first embodiment of the invention.

0037The device <b>1</b> comprises a processor <b>3</b> and a memory <b>5</b>, connected so as to be able to exchange data such as a security key or data.

0038The memory <b>5</b> can store data, and comprises a secured memory space <b>7</b>, able to securely store in particular the security key(s) and/or the data to be encrypted or decrypted, at least temporarily.

0039The processor <b>3</b> comprises an algorithmic cryptography application <b>9</b>, which can apply a cryptography algorithm such as encryption or decryption to data to be protected or that is protected, and means <b>11</b> for protecting the algorithmic application.

0040The microprocessor <b>3</b> is thus able to apply a cryptography algorithm to a message and implement a method for protecting that algorithm so as to prevent detection of the key and/or data by an adversary.

0041<figref idref="DRAWINGS">FIG. 2</figref> shows the primary steps of the protection method according to one embodiment of the invention, implemented by the protection device <b>1</b> as shown in <figref idref="DRAWINGS">FIG. 1</figref> during execution of a cryptography algorithm on the data requiring cryptographic protection, involving a security key.

0042We will hereafter consider that this cryptography algorithm is an encryption, but the protection method described in reference to <figref idref="DRAWINGS">FIGS. 2 to 5</figref> could indifferently be applied to decryption operations or any other type of cryptographic protection algorithm.

0043The execution of this cryptography algorithm comprises implementing a plurality of mathematical operations O_i, also called cryptographic operations, successively applied to the initial data, then to the data obtained after each of these operations. In the rest of the description, D₀will denote the initial data, D_ithe data obtained after an operation O_i, and D_n, the data obtained at the end of the cryptography algorithm.

0044The operations O_i, that depend on the security key, denoted K, are for example chosen from among basic operations such as addition, subtraction, multiplication and division, any operation derived from these basic operations, such as exponentiation or polynomial evaluation, or binary operations such as the “exclusive or” XOR or the “and” function AND.

0045Each of these operations O_iis protected from possible attacks by the inventive method, The encryption of the data D₀thus more generally comprises implementing a plurality of protected mathematical operations OP_i, the results of which are identical to the results of the operations O_i, but which are protected from attacks such as D channel attacks.

0046The steps carried out during each protected operation OP_i, are detailed in <figref idref="DRAWINGS">FIG. 3</figref>.

0047The protection of each mathematical operation, and more generally of the entire cryptography algorithm, rests on the application to the data, advantageously before each operation, of a first group morphism, or homomorphism, reversible and randomly selected, and the application, advantageously after each operation, of a reverse homomorphism the first homomorphism.

0048Thus, the implementation of a protected operation OP_icomprises a step <b>20</b> for applying a first homomorphism, denoted M_i, to the initial data D₀or to the data D_i−1resulting from the protected operation OP_i−1. Then, during step <b>22</b>, the operation O_iwhich depends on the key K, is applied to the result M_i(D_i−1) obtained at the end of step <b>20</b>. Lastly, during step <b>24</b>, a second homomorphism, denoted M_i⁻¹, opposite the first morphism M_i, is applied to the result of the operation O_i.

0049A group is an algebraic structure defined as a set E of elements, provided with at least one binary operation, generally denoted additively (+_E) or multiplicatively (×_E). All of the elements of the group have an inverse for the binary law. Furthermore, the net comprises a neutral element denoted O_Ewhen the law is denoted additively, or 1_Ewhen the law is denoted multiplicatively.

0050A set is a ring if it has two binary laws, generally denoted +_Eand ×_Erespectively, such that (E, +_E) is a group.

0051Furthermore, if all of the elements, with the exception of the zero element, are reversible by the multiplicative law, the ring E is a field,

0052A group morphism between two groups E and F. possibly equal, is defined as an application φ compatible with the law of those groups, i,e. such that for any x,y ∈ E, φ(x+_Ey)=φ(x)+_Fφ(y) and φ(0_E)=0_F, where +_Eand +_Fdesignate the binary law of groups E and F, respectively, and O_Eand O_Ftheir neutral element,

0053Furthermore, if a morphism φ is bijective, it is reversible. Thus, denoting its inverse with φ⁻¹, for any element x of the set E: φ⁻¹(φ(x))=φ(φ⁻¹(x))=x.

0054Furthermore, a group morphism is a ring morphism if it involves an application φ defined between two rings E and F, and compatible with the laws of those rings, i.e. such that:

0000<br />for any x,y ∈ E, φ(x+_Ey)=φ(x)+_Fφ(y)  (1)

0000<br />for any x,y ∈ E, φ(x×_Ey)=φ(x)×_Fφ(y)  (2)

0000<br />φ(0_E)=0_Fand φ(1_E)=1_F

0055A ring morphism therefore keeps all of the usual operations, such as addition and multiplication, but also the operations derived from them such as exponentiation or composition by a polynomial, or their reverse operations (subtraction or inversion of the reversible elements).

0056In the rest of the description and claims, the general term “homomorphism” will designate any application of a set E toward a set F. possibly identical, having at least one group structure, this application preserving at least one binary law of those sets.

0057Of course, this name also includes any morphism having, aside from the properties of a group morphism, additional properties, and in particular ring morphisms, algebra morphisms or field morphisms. For example, an algebra morphism keeps, aside from the two binary operations, a so-called external law, for example multiplication by an element of a different body from the algebra in question.

0058Thus, if one considers that the data D are elements of a ring E provided with an addition and a multiplication, and that the morphism M_iapplied to the data D_iduring step <b>20</b> is a reversible morphism as previously defined, for example an endomorphism, and the reverse of which is the morphism M_i⁻¹applied during step <b>24</b>, the data D_i+1obtained at the end of step <b>24</b> verify the following equality:

0000<br />D_i=M_i⁻¹(O_i(M_i(D_i−1)))=O_i(D_i−1)

0059In fact, since the operation O_iis a basic operation of the ring E, or an operation derived from the basic operations of the ring E, this operation O_iis preserved by the morphisms M_iand M_i⁻¹. In particular, since the morphism M_ipreserves the additive law and the multiplicative law of the ring E, all of the operations derived from those two laws, therefore all of the operations O_i, are also preserved.

0060Consequently, the data D_i, obtained at the end of step <b>24</b> are identical to the data that would have been obtained solely by applying the operation O_ito the data D_i−1.

0061However, due to the random nature of the applied ring morphism, the bits of the input variables are randomly altered. The energy signature (electrical and/or thermal and/or electromagnetic) of the protected operation OP_ias well as its execution duration are therefore random, unlike those of the operation O_i, which makes any analysis of the energy consumption or emissions, or the execution time, ineffective.

0062Applying a morphism to the data D_i−1before each mathematical operation O_iand the reverse morphism after that operation thereby makes it possible to conceal the energy signature of the operations O_isuccessively applied to the data to be encrypted, therefore to protect the encryption of that data from attacks such as side channel attacks, without altering the final result D_nof the cryptography algorithm, i.e,. the encrypted data.

0063Advantageously, the morphism M_iand its opposite M_i⁻¹used during the various protected operations OP_iare different from one another, and are chosen randomly. Thus, the energy signature of the morphisms M_icannot be analyzed. Furthermore, the morphisms M_iused are advantageously modified upon each execution of the cryptography algorithm, such that the energy signature of that algorithm is different upon each execution, preventing any statistical analysis of that signature.

0064Each morphism M_iis then randomly chosen before executing the operation O_i, for example by random drawing of that morphism in a pre-established database of morphisms, or by determining new morphisms during execution of the algorithm.

0065The morphisms M_iare for example Frobenius morphisms, defined on he ring E of characteristic p>0 by:

0000<br />Frob_E:x→x^p,

0000or any morphism defined from the Frobenius morphism.

0066The ring E is then for example an extension of a Galois field of degree k≧2, denoted GF(p^k). A Galois field, denoted GF(p), is defined by all of the modulo p integers, in particular denoted Z/pZ, p being a prime number. In such a field, x^ρ=x,

0067Alternatively, the ring morphisms M_ican be homomorphic encryptions, i.e. encryption operations having the same properties as a morphism, and depending on a key Ks.

0068These homomorphic encryptions are advantageously completely homomorphic encryptions, as defined in “Fully Homomorphic Encryption Using Ideal Lattices,” Gentry C., STOC 2009, 169-178. Such morphisms have algebraic properties substantially identical to the field morphisms, and thus able to be considered ring morphisms. In particular, such morphisms completely preserve the structure of the starting set, ring or field, and in particular the additive law XOR and the multiplicative law AND, and are reversible.

0069Such morphisms can thus be used when the operations Oi executed during the cryptography algorithm are binary operations, for example XOR operations, AND operations, or operations derived from them.

0070Furthermore, homomorphic encryptions preserving L types of operations (for example addition and/or multiplication) may also be used.

0071Homomorphic encryption also has the advantage of depending on a key Ks, hereafter called secondary key because the encrypted data obtained at the end of the cryptography algorithm do not depend on that key. Homomorphic encryption can therefore be written as a function C(D_i, K_s), or, with a fixed key, as a function f(D_i) having the homomorphic properties previously described.

0072Consequently, a same homomorphic encryption function C can create a very large number of different reversible morphisms f (of order 10³⁰⁰), by modifying only the key Ks. In practice, a number of different keys of order 10⁴⁰may prove sufficient.

0073Thus, the morphisms M_i(and their opposites) used to protect the successive operations of a cryptography algorithm can be chosen randomly by selecting a same encryption C for all of the protected operations OP_i, but while randomly choosing the key Ks for that encryption before each of those operations.

0074Alternatively, the morphisms M₁can be simply homomorphic encryptions, not preserving the additive law and the multiplicative law, but only one of those laws. This may for example involve RSA (Rivest Shamir Adleman) encryption, which preserves only the multiplication. Such morphisms M_ican also be used when the operations O_ionly use a single type of basic operation, for example only addition or only multiplication.

0075It should, however, be understood that the embodiment presented above is not limiting.

0076In particular, according to another embodiment, illustrated in <figref idref="DRAWINGS">FIG. 4</figref>, the reverse morphism M_i⁻¹is not applied immediately after the operation O_i, but after several consecutive operations O_i, O_i+1. . . Thus, in the embodiment illustrated in <figref idref="DRAWINGS">FIG. 4</figref>, one of the protected operations OP_icomprises the application of a homomorphism M_ito the data D_i−1, followed by the application of the operation O_i. That protected operation OP_iis itself directly followed by the application of the operation O_i+1, then the reverse morphism M_i⁻¹. The operation O_i+1is thus applied to the image of the data D_iby the morphisrn M_i.

0077Furthermore, several morphisms can be applied to the data before each operation O_i, the reverse morphisms then being applied successively after each operation Oi, so as to offer better resistance to attacks.

0078Furthermore, the morphisms used are not necessarily endomorphisms, and can be applications of a first ring E toward a second ring F whereof the additive and multiplicative laws are advantageously different from the additive and multiplicative laws of the first ring E. Such morphisms have the advantage of transposing the operations O_iin an algebraic space F different from the algebraic space E of the data D_i, which further increases the protection of the cryptography algorithm. In fact, in this embodiment, an attacker cannot access the mathematical set in which the operations are performed, even using in-depth statistics on the energy signals of the computations.

0079According to one particular embodiment, the operations O_iand/or the morphisms and M_i⁻¹are not done via computations, but via correlation maps, making it possible to access the result of an operation without computation from values of the input variables (the data D_ifor example). <figref idref="DRAWINGS">FIG. 5</figref> thus illustrates two successive protected operations done during the execution of a cryptography algorithm according to this embodiment.

0080During a first protected operation OP₁, the processor <b>3</b> applies to the data D₀the morphism M₁and operation O₁, without computation, but by accessing a correlation map T₁corresponding to the operation O₁∘M₁, stored in the protected memory <b>7</b>. Thus, during this operation OP₁, the processor <b>3</b> looks for the image O₁∘M₁(D₀) of the input data D₁by combining the morphism M₁and the operation O₁.

0081Then, during the following protected step OP₂, the processor applies to the data M₁(D₁) resulting from step OP₁the reverse morphism M₁⁻¹, followed by the morphism M₂, and operation O₂, using a single correlation map T₂corresponding to the operation O_{2 ∘M}₂∘M₁⁻¹, stored in the protected memory <b>7</b>.

0082The following steps OP_iare carried out according to the same principle. However, the reverse morphism M_n⁻¹is applied to the data during the last step OP_n, so as to obtain, at the end of the n steps OP₁, OP₂, . . . OP_n, the same encrypted data as those that would have been obtained by applying only operations O₁, . . . O_n.

0083Advantageously, the morphisms M_iand M_i⁻¹are applications of a first ring E toward a second ring F different from E, and transposing the operation O_iinto a different algebraic space from the algebraic space E of the data D_i−1. Such a transposition results in preventing a possible attacker from determining a linear relationship between the input data and the output data of the operations OPi, and to deduce therefrom the operations O_iperformed.

0084The use of such correlation maps is thus particularly advantageous to protect the cryptography algorithms when the attackers have the possibility of monitoring the computations done step by step, the protection method according to the invention therefore making it possible to improve the security of cryptography systems in a white box.

0085It will be noted that when the cryptography algorithm comprises several mathematical operations O_i, the latter are not necessarily all protected by applying a reversible morphism.