Automatic insertion of masking into an algorithm

AUTOMATIC INSERTION OF MASKING INTO AN ALGORITHM

The present invention has application in the field of cryptography, and in particular relates to a method for protecting an implementation of an algorithm against side-channel attacks.

Existing encryption algorithms that involve encrypting sensitive data provide effective robustness against cryptanalysis and content recovery attacks. Since the attacker has only knowledge of the input and output of the encryption algorithm, these techniques are referred to as "black box techniques". Most encryption algorithms are standardized, and one of the most popular known and used is the Advanced Encryption Standard (AES). The confidentiality of encryption is based on a shared secret encryption key. The best option for an attacker to ignore the secret key is to try all possible combinations (brute force decoding). If the key is 128 or 256 bits long, the number of iterations required makes brute force decoding very computationally difficult to manage.

However, some attacks, called Side-Channel Attacks (SCAs), are executed in cryptographic algorithms based on information leaking from the physical implementation of the cryptographic algorithm, such as timing information, power consumption, electromagnetic leaks, etc. It gives attackers an opportunity to retrieve secret information.

Therefore, first of all, there is a need to provide a method for protecting the implementation of an algorithm that is sensitive to such attacks.

Any algorithm can be represented as a graph of operations, or a call graph, which is a directed graph in which each node is a function and each edge is an intermediate variable (also called an inner variable). . This call graph may also be referred to as a data flow graph or a control flow graph.

A function may be a single operation, or it may be a combination of linear or non-linear operations. It is a straight piece of code with no jumps. When a function contains multiple operands, it can be decomposed into multiple unary or binary operands.

A typical operation is one that can be implemented in a given technology. For example, a software program can compute arithmetic and logical operations such as addition ('+') or exclusive boolean OR ('XOR'). A Digital Signal Processor (DSP) or field programmable gate array (FPGA) is implemented in a look-up-table (LUT) or arithmetic operation using a multiply-accumulate (MAC) unit. Any function can be calculated. An Application Specific Integrated Circuit (ASIC) can calculate any type of operation by utilizing a standard cell library.

A function can be expressed in a high-level language, but can also be mapped as a set of operations. It is the compiler's job to translate these functions, potentially described in a high-level language, into a machine language that optimizes processing time and resource consumption.

The graph representing the algorithm is a directed graph: each node or function has as many entering edges as the input argument and as many outgoing edges as the output result. For example, if a function is a simple binary operation (with two arguments and one result), it has two inputs and one output.

Edges pass typed variables that are passed from node to node. The type can be a byte, a 32-bit word, and so on.

Considering a sensitive algorithm, such as a cryptographic algorithm, described as a call graph, and transforming the algorithm to protect the cryptographic algorithm against side-channel attacks, regardless of the type of algorithm or any consideration regarding the implementation of the cryptographic algorithm. It is an object of the present invention.

In order to increase the robustness of the algorithm against side-channel attacks, it is known to mask important data of the algorithm. One example of masking is based on secret sharing, which divides the initial variable into a plurality of new variables such that the sum of the new variables yields the initial variable. The sum must be understood according to the underlying type of the variable. For example, if the variable is one byte, the sum may be bitwise XOR or addition modulo 256 addition.

If the operation affecting the masked data is a linear function, the value of the masked output of the function may be calculated from the masked input. However, if the function is non-linear (eg, a power function, a substitution box of a cryptographic algorithm, ...), the mask calculation may not be possible. The mask must be removed from the function's input, and a new mask must be inserted at the function's output.

Various masking techniques are known, some of which have been proven. They apply to linear programs, which are linear call graphs. Masking is a chaining operation with random reshare (or refresh) of the mask between operations, whenever appropriate. However, if the graph is not straight, some vulnerabilities may appear.

In Provably secure higher-order masking of AES by M. Rivain and E. Proof in CHES 2010, pages 413-427, a fully masked AES algorithm is presented. In this paper, the masking of specific linear and nonlinear functions is described, and the functions are chained to describe the complete AES algorithm. However, JE of FSE 2013 pages 11-13. Even with an approach specifically dedicated to the AES algorithm, some implementation problems may arise, as shown in High-Order Side Channel Security and Mask Refreshing by Coron, E. Proof, M. Rivain, and T. Roche. These implementation problems arise from the reuse of some variables, and therefore the achieved level of security is reduced.

Thus, today, most masking implementations are performed manually, which is prone to implementation errors (eg, sensitive variables are not masked). Only a few studies consider automatic masking.

Among these studies is the article Compiler assisted masking, Cryptographic Hardware and Embedded Systems by A. Moss, E. Oswald, CHES 2012, pages 58-75. In this paper, sensitive data is annotated by the programmer, and their confidentiality is treated as values in a grid that allows the compiler to pass confidential information through the program. Once compiled, the secret data never appears in plain text during program execution, thereby ensuring the confidentiality of the masked data, especially against side-channel attacks. The algorithm then takes steps to detect sensitive information leaks in all values of the program, especially in temporary variables introduced when transforming expressions, and if a leak occurs, it uses a set of program transforms to try to prevent the leak. try

A disadvantage of the solution revealed in this paper is that it only applies to first-order Boolean masking schemes and linear codes. Moreover, the steps of detecting leaks and transforming programs to prevent such leaks are not constrained to converge.

Synthesis of masking countermeasures against side channel attacks, Computer aided verification (pages 114-130) by Eldib H., Wang C. of Springer International Publishing, January 2014, in which the entire algorithm is masked, including all intermediate values. that is suggested To deal with non-linear functions, it is proposed to determine a functionally equivalent linear function, to ensure that the function is equally and perfectly masked for all possible inputs.

This method has similar disadvantages to Moss et al.'s method, since it only applies to the call graph of the Boolean type. Also, the method follows a trial and error methodology with no guaranteed execution time.

Accordingly, there is a more stringent need for a fully automatic and robust method for converting an unprotected algorithm into a secure version of the algorithm.

To address these and other problems, a computer-implemented method for converting a call graph representation of an algorithm into a secured call graph representation of the algorithm is provided. A call graph includes one or more inputs, one or more edges (c, d, e), one or more nodes (P, Q, R, S), and one or more outputs (g). The edges of the call graph represent the internal variables (or intermediate variables) of the algorithm, and the nodes of the call graph represent the linear or non-linear basic function of the algorithm. A computer implemented method according to the present invention comprises:

<img file="KR20180098172A_D0001.tif" /> masking each input of the call graph;

<img file="KR20180098172A_D0002.tif" /> replacing each unmasked internal variable of the call graph with a masked variable;

<img file="KR20180098172A_D0003.tif" /> replacing at least each nonlinear function in the call graph with an equivalent function applied to the masked variable;

<img file="KR20180098172A_D0004.tif" /> Unmasking each output of the call graph.

The method advantageously applies to both linear and non-linear call graphs with limited and deterministic execution times, and is not limited to boolean types of operations.

Transforming an unprotected algorithm into a secure version of the algorithm satisfies two required characteristics:

<img file="KR20180098172A_D0005.tif" /> Preserves semantics, i.e., the same result is obtained from a determined set of inputs compared to the original program, and

<img file="KR20180098172A_D0006.tif" /> Mask all intermediate variables (i.e. variables passed by vertices).

If the call graph includes parts that are iteratively processed, replacing the unmasked internal variable by the masked internal variable may include: identifying, and using the same mask for these variables at the input and at the output of that portion of the call graph.

Alternatively, replacing an unmasked inner variable by a masked inner variable comprises: identifying an inner variable used as both an input and an output of a portion of a call graph that is iteratively processed, and This may be ensured by inserting an additional node at the feedback edge to modify the mask of the internal variable.

Advantageously, the mask of an internal variable in a portion of the call graph that is processed iteratively may be changed at regular intervals, and the associated function is modified accordingly. This mechanism can be achieved by inserting an additional node into the call graph to refresh the mask of the internal variable of the iteration part.

In a computer implemented method according to certain embodiments of the present invention, the equivalence function calculated in the step of replacing at least each non-linear function in the call graph with an equivalence function applied to the masked variable uses a match table. may be implemented. According to one embodiment of the present invention, the linear function of the call graph may be replaced by an equivalent function that takes into account the masks of the input and output internal variables.

According to one embodiment of the present invention, some or all of the mask values of the secure call graph may be randomly determined.

According to one embodiment of the present invention, the computer implemented method may further comprise the further step of compiling the call graph to generate protected executable code.

The present invention also provides a computer program product stored on a non-volatile computer readable data storage medium comprising computer executable instructions for causing a computer system to perform a computer implemented method according to any embodiment of the present invention, and a computer A non-volatile computer-readable data storage medium comprising computer-executable instructions for causing a system to perform the computer-implemented method.

The invention also relates to a system comprising a processor coupled to a memory, wherein the memory causes the system to perform a computer implemented method for converting a call graph representation of an algorithm into a secure call graph representation of the algorithm. Stores executable instructions. A call graph includes one or more inputs, one or more edges (c, d, e), one or more nodes (P, Q, R, S), and one or more outputs (g). The edges of the call graph represent the internal variables of the algorithm, and the nodes of the call graph represent the linear or non-linear basic function of the algorithm. The system includes a processing device, the processing device comprising:

<img file="KR20180098172A_D0007.tif" /> to mask each input of the call graph,

<img file="KR20180098172A_D0008.tif" /> to replace each unmasked internal variable in the call graph with a masked variable,

<img file="KR20180098172A_D0009.tif" /> to replace at least each nonlinear function in the call graph by an equivalent function applied to the masked variable, and

<img file="KR20180098172A_D0010.tif" /> to unmask each output of the call graph

is composed

BRIEF DESCRIPTION OF THE DRAWINGS The present invention will be better understood, and its various features and advantages will appear from the following description of a number of exemplary embodiments, which are provided for illustrative purposes only, and from the accompanying drawings thereof, in which: 1a shows an unprotected call graph as known from the prior art; 1b and 1c show a call graph which is protected according to two embodiments of the invention, advantageously ensuring in particular the consistency of the mask applied to the variables used as inputs and outputs of the repeating part of the graph; , - Figures 2a and 2b illustrate two ways of processing a linear function; 3 illustrates one way of processing a non-linear function, by constructing a match table equivalent to the non-linear function, taking into account masked inputs and outputs; Figure 4a shows an unprotected call graph with the repeating part expanded for illustrative purposes; - Figures 4b and 4c are diagrams showing a protected call graph according to two embodiments of the present invention, wherein the mask of internal variables used in the iteration part of the call graph is modified at each iteration, and the repeating part is for illustrative purposes; has been developed for - Figure 5a is a typical call graph representation of an AES algorithm, Figure 5b is a corresponding protected call graph generated according to one embodiment of the present invention; 6 is a flowchart depicting a computer implemented method according to certain embodiments, and 7 illustrates a system that may be used for processing the present invention; The examples disclosed herein are merely illustrative of some embodiments of the present invention. They do not in any way limit the scope of the invention as defined by the appended claims.

1A shows an unprotected call graph as known from the prior art. This representation is a standard representation for purposes of illustration.

The unprotected call graph of Figure 1A illustrates the execution of computer code. It contains a plurality of nodes (P, Q, R, S), each of which relates to a function performed by the code. As indicated above, each function expressed as a node may consist of a single operation or a combination of operations. A function may or may not be linear.

The unprotected call graph also includes oriented links that connect the output of a node to the input of another node, called an edge of the graph. These edges are associated with intermediate variables (c, d, e) that are transferred from one function to the next.

The unprotected call graph further includes one or more inputs (a, b, f), and one or more outputs (g).

The unprotected call graph also includes an iteration portion 101 in which functions P, Q, R and S are processed multiple times, with subsequent iterations taking as input the output of the previous iteration.

The call graph is a representation of the interdependencies of functions during the execution of a program, and the interactions required to produce an output variable g from the input variables a, b, f. It can be described using various programming languages, for example, Graphic, Unified Modeling Language (UML) or HyperText Markup Language (HTML). It can be compiled from source code using software such as Doxygen© or Eclipse©, or compiled code (assembler language, LLVM-IR (Low Level Virtual Machine - Intermediate Representation; Low Level Virtual Machine - Intermediate Representation), VHDL (VHSIC Hardware) Description Language (VHSIC hardware description language), can be generated automatically from Verilog©, or even manually.

1B shows a protected call graph according to a first embodiment of the present invention.

In order to provide robustness against cryptography and content recovery attacks, the present invention involves masking each variable of a program with a mask, and, in accordance with some advantageous embodiments of the present invention, changing this mask during program execution. based on

To this end, the input variables a, b, f are masked (111, 112, 113). mask value (m₁, m₂, m₆) may be arbitrarily selected. The masked variable is then aθm₁, bθm₂ and fθm₆is designated as

Then, each unmasked internal variable (c, d, e) of the call graph is the masked variable (cθm)₃, dθm₄, eθm₅) is replaced by The mask may be chosen randomly, or if the internal variable is the output of a linear function, it may be correspondingly inherited from the mask used for the input of the function.

In this embodiment, to ensure consistency of the protected call graph, when an internal variable is used as both the input and output of the repeating portion of the graph (for Fig. 1g), the mask variable is the input and You can also use the same mask on both outputs. Thus, the masks associated with variables b and g are the same (m₂).

Thus, the input of function P' is masked equally at each iteration.

After assigning a mask to each input and replacing each unmasked inner variable with a masked variable, the functions (P, Q, R, S) associated with the nodes of the call graph are for (P', Q', R', S').

If the function is linear and the masking is Boolean, the output mask may be inherited from the input mask. Thus, the function does not need to be modified. Otherwise, the function must be replaced by an equivalent function that arrives at the same result, while taking the masked variable as input, and masks the output of the function.

If the function is non-linear, it is generally not possible to make a link between the output mask and the input(s) mask(s). Unmasking the input data, processing the function, and masking the result cannot be considered, since unprotected information would appear and could be considered an information leak. Thus, a function may be replaced by a match table that gives all possible results of the function, the match table being constructed taking into account input and output masks. In this way, in contrast to the prior art, all variables processed by the algorithm are protected and no approximation of the non-linear function(s) will be made.

Finally, the variable g that outputs the call graph may be unmasked (114).

In the first embodiment, all internal variables are correspondingly protected, and the result of the protected call graph of FIG. 1B is exactly the same as the result of the unprotected call graph of FIG. 1A . Except for masking the input and unmasking the output of the program, this first embodiment does not affect the number of nodes in the program. Its final complexity and processing time will not be affected by the additional protection layer. Once compiled, none of the internal variables will appear unprotected. Thus, the execution of the program is fully protected against cryptography and content recovery attacks.

1C shows a second embodiment of the present invention. In this embodiment, as in Fig. 1b, the inputs a, b and f are masked, the unprotected internal variables c, d, e are replaced by the protected variables, and the function is modified correspondingly, The output (g) of the call graph is unmasked.

However, the consistency of the masking with respect to the repeating portion of the graph introduces to the feedback loop 101 of the repeating portion an additional node 120 configured to modify the mask value of an internal variable used as both an input and an output of the repeating portion. Guaranteed by inserting

In Fig. 1c, the output of the repeating part is the masked variable (gθm₇), and node 120 is gθm₇gθm₂Modify the mask of this variable to convert to . To ensure that the information does not appear unprotected, the output mask (m₇) before the input mask (m₂) is applied. As in Fig. 1b, the input of function P' has the same mask at each iteration.

An advantage of the second embodiment compared to the first embodiment is that all the masks may be randomly selected.

Various methods may be used to mask the data. Masking may be, for example, simple first-order Boolean masking, such as summing a variable with a secret shared value, higher-order Boolean masking, or any other more sophisticated masking technique. One of the advantages of the present invention is that it is compatible with any masking technique.

Figure 2a illustrates how to process a linear function. In this function, if the masking is Boolean, the mask applied to the output variable(s) 203 depends on the mask applied to the input variable(s) 201 and 202 . Thus, the output mask is given by applying a linear function to the input mask. In this example, the input variables (a and b) are the values (m₁ and m₂) are masked by The output of the function is the mask(f(m₁, m₂)) is masked by the value that is the result of the function applied to it. Considering a simplified example, if function 211 is a multiplicative function, then f(m₁, m₂) is m₁ *m₂same as

2B illustrates an embodiment for processing a linear function when the protected value appearing as a result of the function has a particular mask value.

In this embodiment, two possibilities may be implemented:

<img file="KR20180098172A_D0011.tif" /> Inserting an additional node 212 into the call graph, the additional node is the mask f(m) that affects the result of the linear function₁, m₂) required mask (m₃) to the conversion to To this end, the function 212 is a mask f(m)₁, m₂)) on the result of the linear function before removing the mask (m₃) may be added, or

<img file="KR20180098172A_D0012.tif" /> Compute a match table 221 equivalent to a linear function taking into account the values of the mask, the match table stored in memory. This table is aθm₁ and bθm₂Include as input all possible values of , and output each of these values (cθm₃) with the corresponding value of The match table may be computed by executing functions 211 and 212 for all possible inputs. This table may be stored encrypted, but it may not be necessary, since the data contained in the table does not allow determining any information about the original unprotected data processed by the function.

Processing of a linear function as shown in Figure 2b allows to use a random mask for each internal variable of the call graph.

3 illustrates an embodiment for processing a non-linear function. In this embodiment, the processing of the non-linear function is based on constructing a match table equivalent to the function, taking into account the masked inputs and outputs. It should be noted that this processing can also be applied to process linear functions.

In contrast to the linear function shown in Figures 2a and 2b, the mask of the output values cannot be determined from the mask of the input values. For this reason, the non-linear function must be replaced by an equivalent match table 310 that provides the result of the function for every possible set of inputs. The match table is an input variable (aθm₁ and bθm₂) may be computed by unmasking 301 and 302 , applying a nonlinear function 303 , and masking the result of the nonlinear function 304 .

To construct a table, all possible input variables may be browsed. Accordingly, the table may be proportional to the number of inputs, the number of outputs, and/or the data size. For example, considering that the inputs (a and b) are coded over 8 bits, the relevant match table is: 2^8(number of possibilities for a) * 2^8(number of possibilities for b) * It is a table that reaches a size of 8 bits (size of c).

Fig. 4A shows the unprotected call graph of Fig. 1A in an embodiment in which the iterative portion of the algorithm is deployed. In the following description of FIG. 4A , it is contemplated that the repeating portion is executed only twice, for illustrative purposes only.

The function (P, Q, R, and S) is executed twice, where the values of the inner variable (c', d', e' and g') during the second iteration are equal to the values of the same variable during the first iteration (c , d, e and g).

4B and 4C show a protected call graph according to another embodiment of the present invention, wherein the mask of internal variables used in the iteration portion of the call graph is modified at each iteration. In the following description of Figs. 4b and 4c, it is considered that the repeating part is developed as in Fig. 4a.

A high level of protection is obtained by refreshing the mask value at the end of each iteration (ie by changing the mask value), especially against side-channel attacks that use certain aspects of the mask being applied.

In Figure 4b, the first iteration is masking each input (a, b and f), masking each internal variable (c, d, e and g) to the masked variable (cθm)₃, dθm₄, eθm₅ and gθm₇), and modifying the function to take into account the masked variables (P', Q', R' and S'), as in Fig. 1b or 1c.

For subsequent iterations, the masks used for the internal variables c, d, e and g are modified, and the associated function is modified correspondingly. The mask applied to the variable used as input to the iteration may also be modified. In that example, the input (a and f) has a mask (m₁ and m₆Nodes 111 and 113 applying a new mask m₈ and m₁₂) is changed to the nodes 401 and 403 that apply. Masked variable (cθm)₃, dθm₄ and eθm₅) is the new masked variable (cθm₉, dθm₁₀ and eθm₁₁) is changed to mask (m₁ and m₂A function (P') which takes as input a variable masked by ) is modified with an equivalent function (P"), where₈ and m₇It takes as input a variable masked by . If function P' is a linear function and the output of the function is masked by a mask that is inherited from the input mask, then P' may remain unmodified. The functions Q', R' and S' are correspondingly modified into the functions Q", R" and S".

In an alternative embodiment (not represented), the masks of inputs a and f may not be modified from iteration to iteration.

The call graph may be represented, for example, in FIG. 1C , using an additional node corresponding to refreshing the mask of all variables involved in the iteration, such as node 120 in the feedback loop of the iteration portion.

4C illustrates another embodiment in which node 402 is inserted into a feedback loop of an iteration. This node 402 is involved in refreshing all masks applied to the inputs and variables involved in the iteration. Also, as shown in Fig. 4c, this node further changes the mask affecting the output of the previous iteration, thereby causing the mask (m₇) to the mask (m₉) can be converted to

5A is a call graph representation of an unencrypted AES algorithm. These exemplary representations are used to illustrate the method according to the present invention. This representation is byte 0 (x₀), and iteratively processed steps of the AES algorithm, called "round steps". In the standard implementation of the AES algorithm, the first round (pre-processing) and the last round (post-processing) are special. These rounds are not represented here, and Fig. 5a focuses only on the intermediate rounds of the data path (AES key (k_It's) not shown).

Each round is an iterative process, where y is the output of one iteration of the round.₀ byte is the input to the round, x₀This means that it loops back to .

In the call graph representation, the circles represent operations performed on different variables, while the edges of the graph represent internal variables. In Figure 5, there are no inputs or outputs, as they are processed in the first and last iterations (not represented) of the round.

x in round₀The first function applied to is called a permutation box (known as S-box). This permutation is the main element of the algorithm and x₀It is a bijective nonlinear operation performed on . The output of the first substitution box is the intermediate variable (a) of FIG. 5A.

The following function applied to a is a set of three linear operations performed on the Galois field: times 1 (times 1), times 2 (times 2), and times 3 (times 3). These operations are linear.

The results of these operations, called b, b' and b", are bytes 5, 10 and 15 (x₅, x_A, x_F) is mixed with the result of the corresponding operation performed on This operation is referred to as "Mixcolumn". Blend is an XOR operation performed on four entries. This function is equivalent to three consecutive XOR operations. The output of the "mixcolumn" operation is the intermediate variable (c).

The next function applied to c is a step called "Addroundkey", which XORs c to the key (or the specific bytes processed from the key) (k₀), mixed with y to be used as input for subsequent iterations₀create

5B is a call graph representation of the AES algorithm of FIG. 5A after being protected in accordance with one embodiment of the present invention.

x₀Since is the intermediate variable, it is the mask (θm₀₀) is masked by this mask is x₀may be an XOR performed between and a known random value, but it may also be multidimensional sharing meaning that multiple mask layers are applied. In the latter case, θm₀₀is not necessarily a byte (8-bit) share, but can be any dimension of sharing. It may also be a pair or triplet or any other association of masks having the same or different sizes.

After processing in the S box step, the intermediate variable (a) is the mask (θm)₀₁) is masked by Since the permutation box is a non-linear function, as illustrated in Fig. 3, it is the mask (θm₀₀) must be replaced by an equivalent match table that removes all at once, performs a non-linear function, and masks the result (θm₀₁) must be used to mask it. Therefore, θm₀₁is necessarily θm₀₀is not related to

One After performing the doubling, doubling, and tripling operations, the intermediate variable (b) is the mask (θm).₀₂) may be masked by In some embodiments, the mask is θm₀₁may be equal to, or the function may be replaced by an equivalent match box, so that θm₀₂is θm₀₁can be selected completely independently of

In another embodiment, an equivalent match table 501 may be computed that performs the operation of the permutation box and the operation of 1, 2, and 3 times. The match table is one input (x₀qm₀₀) and three outputs (bθm₀₂, b'θm₀₂, b"θm₀₂) may have Alternatively, three match tables may be computed, each of which has one input and one output. Permutation boxes, regrouped by 1x, 2x and 3x operators in the match table, represent operations called "T-box" (Table box) when unencrypted.

In other embodiments, a different mask may be assigned to each of the intermediate variables b, b' and b".

The step of mixing the results of calculations performed on various bytes is a linear function. As a result, the output mask (θm₀₃) is the mask of the input (θm₀₁, θm₅₁, θm_A1, and θm_F1)(θm₅₁, θm_A1, and θm_F1is the variable (x₅, x_A and x_F) can be retrieved from the mask each associated with the output of the T box calculation for processing. However, the output mask (θm) is completely independent of the input mask.₀₃) may be computed with an equivalent match table allowing to select

In the next step, the intermediate variable (cθm₀₃) is the key (k₀) is mixed with Since the key is a constant and not a variable, the key does not need to be masked. The result of mixing is y₀θm₀₄am. Since the mixing operation is linear, θm₀₄is θm₀₃, or can be completely independent if the mixing function is replaced by an equivalent match table.

Finally, a refresh node 502 may be inserted. The first purpose of the refresh node is to₀/x₀) is used as the input/output of the repeating part of the call graph, θm₀₄θm₀₀It is to ensure the consistency of the protected call graph by converting to . In some embodiments, the refresh mask may further involve changing the mask for at least some of the internal variables belonging to the iterative loop (in which case the mask θm₀₀, θm₀₁, θm₀₂, θm₀₃ and θm₀₄)Lim).

When the nodes of a linear function inherit from their parent node, the mask(s) of the variable that is the input to the loop (θm in Fig. 5a)₀₀) and a mask of variables that are output(s) of the non-linear function(s) (θm in FIG. 5B , according to an embodiment)₀₁ or θm₀₂) can be refreshed. This means modifying the associated equivalence table to ensure call graph consistency. The refreshed mask is automatically propagated to the input/output of the linear function.

It should be noted that the refresh node 512 is optional. Another way to ensure the consistency of the protected call graph is, for example, θm₀₀θm equal to₀₄may be to choose

6 is a flowchart depicting a computer implemented method in accordance with certain embodiments.

The method includes:

- masking the input of the call graph to generate a masked input (601);

- replacing (602) unprotected variables of the graph represented by edges of the graph by masked variables. The mask of the masked variable may be chosen randomly, or may be the result of the use of a linear function on the masked variable;

- replacing ( 603 ) at least the non-linear function of the calling graph represented by the nodes of the graph by the equivalent function, so as to perform the same operation as the initial function, taking into account the mask affecting the input/output of the function. This operation can also be performed on linear functions of the call graph. One possible implementation is to replace the function by a match table that is created taking into account the masks affecting the input/output, and to relate the output value to each possible combination of the input values; and

- unmasking (604) the output of the call graph.

The method according to the invention modifies the repeating portion of the graph such that the masked inputs and variables are refreshed at each iteration of the loop, either regularly or randomly, or at a slower rate (meaning that the value of the mask is modified). may include an additional optional step 605 of Therefore, a variable that is calculated repeatedly is never protected with the same mask. Although not limited to this application, the method according to the present embodiment has particular advantages when applied to cryptographic algorithms that often include a very large number of iterations performed over small computations.

The methods described herein may be provided to any type of processor or any software programmable machine, such as, for example, a microprocessor, microcontroller, or DSP to implement the functions/acts specified herein. may be implemented by computer program instructions that create a machine that executes the instructions. These computer program instructions may also be stored on a computer-readable medium capable of instructing a computer to function in a particular manner. To this end, computer program instructions may be loaded onto a computer such that the executed instructions provide a process for implementing the functions specified herein, cause performance of a series of operational steps, and thereby create a computer implemented process. have.

The method includes protected compiled code that can be used alone, but can be paired with a compiler, and thereby be executed by a computational machine, to generate a protected representation of an algorithm from an unprotected algorithm; or hardware code, for example, in the form of a netlist implemented on a dedicated computing machine such as a field programmable gate array (FPGA), or an application specific integrated circuit (ASIC) and generated by a compiler.

To this end, the method may include an additional step 606 of compiling the protected call graph to generate executable code that is robust to cryptography and content recovery attacks.

7 illustrates a system, eg, a general purpose computer system, that may be used to process the present invention. The system retrieves unprotected data, such as non-volatile computer readable memory (M) in which a computer program product is stored, source code or executable code processed by a processor (CPU), or unprotected call graphs, It includes an input/output interface I/O for generating a call graph, wherein the processor is coupled to the memory and the input/output interface via a data bus.

More generally, the methods and devices described herein may be implemented by various means. For example, these techniques may be implemented in hardware, software, or a combination thereof.

Various embodiments of the present invention provide several advantages, including:

- they present a high-level approach that is not related to implementation;

- they give the algorithm robustness against all kinds of side-channel attacks, notably because all variables processed by the algorithm are masked while the meaning of the algorithm is preserved;

- they are applicable to any type of software program, to linear and non-linear functions;

- they are fairly easy to implement and compile,

- they do not represent information leakage, since all variables are masked;

- They can be programmed to run automatically, without involving a human operator.

Although embodiments of the present invention have been illustrated by way of description of various examples, and while these embodiments have been described in considerable detail, it is the applicant's responsibility to limit or in any way limit the scope of the appended claims to these details. not intentional Additional advantages and modifications will be readily apparent to those skilled in the art. Accordingly, the invention in its broader aspects is not limited to the specific details, representative methods, and exemplary embodiments shown and described.