METHOD FOR PROTECTING SUBSTITUTION OPERATION AGAINST SIDE-CHANNEL ANALYSIS

Abstract

A method for executing an operation by a circuit, may include using a first mask set of mask parameters including a same number of occurrences of all possible values of a word of an input data in relation to a size thereof, using an input set including for each mask parameter in the first mask set a data obtained by applying XOR operations to the input data and to the mask parameter and providing an output set including all data resulting from the application of the operation to a data in the input set. The output data may be obtained by applying XOR operations to any of the data in the output set and to a respective second mask parameter in a second mask set including a same number of occurrences of all possible values of the second mask parameters in relation to a size of thereof.

Claims

1. A method for executing by a circuit an operation applied to an input data comprising at least one word, the method comprising: applying the operation to all data in an input set comprising data obtained by applying Exclusive OR (XOR) operations to the input data and to all first mask parameters in a first mask set, each first mask parameter in the first mask set comprising at least one word, the words in the first mask set having a same size and forming a first word subset comprising a single word from each first mask parameter of the first mask set and a same number of occurrences of all possible values of the words; and providing as an output of the operation, an output set comprising all data resulting from the application of the operation to one of the data in the input set, the output data being obtained by applying XOR operations to any one of the data in the output set and to a respective second mask parameter in a second mask set, each second mask parameter in the second mask set comprising at least one word, the words in the second mask set having a same size and forming a second word subset comprising a single word from each second mask parameter of the second mask set and a same number of occurrences of all possible values of the words.

2.-30. (canceled)

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0025] The method and/or device may be better understood with reference to the following drawings and description. Non-limiting and non-exhaustive descriptions are described with the following drawings. In the figures, like referenced signs may refer to like parts throughout the different figures unless otherwise specified.

[0026] FIG. 1 illustrates a conventional architecture of a secure circuit;

[0027] FIG. 2 is a block diagram of a protection circuit according to an example embodiment;

[0028] FIG. 3 is a block diagram of data illustrating a method for protecting data, according to an example embodiment;

[0029] FIG. 4 is a block diagram of data illustrating a method for protecting data, according to another example embodiment;

[0030] FIG. 5 is a flowchart of a method for protecting data, according to an example embodiment;

[0031] FIG. 6 is a block diagram of data illustrating an operation protected according to an example embodiment;

[0032] FIG. 7 is a flowchart of an operation protected according to an example embodiment;

[0033] FIG. 8A is a block diagram of substitution tables, illustrating a method for protecting a substitution table, according to an example embodiment;

[0034] FIG. 8B is a block diagram of substitution tables, illustrating a method for protecting a substitution table, according to another example embodiment;

[0035] FIG. 8C is a block diagram of substitution tables, illustrating a method for protecting a substitution table, according to another example embodiment;

[0036] FIG. 9 is a flowchart of a method for generating a protected substitution table, according to an example embodiment;

[0037] FIG. 10 is a flowchart of a method for generating a protected substitution table, according to another example embodiment;

[0038] FIG. 11 is a flowchart of a substitution operation protected according to an example embodiment;

[0039] FIG. 12 is a block diagram of an AES encryption circuit protected according to an example embodiment;

[0040] FIG. 13 is a block diagram of a conventional mix column operation in AES encryption algorithm,

[0041] FIG. 14 is a block diagram of an AES mix column circuit of a protected AES encryption circuit, according to an example embodiment;

[0042] FIG. 15 is a flowchart of an XOR operation protected according to an example embodiment; and

[0043] FIG. 16 illustrates a protection circuit, according to an example embodiment.

DETAILED DESCRIPTION

[0044] In view of the drawbacks and considerations noted above, it may be desirable to propose a protection for an integrated circuit or a software program against one or more of side-channel analyses. To this purpose, it is known to mask a sensitive data using a random value, by combining the sensitive data with a randomly chosen mask by Exclusive OR (XOR) operations. For example, the following operation:

C=AB,

with A and B representing sensitive data, and representing the XOR operator can be protected using mask values U and V randomly chosen:

A=AU,

B=BV,

C=AB=CUV,

[0045] Therefore the resultant data C is protected as being not directly present in the computing unit performing its computation, but it can be deduced from the masked data C and the mask values U and V, using the following equation:

C=CUV.

[0046] It may also be desirable to propose a protection method which is efficient against two-order known side-channel analyses. For instance, known protection methods having independent operations in a random order and/or dummy operations added which may require a temporal alignment of operations of a data processing to analyze. Such known methods may appear to be efficient against a first order version of the above-described analyses, but not against a second order version of some analyses methods that combines two analyses of distinct parts of a data processing and a correlating results of the two analyses.

[0047] Circuits against side channel analysis may be described in French Patent application no. FR16 51443 filed on Feb. 22, 2016 by Applicant, which discloses a method for analysing traces representative of the activity of a circuit when the latter executes an operation successively on different input data. This method may include extracting a part of each trace, and generating a histogram from each extracted trace part, by counting an occurrence number of each possible value appearing in each of the extracted parts of these traces. Partial results of the operation may then be computed by applying the operation to each input data and each possible value of a part of a secret key involved in the operation. The method may then identify for each possible part value of the secret key, all the input data which provide the same partial result. For each possible part value of the secret key, the occurrence numbers in the histograms, corresponding to the identified input data and the part value of the secret key may then be added. The part of the secret key can be determined by subjecting the added occurrence numbers to a statistical analysis. The statistical analysis may assume that if a value related to the secret key has leaked in the extracted parts of the traces, it can be highlighted by the added occurrence numbers.

[0048] Example embodiments may relate to a method for encrypting or decrypting an input data according to a cryptographic algorithm including a substitution operation.

[0049] Example embodiments may also relate to a circuit including a processor and configured to implement the above-defined methods. The circuit may include one circuit performing a substitution operation, for each masked substitution table. The circuit may include a co-processor.

[0050] Example embodiments may also relate to a device including a circuit as above-defined, arranged on a medium, such as, for example, a plastic card.

[0051] Example embodiments may also relate to a computer program product loadable into a computer memory and including code portions which, when carried out by a computer, configure the computer to carry out the steps of the methods as described herein.

[0052] FIG. 1 illustrates a secure integrated circuit CT, for example, arranged on a portable medium HD such as a plastic card or any other medium, or in a terminal such as a mobile terminal. The integrated circuit CT may include a microprocessor PRC, an input/output circuit IOC, memories M1, M2, M3 coupled to the microprocessor by a data and address bus and, optionally, a cryptographic computation co-processor CP1 or arithmetic accelerator, and/or a random number generator RGN. The memories can include a volatile memory M1, for example of RAM type (Random Access Memory) containing volatile application data, a non-volatile memory M2, for example an EEPROM or Flash memory, containing non-volatile data and application programs, and possibly a read-only memory M3 (or ROM memory) containing the operating system of the microprocessor and constant data. The operating system can be also stored in the non-volatile memory.

[0053] The communication interface circuit 10C may be of contact type, for example according to the ISO/IEC 7816 standard, of contactless type by inductive coupling, for example according to the ISO/IEC 14443 A/B or ISO/IEC 13693 standard, of contactless type by electrical coupling (UHF interface circuit), or of both contact and contactless type. The interface circuit IOC may also be coupled through a specific interface, to another circuit such as an NFC (Near-Field Communications) controller, or a main circuit of a terminal such as a mobile terminal or a connected object.

[0054] In some implementations, the integrated circuit CT may be configured to execute operations of encrypting, decrypting and/or signing messages that may be sent to the integrated circuit CT, using cryptographic functions and/or operations. These cryptographic functions and/or operations can be carried out by the microprocessor PRC of the circuit CT or partially or totally entrusted by the microprocessor PRC to the co-processor CP1.

[0055] Example embodiments as described herein propose protection methods for an operation, e.g., an operation in a cryptographic algorithm against side channel analyses. Accordingly, the operation may receive an input data, and may provide an output data as a function of the value of the input data. In some implementations, a protection according to an example embodiment involves executing the operation to be protected for all the data of an input set of data. Each data in the input set including at least one word, wherein the words in the input set having a same size and forming a word subset or column including a single word from each data in the input set and a same number of occurrences of all the possible words in relation to the size of the words. Thus, the input set may include the input data required to be processed by the operation. The result provided by the operation may be an output set of data, in which each data may include at least one word. The words in the output set may have the same size and may form a word subset or column including a single word from each data in the output set and the same number of occurrences of all the possible words in relation to the size of the words.

[0056] As described herein, word may designate a group of bits in a data, and word column may designate a subset in a data set including a single word from all data in the data set, in which all the words in the word column may have the same size. The words forming a word column may not be necessary aligned, i.e., do not necessary includes the same bit positions in the data of the data set.

[0057] FIG. 2 illustrates a circuit CT1 receiving an input data X to be processed and serially performing several operations OP1, OP2, . . . OPn applied to the input data X. In some implementations, the circuit CT1 may include several circuits OC each serially performing the operations OP1, OP2, . . . OPn. Each circuit OC may receive the input data X and a respective input mask parameter u of an input mask parameter set. Thus, the circuit CT1 may include MX+1 circuits OC respectively receiving masks equal to 0, 1. . . MX, MX representing the greatest possible value of the mask parameter u when considering the size in bits of the mask parameter. Each circuit OC may include a circuit XG applying Exclusive OR operations (XOR) to the input data X and to the mask parameter u (=0 or 1, . . . or MX). In each circuit OC, the data X u (u=0, . . . MX) provided by the circuit XG of the circuit OC may be applied to an input of the operation OP1 of the circuit OC. The operations OP1-OPn are such that:

OPn(. . . OP2(OP1(X u)) . . . )=CX v(u), (1)

where represents the XOR operator, v(u) represents an output mask parameter depending on the input mask parameter u and CX is the result of the operations OP1-OPn applied to the input data X:

CX=OPn( . . . OP2(OP1(X)) . . . ) (2)

[0058] Thus, each circuit OC may provide an output data equal to CX v(u) (u=0, 1, . . . , or MX). Therefore, the circuit CT1 may provide an output set PCX including the output data CX v(0), CX v(1), . . . CX v(u), CX v(MX). The operations OP1-OPn can be adapted such that the output data corresponding to the input data X u provided by the operations OP1-OPn may be equal to CX v(u) for each value of the mask parameter u (0-MX) and the set of output mask parameters v(u) with u=0 to MX, may include a same number of occurrences of all possible values when considering the size of the output masks parameters v(u). Each output mask parameter v(u) can be equal to the corresponding input mask parameter u. In some implementations, the computations of the output data in the output set PCX may be performed in a random order, and/or stored in a random order. In this way, the different values of the mask parameter u may be respectively applied to the circuits OC in a random order. Thus, the circuit OC of rank k in the circuit CT1 may receive an input mask parameter u =U[k], U being a mask set generated by random permutation of all possible numbers between 0 and MX. In a same way, the circuit OC of rank 0 in the circuit CT1 may receive a mask parameter U[0], and the circuit OC of rank MX in the circuit CT1 may receive an input mask parameter U[MX].

[0059] In other implementations, the circuits OC may be independent from each other and the computation of each of the data CX v(u) of the output set PCX may be independent from the computations of the other data of the output set. Therefore the operations OP1-OPn in all the circuits OC can be performed in any order, provided that the order of the operations within each circuit OC is respected.

[0060] Unlike the protections of prior circuits involving hiding the operation to be protected in a flood of identical operations applied to random data, and thus, uncorrelated from the required input data of the operation to be protected, example embodiments herein are to execute the operation on other data not chosen randomly. Indeed, such other data may be correlated with the required input data insofar as the input set formed of such other data and of the required data to be processed is such that each data in the input set may include at least one word. The words in the input set may have the same size and may form a word subset or column including a single word from each data in the input set and a same number of occurrences of all possible values of one word in relation to word size. The words forming a word column may not be necessary aligned, i.e., do not necessary includes the same bit positions in the data of the data set. Since the processed input data are not randomly chosen, statistical analyses cannot extract a signal reflecting the processing of the required input data from a signal including a random part. The different mask parameters could have unpredictable positions in the mask set, but known by the circuit performing the operation.

[0061] In some implementations, if the circuit CT1 performing the operations OP1-OPn undergoes an error such as one caused by a successful fault injection, the value of at least one word of the data in the output set PX is changed. If only one word is changed, each word rank of the data in the output set does not include all possible values of the words, but includes two identical words. The word may have a changed value having necessary the value of another word in the same word rank in the output set. Thus, such a fault injection can be detected by looking for two data in the output set having a same value. If two data are changed, the fault injection would not be detected only when the values of these two data are swapped, which has a very low probability of occurrence. Due to the property of the XOR operation, an error can be easily detected by combining together by XOR operations, all the output data in the output set PCX. The result of this combination may be equal to zero when the output set includes at least one word column including all possible values of the words with a same number of occurrences. In other implementations, in order to detect a fault injection is to add each word in the output set with the corresponding mask parameter by XOR operations. The results of the XOR operations should all be equal to a word of the expected output data of the operation.

[0062] FIG. 3 illustrates an example of the input data X1 which may be combined by an operation XG of the circuits OC with a mask set U including mask parameters U[0. . . MX], MX being an index having the greatest possible value of the input data X1 taking into account the size in bit number of the data X1. The result provided by the operation XG may be an output set PX1, for example arranged in a table, including the data P1[0], P1[1], . . . P1[m], P1[MX], where each data P1[m] may be equal to X1.sup. U[m]. The data in the output set PX1 can be arranged and/or computed in a random order.

[0063] FIG. 4 illustrates an input data X2 including several words X2[0], X2[1], . . . X2[b], . . . X2[BX] in accordance with another example embodiment. In some implementations, each word of the input data X2 may be combined by the operation XG of the circuits OC with a respective mask parameter U[0], . . . U[MX] of the mask set U, where each mask parameters U[0], . . . U[MX] has the size of one word, and the index MX corresponds to the greatest possible value of one word of the input data X2 or of the mask parameters U[m], taking into account the size in bit number of each of these words. The result provided by the operation XG may be an output set PX2, for example arranged in a table PX2[0 . . . MX,0 . . . BX] including data P2[m,b]=X2[b].sup. U[m], where m varies between 0 and MX and b varies between 0 and BX. The data in the output set PX2 can be arranged and/or computed in a random order.

[0064] FIG. 5 illustrates steps (operations, functions, processes, etc.) S1 to S8 of a procedure for generating the input set PX2 from the input data P2 including BX+1 words to be applied to the operation XG of the circuits OC, according to an example embodiment. Steps S1 to S7 may be first successively carried out. At step S1, the input data X2 may be provided to the procedure. At step S2, two permutations U and PM in the form of tables may be generated randomly using a random permutation generation function RNP receiving extremum values 0 and MX for the permutation U and 0 and KX for the permutation PM. The permutation U may include MX+1 values between 0 and MX, where MX+1=2P, P being the number of bits of each of the words X2[b] forming the input data X2. The permutation PM may include (MX+1)(BX+1) values between 0 and the maximum value KX equal to (MX+1)(BX+1)-1. At step S3, an index k may be initialized to zero (0). At step S4, indexes m and b may be computed from the index k by considering that the permutation PM is a two-entry table including rows of BX+1 elements and columns of MX+1 elements. Thus, the index m can be computed as being the integer part INT ( ) of the division of the value PM[k] by (BX+1), and the index b can be computed as being the difference between the value PM[k] and the product of the index m by (BX+1). Step S5 may compute the table elements P2 of the two-entry table PX2. Each table element P2[m,b] at indexes m and b may be set to the result X2[b].sup. U[m] of XOR operations applied to the words X2[b] and U[m]. Due to the use of the random permutation PM, the words P2[m,b] may be computed in a random order and arranged in the table PX2, which may also be in a random order. At step S6, the index k may be incremented by one (1). At step S7, the index k may be compared with the maximum value KX. If the index k is greater than the value KX, step S8 may be carried out, otherwise steps S5 to S7 may again be carried out for a new iteration. At step S8, the input set PX2 may be completely defined and may provide as output of steps S1 to S7.

[0065] in some implementations, the generation and use of the permutation PM can be omitted if the data in the table PX2 can be computed and/or stored in a predetermined order. In addition, the large permutation PM can be replaced by two permutations of MX+1 elements and BX+1, respectively., The elements of which may be read within two nested loops. For example, one for selecting an element of a first one of the two permutations and, one for selection an element of the other one of the two permutations.

[0066] The operations OP1-OPn can include an operation combining the input data X1 to another data by XOR operations.

[0067] FIG. 6 illustrates an example of one operation OPk of the operations OP1-OPn, combining with each other data X3 and X4. The data X3 may result from a previous operation among the operations XG, OP1-OPn, and thus has the form of an output set PX3 (like the output set PX2) including words P3[0,0], . . . P3[MX,BX]. The data X4 may have the same size as the data X3, and thus, may include words X4[0], . . . X4[b], . . . X4[BX]. The result provided by the operation OPk may be an output set PX5, for example arranged in a two-entry table, including the data P5[m,b], where m varies between 0 and MX and b varies between 0 and BX. Thus each output data P5[m,b] may be equal to OPk(P3[m,b], X4[b]). The data in the output set PX5 can be arranged and/or computed in a random order. The operation OPk may be for example an XOR operation.

[0068] FIG. 7 illustrates steps (operations, functions, processes, etc.) S11 to S18 of a procedure for generating the output set PX5 resulting from the application of an operation to the output set PX3 and the data X4, according to an example embodiment. Steps S11 to S17 may be first successively carried out. At step S11, the output set PX3 and the input data X4 including BX+1 words may be input. At step S12, a permutation PM in the form of a table may be randomly generated using the function RNP, the permutation PM including (MX+1)(BX+1) values between 0 and a maximum value KX=(MX+1)(BX+1)-1, where MX+1=2P, P being the number of bits of each of the words X4[b] forming the input data X4. At step S13, an index k may be initialized to zero (0). At step S14, indexes m and b may be computed from the index k by considering that the permutation PM may be a two-entry table including rows of BX+1 elements and columns of MX+1 elements. Thus, the index m can be computed as being the integer part of the division of the value PM[k] by (BX+1), and the index b can be computed as being the difference between the value PM[k] and the product of the index m by (BX+1). Step S15 may compute output data P5[m,b] of the output set PX5 in the form of a two-entry table. Each output data P5[m,b] at indexes m and b may be set to the result OPk(P3[m,b],X4[b]) of the operation OPk applied to the words P3[m,b] and X4[b]. Due to the use of the permutation PM, the output data P5[m,b] in the table PX5 may be computed in a random order and arranged in the table PX5 also in a random order. At step S16, the index k may be incremented by one (1). At step S17, the index k may be compared with the maximum value KX. If the index k is greater than the value KX, step S18 may be carried out; otherwise steps S15 to S17 may again be carried out for a new iteration. At step S18, the output set PX5 may be completely defined and may provide as output for steps S11 to S17.

[0069] In the example implementation of step S15 in FIG. 7, the operation OPk may be an XOR operation. Thus, the output data P5[m,b] in the output set PX5 may be equal to P3[m,b], .sup. X4[b], for each indexes m (=0 . . . MX), and for each index b (=0 . . . BX). It can be observed that each data P5[m] (of size BX+1) in the output set PX5 may be the result of the operation P3[m].sup. X4 where P3[m]=X1.sup. U[m]. If CX1=X1 .sup.X4, then P5[m]=X1 .sup.X4.sup.U[m]=CX1.sup.U[m]. Therefore, the mask U[m] applied to the input value X1 can be retained throughout the computations performed by the operations OPi in the circuits OC. The operation OPk can be any other operation than XOR, provided that this operation is performed bitwise and is reversible or bijective.

[0070] In some implementations, it is not necessary to compute the data in the table PX5 in a random order or to store the data in a random order. In such cases, the use of the permutation PM may not be mandatory.

[0071] It may be further desirable to have among the operations OPi a substitution operation using a substitution or lookup table. Such a substitution operation may receive an input data, and may provide an output data read in the table using the input data as an index. According to an example embodiment, a masked substitution table SBM may be computed using the following equation:

SBM[i U]=SB[i] V, (3)

where SB is the substitution or lookup table, i is an index for selecting a value SB[i] in the substitution table SB and U and V are input and output masks respectively.

[0072] FIG. 8A illustrates the substitution table SB and the masked substitution table SBM derived from the substitution table SB by applying equation (2) to each value SB[i] in the substitution table SB. Thus, the result of the substitution operation applied to a masked input data D U may be an output data masked by the known output mask V.

[0073] As illustrated in FIG. 8B, the masked substitution table SBM can also be obtained by applying the following equation:

SBM[i]=SB[i U]V, (4)

to each value SB[i] of the substitution table SB.

[0074] Therefore, the expected output data CX1 can be deduced from the output data provided by the circuit OC processing the masked input data X.sup. U. However the output data CX1 cannot be deduced from the output data provided by the other circuits OC since in these other circuits, the input data applied to the substitution operation may not be combined with the mask parameter U used to generate the mask substitution table SBM according to equation (3) or (4).

[0075] According to an example embodiment, a masked substitution table SBM[u] may be computed for each circuit OC, such that:

SBM[u,D u]=SB[D]v(u), (5)

for each value of the mask parameter u (0 . . . n), where v(u) is a mask parameter corresponding to the value of the mask parameter u, such that v(u1)v(u2) for all mask parameters u1, u2 with u1u2. Therefore, each output data of the substitution operation performed by the circuits OC may be equal to the output data CX masked by the mask parameter v(u) (=CX v(u)).

[0076] FIG. 8C illustrates the substitution table SB and the masked substitution table SBM according to an example embodiment. The substitution table SB may be a single-entry table including MX+1 values SB[0], SB[1], . . . SB[MX]. The masked substitution table SBM may be a two-entry table including one single-entry table SBM[u] of the size of the substitution table SB for each mask value u. Thus, the masked substitution table SBM may include MX+1 single-entry tables of the size of the substitution table SB.

[0077] FIG. 9 illustrates steps (operations, functions, processes, etc.) S21 to S30 of a procedure for computing a masked substitution table SBM from the substitution table SB, according to an example embodiment. Steps S21 to S27 may be first successively carried out. At step S21, the substitution table SB may be input. At step S22, two permutations U and V in the form of tables may be randomly generated using the function RNP. The permutations U and V include MX+1 values between 0 and MX, where MX+1 may be the amount of values in the table SB. At steps S23 and S24, respectively, indexes i and j may be initialized to zero (0). Step S25 may compute the table values SBM[i,j] of the two-entry table SBM. Each table value SBM[i,j] at indexes i and j may be set to the result SB[j.sup.U[i]].sup.V[i] of XOR operations applied to the data SB[j.sup.U[i]] and V[i]. At step S26, the index j may be incremented by one (1). At step S27, the index j may be compared with the maximum value MX. If the indexj is greater than the value MX, step S28 may be carried out; otherwise steps S25 to S27 may again be carried out for a new iteration. At step S28, the index i may be incremented by one (1). At step S29, the index i may be compared with the maximum value MX. If the index i is greater than the value MX, step S30 may be carried out; otherwise steps S24 to S27 may again be carried out for a new iteration. At step S30, the masked substitution table SBM may be completely defined and may be provided as output of steps S21 to S29. Thus, each column i of the masked substitution table SBM may correspond to the substitution table SB masked using a particular couple of masks (U[i], V[i]).

[0078] FIG. 10 illustrates (operations, functions, processes, etc.) steps S31 to S38 of a procedure for computing the masked substitution table SBM from the substitution table SB, according to an example embodiment. Steps S31 to S37 may be first successively carried out. At step S31, the substitution table SB may be input. At step S32, three permutations U, V and PM in the form of tables may be randomly generated using the function RNP. The permutations U and V may include MX+1 values between 0 and MX, where MX+1 may be the amount of values in the table SB. The permutation PM may include (MX+1)(MX+1) values between 0 and a maximum value KX equal to (MX+1)(MX+1)-1. At step S33, an index k may be initialized to zero (0). At step S34, indexes i and j may be computed from the index k by considering that the permutation PM may be a two-entry table including rows of MX+1 elements and columns of MX+1 elements. Thus, the index i can be computed as being an integer part of a division of the value PM[k] by (MX+1), and the indexj can be computed as being a difference between the value PM[k] and a product of the index i by (MX+1). Step S35 may compute the table values SBM[i,j] randomly selected in the masked substitution table SBM, using the random permutation PM. Each value SBM[i,j] at indexes i and j in the masked substitution table SBM may be set to the result SB[[j.sup.U[i]].sup.V[i] of an XOR operation applied to the data SB[j.sup.U[i]] and V[i]. The mask parameters U[i] and V[i] may be also randomly selected in the tables U and V since the indexes i and j are defined using the permutation PM. At step S36, the index k may be incremented by one (1). At step S37, the index k may be compared with the maximum value KX. If the index k is greater than the value KX, step S38 may be carried out; otherwise steps S35 to S37 may again be carried out for a new iteration. At step S38, the masked substitution table SBM may be completely defined and may be provided as output of steps S31 to S37.

[0079] In some implementations, in a process including the procedures of FIG. 5 and 9 or 10, a single permutation U may be generated and used at steps S5 and S25 or S35.

[0080] FIG. 11 illustrates steps (operations, functions, processes, etc.) S41 to S48 of a procedure performing a protected substitution operation, using the masked substitution table SBM, according to an example embodiment. Steps S41 to S47 may be first successively carried out. At step S41, the masked substitution table SBM and a protected data in the form of an input set PX6 may be input. The input set PX6 may include words P6[0,0], . . . P6[MX,BX]. At step S42, one permutation PM in the form of a table may be randomly generated using the function RNP. The permutation PM may include (MX+1)(BX+1) values between 0 and the maximum value KX equal to (MX+1)(BX+1)-1. At step S43, an index k may be initialized to zero (0). At step S44, indexes m and b may be computed as in step S4. Step S45 may compute the output data P7[m,b] randomly selected in the output set PX7, using the random permutation PM. Each output data P7[m,b] at indexes m and b may be set to the value of the element SBM[m,P6[m,b]] selected in the table SBM[m] at an index defined by the output data P6[m,b] selected in the table PX6 at indexes m and b. At step S46, the index k may be incremented by one (1). At step S47, the index k may be compared with the maximum value KX. If the index k is greater than the value KX, step S48 may be carried out; otherwise steps S44 to S47 may again be carried out for a new iteration. At step S48, the output set PX7 may be completely defined and may be provided as output of steps S41 to S47.

[0081] In some implementations, the number of the possible masked substitution tables SBM obtained from a same substitution table SB, is reduced by choosing identical tables for the mask tables U and V. Thus the equations (3) and (4) become:

SBM[DU]=SB[D]U, (6)

and

SBM[D]=SB[DU]U, (7)

[0082] The operations performed at steps S25 and S35 become:

SBM[i,j]=SB[jU[i]]U[i](8)

[0083] Accordingly, the number of possible masked substitution tables may be reduced by a factor (MX+1), which may enable all the possible masked tables to be precomputed and stored in a memory, instead of being computed and stored each time new mask tables U and V are generated.

[0084] In some implementations, the generation of a random permutation may have a non-negligible cost in terms of amount of required computation operations. For example, the generation of one of the permutations U and V at steps S22, S32 may be avoided by computing the values of the mask table V as a function of the values of the mask U, or inversely. For example, each value V[m] of the mask table V may be chosen equal to U[m].sup.K, K being a constant parameter which may be randomly chosen when the mask table U is generated. In other implementations, each value V[m] may be chosen equal to U[m.sup.K1].sup.K2, K1, K2 being constant parameters which may be randomly chosen when the mask table U is generated. The mask table V can also be randomly generated and the mask table U determined in a same way as a function of the values in the table V.

[0085] In some implementations, the number of different values in the substitution table SB can be smaller than its number of values. Thus, each value in the table SB may have a same number of occurrences greater than one. In such a case, the mask table V may be generated so as to include the same number of occurrences of the same values in the table SB.

[0086] All the operations performed in AES (Advanced Encryption Standard) algorithm either implemented by software or in hardware can be protected using the procedures previously disclosed. For example, the architecture presented in FIG. 2 can be applied to AES algorithm.

[0087] FIG. 12 illustrates a cryptographic calculation circuit OC1 as an example of the circuit OC of FIG. 2. The OC1 may implement the AES algorithm for encrypting a data. For further details about AES algorithm, the document Advanced Encryption Standard FIPS PUB 197 published on 26th Nov. 2001 can be referred to. The cryptographic calculation circuit OC1 may be included in a circuit CT2 including several cryptographic calculation circuits OC1. Each cryptographic calculation circuits OC1 may receive a data X1 to be processed and a mask parameter index m, and may supply a resultant data CX1 combined by XOR operations with a mask parameter V[m] corresponding to the mask parameter index m.

[0088] The circuit OC1 may include circuits XG1, XG2, XG3 performing XOR operations, a substitute calculation circuit SBB, a row-based circular permutation calculation circuit SHR, a multiplexer MUX, and a column-based permutation calculation circuit MXC. The circuits SBB, SHR, and MXC may be compliant with the AES. The circuit XG1 may receive both the data X1 to be encrypted and a derived key KT[0] at an index 0 in a round key table KT supplied to the circuit OC1. The output of the circuit XG1 may be processed by the circuits SBB and SHR. The output of the circuit SHR may be transmitted by the multiplexer MUX to the circuit MXC at rounds 0 to R-1 of the AES algorithm, and at a last round R, to the circuit XG3 receiving at another input a last derived key KT[R] at an index R in the round key table KT. At the rounds 0 to R-1, the output of the circuit MXC may be processed by the circuit XG2 receiving a derived key KT[r] (r=1, . . . , R-1) read in the table KT. The output of the circuit XG2 may be processed by the circuits SBB and SHR. When a certain number (R- 1 ) of calculation rounds are performed (10, 12 or 14, in accordance with AES algorithm) by the chain including the circuits SBB, SHR, MXC, XG2, the multiplexer MUX may be actuated to provide the output of the circuit SHR to the input of the circuit XG3 which may provide the output data CX1.

[0089] During a first calculation round, the data X1 may be processed by the circuit XG1 which may be added to the first derived key KT[0] by XOR operations. The circuit XG1 may provide the resulting data X1.sup.K[0] which may be successively processed by the circuits SBB, SHR, MXC and XG2. Then the circuit XG2 may combine the data provided by the circuit MXC with a derived key KT[r] (r=1, . . . , R-1). The circuits SBB, SHR, MXC and XG2 may be successively activated for several rounds of the AES algorithm. The circuits SBB, SHR and XG3 may be activated at a last round R of the AES algorithm. At each round j, a round key KT[r] (r=0, . . . , R) may be read in the table KT.

[0090] The substitute calculation circuit SBB may be generally implemented using a substitution table receiving an input data used as an index to select an output data in the substitution table. The substitution table may include 256 bytes, and each byte of the data to be processed by the circuit SBB may be used as an index to select a byte in the substitution table SB. The permutation calculation circuit SHR can be placed before the substitute calculation circuit SBB.

[0091] According to an example embodiment, the circuit OC1 may include circuits XG4 and XG5 performing XOR operations with mask parameters U[m] and U[m].sup. V[m] respectively (with m=0, . . . MX). The circuit XG4 may receive the mask table U[0. . . MX] including MX+1 mask parameters having the size of one word (e.g. one byte), and the input data X1[0. . . BX] of BX+1 words (16 bytes, BX=15) of the size of the mask parameters, and may perform XOR operations with the mask parameters U[m] for each word of the size of the mask parameter included in the input data X1. The circuit XG4 may provide to the circuit XG1 a masked input data, noted X1.sup. U[m] for each value of the index m. Thus, the circuit XG4 can implement the steps S1 to S8 of FIG. 5, XOR operations being performed for each mask parameter U[m] in the mask table U[0. . . MX], a randomly selected permutation of 256 values between 0 and 255. The result provided by the circuit XG4 to the circuit XG1 may be the output set PX10 having the form of the output set PX2[0. . . MX, 0 . . . BX] (FIGS. 4, 5). The operation performed by the circuits XG1, XG2 and XG3 may be realized according to FIG. 6, by executing the steps S11 to S18 (FIG. 7). The input set of the circuit XG1 may be the output set PX10 provided by the circuit XG4, and may have the form of the input set PX3 in FIG. 7. The input data X4 in FIG. 7 may be the round key KT[0,0 . . . BX] for the circuit XG1, the round key KT[r,0 . . . BX] (r=1, . . . R-1) for the circuit XG2, and the round key KT[R,0 . . . BX] for the circuit XG3, each round key in the table KT including BX+1 bytes. The circuit XG1 may provide an output set PX20[0 . . . MX,0 . . . BX] having the form of the output set PX5[0 . . . MX,0 . . . BX] (FIG. 7).

[0092] The substitution table SB provided to the circuit SBB may be the two-entry table SBM[0 . . . MX,0 . . . MX] generated by executing the steps of FIG. 9 or 10, and obtained with the masks tables U and V. The mask table U may be the same as the one input to the circuit XG4. The operation performed by the circuit SBB may include the steps S41 to S48 as disclosed in FIG. 11, in which the input set PX6 may be the output set PX20 provided by the circuit XG1. The circuit SBB may provide an output set PX3j (PX30 for the round 0) in the form of the output set PX7[0 . . . MX,0 . . . BX] (FIG. 11).

[0093] The circuit SHR may be designed to process separately each data PX3j[m, 0 . . . BX] (m=0, . . . MX) in the output set PX3j. The circuit SHR may provide an output set PX4j[0 . . . MX,0 . . . BX] including a table PX4j[m,0 . . . BX] for each value (0 to MX) of the index m. The circuit MXC may provide an output set PX5j[0 . . . MX,0 . . . BX].

[0094] FIG. 13 illustrates the circuit MXC accordance to an example embodiment. The circuit MXC may combine an output data X6 of the circuit SHR with a coefficient matrix MC of 44 elements. To this purpose, the output data X6 may be organized into a matrix format of 44 elements x0 to x15. Each of the elements of the matrix X6 corresponding to the bytes of the data X6 which may be encoded on 128 bits. The elements of the matrix X6 may be combined together by XOR operation circuit XG6 with the elements of the matrix MC to produce a resultant matrix TR of 44 elements where each element has the following form:

a.Math.x<i>b.Math.x<i+1>c.Math.x<i+2>d.Math.x<i+3 >, (9)

where a, b, c, d (=1, 2 or 3) are the elements of one line of the matrix MC and i is equal to 0, 4, 8 and 12. In accordance to AES algorithm, the operation 2.Math.x may be performed by using the operation LS1(x) if x is lower than 128 (when the most significant bit (MSB) of x equals 0) and the operation LS1(x) 0 x1B if x is greater or equal to 128 (when the MSB of x equals 1), LS1(x) representing a shift to the left by one bit in the byte x. The operation 3.Math.x is performed using the operation 2.Math.x x.

[0095] Since each byte b of the input data X6 is represented by one table PX4j[0 . . . MX,b], the circuit MXC may perform 316 XOR operations for each byte in the output set PX4j. One more XOR operations may be necessary to perform the operation 3.Math.x. In some implementations, the operations 2.Math.x and 3.Math.x may be implemented by lookup tables.

[0096] As illustrated in FIG. 14, the XOR operations for computing an element of the matrix TR as disclosed in FIG. 13 is performed within each table PX4j[m], and these operations provides a table PX5j[m] for each table PX4j[m].

[0097] In addition, the order of the operations should be examined when performing the operations of the circuit MXC to keep the masks on the data, since each byte x<j> is masked by a same mask v (=V[m], x<j>=x<j> v). The operations of the equation (9) are performed by applying the following property:

a(xv)=axav, with a=2 or 3. (10)

[0098] Thus:

[00001]$\begin{array}{cc}\begin{array}{c}A=.Math.2.Math.x.Math.03.Math.x.Math.12.Math.v3.Math.v{x}^{}.Math.2x^{}.Math.3\\ =.Math.2.Math.x.Math.03.Math.x.Math.12.Math.v2.Math.vv{x}^{}.Math.2x^{}.Math.3\\ =.Math.2.Math.x.Math.03.Math.x.Math.1vx.Math.2v{x}^{}.Math.3\\ =.Math.2.Math.x.Math.03.Math.x.Math.1x.Math.2x^{}.Math.3\end{array}& \left(11\right)\end{array}$

[0099] Therefore, at this step of the computations, the mask v is removed, which can form a leakage exploitable by a side-channel analysis to determine the data x, even if the mask v reappears when the last XOR operation is performed:

A=(2x<0>3x<1>x<2>x<3>)v. (12)

[0100] In contrast, if the computation of element A is performed in the following order:

A=2x<0>x<2>x<3>3x<1>, (13)

we obtain:

[00002]$\begin{array}{cc}\begin{array}{c}A=.Math.2.Math.x.Math.0x.Math.2x^{}.Math.33.Math.x^{}.Math.12.Math.vv\\ =.Math.2.Math.x.Math.0x.Math.2x.Math.33.Math.x^{}.Math.13.Math.vv\\ =.Math.2.Math.x.Math.0x.Math.2x.Math.33.Math.x^{}.Math.12.Math.vvv\\ =.Math.2.Math.x.Math.0x.Math.2x.Math.33.Math.x.Math.12.Math.v3.Math.v\\ =.Math.2.Math.x.Math.0x.Math.2x.Math.33.Math.x.Math.1v.\end{array}& \left(14\right)\end{array}$

[0101] Therefore, when performing the XOR operations in the order of the coefficients a, b, c, d, may be equal to (2 1 1 3), respectively, the result of each XOR operation may be always masked. The orders (1 2 1 3), (3 1 1 2) and (1 3 1 2) may also maintain the masking after each XOR operation. In some implementations, the mask v applied to the input data may be kept in the output data of the operation performed by the circuit MXC.

[0102] In FIG. 12, the circuit XG2 may provide an output set PX6j[0 . . . MX,0 . . . BX] having the form of the output set PX5[0 . . . MX,0 . . . BX] (FIG. 7). The circuit XG5 may be connected in series and may be interposed between circuits XG2 and SBB. The circuit XG5 may receive the output set PX6j from the circuit XG2 and at another input the mask table W=U V resulting from the combination of the tables U and V by XOR operations. Thus, each value W[m] in the table W may be equal to the XOR sum U[m] V[m] of the values U[m] and V[m] selected at index m in the mask tables U and V. The table W can be computed as soon as the masks tables U and V are generated. By a suitable choice of the permutations U and V, each word column of the table W can include a same number of occurrences of all possible values of a word having the size of the words of the masks parameters U[m] and V[m].

[0103] According to an example embodiment, one or several pairs (U0, V0) of mask tables U0 and V0 may be stored in the circuit CT1, Each pair (U0, V0) may be tested as providing a table W including mask parameters W[m]=U0[m] V0[m]) and at least one word column including the same number of occurrences of all possible values of the words. The circuit CT1 may be configured to derive pairs of mask tables (U2, V2) as follows:

U2[m]=PM(U1[m]UR) V2[m]=PM(V1[m]VR), for each index m, (15)

or

U2[m]=PM(U1[m])UR V2[m]=PM(V1[m])VR, for each index m, (16)

where UR and VR are random words of the size of any of the masks parameters U[m] or V[m], U1 and V1 are previously computed tables obtained by the equations (15) or (16), or equal to U0 and V0 respectively, and PM is a randomly selected permutation applied to the elements of the tables U1 and V1. It can be proved that each pair (U2, V2) computed using the equation (15) or (16) has a property of providing a table W including a word column including the same number of occurrences of all possible values of the words.

[0104] The circuit XG5 may provide an output set PX2j to the circuit SBB. The circuit XG5 can implement steps S51 to S58 illustrated in FIG. 15. The steps S51 to S58 may perform application of a mask table W[0 . . . MX] to an input set PX8[0 . . . MX,0 . . . BX], according to an example embodiment. Steps S51 to S57 may first be successively carried out. At step S51, the mask table W and a protected data having the form of the input set PX8 may be input. The input set PX8 may include words P8[0,0], . . . P8[MX,BX] and the mask table may include masks parameters W[0], . . . W[MX]. At step S52, a permutation PM in the form of a table may be randomly generated using the function RNP, the permutation PM including (MX+1)(BX+1) values between 0 and a maximum value KX=(MX+1)(BX+1)-1, where MX+1 is the number of values in the table PX8 and MX is the greatest value in this table. At step S53, an index k may be initialized to zero (0). At step S54, indexes m and b may be computed as in step S4. Step S55 may compute the output word P9[m,b] at indexes m and b in the output set PX9 by combining XOR operations the input word P8[m,b] at indexes m and b randomly selected in the input set PX8 with the mask parameter W[m] at index m randomly selected in the mask table W, using the random permutation PM (P9[m,b]=P8[m,b].sup.W[m]). At step S56, the index k may be incremented by one (1). At step S57, the index k may be compared with the maximum value KX. If the index k is greater than the value KX, step S58 may be carried out; otherwise steps S54 to S57 may be again carried out for a new iteration. At step S58, the output set PX9 may be completely defined and may be provided as output of steps S51 to S57.

[0105] Therefore, the output set PX2j provided by the circuit XG5 may include words P9[m,b] masked with the mask parameters W[m]=U[m].sup.V[m] (m=0, . . . MX). Since the data in the output set PX6j are already masked with the masks parameters V[m] applied by the circuit SBB, these masks may be removed by the circuit XG5. Thus, the data set PX2j may include data only masked by the mask parameters U[m], and thus, the data set PX2j may be ready to be further processed by the circuit SBB.

[0106] At a last round R, the circuit SBB may provide an output set PX3R[0 . . . MX,0 . . . BX] in which each element PX3R[m,b] may be masked by a mask V[m] of the mask table V. The circuit XG3 may apply the round key KT[R,0 . . . BX] to the output set PX4R according to the procedure of FIG. 7, and may provide an output set PX7R[0 . . . MX,0 . . . BX] in the form of a two-entry table in which each element at indexes m and b may be equal to CX1[b].sup. V[m] and may correspond to an input data X1[b].sup. U[m] at the output of the circuit XG4. Therefore, the output data CX1[0 . . . BX] processed by each of the circuits OC1 can be deduced from each row m (=0, . . . MX) in the output set PX7R by applying the mask V[m] to the data PX7R[m, 0 . . . BX].

[0107] In some implementations, all the data processed by the processing chain including the circuits SBB, SHR, MXC, XG2, XG5 and XG3, may always be masked by either the parameter U or the parameter V. Thus, this processing chain forms a protected area in the circuit OC1. The circuit OC1 can be implemented by software with the same level of protection, since this protection depends on masking operations which can be implemented by either hardware or software without a reduction of the protection level. The circuit OC1 can be implemented either by software executed by the processor PRC or the co-processor CP1, or by hardware for example implemented in the co-processor CP1.

[0108] In some implementations, the circuit XG3 can be configured to output only the output data CX1.

[0109] In some implementations, the masks parameters U[m] can be added to the round key KT[0] instead of the input data X1. The mask parameters W[m] could also be added to the round keys KT[1] to KT[R-1], and the mask parameters V[m] could also be added to the round key KT[R]. Thus, a transformed round key table resulting from the above computations can be precomputed from the table KT, and the circuits XG4 and XG5 can be removed from the circuit OC1. Therefore, the protection method can be implemented in a circuit performing AES encryption or decryption without having to modify the circuit.

[0110] In some implementations, the circuit XG5 can be omitted, and a new masked substitution table SBM generated at each round according to the procedure of FIG. 10, using the mask table V as an input mask table U. Accordingly, only another output mask table V and a new permutation PM should be generated at step S32.

[0111] As an alternative of generating a permutation PM at each of the steps S12, S32, S42 and S52 in the circuit OC1, the permutation PM can be generated only once at each round performed by the circuit OC1, or only once in step S2 for the first round and at step S12 or S32 for the last round. Also in one or several of the steps S2, S12, S32, S42 and S52, the generation of the permutation PM can be replaced by the generation of two permutations, one being used for the index m or i, and the other for the index b or j.

[0112] The decryption operation according to AES algorithm includes substantially the same operations as the encryption operation. Therefore, the previously described method for protecting a sequence of operations can be applied to protect a program or a circuit implementing the AES decryption operation. More particularly, an AES decryption circuit includes circuits performing XOR operations with keys derived from the secret key SK, an inverse substitute calculation circuit, an inverse row-based circular permutation calculation circuit, an inverse column-based permutation calculation circuit, and/or the same key round table KT. The method previously disclosed can be applied to each operation performed by the decryption operation. The inverse column-based permutation calculation circuit also computes data having the following form:

ax<i>.sup.bx<i+1>.sup.cx<i+2>.sup.dx<i+3>,

[0113] where the group of coefficients (a, b, c, d) is equal to permutations of (9, 11, 13, 14). These coefficients allow the XOR operations to be computed in any order without removing the mask, and the resulting data keeps the same mask as the input data.

[0114] In some implementations, several words may be computed at a same time in a hardware architecture including wider buses than the size of the data to be processed by the operation, such as 32-bit or 64-bit since XOR operations are bitwise. In a 32-bit architecture, four bytes of the output data can be computed at the same time, and in a 64-bit architecture, eight bytes can be computed at the same time. Thus, in FIGS. 5, 7, 11 and 15, several iterations of a loop based on the index b can be grouped by processing several words in a same iteration. For example, in FIG. 5, several or all of the computations at step S5 for b=0 to BX can be performed in a single operation by concatenating the mask value U[m] with itself several times to form a word of the size of the data P2[m,0 . . . BX], as follows:

P2[m,0 . . . BX]=X2[0 . . . BX].sup.U[m]//U[m]//.. . . //U[m], (17)

[0115] // representing the concatenation operator of binary words.

[0116] In a same way, the computations performed at step S55 in FIG. 15 can be performed as follows:

P9[m,0 . . . BX]=P8[m, 0 . . . BX].sup.U[m]//U[m]//. . . //U[m], (18)

[0117] In some implementations, if the circuit CT2 performing the AES operations undergoes an error such as one caused by a successful fault injection, the value of at least one word in the output set PX6R[0 . . . MX] may be changed. If only one word is changed, a word column m of the output set no longer may include all possible values of an output word and may include two identical words. The changed word may have necessarily the value of another word in the output set. Thus, such a fault injection can be detected by looking for two words in a column m of the output set having a same value. If two words are changed in a same column of the output, the fault injection would not be detected only when the values of these two words are swapped, which has a very low probability of occurrence. Using to the property of the XOR operation, an error can be easily detected by combining together by XOR operations all the words in each column m of the output set. The result of this combination may be equal to zero when the column m of the output set includes all possible values of an output word with a same number of occurrences.

[0118] It is noted that the protection method previously disclosed may be applied only to some operations performed in the AES algorithm which would be detected as vulnerable to side channel analyses. For example, the protection method previously disclosed can be applied only to the first and last rounds of the AES algorithm, from which sensitive data could leak, or only to the substitution operations.

[0119] More generally, the protection method previously disclosed can be applied to other encryption algorithms, implemented either by software or in hardware, and including XOR operations combining sensitive data, such as ARIA. ARIA algorithm may process 128-bit data divided in 16 bytes and may be performed by round. Each round may include a round key addition by XOR operations, a substitution step using two precomputed substitution tables and their inverses and a diffusion step. The substitution step processes byte per byte the input data combined with the round key, and the diffusion step may apply 16 different XOR combinations to the 16 bytes of the data provided by the substitution step. In each of these combinations, seven bytes of the data are added by XOR operations.

[0120] FIG. 16 illustrates an integrated circuit CT3 arranged on a portable medium HD such as, for example, a plastic card, and implementing one of the protection methods previously described, according to an example embodiment. The integrated circuit CT3 may include the same units as the integrated circuit CT described above in connection with FIG. 1, and differs from the latter in that the co-processor CP1 is replaced with a co-processor CP2 implementing one and/or the other protection methods described above, for example in the form of the circuit CT1 or CT2. Therefore, according to an example embodiment, the co-processor CP2 may be configured to provide output set of resulting data, rather than a single data of a cryptographic operation. Each output set may include the expected result of the cryptographic operation, wherein the output set may be such that all data in the output set have a same number of occurrences. The processor PRC can be configured to have access to the mask table V. Thus, the processor PRC can deduce the output data from the output set by combining any one of the data in the output set by one mask parameter in the mask table V. The selected data may have a same rank in the output set as the mask parameter selected in the mask table V.

[0121] The co-processor CP2 may also be configured to execute a part of the cryptographic operation. In this case, the processor PRC may be configured to produce output tables of resulting data including the result of the cryptographic operation. Each output table may be such that all data in it have a same number of occurrences.

[0122] The methods disclosed herein may also be implemented by software programs executable by a computer system. Further, implementations may include distributed processing and parallel processing, especially for processing in parallel several or all data in the input data sets and/or for providing in parallel several or all data in the output data sets.

[0123] The illustrations described herein are intended to provide a general understanding of the structure of various embodiments. These illustrations are not intended to serve as a complete description of all of the elements and features of apparatus, processors and systems that utilizes the structures or methods described therein. Many other embodiments or combinations thereof may be apparent to those of ordinary skills in the art upon reviewing the disclosure by combining the disclosed embodiments. Other embodiments may be utilized and derived from the disclosure, such that structural and logical substitutions and changes may be made without departing from the scope of the disclosure.

[0124] Further, the disclosure and the illustrations are to be considered as illustrative rather than restrictive, and the appended claims are intended to cover all such modifications, enhancements and other embodiments, which fall within the true spirit and scope of the description. Thus, the scope of the following claims is to be determined by the broadest permissible interpretation of the claims and their equivalents, and shall not be restricted or limited by the foregoing description.