Table splitting for cryptographic processes

• US 8,619,985 B2
• Filed: 04/27/2010
• Issued: 12/31/2013
• Est. Priority Date: 04/27/2010
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Blackberry Limited
• Inventors: Gebotys, Catherine Helen
• Primary Examiner(s): Tabor, Amare F
• Application Number:
  US12/768,160
• Publication Number:
  US 20110261958A1
• Time in Patent Office: 1,344 Days
• Field of Search: 380/28, 380/252, 380/255, 380/263, 380/29, 380/42
• US Class Current: 380/252
• CPC Class Codes: H04L 2209/043 of tables, e.g. lookup, substitution or mapping
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 9/003 for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]

Abstract

For a defined cryptographic process including an original substitution table, split masked substitution tables are provided to resist cryptographic attacks. The split masked substitution tables are defined with reference to a set of random value data words and a mask value. An entry in the split masked substitution tables is defined by selecting bits from the corresponding entry in the original masked substitution table, as masked by the corresponding one of the set of random value data words and by selecting bits from the corresponding one of the set of random value data words as masked by the mask value. The split masked substitution tables are usable in a modified cryptographic process based on the defined cryptographic process to permit a masked output to be generated. The split masked substitution tables are refreshed by each entry in the tables being refreshed upon access during execution of the modified cryptographic process.

Claims

1. A computing device implemented method to resist power analysis attacks on a computing device by executing cryptographic steps based on a defined cryptographic process, the defined cryptographic process accepting an input, generating an output, and utilizing one or more originally-defined substitution tables, the method comprising a processor of the computing device in communication with a memory for executing the steps of:

a) defining n sets of random value data words r1(x) . . . rn(x), each data word having bits with defined bit locations, each set of random value data words comprising data word entries such that data words r1[x], . . . rn[x] correspond to entry S[x] in the original substitution table,

b) defining a mask value,

c) generating a set of split, masked tables by, for each entry S[x],

i) masking the data word S[x] with corresponding data words r1[x], . . . , rn[x] in the set of random values to define a masked data word having bits with defined bit locations,

ii) masking the mask value with a selected value r1[x] of the corresponding set of random values to define a randomized mask data word for S[x], having bits with defined bit locations, and

iii) generating each of the entries in a split, masked table by selecting bits from the masked data word, the randomized mask data word and, where the size n of the set of random values is 2 or more, the random value data words in the set other than the selected value r1[x], whereby each selected bit used to define each split masked table entry is selected from a correspondingly defined bit-location in its original data word, each of the bits in the entry in the split masked substitution table being defined in accordance with a pre-selected pattern.

2. The method of claim 1 in which the selection of bits from the masked data word, the randomized mask data word and, where the size n of the set of random values is 2 or more, the random value data words in the set other than the selected value r1[x] is carried out by selecting contiguous bits from the said data words and the step of generating each of the entries in a split masked table comprises the step of concatenating the selected contiguous bits to form the entry.

3. The method of claim 2 in which the size n of the set of random values is 1 and the length of the masked data word and of the randomized mask data word is 32 bits, the selection of bits comprising the step of selecting the first 16 bits from the masked data word and from the randomized mask data word to form an entry in a first split masked table by concatenation and a further selection of bits comprising the step of selecting the second 16 bits from the masked data word and from the randomized mask data word to form an entry in a second split, masked table by concatenation.

4. A computing-device program product for implementing a method to resist power analysis attacks on a computing device by executing cryptographic steps based on a defined cryptographic process, the defined cryptographic process accepting an input, generating an output, and utilizing one or more originally-defined substitution tables, the program product comprising program code embodied in a non-transitory program product storage media for execution by a processor of the device for implementing the method of:

a) defining n sets of random value data words r1(x) . . . rn(x), each data word having bits with defined bit locations, each set of random value data words comprising data word entries such that data words r1[x], . . . rn[x] correspond to entry S[x] in the original substitution table,

b) defining a mask value,

c) generating a set of split, masked tables by, for each entry S[x],

i) masking the data word S[x] with corresponding data words r1[x], . . . , rn[x] in the set of random values to define a masked data word having bits with defined bit locations,

ii) masking the mask value with a selected value r1[x] of the corresponding set of random values to define a randomized mask data word for S[x], having bits with defined bit locations, and

iii) generating each of the entries in a split, masked table by selecting bits from the masked data word, the randomized mask data word and, where the size n of the set of random values is 2 or more, the random value data words in the set other than the selected value r1[x], whereby each selected bit used to define each split, masked table entry is selected from a correspondingly defined bit-location in its original data word, each of the bits in the entry in the split, masked substitution table being defined in accordance with a pre-selected pattern.

5. A computing device operative to resist power analysis attacks by executing cryptographic steps based on a defined cryptographic process, the defined cryptographic process accepting an input, generating an output, and utilizing one or more originally-defined substitution tables, the computing device including a processor in communication with a memory for executing the cryptographic operation, the device operative to:

a) define a mask value,

b) generate a set of split, masked substitution tables corresponding to each of the one or more substitution tables, by, for each entry in each of the one or more substitution tables, masking the substitution table entry with one or more corresponding random values, masking a one of the corresponding random values with the mask value and, distributing the masked substitution table entry, the masked corresponding random value and any remaining corresponding random values not masked by the mask value across the set of split, masked substitution tables corresponding to substitution table entry'"'"'s substitution table; and

,

c) store the sets of split, masked substitution tables for use in the cryptographic process.

6. A data processing system or network comprising at least one computing device for implementing a method to resist power analysis attacks on the computing device by executing cryptographic steps based on a defined cryptographic process, the defined cryptographic process accepting an input, generating an output, and utilizing one or more originally-defined substitution tables, the computing device including a processor in communication with a memory for executing the cryptographic operation, the device operative to:

a) define a mask value,

b) generate a set of split, masked substitution tables corresponding to each of the one or more substitution tables, by, for each entry in each of the one or more substitution tables, masking the substitution table entry with one or more corresponding random values, masking a one of the corresponding random values with the mask value and, distributing the masked substitution table entry, the masked corresponding random value and any remaining corresponding random values not masked by the mask value across the set of split, masked substitution tables corresponding to substitution table entry'"'"'s substitution table; and

,

c) storing the sets of split, masked substitution tables for use in the cryptographic process.