Encryption/description method protected against side-channel attacks

Abstract

The present invention relates to a method for encryption or decryption of a data block from a secret key, wherein the method comprises: generating a first round key k.sub.r dependent on the secret key, selecting each of a first mask (b.sub.r) and a second mask (b.sub.r+1) in a set consisting of a mask of bits all at one and a mask of all zero bits, calculating a first masked key k.sub.r from the first round key k.sub.r and the first mask (b.sub.r) as follows:
k.sub.r=k.sub.r(b.sub.r)
wherein is an exclusive disjunction, executing a first encryption round applied to two first data dependent on the data block, by means of the first masked round key k.sub.r so as to produce two second data, after producing the first masked key k.sub.r, generating a second round key k.sub.r+1 dependent on the secret key, calculating a second masked key k.sub.r+1 from the second round key k.sub.r+1 and the second mask (b.sub.r+1) as follows: k.sub.r+1=k.sub.r+1(b.sub.r+1), calculating two third data L.sub.r.sup.b.sup.r+1, R.sub.r.sup.b.sup.r+1 as follows:
R.sub.r.sup.b.sup.r+1=R.sub.r.sup.b.sup.r(b.sub.r1)(b.sub.r)
L.sub.r.sup.b.sup.r+1=L.sub.r.sup.b.sup.r(b.sub.r1)(b.sub.r)
and executing a second encryption round following the first encryption round, wherein the second encryption round is applied to the two third data L.sub.r.sup.b.sup.r+1, R.sub.r.sup.b.sup.r+1 by means of the second masked round key k.sub.r+1.

Claims

1. A computer-implemented method for encrypting or decrypting an input data block from a secret key, wherein the method comprises steps of: generating a first round key k.sub.r dependent on the secret key, selecting each of a first mask (b.sub.r) and a second mask (b.sub.r+1) in a set consisting of a mask of bits all at one and a mask of all zero bits, calculating a first masked key k.sub.r from the first round key k.sub.r and the first mask (b.sub.r) as follows:
k.sub.r=k.sub.r(b.sub.r) wherein is an exclusive disjunction, executing a first encryption round applied to two first data dependent on the input data block, by means of the first masked round key k.sub.r so as to produce two second data L.sub.r.sup.b.sup.r, R.sub.r.sup.b.sup.r, after producing the first masked key k.sub.r, generating a second round key k.sub.r+1 dependent on the secret key, calculating a second masked key k.sub.r+1 from the second round key k.sub.r+1 and the second mask (b.sub.r+1) as follows:
k.sub.r+1=k.sub.r+1(b.sub.r+1) calculating two third data L.sub.r.sup.b.sup.r+1, R.sub.r.sup.b.sup.r+1 as follows
R.sub.r.sup.b.sup.r+1=R.sub.r.sup.b.sup.r(b.sub.r1)(b.sub.r)
L.sub.r.sup.b.sup.r+1=L.sub.r.sup.b.sup.r(b.sub.r1)(b.sub.r) executing a second encryption round following the first encryption round, wherein the second encryption round is applied to the two third data L.sub.r.sup.b.sup.r+1, R.sub.r.sup.b.sup.r+1 by means of the second masked round key k.sub.r+1, so as to produce two fourth data, generating an output data block dependent on the two fourth data, and storing the output data block in a memory.

2. The method according to claim 1, comprising generating a plurality of round keys, and comprising a plurality of successive encryption rounds, wherein a round key is generated before each encryption round, and wherein: for each generated round key, a mask associated with the round key is selected, and an exclusive disjunction of the round key and of the associated mask is calculated so as to produce a masked key, calculating two third data by means of the masked key is performed between each pair of successive encryption rounds.

3. The method according to claim 2, wherein selecting each mask is performed before the plurality of encryption rounds and/or before the generation of the plurality of round keys.

4. The method according to claim 1, wherein the first mask (b.sub.r) and the second mask (b.sub.r+1) are selected randomly.

5. The method according to claim 1, wherein the mask of bits all at one and the mask of all zero bits are equiprobable.

6. The method according to claim 1, comprising generating a number having a plurality of bits, each round key being associated with one of the bits, and wherein the mask selected to mask a round key is: the mask of bits all at one if the bit associated with the round key has a first value, the mask of all zero bits if the bit associated with the round key has a second value different to the first value.

7. The method according to claim 1, wherein the encryption round applied to the two first data comprises: applying an encryption function to one of the two first data by means of the first masked round key so as to produce an intermediate datum, wherein the first datum also forms one of the two second data, calculating an exclusive disjunction of the intermediate datum and of the other first datum so as to produce the other second datum.

8. A non-transitory computer-readable medium comprising code instructions for causing a computer to perform a method for encrypting or decrypting a data block from a secret key, wherein the method comprises steps of: generating a first round key k.sub.r dependent on the secret key, selecting each of a first mask (b.sub.r) and a second mask (b.sub.r+1) in a set consisting of a mask of bits all at one and a mask of all zero bits, calculating a first masked key k.sub.r from the first round key k.sub.r and the first mask (b.sub.r) as follows:
k.sub.r=k.sub.r(b.sub.r) wherein is an exclusive disjunction, executing a first encryption round applied to two first data dependent on the data block, by means of the first masked round key k.sub.r so as to produce two second data L.sub.r.sup.b.sup.r, R.sub.r.sup.b.sup.r, after producing the first masked key k.sub.r, generating a second round key k.sub.r+1 dependent on the secret key, calculating a second masked key k.sub.r+1 from the second round key k.sub.r+1 and the second mask (b.sub.r+1) as follows:
k.sub.r+1=k.sub.r+1(b.sub.r+1) calculating two third data L.sub.r.sup.b.sup.r+1, R.sub.r.sup.b.sup.r+1 as follows
R.sub.r.sup.b.sup.r+1=R.sub.r.sup.b.sup.r(b.sub.r1)(b.sub.r)
L.sub.r.sup.b.sup.r+1=L.sub.r.sup.b.sup.r(b.sub.r1)(b.sub.r) executing a second encryption round following the first encryption round, wherein the second encryption round is applied to the two third data L.sub.r.sup.b.sup.r+1, R.sub.r.sup.b.sup.r+1 by means of the second masked round key k.sub.r+1.

9. A device for encryption or decryption of an input data block from a secret key, the device comprising at least one processor configured to: generate a first round key k.sub.r dependent on the secret key, select each of a first mask (b.sub.r) and a second mask (b.sub.r+1) in a set consisting of a mask of bits all at one and a mask of all zero bits, calculate a first masked key k.sub.r from the first round key k.sub.r and the first mask (b.sub.r) as follows:
k.sub.r=k.sub.r(b.sub.r) wherein is a XOR operator, execute an encryption round applied to two first data dependent on the input data block, by means of the first masked round key k.sub.r so as to produce two second data L.sub.r.sup.b.sup.r, R.sub.r.sup.b.sup.r, after producing the first masked key k.sub.r, generate a second round key k.sub.r+1 dependent on the secret key, calculate a second masked key k.sub.r+1 from the second round key k.sub.r+1 and the second mask (b.sub.r+1) as follows:
k.sub.r+1=k.sub.r+1(b.sub.r+1) calculate two third data L.sub.r.sup.b.sup.r+1, R.sub.r.sup.b.sup.r+1 as follows
R.sub.r.sup.b.sup.r+1=R.sub.r.sup.b.sup.r(b.sub.r1)(b.sub.r)
L.sub.r.sup.b.sup.r+1=L.sub.r.sup.b.sup.r(b.sub.r1)(b.sub.r) execute a following encryption round applied to the two third data L.sub.r.sup.b.sup.r+1, R.sub.r.sup.b.sup.r+1 by means of the second masked round key (k.sub.r+1) so as to produce two fourth data, generate an output data block dependent on the two fourth data, and store the output data block in a memory.

10. A smart card comprising an encryption or decryption device according to claim 9.

Description

DESCRIPTION OF THE FIGURES

(1) Other characteristics, aims and advantages of the invention will emerge from the following description which is purely illustrative and non-limiting and which must be considered with respect to the appended drawings, wherein:

(2) FIG. 1 schematically illustrates an encryption or decryption device.

(3) FIGS. 2, 3 and 4 schematically illustrate steps of an encryption or decryption method, according to an embodiment of the invention.

(4) In all figures, similar elements bear identical reference numerals.

DETAILED DESCRIPTION OF THE INVENTION

(5) In reference to FIG. 1, an encryption device 1 comprises at least one processor 10 and at least one memory 12.

(6) The processor 10 is configured to execute a symmetric block encryption program.

(7) The memory 12 is configured to store data used by this program.

(8) In particular, the memory 12 comprises a non-volatile memory unit which stores data to be used during each execution of the program. These data especially comprise two permutation tables PC1 and PC2.

(9) The non-volatile memory unit is of HDD, SSD, Flash type, etc.

(10) The memory 12 also comprises a volatile memory unit (for example of RAM type). The purpose of the volatile memory unit is to temporarily store data generated by the processor 10.

(11) The volatile memory unit especially comprises three memory registries: a first registry X, a left registry L, and a right registry R.

(12) For example, the encryption device 1 is a smart card, a smart card component, or it comprises a smart card (bank card, etc.).

(13) In reference to FIG. 2, a DES encryption method comprises the following steps.

(14) The encryption method inputs a data block B to be encrypted and a secret key K and produces an encrypted data block B.

(15) The processor 10 conventionally executes: a key schedule 200 generating n round keys k.sub.1, . . . , k.sub.r, . . . , k.sub.n from the secret key K; a succession of n encryption rounds 300, each round using one of the generated round keys.

(16) Masks Selection

(17) Also, non-conventionally, two predetermined binary masks are stored in the non-volatile unit of the memory 12: a mask whereof the bits are all of value 1, called all-at-1 mask, and a binary mask whereof all the bits are zero, called zero mask.

(18) Each of the two binary masks has a number of bits equal to the number of bits of the block B to be encrypted.

(19) In a step 100, the processor 10 selects n binary masks from the two predetermined binary masks, the selected masks being noted (b.sub.1), . . . , (b.sub.r), . . . , (b.sub.n). In other words, each binary mask (b.sub.r) is either the all-at-1 mask or the zero mask.

(20) As will be evident below, the binary mask (b.sub.r) is associated with the round key k.sub.r.

(21) Each binary mask (b.sub.r) is selected randomly, for example according to a uniform law such that each of the two all-at-1 and zero masks are equiprobable.

(22) The selection 100 of the binary masks is preferably conducted before the succession of encryption rounds 300 and/or before the key schedule 200 generating the n round keys.

(23) For example, the selection 100 of the binary masks comprises a query by the processor to a function which randomly draws a number having at least n bits. Each bit of the drawn number is associated with one of the round keys: the r-ith bit starting from the right (or left) of the drawn number, noted b.sub.r, is for example associated with the key k.sub.r.

(24) When the mask (b.sub.r) is to be used in a calculation, the processor reads the value of the bit b.sub.r of the number which has been drawn previously. As a function of this value, the processor loads the mask all-at-1 or the zero mask which are pre-stored. For example: the processor loads the mask all-at-1 if b.sub.r=1, and the processor loads the zero mask if b.sub.r=0,
or vice-versa.

(25) With such a selection method it is unnecessary to store the n masks selected in addition to the mask all-at-1 and the zero mask. Only the number of n bits drawn randomly is to be stored, which enables memory consumption economy.

(26) Of course, other methods are possible for generating each binary mask (b.sub.r). According to one of them, the processor 10 generates the mask (b.sub.r) by calculating the result of b.sub.r1. If b.sub.r is zero the processor 10 obtains 1=11111111 (on an octet) in signed representation, and therefore the binary mask of bits all-at-1, and if b.sub.r is 1 then the processor 10 obtains 0=00000000 (on an octet), therefore the zero binary mask.

(27) Round Keys Schedule

(28) In reference to FIG. 3, the key schedule 200 comprises the following steps.

(29) In a step 202, the processor 10 executes permutation on at least one portion of the secret key K, and this by means of the first permutation table PC1.

(30) The secret key K has typically 64 bits including 56 base bits contributing entropy to the secret key K and 8 additional redundancy bits not contributing entropy to the secret key K. The portion of the key K subject to the permutation 100 is formed by the 56 base bits, and permutation 100 produces binary data having a cumulative length of 56 bits also.

(31) The result of permutation 202 is split into two initial binary data: most significant 28 bits of this result and least significant 28 bits of this result.

(32) The method then executes a plurality of iterations, each iteration producing a round key.

(33) The iteration of index r producing the key k.sub.r comprises the following steps.

(34) In a step 204, the processor 10 performs rotation applied to initial data which depend on the secret key K so as to produce two binary data offset by a certain number of bits (for example rotation to the left).

(35) In the first iteration, the data to which rotation is applied are the binary data produced by the permutation 202. In a reference iteration of index r which is not the first iteration, the initial data are produced by the iteration of index r1 preceding the reference iteration of index r.

(36) In a step 206, the processor 10 swaps the offset binary data by means of the table PC2 so as to produce the round key k.sub.r. More precisely, permutation 104 is executed on the concatenation of the two offset binary data.

(37) The round key k.sub.r is for example stored in the first memory registry X, this registry being common to all iterations.

(38) In a step 106, the processor 10 executes masking 208 of the round key. This masking 208 is done by calculating the exclusive disjunction of the round key k.sub.r and of the selected mask (b.sub.r). The result k.sub.r(b.sub.r) of this masking 208 constitutes a masked key 14.

(39) The masked key k.sub.r is for example stored in the first memory registry X in place of the round key k.sub.r.

(40) Steps 204, 206, 208 are repeated during each iteration of the key schedule 200. The data to which the rotation step 204 of an iteration not being the first iteration is applied are executed on the data offset during the preceding iteration.

(41) DES Encryption Rounds

(42) In reference to FIG. 4, in the plurality of encryption rounds 300 each encryption round uses one of the round keys generated during the key schedule.

(43) A masked round key is generated before each encryption round. In particular, as indicated previously, the masked round key k.sub.r is stored in the first memory registry X before its use during the encryption round of index r, and the following masked round key k.sub.r+1 is stored in the same first memory registry X before its use during a following encryption round of index r+1.

(44) Also, the plurality of encryption rounds 300 uses the right registry R and the left registry L.

(45) An encryption round of index r comprises the following sub-steps.

(46) It is assumed that a datum L.sub.r1.sup.b.sup.r dependent on the input data block B has been stored in the left registry L. Similarly, a datum noted R.sub.r1.sup.b.sup.r also dependent on the data block B has been stored in the right registry R.

(47) The encryption round of index r is applied to the data L.sub.r1.sup.b.sup.r and R.sub.r1.sup.b.sup.r and also uses the masked round key k.sub.r=k.sub.r(b.sub.r).

(48) The processor 10 applies 302 a predetermined encryption function to the datum R.sub.r1.sup.b.sup.r contained in the right registry R by means of the masked round key k.sub.r so as to produce an intermediate datum (R.sub.r1.sup.b.sup.r, k.sub.r). The predetermined encryption function is known per se.

(49) The processor 10 calculates 304 the exclusive disjunction of the intermediate datum and of the datum L.sub.r1.sup.b.sup.r contained in the left registry L. The result of this calculation 304 is then stored in the right registry R and is noted R.sub.r.sup.b.sup.r.

(50) Also, the processor copies the datum R.sub.r1.sup.b.sup.r in the left registry L.

(51) On completion of the encryption round of index r this eventually gives:
L.sub.r.sup.b.sup.r=R.sub.r1.sup.b.sup.r
R.sub.r.sup.b.sup.r=L.sub.r1.sup.b.sup.r(R.sub.r1.sup.b.sup.r,k.sub.r(b.sub.r))

(52) In a conventional DES encryption or decryption method, a following encryption round (of index r+1) would be applied directly to the data R.sub.r.sup.b.sup.r and L.sub.r.sup.b.sup.r.

(53) However, in terms of the present invention and in a non-conventionally manner, the second data R.sub.r.sup.b.sup.r and L.sub.r.sup.b.sup.r are subject to a correction 306 before their use during the following encryption round of index r+1.

(54) The correction 306 comprises the following calculations:
R.sub.r.sup.b.sup.r+1=R.sub.r.sup.b.sup.r(b.sub.r1)(b.sub.r)
L.sub.r.sup.b.sup.r+1=L.sub.r.sup.b.sup.r(b.sub.r1)(b.sub.r)

(55) The following encryption round of index r+1 is applied to the two corrected data R.sub.r.sup.b.sup.r+1 and L.sub.r.sup.b.sup.r+1, and also uses the round key k.sub.r+1. This following round comprises the same steps as those described previously: application 302 of the encryption function to the corrected datum R.sub.r.sup.b.sup.r+1, by means of the masked round key k.sub.r+1=k.sub.r+1(b.sub.r+1) so as to produce a new intermediate datum; calculation 304 of the exclusive disjunction of the new intermediate datum and of the corrected datum L.sub.r.sup.b.sup.r+1 so as to produce the datum R.sub.r+1.sup.b.sup.r+1.

(56) The same steps are performed during each of the n encryption rounds. For each generated round key, the correction 306 is performed between each pair of successive encryption rounds.

(57) Since the DES encryption is symmetrical, a data block is decrypted by means of the same secret key K and the same steps as those of the DES encryption method described previously.

(58) It is observed that during the described encryption method, storing in the first memory registry X of the clear round key k.sub.r executed during an iteration of index r of the key schedule (not being the first iteration) overwrites the masked key k.sub.r1=k.sub.r1(b.sub.r1) stored during the preceding iteration of index r1 of the key schedule.

(59) As the masks (b.sub.r1) and (b.sub.r) are each likely to be either the all-at-1 mask or the zero mask, four different cases may present: b.sub.r1=0 and b.sub.r=0, or b.sub.r1=1 and b.sub.r=0, or b.sub.r1=0 and b.sub.r=1, or b.sub.r1=1 and b.sub.r=1.

(60) In other words, according to the selected masks, the modification of the content of the first memory registry X will be different.

(61) An attacker probing the content of the first registry X is faced with uncertainty preventing him from determining whether the change in value of bit of rank k in the first registry X results from the difference between the bit of rank k of the round key k.sub.r and the round key k.sub.r+1, or whether it results from the difference between the masks (b.sub.r1) and (b.sub.r). The attacker therefore cannot deduce information letting him guess the round keys and consequently the secret key K on which they depend, by observing the first registry X.

(62) Also, the correction made between two successive rounds of indices r and r+1 is coherent with the applied values of the masks (b.sub.r) and (b.sub.r+1).

(63) In the embodiment described above, the registry X would serve as transit point for the different round keys generated and may be scrutinized by the attacker. It should be noted however that attacks of the same type may obviously be undertaken even if such a registry X is not being used. The attacker may for example observe signals which transit over conductive wires of the device 1 during execution of the DES encryption/decryption for the same purposes. More generally, the invention lends extra protection to any encryption/decryption algorithm during which at least two round keys are generated successively, a context allowing an attacker to try to go back to the key K by examining the differences between the two successively generated keys.

(64) The invention may further be generalized from other symmetric block encryption/decryption methods, for example the TDES encryption method.