Encryption device of a substitution-box type, and corresponding encryption method and computer program product

Technical field

0001The present description relates to a device of the Substitution-Box (S-Box) type, which is suitable for operating in a symmetric-key encryption apparatus, in particular an AES (Advanced Encryption Standard) encryption apparatus, and comprises at least one module configured for carrying out a non-linear operation in a finite field of an encryption method implemented by the encryption apparatus, the module comprising at least one reprogrammable look-up table.

0002Various embodiments may be applied to encryption of data contained in smartcards or set-top boxes.

Technological background

0003Look-up tables (LUTs), also referred to as "association tables", are data structures that enable association to any admissible combination of input data of a corresponding (not necessarily unique) configuration of output data. Normally, the use of a look-up table makes it possible to speed up operations, in so far as access to the datum in the table is faster than calculation of the datum itself.

0004Look-up tables are hence frequently used in encryption algorithms, whether hardware or software, to carry out complex calculations. For example, a look-up table, the so-called "Substitution Box" or "Sbox", is used in many symmetric-key block algorithms, in particular in the known AES encryption algorithm for implementing operations such as, for example, the SubBytes operation.

0005In order to discover the key, in particular of symmetric-key block-encryption algorithms, such as the AES algorithm, it is known to use the so-called "side-channel attacks", i.e., attacks that exploit the information that can be derived, through a so-called "leakage" process, i.e., a process of leakage of information, from physical implementation of the encryption procedure, for example by measuring the energy absorption of the circuit.

0006Several of the countermeasures against the above side-channel attacks exploit the presence of look-up tables in the circuits that implement the algorithms, performing operations of initialization of the values contained in these tables.

0007The way in which the look-up table is initialized is critical for effective protection against side-channel attacks, and it is difficult to obtain a protection from high-order attacks. In general, a side-channel attack is defined as ν-variate if it combines a number ν of time instances, for example clock cycles, of the controlled physical manifestation, and is said to be of the d-th order if it requires statistical momenta of order d to be considered for distinguishing the correct hypotheses from the erroneous ones.

0008It is known, for example, to use as countermeasure against side-channel attacks operations of linear, Boolean, masking of the data. According to this technique, each datum is masked via a Boolean XOR operation with mask values. It is convenient to incorporate also the mask values in the look-up table.

0009It is known in general to initialize a look-up table where there are input data <i>din</i>, i.e., the data that indicate the address or location of the values to be retrieved in the table, via a first input mask <i>R</i>₁ and to mask output data <i>dout</i>, i.e., the values retrieved at the address or location specified by the input data <i>din</i>, via a first output mask <i>R</i>₂. This is done by storing in the location of the look-up table corresponding to the address given by <i>din</i>⊕<i>R</i>₁, i.e., by the XOR operation between the input data <i>din</i> and the first input mask <i>R</i>₁, a value given by <i>dout</i>⊕<i>R</i>₂, i.e., by the XOR operation between the output data <i>dout</i> and the first output mask <i>R</i>₂. This is usually done one at a time for all the possible values of the input data <i>din</i> and performing the operation of storage in the look-up table of the corresponding output data.

0010The so-called "high order" side-channel attacks attack different points of the algorithm that use the same mask values so that the protection of the aforesaid mask can be removed. In general, given a mask, initialization of the look-up table with this mask and access to the masked data during computation means having at least two different operations in two different cycles that use one and the same mask, the corresponding attack thus qualifying as second-order attack.

0011In the above context, the countermeasures against high-order attacks are usually complex and are very penalizing in terms of latency time and circuit area required for their implementation. Moreover, in hardware implementations, the level of protection must be defined at the moment of design, because this affects the design itself and, as has been said, the area of the circuit to be designed. This constitutes a further complexity and drawback.

0012The foregoing is encountered in particular in AES encryption apparatuses, which, as has been said, implement S-Box devices in order to carry out operations, such as, for example, the SubBytes operation, that comprise at least one look-up table, in particular for carrying out the inversion required by the SubBytes operation.

0013The look-up table that implements the S-Box has a considerable size, and this determines a high latency, which limits the performance against side-channel attacks United States Patent Application Publication.

0014Document <patcit id="pcit0001" dnum="US2010322412A1"><text>US2010/322412 A1 to C. Hung and T. Yeh</text></patcit> discloses a device of a Substitution-Box type dealing with Galois Field computation, in the context of AES SBOX.

0015United States Patent Application Publication Document <patcit id="pcit0002" dnum="US20060093136A1"><text>US 2006/0093136 A1 to M. Zhang and A. Nemat</text></patcit>; and the <b>publication by</b><nplcit id="ncit0001" npl-type="b"><text> Wong M.M., MLD Wong, I Hijazin, AK Nandi "Composite field GF (((2 2)2)2) AES S-Box with direct computation in GF (24) inversion", Information Technology in Asia (CITA 11), 2011 7th International Conference on, IEEE, 12 July 2011, pages 1-6</text></nplcit><b>, may also be of interest for the present application.</b>

0016<nplcit id="ncit0002" npl-type="s"><text>D. Canright, "Masking a Compact AES S-box", Naval Postgraduate School, Monterey, CA 93943</text></nplcit>, discloses inversion in the sub-field and sub-subfield with masking at the data level.

Object and summary

0017The object of the embodiments described herein is to improve the potential of the methods according to the known art as set forth previously. The invention is defined in the claims.

0018Various embodiments achieve the above object thanks to a device having the characteristics specified in the ensuing claims. Various embodiments may refer also to an encryption method as likewise to a computer program product that can be loaded into the memory of at least one computer (e.g., a terminal in a network) and comprises portions of software code suitable for carrying out the steps of the method when the program is run on at least one computer. As used herein, the aforesaid computer program product is understood as being equivalent to a computer-readable medium containing instructions for control of the computer system so as to co-ordinate execution of the method according to the invention. Reference to "at least one computer" is meant to highlight the possibility of the present invention being implemented in a modular and/or distributed form. The claims form an integral part of the technical teachings provided herein in relation to the invention.

0019Various embodiments may envisage use of the invention in S-Box devices for AES encryption. Various embodiments may envisage that the above S-Box uses a look-up-table structure with tower-of-field architecture. Various embodiments may envisage that the above S-Box uses a look-up-table structure implemented via flip-flops to enable fast execution. Various embodiments may envisage that the above S-Box executes, in a single clock cycle, steps of masking of the aforesaid look-up tables.

Brief description of the drawings

0020Various embodiments will now be described, purely by way of example, with reference to the annexed figures, wherein: <ul id="ul0001" list-style="dash" compact="compact"><li><figref idref="f0001">Figures 1a and 1b</figref> show blocks diagrams illustrating the method according to the invention;</li><li><figref idref="f0002">Figures 2a and 2b</figref> show blocks diagrams illustrating application of the method according to the invention to AES encryption;</li><li><figref idref="f0003">Figure 3</figref> shows a block diagram illustrating details corresponding to the application of <figref idref="f0002">Figure 2b</figref>;</li><li><figref idref="f0004">Figure 4</figref> shows a known block diagram of an S-Box device;</li><li><figref idref="f0005">Figure 5</figref> shows a look-up table used in the device of <figref idref="f0004">Figure 4</figref>;</li><li><figref idref="f0006">Figure 6</figref> shows a block diagram illustrating details of the device of <figref idref="f0005">Figure 5</figref>;</li><li><figref idref="f0007">Figure 7</figref> shows a block diagram of a device according to the invention;</li><li><figref idref="f0008">Figure 8</figref> shows a block diagram illustrating details of the device of <figref idref="f0007">Figure 7</figref>;</li><li><figref idref="f0009">Figure 9a</figref> shows a circuit implementation of an element of the device according to the known art; and</li><li><figref idref="f0010">Figure 9b</figref> shows a circuit implementation of an element of the device according to the invention.</li></ul>

Detailed description

0021In the ensuing description, numerous specific details are provided in order to facilitate as much as possible understanding of the embodiments provided by way of example. The embodiments may be implemented with or without specific details, or else with other methods, components, materials, etc. In other cases, structures, materials, or operations that are well known are not shown or described in detail so that aspects of the embodiments will not be obscured. Reference in the framework of the present description to "an embodiment" or "one embodiment" means that a given peculiarity, structure, or characteristic described in connection with the embodiment is comprised in at least one embodiment. Hence, recurrence of phrases such as "in an embodiment" or "in one embodiment" in various points of the present description does not necessarily refer to one and the same embodiment. Moreover, the peculiarities, structures, or characteristics may be combined in any convenient way in one or more embodiments.

0022The notations and references are here provided only for convenience of the reader and do not define the scope or the meaning of the embodiments.

0023The solution according to the invention envisages in general a device of a Substitution-Box (S-Box) type suitable for operating in a symmetric-key block-encryption apparatus, preferably an AES (Advanced Encryption Standard) encryption apparatus, which comprises a module configured for carrying out a non-linear operation in a finite field of an encryption method, specifically the inversion of the SubBytes operation in the AES finite field, implemented by the encryption apparatus, for example the apparatus of a set-top box, where the aforesaid module comprises a plurality of composite look-up tables that implement the above non-linear operation in a composite field that derives from the finite field, each of the composite look-up tables being smaller than a single look-up table that is to implement autonomously the non-linear operation in a finite field, in particular smaller than the look-up table normally used for carrying out inversion of the SubBytes operation.

0024There now follows a preliminary description of a preferred context of operation of the above S-Box device according to the invention, in which it is envisaged to carry out an encryption procedure, which, for defence against side-channel attacks, adopts a strategy of initialization of the look-up table via masking. This context, the corresponding method of which forms the subject of a parallel co-pending application filed in the name of the present applicant, envisages carrying out an operation of initialization of the look-up table by masking via a first input mask the data at input to the look-up table and with a first output mask the data at output from the look-up table. It is then envisaged to re-initialize the look-up table via the steps of providing a second input mask and a second output mask, and computing the values of re-initialization of the look-up table as a function of a logic combination of the values of the first and second input masks and of a logic combination of the values of the first and second output masks. As has been said, the above initialization operations are preferably carried out on one or more of the composite look-up tables of the S-Box device according to the invention, which will be described in greater detail in what follows with reference to <figref idref="f0004 f0005 f0006 f0007 f0008 f0009 f0010">Figures 4-9</figref>.

0025With reference to <figref idref="f0001">Figures 1a and 1b</figref>, there is hence now described in greater detail the above operating context, which specifically envisages a protection from side-channel attacks that comprises an initialization procedure 100, which envisages writing initialization values in the look-up table, applying at least two successive initialization steps, 110 and 120.

0026With reference to <figref idref="f0001">Figure 1a</figref>, represented therein is the step of initialization 110 of a look-up table 50, for example the look-up table of an S-Box for implementing AES encryption. The reference 110 designates the initialization operations, i.e., the operations of writing in the look-up table 50.

0027In the framework of the above initialization operation 110, first-initialization output data <i>dout_ref</i> are sent at input to the look-up table 50, where they are combined, in an XOR block 110a, with the first output mask <i>R</i>₂, in order to produce masked output data <i>dout_mask.</i>

0028These masked output data <i>dout_mask</i> are written in the look-up table 50 at a masked input datum, or, address, <i>din_mask</i>, which is in turn obtained from a first-initialization address <i>din_ref</i> combined in an XOR block 110b with the first input mask <i>R</i>₁.

0029The masked output data <i>dout_mask</i> = <i>dout_ref</i> ⊕ <i>R</i>₂ are written in the look-up table 50 at the masked addresses <i>din_mask</i> = <i>din</i>⊕ <i>R</i>₁ according to the formula <maths id="math0001" num="(1)"><math display="block"><mi mathvariant="italic">dou</mi><msub><mi>t</mi><mi mathvariant="italic">mask</mi></msub><mo>=</mo><mi>F</mi><mfenced separators=""><mi mathvariant="italic">di</mi><msub><mi>n</mi><mi mathvariant="italic">mask</mi></msub><mo>⊕</mo><msub><mi>R</mi><mn>1</mn></msub></mfenced><mo>⊕</mo><msub><mi>R</mi><mn>2</mn></msub></math><img file="EP2928112B1_D0001.tif" /></maths> where F is a generic function <i>F</i>(<i>x</i>) implemented via the look-up table 50; in the case provided by way of example, <i>F</i>(<i>x</i>) may correspond to <i>S-Box</i>(<i>x</i>), more specifically to one of the suboperations that constitute the inversion, for example the inversion in <i>GF</i>(2⁴)<i>.</i> If the look-up table 50 were not subject to masking, its content would simply correspond to the function <i>F</i>(<i>x</i>) applied to the inputs. We denote in what follows by <i>LUT</i>⁰ the function implemented by the masked look-up table, which supplies the masked output data <i>dout_mask.</i>

0030The first-initialization output data <i>dout_ref</i> and the first-initialization addresses <i>din_ref</i> are plaintext data that usually come from a reference table that implements the function <i>F</i> (see also in this regard blocks 420-423 in <figref idref="f0009">Figure 9a</figref>, described in the sequel of the present disclosure).

0031The reference 130 designates, instead, an operation of reading of the data; by accessing the look-up table 50 with the masked address <i>din_mask</i>, it returns the output <maths id="math0002" num="(2)"><math display="block"><mi mathvariant="italic">dou</mi><msub><mi>t</mi><mi mathvariant="italic">mask</mi></msub><mo>=</mo><mi mathvariant="italic">LU</mi><msup><mi>T</mi><mn>0</mn></msup><mfenced separators=""><mi mathvariant="italic">di</mi><msub><mi>n</mi><mi mathvariant="italic">mask</mi></msub></mfenced></math><img file="EP2928112B1_D0002.tif" /></maths>

0032<figref idref="f0001">Figure 1b</figref> shows, instead, an operation of sequential initialization 120, or re-initialization, that is carried out after the first initialization 110. It is, in fact, envisaged to define a second input mask <maths id="math0003" num=""><math display="inline"><msubsup><mi>R</mi><mn>1</mn><mo>′</mo></msubsup></math><img file="EP2928112B1_D0003.tif" /></maths> and a second output mask <maths id="math0004" num=""><math display="inline"><msubsup><mi>R</mi><mn>2</mn><mo>′</mo></msubsup><mo>,</mo></math><img file="EP2928112B1_D0004.tif" /></maths> and to evaluate a combination of input masks Δ₁ as XOR operation between the first input mask <i>R</i>₁ and the second input mask <maths id="math0005" num=""><math display="inline"><msubsup><mi>R</mi><mn>1</mn><mo>′</mo></msubsup><mo>,</mo></math><img file="EP2928112B1_D0005.tif" /></maths><maths id="math0006" num=""><math display="inline"><msub><mi mathvariant="normal">Δ</mi><mn>1</mn></msub><mo>=</mo><msubsup><mi>R</mi><mn>1</mn><mo>′</mo></msubsup><mo>⊕</mo><msub><mi>R</mi><mn>1</mn></msub><mo>,</mo></math><img file="EP2928112B1_D0006.tif" /></maths> as well as to evaluate a combination of output masks Δ₂ as XOR operation between the first output mask <i>R</i>₂ and the second output mask <maths id="math0007" num=""><math display="inline"><msubsup><mi>R</mi><mn>2</mn><mo>′</mo></msubsup><mo>,</mo></math><img file="EP2928112B1_D0007.tif" /></maths><maths id="math0008" num=""><math display="inline"><msub><mi mathvariant="normal">Δ</mi><mn>2</mn></msub><mo>=</mo><msubsup><mi>R</mi><mn>2</mn><mo>′</mo></msubsup><mo>⊕</mo><msub><mi>R</mi><mn>2</mn></msub></math><img file="EP2928112B1_D0008.tif" /></maths> according to the formula <maths id="math0009" num="(3)"><math display="block"><mi mathvariant="italic">dou</mi><msubsup><mi>t</mi><mi mathvariant="italic">mask</mi><mo>′</mo></msubsup><mo>=</mo><mi mathvariant="italic">LU</mi><msup><mi>T</mi><mn>0</mn></msup><mfenced separators=""><mi mathvariant="italic">di</mi><msubsup><mi>n</mi><mi mathvariant="italic">mask</mi><mo>′</mo></msubsup><mo>⊕</mo><mfenced separators=""><msubsup><mi>R</mi><mn>1</mn><mo>′</mo></msubsup><mo>⊕</mo><msub><mi>R</mi><mn>1</mn></msub></mfenced></mfenced><mo>⊕</mo><mfenced separators=""><msubsup><mi>R</mi><mn>2</mn><mo>′</mo></msubsup><mo>⊕</mo><msub><mi>R</mi><mn>2</mn></msub></mfenced></math><img file="EP2928112B1_D0009.tif" /></maths> Consequently, once the initialization step 110 has been carried out, instead of repeating the same step 110 and simply using the new, or second, input and output masks <maths id="math0010" num=""><math display="inline"><msubsup><mi>R</mi><mn>1</mn><mo>′</mo></msubsup></math><img file="EP2928112B1_D0010.tif" /></maths> and <maths id="math0011" num=""><math display="inline"><msubsup><mi>R</mi><mn>2</mn><mo>′</mo></msubsup></math><img file="EP2928112B1_D0011.tif" /></maths> for generating a new masked look-up table, the new content <i>LUT'</i> of the table 50 is generated starting from the previous version according to step 120, i.e., the content <i>LUT</i>⁰ deriving from the operation 110, reading in the aforesaid content <i>LUT</i>⁰ of the previous look-up table for each of the possible addresses that can be generated <i>din_mask</i> = <i>din_ref</i> ⊕ <i>R</i>₁ the corresponding value stored, which, for what has been said, is <i>dout_mask</i> = <i>dout_ref</i> ⊕ <i>R</i>₂. Starting from the masked input datum <i>din_mask</i> = <i>din_ref</i> ⊕ <i>R</i>₁, a new masked input datum <i>din'_mask</i> = <i>din_mask</i> ⊕Δ₁ is generated, where <maths id="math0012" num=""><math display="inline"><msub><mi mathvariant="normal">Δ</mi><mn>1</mn></msub><mo>=</mo><msubsup><mi>R</mi><mn>1</mn><mo>′</mo></msubsup><mo>⊕</mo><msub><mi>R</mi><mn>1</mn></msub><mo>.</mo></math><img file="EP2928112B1_D0012.tif" /></maths> It should be noted how, if all the terms are rendered explicit, the new masked input datum <i>din'_mask</i> = <i>din_mask</i> ⊕ Δ₁ will involve cancelling out of the contribution of the first, or past, input mask <i>R</i>₁, there remaining only the contribution of the second, or new, input mask <maths id="math0013" num=""><math display="inline"><msubsup><mi>R</mi><mn>1</mn><mo>′</mo></msubsup><mo>,</mo></math><img file="EP2928112B1_D0013.tif" /></maths> so that <maths id="math0014" num=""><math display="inline"><mi mathvariant="italic">din</mi><msub><mo>′</mo><mi mathvariant="italic">mask</mi></msub><mo>=</mo><mi mathvariant="italic">di</mi><msub><mi>n</mi><mi mathvariant="italic">ref</mi></msub><mo>⊕</mo><msubsup><mi>R</mi><mn>1</mn><mo>′</mo></msubsup><mo>.</mo></math><img file="EP2928112B1_D0014.tif" /></maths>

0033Likewise, starting from the masked output datum <i>dout_mask</i> = <i>dout_ref</i> ⊕ <i>R</i>₂, a new masked output datum <i>dout'_mask</i> = <i>dout_mask</i> ⊕ Δ₂ is obtained, where <maths id="math0015" num=""><math display="inline"><msub><mi mathvariant="normal">Δ</mi><mn>2</mn></msub><mo>=</mo><msubsup><mi>R</mi><mn>2</mn><mo>′</mo></msubsup><mo>⊕</mo><msub><mi>R</mi><mn>2</mn></msub><mo>,</mo></math><img file="EP2928112B1_D0015.tif" /></maths> with a corresponding cancelling out of the contribution of the first, or past, output mask <i>R</i>₂, there remaining just the contribution of the second, or new, output mask <maths id="math0016" num=""><math display="inline"><msubsup><mi>R</mi><mn>2</mn><mo>′</mo></msubsup><mo>,</mo></math><img file="EP2928112B1_D0016.tif" /></maths> so that <maths id="math0017" num=""><math display="inline"><mi mathvariant="italic">dout</mi><msub><mo>′</mo><mi mathvariant="italic">mask</mi></msub><mo>=</mo><mi mathvariant="italic">dou</mi><msub><mi>t</mi><mi mathvariant="italic">ref</mi></msub><mo>⊕</mo><msubsup><mi>R</mi><mn>2</mn><mo>′</mo></msubsup><mo>.</mo></math><img file="EP2928112B1_D0017.tif" /></maths>

0034The new masked output datum <i>dout'_mask</i> is stored as new content <i>LUT'</i> of the look-up table 50 at the address corresponding to the new masked input datum, or address, <i>din'_mask.</i> This new content <i>LUT'</i> of the look-up table 50 is based only upon the content of the second, or new, masks, namely, the input mask <maths id="math0018" num=""><math display="inline"><msubsup><mi>R</mi><mn>1</mn><mo>′</mo></msubsup></math><img file="EP2928112B1_D0018.tif" /></maths> and the output mask <maths id="math0019" num=""><math display="inline"><msubsup><mi>R</mi><mn>2</mn><mo>′</mo></msubsup><mo>,</mo></math><img file="EP2928112B1_D0019.tif" /></maths> as follows: <maths id="math0020" num="()4"><math display="block"><mi mathvariant="italic">dou</mi><msubsup><mi>t</mi><mi mathvariant="italic">mask</mi><mo>′</mo></msubsup><mo>=</mo><mi>F</mi><mfenced separators=""><mi mathvariant="italic">di</mi><msubsup><mi>n</mi><mi mathvariant="italic">mask</mi><mo>′</mo></msubsup><mo>⊕</mo><mfenced><msubsup><mi>R</mi><mn>1</mn><mo>′</mo></msubsup></mfenced></mfenced><mo>⊕</mo><mfenced><msubsup><mi>R</mi><mn>2</mn><mo>′</mo></msubsup></mfenced></math><img file="EP2928112B1_D0020.tif" /></maths>

0035Consequently, at output from the look-up table 50, we obtain in a reading operation 140, for a given address specified by input data <maths id="math0021" num=""><math display="inline"><mi mathvariant="italic">di</mi><msubsup><mi>n</mi><mi mathvariant="italic">mask</mi><mo>′</mo></msubsup></math><img file="EP2928112B1_D0021.tif" /></maths><maths id="math0022" num="(5)"><math display="block"><mi mathvariant="italic">dou</mi><msubsup><mi>t</mi><mi mathvariant="italic">mask</mi><mo>′</mo></msubsup><mo>=</mo><mi mathvariant="italic">LUT</mi><mo>′</mo><mfenced separators=""><mi mathvariant="italic">di</mi><msubsup><mi>n</mi><mi mathvariant="italic">mask</mi><mo>′</mo></msubsup></mfenced></math><img file="EP2928112B1_D0022.tif" /></maths>

0036In this way, it may be appreciated how the side-channel of each initialization operation provided by step 120 will be linked to the combination of masks <maths id="math0023" num=""><math display="inline"><msub><mi mathvariant="normal">Δ</mi><mn>1</mn></msub><mo>=</mo><msubsup><mi>R</mi><mn>1</mn><mo>′</mo></msubsup><mo>⊕</mo><msub><mi>R</mi><mn>1</mn></msub></math><img file="EP2928112B1_D0023.tif" /></maths> rather than to the second input mask <maths id="math0024" num=""><math display="inline"><msubsup><mi>R</mi><mn>1</mn><mo>′</mo></msubsup></math><img file="EP2928112B1_D0024.tif" /></maths> alone, whereas the datum is masked by the second input mask <maths id="math0025" num=""><math display="inline"><msubsup><mi>R</mi><mn>1</mn><mo>′</mo></msubsup></math><img file="EP2928112B1_D0025.tif" /></maths> alone. The same applies to the output datum and the mask <maths id="math0026" num=""><math display="inline"><msubsup><mi>R</mi><mn>2</mn><mo>′</mo></msubsup><mo>.</mo></math><img file="EP2928112B1_D0026.tif" /></maths> A high-order attack would thus require three elements: the data masked by the second input mask <maths id="math0027" num=""><img file="EP2928112B1_D0027.tif" /></maths> the operation of initialization that involves the combination of masks <maths id="math0028" num=""><math display="inline"><msub><mi mathvariant="normal">Δ</mi><mn>1</mn></msub><mo>=</mo><msubsup><mi>R</mi><mn>1</mn><mo>′</mo></msubsup><mo>⊕</mo><msub><mi>R</mi><mn>1</mn></msub><mo>,</mo></math><img file="EP2928112B1_D0028.tif" /></maths> and at least some other operation that involves the first input mask <i>R</i>₁ alone.

0037The procedure has been described, with reference to <figref idref="f0001">Figures 1a and 1b</figref>, only as regards a first initialization 110 and a re-initialization 120, but it is clear that it can be extended iteratively, using more than two masks.

0038For example, it is possible to carry out an initialization at step 110 with the first input mask <i>R</i>₁, a second initialization at step 120 with a combination of the first mask <i>R</i>₁ and of the second mask <maths id="math0029" num=""><math display="inline"><msubsup><mi>R</mi><mn>1</mn><mo>′</mo></msubsup></math><img file="EP2928112B1_D0029.tif" /></maths><maths id="math0030" num=""><math display="inline"><msubsup><mi>R</mi><mn>1</mn><mo>′</mo></msubsup><mo>⊕</mo><msub><mi>R</mi><mn>1</mn></msub><mo>,</mo></math><img file="EP2928112B1_D0030.tif" /></maths> a third initialization at step 120 with a combination of the second mask <maths id="math0031" num=""><math display="inline"><msubsup><mi>R</mi><mn>1</mn><mo>′</mo></msubsup></math><img file="EP2928112B1_D0031.tif" /></maths> and of a third mask <maths id="math0032" num=""><math display="inline"><msubsup><mi>R</mi><mn>1</mn><mo>"</mo></msubsup><mo>,</mo></math><img file="EP2928112B1_D0032.tif" /></maths><maths id="math0033" num=""><math display="inline"><msubsup><mi>R</mi><mn>1</mn><mo>"</mo></msubsup><mo>⊕</mo><msubsup><mi>R</mi><mn>1</mn><mo>′</mo></msubsup><mo>,</mo></math><img file="EP2928112B1_D0033.tif" /></maths> a fourth initialization at step 120 with a combination of the third mask <maths id="math0034" num=""><math display="inline"><msubsup><mi>R</mi><mn>1</mn><mo>"</mo></msubsup></math><img file="EP2928112B1_D0034.tif" /></maths> and of a fourth mask <maths id="math0035" num=""><math display="inline"><msubsup><mi>R</mi><mn>1</mn><mo>‴</mo></msubsup><mo>,</mo></math><img file="EP2928112B1_D0035.tif" /></maths><maths id="math0036" num=""><math display="inline"><msubsup><mi>R</mi><mn>1</mn><mo>‴</mo></msubsup><mo>⊕</mo><msubsup><mi>R</mi><mn>1</mn><mo>"</mo></msubsup><mo>.</mo></math><img file="EP2928112B1_D0036.tif" /></maths> The look-up table would then be used for calculations on masked data via the fourth mask <maths id="math0037" num=""><math display="inline"><msubsup><mi>R</mi><mn>1</mn><mo>‴</mo></msubsup><mo>.</mo></math><img file="EP2928112B1_D0037.tif" /></maths> A side-channel attack would in this case require operating on the latter fourth-initialization operation, as well as on all the previous initializations, from the first to the third.

0039It should be noted that in general the method, also in the embodiment described with reference to <figref idref="f0001">Figure 1a and 1b</figref>, may be considered as comprising iteration of an initialization step in which the first masks <i>R</i>₁ and <i>R</i>₂ are set to zero, i.e., the case where the table at start is not masked.

0040The method envisages in general choosing the given number of steps of iteration, i.e., the number of times of execution, of the operation 120 of initialization at the moment of run-time, without requiring any further hardware, simply applying a criterion of trade-off between performance and level of protection.

0041There now follows a more detailed description of an implementation of the method of <figref idref="f0001">Figures 1a and 1b</figref> within an AES encryption procedure.

0042<figref idref="f0002">Figure 2a</figref> shows an implementation 200 of the AES encryption procedure. The steps represented constitute the steps for encryption of a 16-byte block, known as AES state. This procedure 200, as likewise the details of the operations 210, 220, 230, 240 are known to a person skilled in the sector (see, for example, the document available at the URL http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf <u>http://en.wikipedia.org/wiki/Advanced Encryption Standa rd</u>)

0043The AES state to be encrypted, designated by A, is subjected to a first SubBytes operation 210, supplying at output a state B, which is subjected to a set 220 of operations ShiftRows + MixColumns + AddKey, to generate a state C. The operations 210, 220 correspond to a first round. Then, in a next round, a second SubBytes operation 230 is carried out, to obtain a state D, as well as a further set 230 of operations ShiftRows + MixColumns + AddKey, to generate a state D. There is carried out a number of rounds envisaged by the procedure 200 according to the number of corresponding round subkeys to be added. The various modes of handling of the AES rounds are in any case in themselves known to a person skilled in the sector.

0044As has been said, the SubBytes operation 210 or 230, which contains a non-linear portion, as will be described in greater detail in what follows, is carried out with the aid of a Substitution Box, or S-Box, which comprises a look-up table.

0045Prior to start of the AES encryption procedure 200 an initial setting of the S-Box is envisaged that serves as base for initialization via the combinations of masks Δ, of the type carried out in step 110 described previously. The masks according to the method are hence applied to the plaintext (i.e., the initial unencrypted AES state).

0046During execution of a round, the S-Box (or S-Boxes where a plurality of them is present) is set with the real masks that have been applied to the AES state via the combinations of masks Δ (initialization 120), and the computation envisaged in steps 210 and 220 is then carried out. This is performed at each round.

0047At the end of the AES encryption procedure 200, the masked S-Boxes are released by carrying out an operation that is the reverse of that of the initial setup, and the masks are removed from the ciphertext that is the product of the AES encryption procedure 200.

0048During the AES encryption procedure 200, the SubBytes operation at step 210 or 230 is calculated by itself; hence, the look-up table of the S-Box is initialized just before each use so that the table will incorporate the masks applied to the datum that is to be processed, which in general may differ from one datum to another.

0049It is possible to carry out a number of initializations of the look-up table of the S-Box between two consecutive uses in order to separate the masks associated thereto.

0050This increases protection against side-channel attacks, given that the possibility of leakage towards a side channel depends upon the sequence of combinations of masks Δ.

0051These operations of multiple initializations are carried out also during initial setup and at the end of the procedure for final release of the ciphertext. As for the sequence of multiple initializations, the initial setup envisages applying in sequence combinations of masks Δ to the plaintext in such a way as to obtain, upon completion of this step, the AES state protected by just one real mask, i.e., a mask effectively stored in the system unlike the combinations of masks, without this mask having ever been used. Likewise, at the end of the procedure, the real mask is removed from the ciphertext using only combinations of masks Δ, and never directly the real mask.

0052In order to prevent leakage due to the single masks, just the combinations of masks Δ are generated and passed on for processing, just the combinations of masks Δ are stored in registers, and just the combinations of masks Δ are used for initialization of the look-up table or tables.

0053<figref idref="f0002">Figure 2b</figref> shows the masks applied by the method with reference to the same encryption procedure 200 as that of <figref idref="f0002">Figure 2a</figref>.

0054For input to the S-Box (1-byte input of 16-byte AES states), input masks <i>L</i> are provided for masking in the first round (steps 210-220), and the input masks <i>N</i> are provided for masking in the second round (steps 230-240). Output masks <i>M</i> are provided for masking in the first round (steps 210-220), and output masks <i>O</i> are provided for masking in the second round (steps 230-240).

0055In this regard, it is possible to consider re-employing the masks to minimize their number using, for example, the following criterion: a distance of two rounds between two values associated to one and the same mask.

0056<figref idref="f0003">Figure 3</figref> shows the masks, of 1 byte each, for initialization of each S-Box prior to the procedure 200. The size of the masks in this step depends upon how many S-Boxes are present. Hence, with 16 S-Boxes there will be 16 bytes for each mask, but with just one S-Box there will be 1 byte for each mask. Input masks <i>R</i>, <i>S</i> are used for the initial setup and final release, and output masks <i>T</i>, <i>U</i> are used for the initial setup and final release.

0057As shown in <figref idref="f0003">Figure 3</figref>, in a step 310 initialization of the input and of the output with the setup masks R (input mask) and T (output mask) is carried out. Next, in a step 320 an initialization of the table is carried out via the combination of the setup mask R (input mask) with the mask <i>S</i> (input mask). The same is performed on the output using the setup masks <i>T</i> and <i>U</i>. Next, a further initialization step 330 is carried out with the input mask <i>L</i> and the output mask <i>M</i>, shown with reference to <figref idref="f0002">Figure 2B</figref>, by combining them with the setup masks <i>S</i> and <i>U</i>. The operation 210 of the first round, in which the data are masked by the masks <i>L</i> and <i>M</i>, is then performed.

0058Hence, with reference to what is shown in <figref idref="f0003">Figure 3</figref>, as regards the first two rounds of the AES encryption algorithm in the example in which there is envisaged re-use of the masks every two rounds, the following 16-byte values are generated and stored, which are then also used for initialization of the S-Boxes: <maths id="math0038" num=""><math display="block"><mi mathvariant="normal">α</mi><mo>=</mo><mi>M</mi><mo>⊕</mo><mi>O</mi></math><img file="EP2928112B1_D0038.tif" /></maths><maths id="math0039" num=""><math display="block"><mi mathvariant="normal">β</mi><mo>=</mo><mi>B</mi><mo>⊕</mo><mi>M</mi></math><img file="EP2928112B1_D0039.tif" /></maths><maths id="math0040" num=""><math display="block"><mi mathvariant="normal">γ</mi><mo>=</mo><mi>T</mi><mo>⊕</mo><mi>U</mi></math><img file="EP2928112B1_D0040.tif" /></maths><maths id="math0041" num=""><math display="block"><mi mathvariant="normal">δ</mi><mo>=</mo><mi>T</mi></math><img file="EP2928112B1_D0041.tif" /></maths><maths id="math0042" num=""><math display="block"><mi mathvariant="normal">ε</mi><mo>=</mo><mi>R</mi><mo>⊕</mo><mi>S</mi></math><img file="EP2928112B1_D0042.tif" /></maths><maths id="math0043" num=""><math display="block"><mi mathvariant="normal">ζ</mi><mo>=</mo><mi>R</mi></math><img file="EP2928112B1_D0043.tif" /></maths>

0059As may be noted, except for the initial masks <i>R</i> and <i>T</i>, only combinations of two logic values are generated and stored. For example, the logic value of the mask <i>M</i> that protects the AES state is never generated alone, is never stored alone, and is never used alone to initialize the S-Boxes. This ensures that the side-channel information produced by handling of the values listed above will never be associated to a single mask, but to combinations of masks, which also contribute to the need to gather various points to carry out an attack.

0060In order to maintain consistency between the masks applied to the data during the linear part of the algorithm, indicated by blocks 220 and 240 in <figref idref="f0002">Figure 2</figref>, further values can be calculated starting from the ones introduced previously, as follows: <maths id="math0044" num=""><math display="block"><mi mathvariant="normal">η</mi><mo>=</mo><mi>S</mi><mo>⊕</mo><mi>L</mi><mo>=</mo><mi mathvariant="italic">MixCols</mi><mfenced separators=""><mi mathvariant="normal">α</mi><mo>⊕</mo><mi mathvariant="normal">β</mi></mfenced><mo>⊕</mo><mfenced open="[" close="]" separators=""><mi mathvariant="normal">ε</mi><mo>⊕</mo><mi mathvariant="italic">MixCols</mi><mfenced><mi mathvariant="normal">γ</mi></mfenced></mfenced><mo>⊕</mo><mfenced open="[" close="]" separators=""><mi mathvariant="normal">ζ</mi><mo>⊕</mo><mi mathvariant="italic">MixCols</mi><mfenced><mi mathvariant="normal">δ</mi></mfenced></mfenced></math><img file="EP2928112B1_D0044.tif" /></maths><maths id="math0045" num=""><math display="block"><mi mathvariant="normal">θ</mi><mo>=</mo><mi>L</mi><mo>⊕</mo><mi>N</mi><mo>=</mo><mi mathvariant="italic">MixCols</mi><mfenced><mi mathvariant="normal">α</mi></mfenced></math><img file="EP2928112B1_D0045.tif" /></maths> where: <maths id="math0046" num=""><math display="block"><mi>L</mi><mo>=</mo><mi mathvariant="italic">MixCols</mi><mfenced><mi>O</mi></mfenced></math><img file="EP2928112B1_D0046.tif" /></maths><maths id="math0047" num=""><math display="block"><mi>N</mi><mo>=</mo><mi mathvariant="italic">MixCols</mi><mfenced><mi>M</mi></mfenced></math><img file="EP2928112B1_D0047.tif" /></maths>

0061As may be noted, the values to be derived for use of the masks in the linear part of the algorithm are also calculated starting from combinations of two or more logic values, given that the operations to be performed are linear. This ensures that also the side-channel information produced by computation of these values will never be associated to a single mask, but to combinations of masks.

0062From what has been described so far, it emerges clearly how the method envisages carrying out frequent initializations of the look-up tables.

0063The time of latency involved in an operation of initialization depends upon the size of the look-up table and limits both the performance and the efficiency of the countermeasures against side-channel attacks.

0064In hardware implementations, for requirements linked to the area of the circuits, the look-up tables are usually implemented via a reprogrammable memory such as, for example, a RAM. The RAM must be filled for initialization by entering one datum at a time, as has been mentioned, entering all the possible input values and storing the respective output values at the corresponding addresses. Hence, it emerges clearly how the latency required depends upon the size of the look-up table (for example, 256 input data for the AES S-Box).

0065Whenever the mask changes, the look-up table must be initialized with that mask.

0066Known countermeasures envisage: <ul id="ul0002" list-style="dash" compact="compact"><li>initializing the look-up table before each operation as completely new masks and hence paying the price of all the latencies associated to these operations; or</li><li>reusing the same masks for different operations and data, rendering, however, the process more vulnerable to high-order side-channel attacks.</li></ul>

0067In implementations that present constraints, for example, of area or of memory size available, a single look-up table is shared between all the bytes of the data, rendering even more evident the disadvantage deriving from initialization.

0068In the light of the initialization operations, in particular in the context of the masking procedure described, the countermeasures against multi-variate high-order attacks require a look-up table that enables: <ul id="ul0003" list-style="dash" compact="compact"><li>initialization of the entire table preferably in a single cycle, generating all the data to be entered and storing them in the same cycle; it should be noted that it is also possible to carry out implementations that operate on a greater number of cycles; the example itself described herein can be used on a number of cycles if the latency due to the initialization operations is accepted; and</li><li>initialization via the combination of masks Δ; in this way, the leakage that may possibly be analysed for a side-channel attack is correlated to the combination of masks Δ and not to the masks proper.</li></ul>

0069Consequently, to meet the need of balancing performance and efficiency in carrying out the initialization operations, in particular the operations of the method described above, which involves repeated initialization operations, according to the invention an S-Box device is here proposed that has a specific structure of look-up table, in particular the look-up table that implements the function required for the AES S-Box.

0070According to the invention, a device is proposed comprising a look-up table, wherein said look-up table is divided into smaller look-up tables, referred to as "composite look-up tables", in particular applying the so-called "tower of fields" architecture. The modes of implementation of this architecture with respect to the AES S-Box are in themselves known, in so far as it is known to use the tower-of-fields architecture for reducing the area occupation of the AES S-Box when it is implemented using pure combinational logic.

0071Via the operation of division of the look-up table into smaller tables, it becomes possible to replace the RAM normally used as reprogrammable memory with flip-flop memory structures, in particular structures that define memory registers. This thus makes it possible to write all the registers in a single clock cycle and consequently carry out initialization of the entire look-up table, in particular of the entire S-Box, in a single clock cycle.

0072Moreover, as will be described in what follows, implementation of the operations in subfields by the look-up tables ensures freedom of regulation of the tables in order to improve the properties thereof required for an effective protection against side-channel attacks.

0073In this way, advantageously, the countermeasures against side-channel attacks may have a lower impact on the performance of the encryption system, whereas the countermeasures against high-order attacks of the method illustrated in <figref idref="f0001">Figures 1a, 1b</figref> are, instead, possible also in devices that present a limitation in regard to the area available.

0074In general, with the device comprising look-up tables according to the invention, the designer has a greater freedom in devising implementation of the tables, in so far as they are no longer linked to the structure of the RAM cell, and a greater freedom in defining the scheme of the countermeasure, in so far as the disadvantage deriving from execution of the initialization operations is removed.

0075The device comprising look-up tables proposed herein can moreover be exploited also for countermeasures in regard to so-called "fault attacks", i.e., attacks with injection of faults.

0076There now follows a more detailed description of the device comprising an S-Box according to the invention.

0077It is envisaged to implement the S-Box isolating the non-linear part of the multiplicative inversion in the finite field, and performing it via finite subfields.

0078The S-Box device, which normally operates on the specific Galois field <i>GF</i>(2⁸) described in the FIPS197 standard cited above, is implemented via decomposition into smaller finite fields, <i>GF</i>(2⁴)² and <i>GF</i>((2²)²)²<i>.</i>

0079More precisely, the above operation of composition envisages: <ol id="ol0001" compact="compact" ol-style=""><li>a) mapping all the elements of the Galois field <i>GF</i>(2⁸) over the composite field using an isomorphism;</li><li>b) computing the multiplying inverse in the composite field; and</li><li>c) mapping the results of the above computation over the Galois field <i>GF</i>(2⁸), using the inverse of the isomorphism used for decomposition.</li></ol>

0080As has been said, the procedure of decomposition into smaller finite fields is in itself known and for any detail the reader is referred, for example, to the paper by <nplcit id="ncit0003" npl-type="s" url="http://class.ece.iastate.edu/tyagi/cpre681/papers/satoh asiacryptt.pdf"><text>Satoh et al. "A Compact Rijndael Hardware Architecture with S-Box Optimization", sect. 4.1-4.3, pp. 245-248 available at the URL http://class.ece.iastate.edu/tyagi/cpre681/papers/satoh asiacryptt.pdf</text></nplcit>. In particular, for the steps a) and c), by way of example, it is possible to use the isomorphism described on page 248, Eq. 13, and for step b) Eqs. 9, 10, 11 on page 247.

0081It is envisaged to implement this approach in an extended way to the look-up tables, in particular reprogrammable look-up tables, in order to maintain the hardware compact.

0082In particular, according to the invention, it is envisaged to replace the single 256x8 look-up table used in the S-Box with a plurality of smaller reprogrammable look-up tables.

0083As shown in <figref idref="f0004">Figure 4</figref>, an S-Box 10 presents to the input data <i>din</i>[8], which specify an 8-bit address, two computation modules, a module 11 for performing a non-linear operation, in particular inversion of the SubBytes operation, and a module 12 for performing a linear operation, specifically the affine transformation of the SubBytes operation. This module 11 is the main reason why the implementation of the S-Box device comprises at least one look-up table. The module 11 for performing a non-linear operation supplies its own output data <i>dout</i>[8], with the result of the inversion, to the module 12 for performing a linear operation, specifically the affine transformation of the SubBytes operation. The module 12 supplies at output the output data of the S-Box <i>sbox_dout</i>[8], i.e., the input data <i>din</i>[8] on which the SubBytes operation has been carried out. In the above module 12 it is possible to maintain the additive masking, as is applies in a known way in the KeyAddition and MixColumns operations.

0084The inventive idea is instead, as has been said, applied in particular in a look-up table in the module 11 for implementing the inversion.

0085<figref idref="f0004">Figure 4</figref> represents the scheme for the direct S-Box function alone, used for AES encryption. In the case of decryption, the inverse function is necessary, called <i>Sbox</i>^-1<i>.</i> As shown in the paper by Satoh <i>et al.</i> referred to previously, it is possible to re-use the same inversion of block 11 for both functions by adding a further block for the inverse function of the affine transformation. This solution is represented in <figref idref="f0005">Figure 5</figref> on page 246 of the paper cited. It is thus clear that the inventive idea that is described for block 11 enables implementation of both the direct function and the inverse function of the SubBytes operation.

0086For a better understanding, described in detail in <figref idref="f0005">Figure 5</figref> is an implementation 22, which already presents a decomposition in <i>GF</i>(2⁴) of the function of inversion of the SubBytes operation, which normally operates, instead, on the Galois field <i>GF</i>(2⁸)<i>.</i> The input data <i>din[8]</i> are supplied to a transformation block 24 that implements the isomorphism that maps the elements of the 8-bit field <i>GF</i>(2⁸), into elements of the subfields <i>GF</i>(2⁴) by dividing the input into 4-bit blocks. This type of implementation is in itself known (see, for example, the aforementioned paper by Satoh et <i>al</i>., <figref idref="f0006">Figure 6</figref>) and comprises three 4-bit multipliers 25a, 25b, 25c that carry out the function MUL4 in the field <i>GF</i>(2⁴), a squaring block 26, a block for multiplication by a constant 31 (corresponding to one of the polynomials chosen for the decomposition into subfields), a first XOR block 27, a second XOR block 28 for the sum of elements of the field, and a look-up table 29 for the inversion INV4. Upstream of the output is a transformation block 30 that recomposes the 8-bit datum to form the output data <i>dout</i>[8], implementing the inverse isomorphism of block 24. Operation of this circuit, as has been said, is in itself known.

0087It should be noted that in this known implementation there is a single look-up table 29 that operates on 4-bit data, whereas the rest of the modules is implemented via combinational logic.

0088Each block represented in <figref idref="f0005">Figure 5</figref> can be in turn decomposed into subfields and hence into blocks that operate on elements of smaller size. <figref idref="f0006">Figure 6</figref> shows in detail, to facilitate understanding, one of the multiplication modules MUL4 25, which in turn, in a known way, is implemented via three multipliers, three 2-bit multipliers 251, and one multiplier for multiplication by a constant 252. This multiplication module MUL4 25 also comprises at input two transformation blocks 253 for dividing the two pairs of 4-bit input data <i>dinA</i>[4] and <i>dinB</i>[4], a transformation block 255 for recomposing the 4-bit output data <i>dout</i>[4], and XOR modules 256 for carrying out the additions.

0089It should be noted that the fact that the multiplier 25 has a pair of 4-bit input data, <i>dinA</i>[4] and <i>dinB</i>[4], renders not convenient implementation thereof via a LUT because it is cumbersome, thus annulling the benefits of the tower-of-fields decomposition.

0090According to the invention, it is envisaged to implement the function of inversion required for the module 11 of the S-Box device by exploiting the fact that the algebraic structure enables decomposition of the function. The criteria listed below are followed: <ul id="ul0004" list-style="dash" compact="compact"><li>implementing the linear operations via combinational logic;</li><li>implementing the non-linear operations via look-up tables; and</li><li>dividing the above look-up tables until they have a sufficiently small size; by way of example, for the multiplications it is preferable to use <i>GF</i>((2²)²)², because, as has been said, it would not be convenient to have the module MUL4 25 implemented as a look-up table; for the inversion it is possible to choose whether to stop at <i>GF</i>(2⁴) or also in this case use <i>GF</i>((2²)²)².</li></ul>

0091Each of the look-up tables that implement non-linear operations is masked by a respective pair of, input and output, masks.

0092In general, the original LUT is made up of 256x8=2048 bits. By appropriately decomposing the blocks with the tower-of-fields method, a number of look-up tables are obtained, which, however, are smaller. For example, the inversion in <i>GF</i>(2⁴) is made up of 16x4=64 bits. Or else, each of the operations MUL2 in <i>GF</i>((2²)²)² is made up of 16x2=32 bits. Since in the example described all the LUTs as a whole require a fraction of the memory bits required for the entire LUT of the S-Box, they can be implemented, and are preferably implemented, using flip-flops.

0093In this way, the initialization of the entire look-up table can be obtained in a single clock cycle given that all the data can be entered in parallel in one and the same clock cycle. Likewise, all the LUTs can be initialized in parallel.

0094<figref idref="f0007">Figure 7</figref> hence describes in detail an implementation 32 of the inversion module of the S-Box according to the invention. Unlike the implementation 22 of <figref idref="f0005">Figure 5</figref>, the squaring with multiplication by a constant (condensed in a single block 36), the inversion INV4 39, in addition to the blocks forming the three 4-bit multipliers 35a, 35b, 35c are obtained through look-up tables that incorporate input and output masks. A transformation block 33 that recomposes the data is provided upstream of the output.

0095In particular, in the above module 32, 8-bit masks are provided for the input data <i>din</i>[8] and the output data <i>dout</i>[8]. Within the module 32, additional 4-bit masks are present for the outputs of the squaring block 36, of the look-up table 39 for the inversion INV4, and of one of the multipliers 35. Moreover, since, as is shown in <figref idref="f0007">Figure 7</figref>, the multiplier MUL4 35 is in turn implemented in a way similar to the multiplier 25, but also in this case condensing in a single block 352 a multiplication with the multiplication by a constant and implementing both this block 352 and the multipliers 351 as look-up tables, three additional 2-bit masks are also provided.

0096Hence, as a whole, the circuit of <figref idref="f0007">Figure 7</figref> uses 34 independent bits for the mask. Even though the function of multiplication is the same, in practice it is possible to consider that there are different look-up tables, because they will have different masks. Each of the three multipliers MUL4 in actual fact is made up of three look-up tables. The implementation described in <figref idref="f0007">Figure 7</figref> shows a 4-bit inversion in block 39, but it is clear that also this block, in variant embodiments, may be decomposed into 2-bit inversion blocks.

0097It should be noted that the decomposition with use of look-up tables enables decomposition of the original function, i.e., the S-Box, not necessarily having to use only operations defined over the fields, such as for example multiplication, squaring, and inversion. Even though the known tower-of-fields decompositions are always based on the above few operations, the solution proposed via the use of look-up tables enables definition and use of functions that do not have any relation with the above classic operations, or else condensation of a number of operations in one and the same look-up table (as is the case described for blocks 25, 35, which carry out squaring with multiplication by a constant), an operation that is problematical to implement with the combinational logic and hence is rarely used. Moreover, since the decomposition of the S-Box described herein is functional for protection from side-channel attacks, the LUTs can be designed according to this purpose and not for the known use of reducing the area, for example by implementing a decomposition that will maintain redundant operations, which are less efficient from the standpoint of area occupation, but can produce benefits as regards protection against side-channel attacks.

0098<figref idref="f0010">Figure 9b</figref> shows an implementation of a look-up table 40 according to the invention, which operates on 2-bit data at input and 2-bit data at output. In general, the size in bits of the input data may differ from the size in bits of the output data. The scheme of this table 40 may be used for building, for example, the table 351 of <figref idref="f0008">Figure 8</figref> and implementing the multiplication function, but may moreover be used for implementing any LUT used within the S-Box proposed. In this table 40 the method described with reference, for example, to <figref idref="f0001">Figures 1a and 1b</figref> is moreover used.

0099Designated by 410-413 are registers that operate as memory cells for the data contained in the LUT, which are designated, respectively, by <i>d0</i>, ..., <i>d3.</i> Each of these data <i>d0</i>, ..., <i>d3</i> are sent from the output of the respective register 410-413 in parallel to a block 419 for selection of the output datum <i>dout</i> and to a respective XOR module 400-403, which carries out thereon the logic XOR with the logic combination of output masks Δ₂. Next, an interconnection matrix 405, provided with a number of multiplexers, under the control of the logic combination of input masks Δ₁, carries out masking, storing the outputs of the XOR modules 400-403 in the registers 410-413 in the order indicated by the logic combination of input masks Δ₁.

0100The selection block 419 is a set of multiplexers, which, in a way of in itself known, under the control of the input datum <i>din</i>, which contains the address of the data in the LUT, selects the appropriate output of the registers 410-413, supplying it as output datum <i>dout</i>, thus implementing the reading operation 140 of <figref idref="f0001">Figure 1b</figref>.

0101<figref idref="f0009">Figure 9a</figref> shows by way of comparison the implementation with flip-flops of a look-up table 41 for generic use, i.e., not specifically in an S-Box, according to the known art that uses a masking method similar to the operation 110 alone described with reference to <figref idref="f0001">Figure 1a</figref>. Reference numbers that are the same as the ones used in <figref idref="f0010">Figure 9b</figref> identify similar components. As may be noted, the XOR modules 400-403 receive at input the first output mask <i>R</i>₂ and directly the reference initialization values <i>F</i>(0), ..., <i>F</i>(3), which may be non-modifiable pre-set values, i.e., hardwired, or, as in the example described, may be contained in specific registers 420-423, storing the outputs of the XOR modules 400-403 in the registers 410-413 in the order indicated by the first input mask <i>R</i>₁<i>.</i> Advantageously, instead, the table 40 of <figref idref="f0010">Figure 9b</figref> sends to the XOR modules 400-403 the logic combinations of output masks Δ₂ and the data <i>d0</i>, ..., <i>d3</i> from the output of the respective register 410-413, storing the outputs of the XOR modules 400-403 in the registers 410-413 in the order indicated by the logic combination of input masks Δ₁.

0102Hence, from the description the advantages of the invention emerge clearly.

0103The device comprising look-up tables according to the invention, via a decomposition of the table of the S-Box device of the AES encryption into smaller tables over finite subfields, advantageously manages to implement the above tables via flip-flop structures, which can be updated in a single clock cycle.

0104The encryption method described, which comprises maskings using single masks and also combinations of masks, implemented in an apparatus that comprises the S-Box device according to the invention can be executed in a fast way, enabling a repeated and flexible use of the steps of initialization according to the invention, which renders the AES encryption procedure even more impervious to side-channel attacks even of high order. The encryption method according to the invention, via operations of initialization based upon combinations of masks, means that the possible correlations obtained by the side-channel attacks are always linked to the above combinations, but not to the values of the individual masks that originate them.

0105In this way, advantageously, the countermeasures against side-channel attacks can have a lower impact on the performance of the encryption system, whereas, instead, it is possible to implement the countermeasures against high-order attacks according to the method of the invention also in devices that present limitation in regard to the area available.

0106Of course, without prejudice to the principle of the invention, the details and embodiments may vary, even significantly, with respect to what has been described herein purely by way of example, without thereby departing from the sphere of protection, which is defined by the annexed claims.

0107The device according to the invention implements encryption procedures that are applied in general on data stored in data media and in particular on data stored in data media of any apparatus that implements an AES encryption system, for example in set-top boxes or smartcards. This AES encryption system can be regarded as a peripheral within a System-on-Chip, which is not used as stand-alone component, but is integrated in a chip of a smartcard or a chip of a set-top box or even chips of other applications that require AES encryption.

0108In general, the above apparatus comprises or is associated to data-processing means and, in particular, comprises one or more processors.