METHOD TO SECURE A SOFTWARE CODE PERFORMING ACCESSES TO LOOK-UP TABLES

Abstract

The present invention relates to a method of securing by a first processor of a securing device, a software code performing, when executed by an execution device, a sensitive operation performing accesses to a plurality of look-up tables (T.sub.0, T.sub.1, . . . T.sub.n), wherein said software code comprises first sequences of instructions performing said accesses, said method comprising the steps of: a) generating (S1) a packed table (T) gathering said look-up tables (T.sub.0, T.sub.1, . . . T.sub.n), b) applying (S2) a permutation (P) to said packed table (T) to obtain a permuted table (T.sub.p), c) replacing (S3) in the software code (SC) at least one of said first sequences of instructions, which when executed at runtime by a second processor of said execution device performs an access to a target value (X) located at a first index (i) in a first look-up table among said plurality of look-up tables by a new sequence of instructions which: a c1) determines using said permutation (P) a permuted index (i.sub.p) of the target value (X) in the permuted table, c2) returns the value memorized at the permuted index in said permuted table (T.sub.p).

Claims

1. A method of securing by a first processor (11) of a securing device (1), a software code (SC) performing, when executed by an execution device (2), a sensitive operation performing accesses to a plurality of look-up tables (T.sub.0, T.sub.1, . . . T.sub.n), wherein said software code comprises first sequences of instructions performing said accesses, said method comprising the steps of: a) generating (S1), by the first processor, a packed table (T) gathering said look-up tables (T.sub.0, T.sub.1, . . . T.sub.n), b) applying (S2), by the first processor, a permutation (P) to said packed table (T) to obtain a permuted table (T.sub.p), c) replacing (S3), by the first processor, in the software code (SC) at least one of said first sequences of instructions, which when executed at runtime by a second processor (21) of said execution device performs an access to a target value (X) located at a first index (i) in a first look-up table among said plurality of look-up tables by a new sequence of instructions which: c1) determines using said permutation (P) a permuted index (i.sub.p) of the target value (X) in the permuted table, c2) returns the value memorized at the permuted index in said permuted table (T.sub.p).

2. The method of claim 1, wherein said new sequence of instructions, when executed at runtime, c0) determines a packed-table index (i.sub.c) of the target value (X) in the packed table (T), and at step c1) determines said permuted index (i.sub.p) from said permutation (P) and said packed-table index (i.sub.c).

3. The method of claim 1, wherein said packed table is generated by concatenating said plurality of look-up tables (T.sub.0, T.sub.1, . . . T.sub.n).

4. The method of claim 1, wherein said permutation (P) is a random permutation.

5. The method of claim 2, wherein said permutation is stored by the execution device as an array comprising the order of the indexes of the packed table in the permuted table and step c1) computes at runtime the permuted index (i.sub.p) by extracting said permuted index memorized at said packed-table index (i.sub.p) in said array.

6. The method of claim 2, wherein said permutation is a predetermined transformation function which transforms the index of each value in the packed table into an index of said value in the permuted table (T.sub.p), and step c1) computes at runtime a permuted index (i.sub.p) by applying said stored transformation function (P) to said packed-table index (i.sub.c).

7. A non-transitory machine-readable storage medium encoded with instructions of a secure software code for secure execution by a second processor (21) of an execution device (2), wherein: said secure software code is a modified version of an unsecure software code performing a sensitive operation performing accesses to a plurality of look-up tables (T.sub.0, T.sub.1, . . . T.sub.n), said unsecure software code comprising first sequences of instructions performing said accesses, the non-transitory machine-readable storage medium is also encoded with: a permuted table (T.sub.p) generated by applying a permutation (P) to a packed table (T) gathering said plurality of look-up tables (T.sub.0, T.sub.1, . . . T.sub.n), a new sequence of instructions replacing at least one of said first sequences of instructions performing an access to a target value (X) located at a first index (i) in a first look-up table among said plurality of look-up tables, and which, when executed at runtime by the second processor (21) of the execution device (2): c1) determines using said permutation (P) a permuted index (i.sub.p) of the target value (X) in the permuted table, c2) returns the value memorized at the permuted index in said permuted table (T.sub.p).

8. A method of securely executing instructions of a secure software code by a second processor (21) of an execution device (2), wherein: said secure software code is a modified version of an unsecure software code performing a sensitive operation performing accesses to a plurality of look-up tables (T.sub.0, T.sub.1, . . . T.sub.n), said unsecure software code comprising first sequences of instructions performing said accesses, a permuted table (T.sub.p) is generated by applying a permutation (P) to a packed table (T) gathering said plurality of look-up tables (T.sub.0, T.sub.1, . . . T.sub.n), when an access is performed to a target value (X) located at a first index (i) in a first look-up table among said plurality of look-up tables, said method comprises the steps of: c1) determining (E1) using said permutation (P) a permuted index (i.sub.p) of the target value (X) in the permuted table (T.sub.p), c2) returning (E2) the value memorized at the permuted index in said permuted table (T.sub.p).

Description

BRIEF DESCRIPTION OF THE DRAWINGS

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

[0042] FIG. 1 illustrates schematically a securing device according to an embodiment of the present invention;

[0043] FIG. 2 illustrates schematically an execution device according to an embodiment of the present invention;

[0044] FIG. 3 illustrates schematically a method of securing a software code according to an embodiment of the present invention;

[0045] FIG. 4 illustrates schematically a method of executing instruction of a secure software code according to an embodiment of the present invention;

[0046] FIG. 5 illustrates step of replacing first sequences of instructions by a new sequence of instructions according to an embodiment of the present invention;

[0047] FIG. 6 illustrates an embodiment for storing the permutation as an array.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

[0048] In the description detailed below, reference is made to the accompanying drawings that show, by way of illustration, specific embodiments in which the invention may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the invention. It is to be understood that the various embodiments of the invention, although different, are not necessarily mutually exclusive. For example, a particular feature, structure, or characteristic described herein in connection with one embodiment may be implemented within other embodiments without departing from the spirit and scope of the invention. In addition, it is to be understood that the location or arrangement of individual elements within each disclosed embodiment may be modified without departing from the spirit and scope of the invention. The description detailed below is, therefore, not to be taken in a limiting sense, and the scope of the present invention is defined only by the appended claims, appropriately interpreted, along with the full range of equivalents to which the claims are entitled.

[0049] The invention aims at securing a software code which when executed performs a sensitive operation comprising several accesses to a plurality of lookup tables, hereafter called LUTs. Such a sensitive operation may for example be a cryptographic process such as a blockcipher encryption process whose operations are coded as LUTs. It may for example be the well-known and widely used AES algorithm.

[0050] If no care is taken to protect a sensitive operation accessing values in LUTs, these accesses will often show a regularity in their arrangement, which can in turn be related to the structure of the sensitive operation itself. Another source of information is the way in which the LUTs themselves are organized, for example in terms of number of elements or number of times they are accessed, which can be related to the structure of the sensitive operation itself as well. In order to secure such a sensitive operation and avoid that an attacker may learn information about it, especially secret information such as secret keys, from monitoring the execution of the process, especially memory accesses when reading a value in a LUT, the main idea of the invention is to mix several LUTs altogether in a single larger LUT. By doing so, when a value is read in one of these LUTs, the attacker cannot easily know to which LUT this value belongs. It prevents the attacker from knowing which LUT embodies an operation using a sensitive data such as a secret key and from trying to retrieve this sensitive data by analyzing a specific LUT. Permuting the elements of a single LUT prevents an attacker from extracting information when accessing its elements only. Combining several LUTs together prevents an attacker from extracting information when accessing LUTs themselves, by blurring their boundaries.

[0051] In order to perform such a mixing, the software code SC performing such a sensitive operation is secured by the first processor 11 of a securing device 1, producing a secured software code SSC which can then be securely executed by an execution device 2.

[0052] Such a securing device 1 may be any electronic device including a processor For example it may be a personal computer PC on which a development environment was installed. FIG. 1 describes an exemplary embodiment of such a securing device 1 comprising a first processor 11, a first RAM memory 12, a first communication unit 13 such as an Ethernet or Wifi network adapter, a first display 14, a first mass memory 15 such as a hard drive, and first user input interface 16. The software code SC to be secured may be stored on the first mass memory 15 of the securing device. The secure software code SSC, obtained after the securing device 1 applies the method according to the first aspect to the software code SC, can also be stored on the first memory 15.

[0053] FIG. 2 describes an exemplary embodiment of the execution device 2. For example it may be a personal computer PC, a mobile device such as a smartphone or a tablet, or a public terminal in a bank or a point of sale. It may also be a simple chip included in a smart card or a credit card. It may comprise a second processor 21, a second RAM memory 22, a second communication unit 23 such as an Ethernet or Wifi network adapter, a second display 24, a second mass memory 25 such as a hard drive, and second user input interface 26. The secure software code SSC, to be executed by the second processor 21 of the execution device 2, may be stored on the second mass memory 25 of the executing device. The securing device 1 and the execution device 2 may be of similar or different types. Both devices may share the same hardware architecture, such as x86, ARM or PowerPC, or have different architectures.

[0054] Most steps of the embodiments described hereafter may be applied to the source code, or the compiled code of the sensitive operation. The following paragraphs will describe an application of the method according to the invention to the compiled code, called hereafter software code, but it shall not be interpreted as a limitation of the scope of the invention. The various arrangements that could be derived by a man skilled in the art by applying one or more of the steps of the invention to source code are included in the scope of the invention. For example, the steps of the method may be applied by a compiler during the compilation of the code, or to the source code before any compilation.

Securing Method Main Steps

[0055] The following paragraphs describe the steps of the method according to the first aspect of the invention, securing the software code SC and producing the secure software code SSC, as depicted on FIG. 3. These steps are performed by the first processor 11 of the securing device 1 and are all labeled with the letter “S” followed by the number of the step.

[0056] When needed, reference is made to steps performed by the execution device 2 when executing the secure software code SSC, after the method according to the first aspect is completed. Such execution steps are labeled with the letter “E” followed by the number of the step and depicted on FIG. 4.

[0057] During a first securing step S1, the first processor 11 generates a packed table T gathering multiple lookup tables T.sub.0, T.sub.1, . . . T.sub.n to which accesses are performed by first sequences of instructions of the sensitive operation. Such a packed table may for example be obtained by simply concatenating together all the tables in any order.

[0058] During a second securing step S2, the first processor 11 applies a permutation P to the packed table T, which generates a permuted table T.sub.p. The permutation P may be predetermined. Alternatively it may be a random permutation generated before or when this second securing step is performed.

[0059] The permutation P may be applied to all the elements of the packed table T or only to a subset of these. Contrarily to the packed table which contains several blocks of elements such that all the elements of a block belong to the same LUT, the permuted table T.sub.p mixes together all the elements of the LUTs T.sub.0, T.sub.1, . . . T.sub.n and an attacker cannot know which element or group of elements belong to which LUT without knowledge of the applied permutation.

[0060] In order to enable the sensitive operation to read elements in the permuted table T.sub.p instead of reading it in the LUTs T.sub.0, T.sub.1, . . . T.sub.n, the first processor 11 of the securing device 1 replaces in the software code SC, during a third securing step S3, at least one of said first sequences of instructions by a new sequence of instructions which enable the second processor 21 of the execution device 2, when executing the sensitive operation, to read elements in the permuted table T.sub.p.

[0061] More precisely, the second processor replaces at least one of said first sequences of instructions, which when executed at runtime by the second processor of the execution device performs an access to a target value X originally located at a first index i in a first look-up table among said plurality of look-up tables T.sub.0, T.sub.1, . . . T.sub.n packed in the packed table T by a new sequence of instructions which: [0062] a during a first execution step E1, determines using said permutation P a permuted index i.sub.p of the target value X in the permuted table, [0063] during a second execution step E2, returns the value memorized at the permuted index in said permuted table T.sub.p.

[0064] In order to compute the permuted index at the first execution step E1, the sequence of instructions, when executed at runtime by the second processor 21 of the execution device 2, may also during a preliminary execution step EU determine a packed-table index is of the target value X in the packed table T. In that case, during the first execution step E1, the sequence of instructions may determine the permuted index i.sub.p of the target value in the permuted table from the permutation P and the packed-table index i.sub.c. The permuted index i.sub.p may thus be obtained just by applying the permutation to the packed-table index i.sub.c.

[0065] As an example, as illustrated on FIG. 5, let us call Seq said new sequence of instructions, and T.sub.i the LUT table to which an access shall be performed in order to retrieve the target value X located at the index i in this LUT. The securing method according to the invention may replace any read command

[0066] read(index i in table T.sub.i)

by a new command

[0067] Seq(index i in table T.sub.i)

evaluated at runtime as

[0068] read(permuted index i.sub.p in the permuted table T.sub.p).

[0069] By doing so, the sequence of instructions acts as a redirection function that redirects the read command to the location of the target value in the permuted table instead of reading it in the unprotected LUT T.sub.i.

[0070] In order to enable the secure software code to retrieve at runtime the target value X from the permuted table T.sub.p, the second processor 21 of the execution device 2 shall have access to the permutation P and the permuted table T.sub.p. They may be stored along with the secure software code in the second mass memory 25 of the execution device 2.

[0071] Different embodiments are possible for storing the permutation P.

[0072] In a first embodiment, the permutation may be stored as an array comprising the order of the indexes of the packed table in the permuted table. For example, as illustrated on FIG. 6, if the indexes (0, 1, 2, 3) of the packed table are permuted to (3, 2, 0, 1), the permutation may be stored as the array (3, 2, 0, 1). In that case, during the first execution step E1, the second processor, when executing the new sequence of instructions, may compute the permuted index i.sub.p by extracting the permuted index memorized at the packed-table index is in the memorized array.

[0073] In a second embodiment, the permutation may be a predetermined transformation function which transforms the index of each value in the packed table T into the index of this value in the permuted table T.sub.p. Let us take as an example the permutation turning indexes (0, 1, 2, 3) into (3, 0, 1, 2). In this example, the applied permutation is the function: X->(X+3) mod 4. In that case the permutation may be stored by just memorizing this transformation function. During the first execution step E1, the second processor, when executing the new sequence of instructions, may then compute the permuted index i.sub.p by applying the stored transformation function P to the packed-table index i.sub.c. This is more efficient than the previous embodiment in terms of memory consumption but it may only be applied to permutation which can be easily described by a transformation function. Consequently it may not be suited to all permutation, especially to randomly defined permutations.

Other Aspects

[0074] In a second aspect, the invention also relates to a non-transitory machine-readable storage medium encoded with the instructions of the secure software code SSC obtained after the first processor 11 of the securing device 1 has performed, on the software code SC called unsecure software code performing a sensitive operation performing accesses to a plurality of look-up tables (T.sub.0, T.sub.1, . . . T.sub.n) and comprising first sequences of instructions performing said accesses to the plurality of look-up tables (T.sub.0, T.sub.1, . . . T.sub.n), at least the securing steps S1 to S3 of the method according to the first aspect described here above. Said secure software code SSC is then a modified version of the unsecure software code SC on which said method according to the first aspect has been applied.

[0075] This non-transitory machine-readable storage medium is also encoded with:

[0076] a permuted table T.sub.p generated by applying a permutation P to a packed table T gathering said plurality of look-up tables T.sub.0, T.sub.1, . . . T.sub.n,

[0077] and a new sequence of instructions replacing at least one of said first sequences of instructions performing an access to a target value X located at a first index i in a first look-up table among said plurality of look-up tables; and which, when executed at runtime by the second processor 21 of the execution device 2 performs the steps E1 to E2 described here above and illustrated on FIG. 4: [0078] c1) determines using said permutation P a permuted index i.sub.p of the target value X in the permuted table, [0079] c2) returns the value memorized at the permuted index in said permuted table T.sub.p.

[0080] In a third aspect, the invention also relates to the method of executing the instructions of the secure software code, as executed by the second processor 21 of the executing device 2. Said secure software code SSC is then a modified version of the unsecure software code (the software code SC) performing a sensitive operation performing accesses to a plurality of look-up tables (T.sub.0, T.sub.1, . . . T.sub.n) and comprising first sequences of instructions performing said accesses to the plurality of look-up tables (T.sub.0, T.sub.1, . . . T.sub.n), on which the method according to the first aspect described here above has been applied. During the second securing step S2 described above, the permuted table T.sub.p has been generated by applying a permutation P to a packed table T gathering said plurality of look-up tables (T.sub.0, T.sub.1, . . . T.sub.n),

[0081] As depicted on FIG. 4, when an access is performed to a target value X located at a first index i in a first look-up table among said plurality of look-up tables, said method according to the third aspect comprises the execution steps E1 to E2 described here above: [0082] c1) during the first execution step E1, the second processor 21 determines using said permutation P a permuted index i.sub.p of the target value X in the permuted table T.sub.p, [0083] c2) during the second execution step E2, the second processor 21 returns the value memorized at the permuted index in said permuted table T.sub.p.

[0084] In addition to these features, the non-transitory machine readable storage medium according to the second aspect of the invention and the method according to the third aspect of the invention may be configured for performing or may comprise any other features described here before.

[0085] As a result, the methods described above enable to securely access elements stored in LUTs without enabling an attacker to easily determine which LUT is accessed among several LUTs used in a sensitive operation, and to extract from it sensitive information.