Protection of a DES algorithm

Field of the invention

0001The present invention relates to the field of encryption algorithms, in particular of the DES (Data Encryption Standard) type, executed by integrated circuits. The invention relates more particularly to the protection of the execution of a DES algorithm against an attack by statistical analysis of the consumption (Differential Power Analysis - DPA) of the circuit which executes the algorithm.

Presentation of the prior art

0002DES or tripleDES algorithms are symmetric (secret key) encryption algorithms used in cryptography, for example, to encrypt data before passing it on unprotected media (Internet, connection between a smart card and a reader card, between a processor and an external memory, etc.). These algorithms are described, for example, in FIPS PUB 46-2 (DES) and FIPS PUB 46-1 standards, and operating modes (known under the names Electronic Codebook - ECB, Cipher Block Chaining - CBC, Cipher Feedback - CFB, Output Feedback - OFB) are described in FIPS PUB 81.

0003These algorithms perform block encryption (64-bit) using keys (64-bit for DES and 128-bit for triple DES) from which 48-bit subkeys are derived. Decryption is performed using the same key (symmetric algorithm). In the description which follows, the DES algorithm will be taken as an example.

0004An encryption block denoted M is subjected to an initial permutation, denoted IP, then to sixteen iterations of a calculation depending on a key, denoted KEY, and finally to an inverse permutation of the initial permutation, denoted IP^-1.

0005The KEY key-dependent calculation can be expressed with the following notations:<ul id="ul0001" list-style="none" compact="compact"><li>i the rank of the iteration between 1 and 16;</li><li>L_iR_i a block of data of 64 bits, resulting from the application of the function f to a block R_i-1 with the subkey K_i, consisting of a word or sub-block L_i 32-bit left b₁ to b₃₂ and a word or sub-block R_i 32-bit right b₃₃ to b₆₄ ;</li><li>K_i a 48-bit block extracted from the 64-bit KEY key and used in the rank i encryption function; and</li><li>f a function of encryption.</li></ul>

0006With the notations above, the result of the initial IP permutation is a block L₀R₀ and each iteration applies:<ul id="ul0002" list-style="none" compact="compact"><li>L_i = R_i-1 ; and</li><li>R_i = L_i-1 (+) f (R_i-1, K_i), where (+) indicates a bit-to-bit addition modulo 2 (Bit-to-bit Exclusive-OR).</li></ul>

0007The result of the last iteration is a block R₁₆L₁₆ which is subject to reverse IP permutation^-1 to provide an encrypted block denoted M '.

0008The function f has three successive stages.

0009A first step is an expansion, denoted E, of the 32 bits of the sub-block R_i-1 in 48 bits to combine them, by a bit-to-bit (+) Exclusive-OR function, with the 48 bits of the subkey K_i of the iteration concerned. The result of this expansion and combination provides eight groups of six bits, denoted B_1i to B_{8i '} such as : <maths id="math0001"><math display="block"><msub><mi mathvariant="normal">B</mi><mrow><mn>1</mn><mo>⁢</mo><mi mathvariant="normal">i</mi></mrow></msub><mo>⁢</mo><msub><mi mathvariant="normal">B</mi><mrow><mn>2</mn><mo>⁢</mo><mi mathvariant="normal">i</mi></mrow></msub><mo>⁢</mo><msub><mi mathvariant="normal">B</mi><mrow><mn>3</mn><mo>⁢</mo><mi mathvariant="normal">i</mi></mrow></msub><mo>⁢</mo><msub><mi mathvariant="normal">B</mi><mrow><mn>4</mn><mo>⁢</mo><mi mathvariant="normal">i</mi></mrow></msub><mo>⁢</mo><msub><mi mathvariant="normal">B</mi><mrow><mn>5</mn><mo>⁢</mo><mi mathvariant="normal">i</mi></mrow></msub><mo>⁢</mo><msub><mi mathvariant="normal">B</mi><mrow><mn>6</mn><mo>⁢</mo><mi mathvariant="normal">i</mi></mrow></msub><mo>⁢</mo><msub><mi mathvariant="normal">B</mi><mrow><mn>7</mn><mo>⁢</mo><mi mathvariant="normal">i</mi></mrow></msub><mo>⁢</mo><msub><mi mathvariant="normal">B</mi><mrow><mn>8</mn><mo>⁢</mo><mi mathvariant="normal">i</mi></mrow></msub><mo>=</mo><msub><mi mathvariant="normal">K</mi><mi mathvariant="normal">i</mi></msub><mfenced><mo>+</mo></mfenced><mo>⁢</mo><mi mathvariant="normal">E</mi><mo>⁢</mo><mfenced><msub><mi mathvariant="normal">R</mi><mrow><mi mathvariant="normal">i</mi><mo>−</mo><mn>1</mn></mrow></msub></mfenced><mo>.</mo></math><img file="EP1638245B2_D0001.tif" /></maths>

0010A second step applies to the 48 bits from the previous step a substitution table, noted S or SBOX. In this step, each group of six bits from the previous expansion is transformed, by one of eight substitution functions (primitive functions), noted S₁ at S₈, substituting each group B_1i to B_8i by a group S₁(B_1i) to S₈(B_8i), each on 4 bits, so as to obtain eight groups of four bits, again 32 bits. The result can be noted: S₁ (B_1i) S₂(B_2i) S₃ (B_3i) ... S₈ (B_8i), the substitution functions S₁ at S₈ being independent of the rank of the iteration.

0011A third step is a permutation, denoted P, of the 32 bits from the previous step. This permutation provides a 32-bit result sub-block corresponding to the result of the function f and which can be expressed in the form:<maths id="math0002"><math display="block"><mi mathvariant="normal">f</mi><mo>⁢</mo><mfenced><msub><mi mathvariant="normal">R</mi><mrow><mi mathvariant="normal">i</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>⁢</mo><msub><mi mathvariant="normal">K</mi><mi mathvariant="normal">i</mi></msub></mfenced><mo>=</mo><mi mathvariant="normal">P</mi><mfenced><msub><mi mathvariant="normal">S</mi><mn>1</mn></msub><mfenced><msub><mi mathvariant="normal">B</mi><mrow><mn>1</mn><mo>⁢</mo><mi mathvariant="normal">i</mi></mrow></msub></mfenced><mo>⁢</mo><msub><mi mathvariant="normal">S</mi><mn>2</mn></msub><mfenced><msub><mi mathvariant="normal">B</mi><mrow><mn>2</mn><mo>⁢</mo><mi mathvariant="normal">i</mi></mrow></msub></mfenced><mo>⁢</mo><msub><mi mathvariant="normal">S</mi><mn>3</mn></msub><mfenced><msub><mi mathvariant="normal">B</mi><mrow><mn>3</mn><mo>⁢</mo><mi mathvariant="normal">i</mi></mrow></msub></mfenced><mo>…</mo><msub><mi mathvariant="normal">S</mi><mn>8</mn></msub><mfenced><msub><mi mathvariant="normal">B</mi><mrow><mn>8</mn><mo>⁢</mo><mi mathvariant="normal">i</mi></mrow></msub></mfenced></mfenced><mo>.</mo></math><img file="EP1638245B2_D0002.tif" /></maths>

0012Each subkey K_i is obtained by applying a key function KS which is a particular function to the key KEY, the function KS depending on the rank i of the iteration, that is: <maths id="math0003"><math display="block"><msub><mi mathvariant="normal">K</mi><mi mathvariant="normal">i</mi></msub><mo>=</mo><mi>KS</mi><mfenced><mi mathvariant="normal">i</mi><mo>⁢</mo><mi>KEY</mi></mfenced><mo>.</mo></math><img file="EP1638245B2_D0003.tif" /></maths>

0013The details of the primitive functions KS, S₁ at S₈ and P, as well as E functions are described in the standards cited.

0014The decryption is carried out by subjecting a block to be decrypted M 'to the initial permutation IP, then to 16 iterations of calculation identical to those of the encryption with the only difference that the subkeys are used in reverse order (we start from the subkey K₁₆ to finish with the subkey K₁). The first block from reverse permutation is block R₁₆L₁₆ and the block from the last iteration to be subjected to the initial reverse IP permutation^-1 is block L₀R₀. IP swapping^-1 gives the deciphered block M.

0015A weakness of DES type algorithms appears during attacks by statistical analysis of the consumption of a circuit executing the algorithm. Such attacks consist in making hypotheses on the key to correlate an intermediate result during iterations to the consumption of the integrated circuit. These attacks reveal the secret of the key. Indeed, the function f is known (DES standard) as well as the input data applied to the algorithm. Assuming part of the subkey K by hypothesis, we obtain an intermediate result L_iR_i. If a correlation is obtained between the intermediate result and the consumption of the circuit at an instant t, the hypothesis on the key is verified. The computing means allow hackers to make hypotheses in sufficient numbers, and thus to hack the secret of the circuit (the key).

0016A first known solution to try to protect a secret manipulated by a DES algorithm is to mask the execution by introducing random numbers in the iterations. This solution has the drawback of requiring a modification of the algorithm itself and is therefore not applicable to circuits in which the DES execution cell already exists in non-reconfigurable wired logic. Indeed, for reasons of speed, the algorithm is generally executed, at least partially, by a wired logic cell integrated into the circuit using the data. The key is generally stored in a secure area of ​​the circuit, for example, in a phase of personalization of the integrated circuits. It is loaded into the algorithm execution cell in a protected manner, for example by applying the methods described in the patents<patcit id="pcit0001" dnum="FR2802668A"><text>FR-A-2 802 668</text></patcit> and <patcit id="pcit0002" dnum="FR2802669A"><text>FR-A-2 802 669</text></patcit>.

0017A second solution known and described in the request <patcit id="pcit0003" dnum="EP1263163A"><text>EP 1263163</text></patcit> consists in hiding the execution of the algorithm with the secret key by making it execute among several executions (of the order of ten) using false keys. These keys are permanently stored in a non-volatile memory associated with the algorithm execution processor or directly hard wired in the circuit. The real key is generally written during the personalization of the circuit (for example, the smart card) by a different person than the manufacturer of the circuit, in a generally inaccessible zone (secure zone of the circuit). Thus, a hacker cannot know, when a hypothesis on a key is verified, if it is the right key or not which was used. A disadvantage of this solution is that, to preserve the masking, it is necessary to protect all the keys (the false ones like the real one) during their loading in the cell of execution of the algorithm. This takes time and lengthens the execution of the algorithm, incompatible with the desired rapid data manipulation. Another drawback of this solution is that it only provides white noise, therefore easily filterable by the pirate.

0018The document <patcit id="pcit0004" dnum="WO0019367A"><text>WO00 / 19367</text></patcit> describes a method according to the preamble of claim 1.

Summary of the invention

0019The present invention aims to improve the security of encryption algorithms, in particular of the DES type, against attacks by statistical analysis of the consumption of an integrated circuit which executes this algorithm.

0020The invention aims in particular to propose a solution compatible with the speed sought for the encryption and decryption of data.

0021The invention also aims to propose a solution which does not require modification of the algorithm itself and which is thus compatible with conventional execution cells of the DES algorithm.

0022To achieve these and other objects, the present invention provides a method of protecting the execution of an algorithmic calculation taking into account at least one valid datum and at least one secret key by an integrated circuit, and performing several iterations. an encryption calculation, consisting in executing the algorithm with the valid data between several executions of the same algorithm with invalid data corresponding to a combination of the valid data with predetermined masks.

0023According to an embodiment of the present invention, the position of the execution with the valid data item among the execution set is selected randomly.

0024According to an embodiment of the present invention, said combination is, for each masked execution, a bit by bit addition of the bits of a block of the valid data item with the bits of the masks.

0025According to an embodiment of the present invention, the execution with the valid datum corresponds to a combination with a neutral mask for the combining operation.

0026According to an embodiment of the present invention, said predetermined masks are chosen so that the result of the application of the algorithm with the same key is different for at least one bit from the result of the application of the valid data algorithm.

0027According to an embodiment of the present invention, the algorithm is the DES, the combination occurring before the execution of the first iteration.

0028According to an embodiment of the present invention, the masks are 64-bit blocks to be combined with 64-bit blocks of the valid data before application of an encryption iteration, the 64-bit block of each mask comprising among the position bits b₇, b₅₇, b₄₉, b₄₁, b₃₃ and B₂₅, between 1 and 6 bits in state 1, the bits of all the other positions being in state 0.

0029The invention also provides a processor for executing a DES-type encryption algorithm or the like.

detailed description

0030These objects, characteristics and advantages, as well as others of the present invention will be explained in detail in the following description of particular embodiments given without limitation. For reasons of clarity, only the steps and elements which are necessary for understanding the invention will be described below. In particular, the production of a calculation processor for the implementation of the invention has not been detailed, it being able to be implemented with any conventional processor, by providing it with the adapted data.

0031A feature of the present invention is to mask the execution of the encryption algorithm by executing this algorithm multiple times with false data, thereby masking the encryption of the "real" data. The real data to be encrypted introduced into the processing cell of the algorithm is combined with masks, preferably predetermined, so as to create false data on which the encryption algorithm is applied. The execution of the algorithm with the non-masked input data is inserted, preferably at a random position, in the series of masked executions. Preferably, all the ciphers are carried out with the same key which is therefore only transferred once in the processing cell of the algorithm.

0032The masks are in fact data blocks of the same size as the data blocks processed by the algorithm at the stage chosen for the combination which are preferably combined by an OR-Exclusive type function (bit by bit addition ) with the data block to be encrypted. Preferably, the masks are chosen according to the algorithm so that the result of the application of the algorithm with the same key is different for at least one bit from the result of the application of the algorithm to the valid data .

0033Consequently, a hacker introducing data which he knows and making assumptions on the key is unable to obtain a correct correlation with the consumption of the integrated circuit insofar as this consumption is a function of different data.

0034The invention will be described below in relation to a preferred implementation over the DES algorithm. However, it more generally applies to any encryption algorithm, on the condition that the creation of the masks to create false data by modification of a message to be encrypted can be adapted.

0035Preferably, the masks manipulated by the algorithm which are used to introduce false correlations on the channel (hide the execution) are prerecorded in the integrated circuit containing the cell.

0036An advantage of running the algorithm with multiple data rather than multiple keys is that the data does not have to be masked for entry into the cell. The protection then slows down the encryption or decryption of the data entered only negligibly compared to the conventional solution using several keys.

0037The present invention takes advantage of the fact that, in any encryption algorithm and in particular in the DES algorithm, the course of the calculation means that successive values ​​can be predicted by making assumptions about the key. False messages (masked data) occurring from the start cause these assumptions to be seen as relating to a false key. In the DES algorithm, at each moment of the calculation where the key intervenes in the form of a subkey with the message, the data and the subkey are then linked by a function arbitrarily noted g to provide an intermediate result noted arbitrarily I which is such that I = g (KEY, D). An attack by consumption analysis consists in seeking to correlate the results I with consumption by making hypotheses on the key KEY. Knowing the data D which it introduces, and knowing the function g (the DES algorithm is known), the pirate calculates a result I from a hypothesis on the key KEY. If the correlation between the value I and the consumption of the circuit is verified, it is that the assumption on the key was the good one.

0038The fact of executing the algorithm on a false data entails that the hacker obtains a correlation on a modified data D '. It follows that the correlation appears on an incorrect key hypothesis. In other words, the hacker believes that the algorithm performs the function I = g (KEY, D) while he ultimately performs I '= g (KEY, D'), with D '= D ( +) A, where A denotes the mask providing the result I '. The hacker believes he knows the data (which he has entered) and therefore makes hypotheses on the key based on consumption analyzes. But this consumption is distorted without him knowing it.

0039In fact, by combining the input data with a mask, the invention indirectly masks the key, taking into account the fact that the potential attacker makes assumptions about this key.

0040As the result provided by the circuit is distorted, it is necessary to randomly insert the "good" execution among a few masked executions (the number of masked executions is chosen according to the time available for the execution of the algorithm) . This is particularly necessary to operate the circuit correctly in the absence of piracy (you must be able to provide the correct encryption during normal execution). This correct result is provided in a different result zone from that in which the false executions are found.

0041Preferably, the execution with the valid datum corresponds in fact to a combination with a neutral mask from the point of view of the combination. Thus, no difference is detectable between the executions. The only reference that must be temporarily stored to be able to identify the execution with the valid data is its position in the set of executions which preferably corresponds to the result of a random draw.

0042In the context of the DES algorithm and according to this preferred embodiment, masks or masking data are stored, for example in a non-volatile memory area, in the integrated circuit.

0043The function of construction of the masks is a function of the algorithm and must be such that for any message D likely to be chosen by the attacker and for any key K (true) or K '(false resulting from a hypothesis), the operation g (bitwise addition in the case of DES) of combining the first subkey K₁ or K₁'with an intermediate result noted I (I = E (R₀) in the case of DES) function of the input data before application of the first subkey, is such that:

0044g (I, K₁') = g (I', K₁), where I 'designates the intermediate result obtained with the masked data.

0045The masks are however constructed independently of the data D with which they are likely to be combined, this data being on the other hand unknown.

0046For the DES algorithm, when we consider the bits of the initial message, we see that certain bit positions (determined by IP and E) are combined with the key bits, for example, bits 1, 2, 3, 4, 5 and 6 of the subkey K₁ are combined by an Exclusive OR (+) with the bits b₇, b₅₇, b₄₉, b₄₁, b₃₃ and B₂₅ of the data block D entered. So a masking by combination of six bits m₁, m₂, m₃, m₄, m₅ and M₆ with bits b₇, b₅₇, b₄₉, b₄₁, b₃₃ and B₂₅ of the data message provides a new message which, when applied as input to the encryption cell achieves the same result at the end of the step of combining with the subkey. Thus, the attacker who calculates the correlation between the data processed by the algorithm during the first round under the hypothesis corresponding to the correct key, does not obtain a correlation, while under the hypothesis of a false key, it will see a correlation appear between the predicted key (its hypothesis) and the data actually calculated.

0047In order to avoid the manipulation of false data, the mask (which can be considered as a predetermined data block - the six masking bits at positions b_7' b_57' b₄₉, b₄₁, b₃₃ and B₂₅) must be entered at the cell entry.

0048According to a preferred embodiment, any combination of states 0 and 1 is chosen for the six bits b₇, b₅₇, b₄₉, b₄₁, b₃₃ and B₂₅ of the masking data block (a combination among the 64 possible) and all its other bits are set to state 0 (neutral element of the addition), so that the bits of the real data message, other than the bits b₇, b₅₇, b₄₉, b₄₁, b₃₃ and B₂₅, are not modified by the mask. As a variant, the other bits of the block will be set randomly. This variant is however not preferred since it risks introducing white noise.

0049The preferred embodiment above takes account of the fact that, in the DES algorithm, the application of the first substitution S (SBOX) only affects the bits b₇, b₅₇, b₄₉, b₄₁, b₃₃ and B₂₅, of the data block. Indeed, by representing the blocks of 64 bits in the form of matrices of eight words of eight bits and by repeating the previous notations, the block of input data can be written: b₁, b₂, b₃, b₄, b₅, b₆, b₇, b₈ ; b₉, b₁₀, b₁₁, b₁₂, b₁₃, b₁₄, b₁₅, b₁₆ ; b₁₇, b₁₈, b₁₉, b₂₀, b₂₁, b₂₂, b₂₃, b₂₄ ; b₂₅, b₂₆, b₂₇, b₂₈, b₂₉, b₃₀, b₃₁, b₃₂ ; b₃₃, b₃₄, b₃₅, b₃₆, b₃₇, b₃₈, b₃₉, b₄₀; b₄₁, b₄₂, b₄₃, b₄₄, b₄₅, b₄₆, b₄₇, b₄₈ ; b₄₉, b₅₀, b₅₁, b₅₂, b₅₃, b₅₄, b₅₅, b₅₆ ; b₅₇, b₅₈, b₅₉, b₆₀, b₆₁, b₆₂, b₆₃, b₆₄.

0050After applying the initial IP permutation, this matrix becomes: b₅₈, b₅₀, b₄₂, b₃₄, b₂₆, b₁₈, b₁₀, b₂; b₆₀, b₅₂, b₄₄, b₃₆, b₂₈, b₂₀, b₁₂, b₄ ; b₆₂, b₅₄, b₄₆, b₃₈, b₃₀, b₂₂, b₁₄, b₆ ; b₆₄, b₅₆, b₄₈, b₄₀, b₃₂, b₂₄, b₁₆, b₈ ; b₅₇, b₄₉, b₄₁, b₃₃, b₂₅, b₁₇, b₉, b₁ ; b₅₉, b₅₁, b₄₃, b₃₅, b₂₇, b₁₉, b₁₁, b₃ ; b₆₁, b₅₃, b₄₅, b₃₇, b₂₉, b₂₁, b₁₃, b₅ ; b₆₃, b₅₅, b₄₇, b₃₉, b₃₁, b₂₃, b₁₅, b₇.

0051When the left and right parts are submitted to the first round, only the right part: b₅₇, b₄₉, b₄₁, b₃₃, b₂₅, b₁₇, b₉, b₁ ; b₅₉, b₅₁, b₄₃, b₃₅, b₂₇, b₁₉, b₁₁, b₃; b₆₁, b₅₃, b₄₅, b₃₇, b₂₉, b₂₁, b₁₃, b₅; b₆₃, b₅₅, b₄₇, b₃₉, b₃₁, b₂₃, b₁₅, b₇, is modified and becomes: b₇, b₅₇, b₄₉, b₄₁, b₃₃, b₂₅, b₁₇ ; b₂₅, b₁₇, b₉, ...; ...; ..., b₁₅, b₇, b₅₇.

0052At the end of the expansion step E, eight words of six bits each are obtained which have the following expression: b₃₂, b₁, b₂, b₃, b₄, b₅; b₄, b₅, b₆, b₇, b₈, b₉; b₈, b₉, b₁₀, b₁₁, b₁₂, b₁₃; b₁₂, b₁₃, b₁₄, b₁₅, b₁₆, b₁₇ ; b₁₆, b₁₇, b₁₈, b₁₉, b₂₀, b₂₁; b₂₀, b₂₁, b₂₂, b₂₃, b₂₄, b₂₅; b₂₄, b₂₅, b₂₆, b₂₇, b₂₈, b₂₉; b₂₈, b₂₉, b₃₀, b₃₁, b₃₂, b₁.

0053Thus, one can mask a datum D by combining it by an Exclusive-OR with a block of which at least one of the bits b₇, b₅₇, b₄₉, b₄₁, b₃₃ and B₂₅ is 1 and all other bits are 0. Any combination of bits of bits b₇, b₅₇, b₄₉, b₄₁, b₃₃ and B₂₅ is valid provided that at least one of them is worth one.

0054All the parts of the data item D are successively masked by applying the same mask to each 64-bit block introduced into the cell.

0055Of course, the present invention is susceptible to various variants and modifications which will appear to those skilled in the art. In particular, although the invention has been described in relation to a preferred embodiment of generation of false data, its transposition to another generation function is within the reach of those skilled in the art, respecting the condition that each portion on which the DPA attack selection function is applied, that is to say each six-bit portion at the input of the substitution steps, differs by at least one bit when it is masked.

0056In addition, the practical realization of an algorithmic execution cell for the implementation of the invention is within the reach of those skilled in the art from the functional indications given above using conventional programming tools.

0057In addition, other functions for combining the masks with the input data can be envisaged provided that the functionalities described above are respected. Bit by bit addition is preferred because of its simplicity.