Protection of a DES algorithm

Field of the invention

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

Presentation of the prior art

0002The DES or tripleDES algorithms are symmetric (secret-key) encryption algorithms used in cryptography, for example, to encrypt data before passing it on unprotected media (Internet, link 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, and modes of operation (known as Electronic Codebook - ECB, Cipher Block Chaining - CBC, Cipher Feedback - CFB, Output Feedback - OFB) are described in FIPS PUB 81.

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

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

0005The calculation depending on the key KEY 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>The_iR_i a 64-bit block of data, 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 bits left b₁ at b₃₂ and a word or sub-block R_i 32 bits right b₃₃ at 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 swap is an L block₀R₀ and each iteration applies:<ul id="ul0002" list-style="none" compact="compact"><li>The_i = R_i-1 ; and</li><li>R_i = L_i-1 (+) f (R_i-1, K_i), where (+) denotes a bit-to-bit addition modulo 2 (Exclusive-OR bit-to-bit).</li></ul>

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

0008The function f has three successive steps.

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 an exclusive-OR function bit-to-bit (+), with the 48 bits of subkey K_i of the iteration concerned. The result of this expansion and combination provides eight groups of six bits, denoted B_1i at B_{8i '} such as : <maths id="math0001" num=""><math display="block"><mrow><msub><mi mathvariant="normal">B</mi><mrow><mn>1</mn><mi mathvariant="normal">i</mi></mrow></msub><msub><mi mathvariant="normal">B</mi><mrow><mn>2</mn><mi mathvariant="normal">i</mi></mrow></msub><msub><mi mathvariant="normal">B</mi><mrow><mn>3</mn><mi mathvariant="normal">i</mi></mrow></msub><msub><mi mathvariant="normal">B</mi><mrow><mn>4</mn><mi mathvariant="normal">i</mi></mrow></msub><msub><mi mathvariant="normal">B</mi><mrow><mn>5</mn><mi mathvariant="normal">i</mi></mrow></msub><msub><mi mathvariant="normal">B</mi><mrow><mn>6</mn><mi mathvariant="normal">i</mi></mrow></msub><msub><mi mathvariant="normal">B</mi><mrow><mn>7</mn><mi mathvariant="normal">i</mi></mrow></msub><msub><mi mathvariant="normal">B</mi><mrow><mn>8</mn><mi mathvariant="normal">i</mi></mrow></msub><mo>=</mo><msub><mi mathvariant="normal">K</mi><mi mathvariant="normal">i</mi></msub><mrow><mo>(</mo><mo>+</mo><mo>)</mo></mrow><mi mathvariant="normal">E</mi><mrow><mo>(</mo><mrow><msub><mi mathvariant="normal">R</mi><mrow><mi mathvariant="normal">i</mi><mo>-</mo><mn>1</mn></mrow></msub></mrow><mo>)</mo></mrow><mo>.</mo></mrow></math><img file="EP1638245A1_D0001.tif" /></maths>

0010A second step applies to the 48 bits from the previous step a substitution table, denoted S or SBOX. In this step, each group of six bits resulting from the preceding expansion is transformed by one of eight substitution functions (primitive functions), denoted S₁ at S₈substituting each group B_1i at 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, noted 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 as:<maths id="math0002" num=""><math display="block"><mrow><mi mathvariant="normal">f</mi><mrow><mo>(</mo><mrow><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></mrow><mo>)</mo></mrow><mo>=</mo><mi mathvariant="normal">P</mi><mrow><mo>(</mo><mrow><msub><mi mathvariant="normal">S</mi><mn>1</mn></msub><mrow><mo>(</mo><mrow><msub><mi mathvariant="normal">B</mi><mrow><mn>1</mn><mi mathvariant="normal">i</mi></mrow></msub></mrow><mo>)</mo></mrow><msub><mi mathvariant="normal">S</mi><mn>2</mn></msub><mrow><mo>(</mo><mrow><msub><mi mathvariant="normal">B</mi><mrow><mn>2</mn><mi mathvariant="normal">i</mi></mrow></msub></mrow><mo>)</mo></mrow><msub><mi mathvariant="normal">S</mi><mn>3</mn></msub><mrow><mo>(</mo><mrow><msub><mi mathvariant="normal">B</mi><mrow><mn>3</mn><mi mathvariant="normal">i</mi></mrow></msub></mrow><mo>)</mo></mrow><mo>...</mo><msub><mi mathvariant="normal">S</mi><mn>8</mn></msub><mrow><mo>(</mo><mrow><msub><mi mathvariant="normal">B</mi><mrow><mn>8</mn><mi mathvariant="normal">i</mi></mrow></msub></mrow><mo>)</mo></mrow></mrow><mo>)</mo></mrow><mo>.</mo></mrow></math><img file="EP1638245A1_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, namely: <maths id="math0003" num=""><math display="block"><mrow><msub><mi mathvariant="normal">K</mi><mi mathvariant="normal">i</mi></msub><mo>=</mo><mi mathvariant="normal">KS</mi><mrow><mo>(</mo><mrow><mi mathvariant="normal">i</mi><mo>,</mo><mi mathvariant="normal">KEY</mi></mrow><mo>)</mo></mrow><mo>.</mo></mrow></math><img file="EP1638245A1_D0003.tif" /></maths>

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

0014The decryption is carried out by submitting a block to be deciphered M 'to the initial permutation IP, then to 16 iterations of computation identical to those of the encryption with the only difference that the sub-keys are used in an inverse order (one starts from the subkey K₁₆ to end with the subkey K₁). The first block resulting from the inverse permutation is the R block₁₆The₁₆ and the block from the last iteration to be subjected to the IP initial inverse permutation^-1 is the block L₀R₀. IP swapping^-1 gives the decrypted block M.

0015A weakness of the DES type algorithms appears during attacks by statistical analysis of the consumption of a circuit executing the algorithm. Such attacks consist in making assumptions on the key to correlate an intermediate result during the iteration with the consumption of the integrated circuit. These attacks make it possible to break the secret constituted by the key. Indeed, the function f is known (DES norm) as well as the input data applied to the algorithm. Assuming part of subkey K hypothetically, we obtain an intermediate result L_iR_i. If we obtain a correlation between the intermediate result and the consumption of the circuit at a time t, the hypothesis on the key is verified. The computing means allow the hackers to make assumptions 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 hide the execution by introducing random numbers in the iterations. This solution has the disadvantage 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 speed issues, the algorithm is generally executed, at least partially, by a wired logic cell integrated in the circuit using the data. The key is usually stored in a secure area of ​​the circuit, for example, in a phase of personalization of the integrated circuits. Its loading into the execution cell of the algorithm is carried out in a protected manner, for example by applying the methods described in patents FR-A-2 802 668 and FR-A-2 802 669.

0017A second known solution is to hide the execution of the algorithm with the secret key by executing it among several executions (of the order of ten) using false keys. These keys are permanently stored in a non-volatile memory associated with the execution processor of the algorithm or directly hard-wired in the circuit. The real key is usually written when customizing the circuit (for example, the smart card) by a different person than the circuit manufacturer, in a generally inaccessible area (secure area of ​​the circuit). Thus, a hacker can not know, when a hypothesis on a key is true, if it is the right key or not that was used. A disadvantage of this solution is that, in order to preserve the masking, it is necessary to protect all the keys (the false ones like the real ones) when they are loaded in the execution cell of the algorithm. This takes time and lengthens, inconsistently with the desired fast manipulation of the data, the execution of the algorithm. Another disadvantage of this solution is that it only brings white noise easily filterable by the pirate.

Summary of the invention

0018The 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 that executes this algorithm.

0019The invention aims in particular to propose a solution compatible with the speed required for ciphering and deciphering data.

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

0021To reach these objects as well as others, the present invention provides a method of protecting the execution of an algorithmic calculation taking into account at least one valid data item and at least one secret key by an integrated circuit, and performing several iterations of an encryption calculation, comprising 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.

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

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

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

0025According 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 of the result of the application of the algorithm to the valid data.

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

0027According 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 applying an encryption iteration, the 64-bit block of each mask comprising among the bits of positions 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.

0028The invention also provides a processor for executing a DES encryption algorithm or the like.

detailed description

0029These and other objects, features, and advantages of the present invention will be set forth in detail in the following non-limiting description of particular embodiments. For the sake of clarity, only the steps and elements that are necessary for understanding the invention will be described later. In particular, the realization of a calculation processor for the implementation of the invention has not been detailed, it can be implemented with any conventional processor, providing the appropriate data.

0030A feature of the present invention is to mask the execution of the encryption algorithm by executing this algorithm several times with false data, thus masking the encryption of the "true" data. The true 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. Execution of the algorithm with the unmasked input is interspersed, preferably at a random position, in the series of masked executions. Preferably, all the ciphers are effected with the same key, which is therefore transferred only once in the processing cell of the algorithm.

0031The 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 exclusive-OR function (bitwise addition ) with the block of data 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 of the result of the application of the algorithm to the valid data .

0032Consequently, an attacker introducing a piece of data that he knows and making assumptions on the key is incapable of obtaining a correct correlation with the consumption of the integrated circuit insofar as this consumption is a function of a different datum.

0033The invention will be described later in connection with a preferred implementation of the DES algorithm. However, it applies more generally to any encryption algorithm, provided that the creation of masks for creating false data by modifying a message to be encrypted can be adapted.

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

0035One advantage of running the algorithm with multiple data rather than multiple keys is that the data does not have to be hidden for introduction into the cell. The protection then slows the encryption or decryption of the input data only negligibly compared to the conventional solution using several keys.

0036The present invention takes advantage of the fact that, in any encryption algorithm and in particular in the DES algorithm, the calculation process makes that successive values ​​can be predicted by making assumptions on the key. The false messages (hidden data) intervening from the beginning make that these hypotheses are seen as relating to a false key. In the DES algorithm, at each moment of the computation where the key intervenes in the form of a subkey with the message, the data and the sub-key are then linked by a function noted arbitrarily g to provide an intermediate result noted arbitrarily I which is such that I = g (KEY, D). An attack by consumption analysis consists in trying to correlate the results I with consumption by making assumptions on the key KEY. Knowing the data D it introduces, and knowing the function g (the DES algorithm is known), the hacker 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 hypothesis on the key was the good one.

0037Running the algorithm on a false data causes the attacker to obtain a correlation on modified data D '. It follows that the correlation appears on a hypothesis of key which is not the good one. In other words, the hacker grows that the algorithm executes the function I = g (KEY, D) while it ultimately executes 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 introduced) and therefore makes assumptions on the key from consumption analyzes. But this consumption is skewed without him knowing it.

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

0039As the result provided by the circuit is distorted, it is necessary to interpose, at random, the "good" execution among some masked executions (the number of masked executions is chosen as a function of the time available for the execution of the algorithm) . This is especially necessary to operate the circuit correctly in the absence of hacking (it must be able to provide the correct encryption during a normal execution). This correct result is provided in a result area different from that in which the false executions are found.

0040Preferably, the execution with the valid data 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 stored temporarily 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.

0041In 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.

0042The masks construction function 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), operation g (bitwise addition in the case of DES) of combination of the first subkey K₁ or K₁'with an intermediate result noted I (I = E (R₀) in the case of the DES) function of the input data before application of the first subkey, is such that:

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

0044However, the masks are built independently of the data D with which they are likely to be combined, these data being however unknown.

0045For the DES algorithm, when we consider the bits of the initial message, we see that some bit positions (determined by IP and E) are combined with the key bits, for example bits 1, 2, 3, 4, 5 and 6 of subkey K₁ are combined with an exclusive-OR (+) with the bits b₇, b₅₇, b₄₉, b₄₁, b₃₃ and B₂₅ of the data block D introduced. Thus, a six-bit combination masking m₁, m₂, m₃, m₄, m₅ and M₆ with the bits b₇, b₅₇, b₄₉, b₄₁, b₃₃ and B₂₅ the data message provides a new message which, when applied to the input of the encryption cell, achieves the same result after 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, whereas under the assumption of a false key, it will see a correlation between the predicted key (its hypothesis) and the data actually calculated.

0046For the manipulation of the false data is not detectable, the mask (which can be considered as a predetermined data block - the six masking bits in the positions b_{7 '} b_{57 '} b₄₉, b₄₁, b₃₃ and B₂₅) must be introduced at the input of the cell.

0047According to a preferred embodiment, one chooses any combination of states 0 and 1 for the six bits b₇, b₅₇, b₄₉, b₄₁, b₃₃ and B₂₅ of the masking data block (a combination of the possible 64) 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₂₅, do not be modified by the mask. Alternatively, the other bits of the block will be set randomly. This variant is however not preferred because it may introduce a white noise.

0048The preferred embodiment above takes into account that, in the DES algorithm, the application of the first substitution S (SBOX) affects only the bits b.₇, b₅₇, b₄₉, b₄₁, b₃₃ and B₂₅, from the data block. Indeed, by representing the 64-bit blocks as eight-word eight-bit matrices and by repeating the previous notations, the input data block can be written as: 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₆₄.

0049After applying the IP initial 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₇.

0050When the left and right parts are subject 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 changed to: b₇, b₅₇, b₄₉, b₄₁, b₃₃, b₂₅, b₁₇ ; b₂₅, b₁₇, b₉...; ...; ..., b₁₅, b₇, b₅₇.

0051At the output 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₁.

0052Thus, it is possible to mask a datum D by combining it with an exclusive-OR with a block including at least one of the bits b₇, b₅₇, b₄₉, b₄₁, b₃₃ and B₂₅ is at 1 and all other bits are at 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.

0053We successively mask all the parts of the data D by applying the same mask to each block of 64 bits introduced into the cell.

0054Of course, the present invention is susceptible of various variations and modifications which will be apparent to those skilled in the art. In particular, although the invention has been described in relation to a preferred embodiment for generating false data, its transposition to another generation function is within the abilities of the person skilled in the art while respecting the condition that each portion to which the DPA attack selection function, i.e., each six bit portion input of the substitution steps, differs from at least one bit when masked.

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

0056In addition, other functions of combining the masks with the input data are possible provided to respect the features described above. Bit-by-bit addition, however, is preferred because of its simplicity.