Method to counter DCA attacks of order 2 and higher on table-based implementations

Abstract

The present invention relates to a method to counter DCA attacks of order 2 and higher order applied on an encoded table-based (TCabi,j) implementation of block-cipher of a cryptographic algorithm to be applied to a message (m), said method comprising the steps of: —translating a cryptographic algorithm block-cipher to be applied on a message (m) into a series of look-up tables (Tabi,j),—applying secret invertible encodings to get a series of look-up tables (TCi,j),—computing message-dependent masking values, comprising the computation of at least two shares of masking value (mmask1, mmask2) for the input of the table network based on at least two different message derivation functions (F1, F2),—re-randomizing the tables (TCi,j) using the computed message-dependent masking values (mmask1, mmask2),—computing rounds to be applied on the message (m) based on the randomized network of tables (TCi,j).

Claims

1. A method to counter DCA attacks of order 2 and higher order applied on an encoded table-based (TC.sub.i,j) implementation of block-cipher of a cryptographic algorithm to be applied to a message (m), said method comprising the steps of: translating a cryptographic algorithm block-cipher to be applied on a message (m) into a series of look-up tables (Tab.sub.i,j) organized in several layers, applying secret invertible encodings to get a series of encoded look-up tables (TCi,j), computing message-dependent masking values, comprising the computation of at least two shares of masking value (mmask1, mmask2) for the input of the table network based on at least two different message derivation functions (F1, F2), re-randomizing the encoded tables (TCi,j) in at least two steps using the computed message-dependent masking values (mmask1,mmask2), comprising: randomizing tables of a first layer using a masking value (mmask1) on the input and the image of said masking value by a random secret function (G(mmask1)) on the output, re-randomizing said randomized tables of the first layer using another masking value (mmask2) on the input and the image of said other masking value by the random secret function (G(mmask2)) on the output, re-randomizing the tables of each other layer j as follows, i being the index of the table in the layer: computation of, for all x, TC_{i,j,G(j−1) (mmask1,i)}(x){circumflex over ( )}{G(j) (mmask1,i)}=TC_{i,j}(x⊕G(j−1) (mmask1,i)) ⊕G(j) (mmask1,i) and, for all x, TC_{i,j, G(j−1) (mmask1,i) ⊕G(j−1) (mmask2,i) }(x){circumflex over ( )}{G(j) (mmask1,i) ⊕G(j) (mmask2,i)}=TC_{i,j, G(j−1)(mmask1,i)}{circumflex over ( )}{G(j) (mmask1,i)} (x⊕G(j−1)(mmask2,i) ⊕G(j) (mmask2,i), computing rounds to be applied on the message (m) based on the re-randomized network of tables (TCi,j).

2. The method according to claim 1, wherein the computation of at least two shares of masking value (mmask1, mmask2) for the input of the table (TCi,j) network is further based on at least two secret constant values (emask1, emask2) obfuscated in the code using obfuscation techniques.

3. The method according to claim 2, wherein the at least two shares of masking values (mmask1,mmask2) are obtained as follows, with n being an integer depending on the concerned cryptographic algorithm block-cipher and emask1 and emask2 being said secret constant values: h1=F1(m) (or h1=F1(M)) h2=F2(m) (or h2=F2(M)) mmask1=emask1⊕trunc1—n(h1)⊕trunc1—n(h2) mmask2=emask2⊕truncn+1—2n(h1)⊕truncn+1—2n(h2).

4. The method according to claim 3, wherein, the cryptographic algorithm block-cipher being part of a DES algorithm, n=96.

5. The method according to claim 3, wherein, the cryptographic algorithm block-cipher being part of an AES algorithm, n=128.

6. The method according to claim 2, wherein the step of computing message-dependent masking values comprises the computation of t values mmask1, mmask2, . . . , mmaskt for the input of the table network based on t secret constant values (emask1, emaskt) obfuscated in the code using obfuscation techniques and p derivation functions (F1, . . . , Fp).

7. The method according to claim 1, wherein the accumulative application of the random secret function (G) is as follows, i being the index of the table in the layer, for the first layer of tables (T), computation of, for all x, TC_{i,1,0}(x){circumflex over ( )}{G(mmask1,i)}=TC_{i,1}(x⊕mmask1,i) ⊕ G (mmask1,i) and, for all x, TC_{i,1,}(x) {circumflex over ( )}{G(mmask1,i)⊕G(mmask2,i)}= TC_{i,1,0}{circumflex over ( )}{G(mmask1,i)} (x)⊕G (mmask2,i).

8. The method according to claim 1, wherein the accumulative application of the random secret function (G) is as follows, i being the index of the table in the layer: for the first layer of tables, computation of, for all x, TC_{i,1,mmask1,i}(x){circumflex over ( )}{G(mmask1,i)}=TC_{i,1}(x⊕mmask1,i) ⊕ G (mmask1,i) and, for all x, TC_{i,1,mmask1,i ⊕mmask2,i}(x) {circumflex over ( )}{G(mmask1,i)⊕ G(mmask2,i)}= TC_{i,1,mmask1,i}{circumflex over ( )}{G(mmask1,i)} (x⊕ mmask2,i) ⊕ G (mmask2,i).

9. The method according to claim 1, wherein the message (m) is firstly combined with a first share (mmask1) of masking value (m ⊕mmask1) and then the result is combined with the next share of masking value (mmask2) ((mmask1) mmask1).

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The following description and the annexed drawings set forth in detail certain illustrative aspects and are indicative of but a few of the various ways in which the principles of the embodiments may be employed. Other advantages and novel features will become apparent from the following detailed description when considered in conjunction with the drawings and the disclosed embodiments are intended to include all such aspects and their equivalents.

(2) FIG. 1 represents a schematic flowchart of a classical implementation of a DES algorithm;

(3) FIG. 2 shows a schematic diagram of an advantageous implementation of the DES algorithm of FIG. 1 as represented as a partial network of table without encodings;

(4) FIG. 3 shows a schematic diagram of an advantageous implementation of the DES algorithm of FIG. 1 modified according to the Chow and al. proposal leading to an encoded table-based implementation of block-cipher of the DES algorithm to be applied to a message;

(5) FIG. 4 shows a flowchart of the method of the invention.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

(6) For a more complete understanding of the invention, the invention will now be described in detail with reference to the accompanying drawing. The detailed description will illustrate and describe what is considered as a preferred embodiment of the invention. It should of course be understood that various modifications and changes in form or detail could readily be made without departing from the spirit of the invention. It is therefore intended that the invention may not be limited to the exact form and detail shown and described herein, nor to anything less than the whole of the invention disclosed herein and as claimed hereinafter. The same elements have been designated with the same references in the different drawings. For clarity, only those elements and steps which are useful to the understanding of the present invention have been shown in the drawings and will be described.

(7) An illustrative example is below given for a DES algorithm implementation according to Chow implementation as disclosed in “A White-Box DES Implementation for DRM Applications”, Chow and al., Oct. 15, 2002, Pre-proceedings for ACM DRM-2002 workshop.

(8) DES algorithm is performed in 16 rounds, each employing the same eight DES S-Boxes (DSBs), S1 . . . S8, and the same ATs, sandwiched between initial and final ATs, initial and final permutations. Each DBS is an instance of .sup.4.sub.6E as disclosed for example in J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, pp. 250-259, CRC Press, 2001 (5th printing with corrections).

(9) FIG. 1 schematically shows an unrolling of two typical DES rounds where Kr is the round sub-key of round r according to Chow and al. As shown on FIG. 1, a Feistel network with a by-pass left-side data-path Lr−1,Lr,Lr+1 is implemented in the round structure. Other parts of the figure represent an active right-side data-path.

(10) FIG. 2 schematically shows an implementation encoded as proposed in the above cited document. Each round is here represented by two layers: the first layer is composed by 12 T-boxes that embed the xor addition with the round key followed by the non-linear DES S-boxes, and the second layer, represented by .sup.r-1M.sub.2 in FIG. 2, is a permutation of the state that is compliant with the DES specification and that is implemented using a network of table. In this second layer, the left and right sides are combined into a single 96 bit representation and a single .sup.rM.sub.2 transform is used to subsume the P-Box, xor, side flip, and E-box.

(11) An initial matrix M.sub.1 is further used to do an initial expansion of the input from 64 bits to the internal 96 bits form and a matrix M.sub.3 is used for the final shrink of the output.

(12) A set of matrix is thus used to implement the rounds of the DES algorithm.

(13) New S-Boxes identified as .sup.r.sub.KS.sub.i, where K is the encryption key, r is the round number, and i is the corresponding DSB (DES S-box) number are produced, such that, for any given input, .sup.r.sub.KSi yields the same result as Si, shown on FIG. 1, would produce in round r if the DES key were K, but the xors of the inputs of the original DSBs have been eliminated. It enables to make the key K disappear from the algorithm.

(14) The obtained implementations are vulnerable to statistical attacks. To counter them, lossy S-Boxes are replaced with a bijective function.

(15) As illustrated on FIG. 2, a split path encoding is performed through calculation of .sup.r.sub.KT.sub.i(.sub.8e)=.sup.r.sub.kS.sub.i(.sub.8e.sub.1 . . . 6)∥R(.sub.8e), for all .sub.8e, for the fixed key K, for round r=1 . . . 16, for S-Box number i=1 . . . 8, where we define R(.sub.8e)=<.sub.8e.sub.1; .sub.8e.sub.6; .sub.8e.sub.7; .sub.8e.sub.8< for all .sub.8e.

(16) Thus converted, each .sup.r.sub.KT.sub.i carries eight bits to the next .sup.rM.sub.2: 4 bits of S-Box output, 2 bits from the right side and 2 bits that can be chosen to be from the left. This means eight T boxes will only carry 16 bits from the left and 16 bits from the right. This means the by-pass capacity of the .sup.r.sub.KT.sub.i's is too small by 32 bits.

(17) Thus four more S-Boxes are added for each round, these extra S-Boxes make it easier to access the bypassed bits for subsequent processing.

(18) FIG. 2 shows an overall data-flow structure of the DES implementation obtained according to Chow immediately prior to de-linearization of ATs and encoding of S-Boxes.

(19) Thus before de-linearization and encoding, each Mi is representable as a matrix. This means for example that the entire implementation consists of networked 8×4 and 8×8 (.sup.r.sub.KT.sub.i) S-Boxes.

(20) Thus a table layer corresponds to “P2,1 .sup.1.sub.KTi-boxes P2,2”, the following level corresponds to next packet of “b1,2{circumflex over ( )}{−1}” à “B1,3”, then next level is of the “b1,3{circumflex over ( )}{−1}, .sup.2.sub.KTi-boxes, b1,4” type etc.

(21) With the implementation as disclosed in Chow and al, the block-cipher of any cryptographic algorithm as DES or AES are transformed into a series of look-up tables. In particular the standard S-boxes are replaced with key-specific S-boxes. These key-specific S-boxes are adapted to next provide local security. Thus, such an implementation is completed as disclosed in the above cited Chow and al document by application of secret invertible encodings for local security. It comprises mixing bijections for increasing the diffusion and non-linear encodings for increasing the confusion. FIG. 2 shows the overall Chow data-flow structure of the proposed DES implementation immediately prior to de-linearization of at s and encoding of S-Boxes characters. The resulting structure would look just the same after de-linearization and encoding, except that each matrix Mi and each .sup.r.sub.KT.sub.i would be replaced by a corresponding table, below generically noted Tab.sub.i,j.

(22) Thus, after such operations, a network of tables Tab.sub.i,j is built where the index i denotes the ith table of layer j. For the first layer of the round with T-boxes, i is among 1 to 12 and j=r as noted in FIGS. 1 and 2. For next layers corresponding to matrix M, more tables are generally used and some rounds r as presented in previous figures are processed with overlap on different layers, leading to an index j specific to the Chow implementation. All this is disclosed in the prior art. At this stage, on input m, the network of tables Tab.sub.i,j computes the value of DES[K](m). However, the intermediary values of the computation are not protected and it is easy to recompute the key K from the knowledge of the intermediary values and the input message.

(23) The DES algorithm is thus embedded in the matrix transformation being an encoded table-based implementation of block-cipher providing local security. The network of tables Tab.sub.i,j is converted into a table of networks TCi,j where the tables are protected using input and/or output secret encodings bi,j. This encoding step as known in prior art is schematically shown on FIG. 3.

(24) The invention applies to such an implementation as shown on FIG. 3 to further counter DCA attacks. It proposes an original masking scheme introducing subsequent mask mmaski, G(mmaski) . . . G{circumflex over ( )}32(mmaski) at each layer of tables TCi,j of the algorithm.

(25) The invention proposes to compute message-dependent masking values and (re)-randomization of tables and to compute rounds based on the randomized network of tables to protect a DES or AES implementation that is implemented using Chow et al. in order to be resistant against a second order DCA.

(26) As shown on FIG. 4, in a first step S1, two shares of masking value denoted mmask1 and mmask2 are computed for the input of the table network. The input is of 96-bit values for DES and of 128-bit values for AES. These two shares of masking values are based on, at least, two different message derivation functions F1 and F2. Those derivation functions are for example one derivation function based on a hash function and one derivation function based on CRC computation.

(27) In a preferred embodiment, the computation is further based on two values emask1 and emask2 that are obfuscated in the code using ad-hoc obfuscation techniques.

(28) The size of the manipulated values depends on the choice of the block-cipher: 96-bit for a Chow et al. implementation of DES, 128-bit for AES. The principle of the invention is the same in both case.

(29) We have for example, according to the preferred embodiment: h1=F1(m) (or h1=F1(M)) h2=F2(m) (or h2=F2(M)) mmask1=emask1⊕trunc1—96(h1)⊕trunc1—96(h2) mmask2=emask2⊕trunc97—122(h1)⊕trunc97—122(h2)

(30) where m is a 96-bit message for DES and M is a 64-bit message for DES. In the DES case, the size depends on whether the message m is the original input M or the message m after the initial transformation in a Chow et al. implementation. For AES, the message M=m and it is a 128-bit message.

(31) In practice, a pseudo random number generator is used to derive the mask from the message. The generator is such that no exploitable algebraic relation exists between the message and its mask. It is here noted that, in a smart card context, the mask is anyhow random and there is no issue regarding the independence between the message and the masking value.

(32) Once the initial values mmask1 and mmask2 are derived using secret obfuscated values, the input message m to the network of tables and the derivation functions F1 and F2, a random secret function G is used in a step S2 in order to derive all the masking values. As an example, G is implemented using tables.

(33) The tables are now randomized in two steps in order to target a resistance against 2nd order analysis.

(34) In more details, for the first layer of tables, one computes in a step S3:

(35) For all x, TC_{i,1,mmask1,i}{circumflex over ( )}{G(mmask1,i)}=TC_{i,1}(x⊕mmask1,i) ⊕G(mmask1,i), and in a step S4:

(36) For all x, TC_{i,1,mmask1,i⊕mmask2,i}{circumflex over ( )}{G(mmask1)⊕G(mmask2,i)}=TC_{i,1,mmask1,i}{circumflex over ( )}{G(mmask1,i)} (x⊕mmask2,i)⊕G (mmask2,i)

(37) For the second layer, one computes, in a step S5, G(G(mmask1)) and G(G(mmask2)), and in a step S6:

(38) For all x, TC_{i,2,G(mmask1,i)}{circumflex over ( )}{G(G(mmask1,i))}=TC_{i,2}(x⊕G(mmask1,i))⊕G(G(mmask1,i)) and, in a step S7:

(39) For all x, TC_{i,2, G(mmask1,i)⊕G(mmask2,i)}{circumflex over ( )}{G(G(mmask1,i))⊕G(G(mmask2,i))}=TC_{i,2,G(mmask1,i)}{circumflex over ( )}{G(G(mmask1,i))} (x ⊕G(mmask2,i))⊕G(G(mmask2,i))

(40) And so on for the other layers. X depends on the table size. For 8-bits sized table, input and output, x describes the set of values [0,1]{circumflex over ( )}8. x corresponds to the input size of the table. The calculation will be performed as many times as there are tables in the layer, this number depending on the type of tables. Tables have an input size and an output size. For T-box tables as an example, input size is 8 bits and output size is 8 bits. For next layer M2,1, XOR tables are necessitated. Thus the input size of a XOR table is 2*4 bits and the output size is 4 bits. AES algorithm requires other sizes of tables.

(41) More generally, for the layer j, one computes in a step S3j−1, G(j−1)(mmask1)) and G(j−1)(mmask2)), and in a step S3j:

(42) For all x, T_{i,j,G(j−1) (mmask1,i)}{circumflex over ( )}{G(j) (mmask1,i)}=T_{i,j}(x⊕G(j−1) (mmask1,i))⊕G(j) (mmask1,i) and, for a step S3j+1:

(43) For all x, T_{i,j, G(j−1) (mmask1,i)⊕G(j−1) (mmask2,i)}{circumflex over ( )}{G(j) (mmask1,i)⊕G(j) (mmask2,i)}=T_{i,j, G(j−1)(mmask1,i)}{circumflex over ( )}{G(j) (mmask1,i)}(x⊕G(j−1)(mmask2,i)⊕G(j) (mmask2,i)

(44) Once all the tables have been re-randomized, the last step of computing rounds based on the randomized network of tables is performed.

(45) With the invention, the input message M is transformed to an input message m for the network of tables and the message m is randomized using mmask1 and mmask2.

(46) Consequently, the input to the network of randomized tables is m⊕mmask1⊕mmask2. At this step, it is important to avoid the computation of mmask1⊕mmask2. One possibility is for example to compute first m⊕mmask1 and next (m⊕mmask1)⊕mmask2.

(47) The proposed implementation does not manipulate the masking value mmask1⊕mmask2 nor the other masking values G(j)(mmask1) ⊕G(j)(mmask2) for the inputs and outputs of tables. It enables to protect against the second order DCA.

(48) When, depending on the network of table, there is a need to recombine several inputs, then it is necessary to add a re-adjustment step between layers. Indeed, the masking value of the output of a Table is not necessarily compliant with the masking value of the input of the next layer. It is thus necessary to add an additional step to re-adjust the masking value with the appropriate masking value. This operation renders the attacks even more difficult.

(49) A generalization of the invention to the order t and the immunity t is given in the following.

(50) Instead of managing 2 values mmask1 and mmask2, t values mmask1, mmask2, . . . , mmaskt are managed. Instead of deriving the shares of masking values using 2 functions, p functions h1, . . . , hp are used. An additional property is thus targeted, i.e. if the attacker succeeds in setting to a constant at most p−1 relevant values during the execution, then all the components mmask1, . . . , mmaskt will however vary. For example, for a DES algorithm: h1=F1(m) h2=F2(m) . . . hp=Fp(m) mmask1=emask1⊕trunc1—96(h1)⊕trunc1—96(h2)⊕ . . . ⊕trunc1-96 (hp) mmask2=emask2⊕trunc97—122 (h1)⊕trunc97—122 (h2)⊕ . . . ⊕trunc97—122 (hp) . . . mmaskt=emaskt⊕trunc1+96(t−1)—96t(h1)⊕trunc1+96(t−1)-96t (h2)⊕ . . . ⊕trunc1+96(t−1)—96t (hp)

(51) where the functions h1, . . . , hp takes as input a 64-bit input message or 96-bit input message for DES and 128-bit input message for AES. It provides output messages of length 96t for DES and 128t for AES.

(52) Once the initial masking values mmask1, . . . , mmaskt are derived using secret obfuscated values, the input message m to the network of tables and the derivation functions F1, . . . , Ft, a random secret function G is used in order to derive all the masking values. As an example, G is implemented using tables.

(53) All the tables of the network are now randomized in t steps in order to target a resistance against tth order analysis.

(54) Firstly the tables of the first layer are randomized using the masking value mmask1 on the input and G(mmask1) on the output. Then the tables of the previous step are re-randomized using the masking value mmask2 on the input and G(mmask2) on the output. Successive similar randomization are performed. Thus in a tth step for the first layer, the tables of the previous step are re-randomized using the masking value mmaskt on the input and G (mmaskt) on the output.

(55) Next, the tables of the second layer are randomized using the masking values on input G(mmask1), . . . , G(mmask) and the masking values on the output of the tables G(G(mmask1)), . . . , G(G(mmask)).

(56) More generally, the tables of the jth layer are randomized by using on input the masking values G(j−1)(mmask1), . . . , G(j−1)(mmask) and on the output G(j)(mmask1), . . . , G(j)(mmask).

(57) Once all the tables have been (re)-randomized, the last step of computing rounds based on the randomized network of tables is performed.

(58) In the above detailed description, reference is made to the accompanying drawings that show, by way of illustration, specific embodiments in which the invention may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the invention. The above detailed description is, therefore, not to be taken in a limiting sense, and the scope of the present invention is defined only by the appended claims, appropriately interpreted, along with the full range of equivalents to which the claims are entitled.