# US 10,644,873 B2 · Method for protecting substitution operation against side-channel analysis

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,644,873 B2
- Document ID: US10644873B2
- Status: Granted
- Kind: B2
- Application number: 15/636,223
- Filed: 2017-06-28
- Published: 2017-12-28
- Granted: 2020-05-05
- Earliest claimed: 2016-06-28
- Assignees: Eshard
- Applicants: Eshard
- Inventors: Antoine Wurcker; Christophe Clavier
- Web page: https://patentgrep.com/patent/US10644873B2

## CPC

- H04L 9/002: {Countermeasures against attacks on cryptographic mechanisms (network architectures or network communication protocols for protection against malicious traffic H04L63/1441)}
- G09C 1/00: Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system (cryptographic typewriters G09C3/00)
- H04L 9/0631: {Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms}
- H04L 9/0861: {Generation of secret information including derivation or calculation of cryptographic keys or passwords}
- H04L 9/14: using a plurality of keys or algorithms
- H04L 2209/04: Masking or blinding
- H04L 2209/08: Randomization, e.g. dummy operations or using noise
- H04L 2209/12: Details relating to cryptographic hardware or logic circuitry
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G09C: CIPHERING OR DECIPHERING APPARATUS FOR CRYPTOGRAPHIC OR OTHER PURPOSES INVOLVING THE NEED FOR SECRECY

## Abstract

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

## Claims

### Claim 1

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

### Claim 2 (depends on 1)

The method of claim 1, wherein the first mask set is generated using a random permutation function.

### Claim 3 (depends on 1)

The method of claim 1, wherein the cryptographic operation is a substitution operation in which the output data is selected in an input substitution table using the input data as an index, the method further comprising:
using masked substitution tables generated from the input substitution table and including one masked substitution table for each of the first mask parameters in the first mask set; and
for each first mask parameter in the first mask set, selecting one of the masked substitution tables corresponding to the first mask parameter, and selecting a first data in the selected masked substitution table, using, as an index, a second data corresponding to the first mask parameter in the input set, the output set including all the first data selected in one of the masked substitution tables.

### Claim 4 (depends on 3)

The method of claim 3, wherein the masked substitution tables are generated by:
generating the first mask set;
generating the second mask set including a number of second mask parameters equal to a number of values in the input substitution table, each second mask parameter having a same number of occurrences in the second mask set;
selecting once, each of the first and second mask parameter, respectively, in the first mark set and the second mask set to form mask pairs, each mask pair including one of the first mask parameters and one of the second mask parameters;
generating, for each mask pair, one of the masked substitution tables, the generation of each of the masked substitution tables including:
selecting each data in the input substitution table, and for each selected data:
computing a masked data by applying the XOR operations to the selected data and to the second mask parameter of the mask pair corresponding to the masked substitution table,
computing a masked index by applying the XOR operations to the first mask parameter of the mask pair corresponding to the masked substitution table and to an original index, and
storing the masked data in the masked substitution table, the selected data being selected at the original index and the masked data being stored at the masked index, or the selected data being selected at the masked index and the masked data being stored at the original index.

### Claim 5 (depends on 4)

The method of claim 4, wherein the generation of the second mask set includes one of the following operations:
the second mask set is generated so that the first mask parameter and the second mask parameter of each mask pair are identical,
the second mask set is deduced from the first mask set by applying a bijective function to the first mask set, and a shift function applied to ranks of the first mask parameters in the first mask set,
the second mask set is deduced from the first mask set by applying a bijective function to the first mask set,
the second mask set is generated using a random permutation function applied to the first mask set, and
the second mask set is generated so that a combination by the XOR operations of each of the first mask parameters in the first mask set with a corresponding second mask parameter in the second mask set produces a third mask set including mask words forming the third mask parameters, each third mask parameter in the third mask set including at least one of the mask words in the third mask set, the mask words in the third mask set having a same size and forming at least one third word subset including a single word from each third mask parameter of the third mask set and a same number of occurrences of all possible values of the mask words in the third word subset.

### Claim 6 (depends on 4)

The method of claim 4, wherein values in the masked substitution tables are determined in random order or stored in randomly selected positions in the masked substitution tables.

### Claim 7 (depends on 4)

The method of claim 4, wherein the substitution operation is included in an operation for encrypting or decrypting the input data according to a cryptographic algorithm.

### Claim 8 (depends on 7)

The method of claim 7, wherein the cryptographic algorithm conforms with an Advanced Encryption Standard (AES) algorithm, the method comprising:
generating a round input set by applying the XOR operations to each word of the input data, to each mask parameter of the first mask set, and to a word of a secret key corresponding to one word of the at least one word of the input data;
performing several intermediate rounds, each intermediate round including:
applying the substitution operation to each word in the round input set,
computing a masked round output set for the intermediate round by applying the XOR operations to each word of a round output set for the intermediate round, to a respective mask parameter of the first mask set and to a respective mask parameter of the second mask set, and
using the masked round output set as a round input set for a next round;
performing a last round including applying the substitution operation to each word in a round input set for the last round; and
providing the output set in which each data is masked by a respective mask parameter of the second mask set.

### Claim 9 (depends on 8)

The method of claim 8, wherein the first mask set and the second mask set are generated so that a third mask set resulting from a combination by the XOR operations of each mask parameter of the first mask set with a corresponding mask parameter of the second mask set includes only one occurrence of all possible values of a word of the input data.

### Claim 10 (depends on 9)

The method of claim 9, further comprising generating a random permutation having a number of elements corresponding to a number of words in the input set, and applying one of the operations of the cryptographic algorithm to words of an operation input set in an order defined by the random permutation.

### Claim 11 (depends on 10)

The method of claim 10, wherein the generating the random permutation is performed during at least one of:
a first round of the cryptographic algorithm;
at each round of the cryptographic algorithm;
at a last round of the cryptographic algorithm; or
before each operation of the cryptographic algorithm.

### Claim 12 (depends on 1)

The method of claim 1, wherein computations of the data in the output set are performed in random order or stored in randomly selected positions in the output set.

### Claim 13 (depends on 1)

The method of claim 1, further comprising detecting, in the output set, a computation error by at least one of:
detecting two identical data in the output set; or
applying XOR operations to each data in the output set and to a corresponding mask parameter in the first mask set or the second mask set, and searching results of the XOR operations for a data different from an expected output data.

### Claim 14

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

### Claim 15 (depends on 14)

The circuit of claim 14, comprising a co-processor.

### Claim 16 (depends on 14)

The circuit of claim 14, wherein the first mask set is generated using a random permutation function.

### Claim 17 (depends on 14)

The circuit of claim 14, wherein the cryptographic operation is a substitution operation in which the output data is selected in an input substitution table using the input data as an index, the circuit configured to:
use masked substitution tables generated from the input substitution table and including one masked substitution table for each of the first mask parameters in the first mask set; and
for each first mask parameter in the first mask set, select one of the masked substitution tables corresponding to the first mask parameter, and select a first data in the selected masked substitution table, using, as an index, a second data corresponding to the first mask parameter in the input set, the output set including all the first data selected in one of the masked substitution tables.

### Claim 18 (depends on 17)

The circuit of claim 17, comprising one circuit performing a substitution operation for each masked substitution table.

### Claim 19 (depends on 18)

The circuit of claim 18, wherein the masked substitution tables are generated by:
generating the first mask set;
generating the second mask set including a number of second mask parameters equal to a number of values in the input substitution table, each second mask parameter having a same number of occurrences in the second mask set;
selecting once, each of the first and second mask parameter, respectively, in the first mask set and the second mask set to form mask pairs, each mask pair including one of the first mask parameters and one of the second mask parameters;
generating, for each mask pair, one of the masked substitution tables, the generation of each of the masked substitution tables including:
selecting each data in the input substitution table, and for each selected data:
computing a masked data by applying the XOR operations to the selected data and to the second mask parameter of the mask pair,
computing a masked index by applying the XOR operations to the first mask parameter of the mask pair corresponding to the masked substitution table and to an original index, and
storing the masked data in the masked substitution table, the selected data being selected at the original index and the masked data being stored at the masked index, or the selected data being selected at the masked index and the masked data being stored at the original index.

### Claim 20 (depends on 19)

The circuit of claim 19, wherein the generation of the second mask set includes one of the following operations:
the second mask set is generated so that the first mask parameter and the second mask parameter of each mask pair are identical,
the second mask set is deduced from the first mask set by applying a bijective function to the first mask set, and a shift function applied to ranks of the first mask parameters in the first mask set,
the second mask set is deduced from the first mask set by applying a bijective function to the first mask set,
the second mask set is generated using a random permutation function applied to the first mask set, and
the second mask set is generated so that a combination by the XOR operations of each of the first mask parameters in the first mask set with a corresponding second mask parameter in the second mask set produces a third mask set including mask words forming the third mask parameters, each third mask parameter in the third mask set including at least one of the mask words in the third mask set, the mask words in the third mask set having a same size and forming at least one third word subset including a single word from each third mask parameter of the third mask set and a same number of occurrences of all possible values of the mask words in the third word subset.

### Claim 21 (depends on 17)

The circuit of claim 17, wherein values in the masked substitution tables are determined in random order or stored in randomly selected positions in the masked substitution tables.

### Claim 22 (depends on 17)

The circuit of claim 17, wherein the circuit is configured to encrypt or decrypt the input data according to a cryptographic algorithm, the substitution operation being included in the cryptographic algorithm.

### Claim 23 (depends on 22)

The circuit of claim 22, wherein the cryptographic algorithm conforms with an Advanced Encryption Standard (AES) algorithm, the circuit being configured to:
generate a round input set by applying the XOR operations to each word of the input data, to each mask parameter of the first mask set, and to a word of a secret key corresponding to one word of the at least word of the input data;
perform several intermediate rounds, each intermediate round including:
applying the substitution operation to each word in the round input set,
computing a masked round output set for the intermediate round by applying the XOR operations to each word of a round output set for the intermediate round, to a respective mask parameter of the first mask set and to a respective mask parameter of the second mask set, and
using the masked round output set as a round input set for a next round;
perform a last round including applying the substitution operation to each word in a round input set for the last round; and
provide an output set in which each data is masked by a respective mask parameter of the second mask set.

### Claim 24 (depends on 23)

The circuit of claim 23, wherein the first mask set and the second mask set are generated so that a third mask set resulting from a combination by the XOR operations of each mask parameter of the first mask set with a corresponding mask parameter of the second mask set includes only one occurrence of all possible values of a word of the input data.

### Claim 25 (depends on 24)

The circuit of claim 24, further comprising generating a random permutation having a number of elements corresponding to a number of words in the input set, and applying one of the operations of the cryptographic algorithm to words of an operation input set in an order defined by the random permutation.

### Claim 26 (depends on 25)

The circuit of claim 25, wherein the generating the random permutation is performed during at least one of:
a first round of the cryptographic algorithm;
at each round of the cryptographic algorithm;
at a last round of the cryptographic algorithm; or
before each operation of the cryptographic algorithm.

### Claim 27 (depends on 14)

The circuit of claim 14, wherein computations of the data in the output set are performed in random order or stored in randomly selected positions in the output set.

### Claim 28 (depends on 14)

The circuit of claim 14, further comprising detecting, in the output set, a computation error by at least one of:
detecting two identical data in the output set; or
applying XOR operations to each data in the output set and to a corresponding mask parameter in the first mask set or the second mask set, and searching results of the XOR operations for a data different from an expected output data.

### Claim 29 (depends on 14)

A device comprising a circuit according to claim 14, arranged on a medium.

### Claim 30

A non-transitory computer-readable storage device including code portions which, when carried out by a computer, configure the computer to carry out one or more instructions and cause one or more processors to:
apply a cryptographic operation to all data in an input set including data obtained by applying Exclusive OR (XOR) operations to an input data and to all first mask parameters in a first mask set including mask words forming the first mask parameters, each first mask parameter in the first mask set including at least one of the mask words in the first mask set, the mask words in the first mask set having a same size and forming at least one first word subset including a single word from each first mask parameter of the first mask set and a same number of occurrences of all possible values of the mask words in the first mask set; and
provide as an output of the cryptographic operation, an output set including all data resulting from an application of the cryptographic operation to all of the data in the input set, an output data of the cryptographic operation applied to the input data being obtained by applying XOR operations to any one of the data in the output set and to a respective second mask parameter in a second mask set including mask words forming the second mask parameters, each second mask parameter in the second mask set including at least one of the mask words in the second mask set, the mask words in the second mask set having a same size and forming at least one second word subset including a single word from each second mask parameter of the second mask set and a same number of occurrences of all possible values of the mask words in the second mask set.