Key masking for cryptographic processes

• US 7,778,419 B2
• Filed: 05/13/2005
• Issued: 08/17/2010
• Est. Priority Date: 05/10/2005
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Blackberry Limited
• Inventors: Gebotys, Catherine Helen
• Primary Examiner(s): Nguyen; Minh Dieu
• Assistant Examiner(s): LANE, GREGORY A
• Application Number:
  US11/128,206
• Publication Number:
  US 20060256963A1
• Time in Patent Office: 1,922 Days
• Field of Search: 380/43, 380/29, 380/28, 380/37, 380/205, 713/171
• US Class Current: 380/205
• CPC Class Codes: H04L 2209/04 Masking or blinding
• CPC Class Codes: H04L 9/003 for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]
• CPC Class Codes: H04L 9/0618 Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation

Abstract

Countermeasures for differential power or electromagnetic analysis attacks are provided with the definition and use of key encryption masks and masked substitution tables in a cryptographic process. Different key encryption masks and masked substitution tables are applied to different portions of masked keys used in the cryptographic process and are rotated as the cryptographic operations are carried out. The rotation of the key encryption masks and the masked substitution tables is non-uniform. Input and output masking for the substitution tables is provided.

Claims

1. A computing device-implemented method for improving the resistance, to power analysis attacks, of a processing unit performing iterative cryptographic operations utilizing key values and substitution tables, the method utilizing masking of the key values and the substitution tables, the method comprising the steps of:

a) initially masking an initial key value,

b) initially defining a set of non-uniform key encryption masks,

c) initially defining a set of masked substitution tables, each masked substitution table being derived from an initial substitution table so as to correspond to one of the key encryption masks from the set of non-uniform key encryption masks,

d) iteratively carrying out the cryptographic operations, such that

each iteration of the cryptographic operations comprises the step of defining a successive masked key value by masking the previous masked key value using a key encryption mask selected from the set of non-uniform key encryption masks, and

each iteration of the cryptographic operations utilizes the successively defined masked key value and the corresponding table from the set of masked substitution tables that corresponds to the selected key encryption mask.

2. The computing device-implemented method of claim 1 in which the step of defining a successive masked key value comprises the step of selecting a key encryption mask from the set of key encryption masks by randomly selecting a mode for stepping through the set of key encryption masks from one of:

increment mode, decrement mode, no change mode and double increment mode.

3. The computing device-implemented method of claim 1 in which each successively defined masked key value is comprised of split key values and the set of key encryption masks is defined to permit masking of each one of the split key values.

4. The computing device-implemented method of claim 3 in which the iterative cryptographic operations are rounds and in which the split key values are split round key values.

5. The computing device-implemented method of claim 4 in which the rounds are rounds in an Advanced Encryption Standard process or in a Data Encryption Standard process.

20. A computing device comprising a memory medium for storing program code executable on the computing device, the memory medium of the computing device storing program code executable on the computing device for carrying out the method of claim 1.

6. A computing device-implemented method for successively masking a key value, the successively masked values being for use by a processing unit performing successive iterations of cryptographic operations utilizing a substitution table, the method comprising the initial steps of:

a) splitting the key value into a set of split key values,

b) defining a set of random mask values,

c) combining multiple random mask values to define non-uniform key encryption masks

and masking the set of split key values with selected key encryption masks to define a set of masked keys for use in the iterative cryptographic operations, and

d) combining multiple random mask values related to the key encryption masks to define non-uniform table masks and generating a set of masked tables derived from the substitution table and corresponding to the set of split key values, for use in the iterative cryptographic operations, the method further comprising, for each iteration of the cryptographic operation, the step of utilizing selected key encryption masks and masked tables, the selection being carried out by a rotation through the respective sets of key encryption masks and masked tables.

7. The method of claim 6, in which the step of selecting the elements in the set of key encryption masks and the set of masked tables further comprises random selection of a mode of rotation from a set of potential rotation modes.

8. The method of claim 7 in which the set of potential rotation modes includes two or more of increment, decrement, no motion and double increment modes.

9. The method of claim 6 in which the masking to generate the masked tables is an input masking, the method further comprising the step of defining output masks for each of the masked tables, the values of the output masks being defined such that the output masks cancel when used in the cryptographic operations.

10. The method of claim 6 in which the definition of the key encryption mask comprises the steps of

a) defining a set of non-uniform initial mask values for application to the split mask values,

b) defining a set of non-uniform rotational mask values, the rotational mask values being applied after the initial mask values and the resulting masked values being available to replace the set of masked key values, and

c) defining a set of tuples of unmasking values defined such that in combination, the tuples of unmasking values cancel each of the initial mask values.

11. The method of claim 6 applied to an AES cryptographic operation.

12. A computing device program product for carrying out iterative cryptographic operations utilizing an initial key value and a substitution table, the computing device program product comprising a computer device usable storage medium having computer device readable program product code stored in said medium, and comprising

a) program code operative to initially mask the initial key value,

b) program code operative to initially define a set of non-uniform key encryption masks,

c) program code operative to initially define a set of masked substitution tables, each masked substitution table being derived from the initial substitution table so as to correspond to one of the set of key encryption masks, and

d) program code operative to carry out each iteration of the cryptographic operations by defining a successive masked key value by masking the previous masked key value using a key encryption mask selected from the set of key encryption masks, and to carry out each iteration of the cryptographic operations utilizing the successively defined masked key value and the corresponding table from the set of masked substitution tables.

13. The computing device program product of claim 12 in which program code operative to define a successive masked key value further comprises program code operative to select a key encryption mask from the set of key encryption masks by randomly selecting a mode for stepping through the set of key encryption masks from one of:

increment mode, decrement mode, no change mode and double increment mode.

14. The computing device program product of claim 12 further comprising program code operative to successively define masked key values by defining split key values and further comprising program code operative to define the set of key encryption masks to permit masking of each one of the split key values.

15. The computing device program product of claim 14 in which the program code operative to carry out the iterative cryptographic operations is operative to carry out cryptographic rounds and in which the program code operative to define split key values is operative to define split round key values.

16. The computing device program product of claim 15 in which the program code operative to carry out cryptographic rounds is operative to carry out rounds in an Advanced Encryption Standard process or in a Data Encryption Standard process.

17. A computing device program product for successively masking a key value, the successively masked values being for use in successive iterations of cryptographic operations utilizing a substitution table, the computing device program product comprising a computing device usable storage medium having computing device readable program product code stored in said medium, and comprising

program code operative to split the key value into a set of split key values,

program code operative to define a set of random mask values,

program code operative to combine multiple random mask values to define non-uniform key encryption masks and to mask the set of split key values with selected key encryption masks to define a set of masked keys for use in the iterative cryptographic operations,

program code operative to combine multiple random mask values related to the key encryption masks to define non-uniform table masks and to generate a set of masked tables derived from the substitution table and corresponding to the set of split key values, for use in the iterative cryptographic operations, and

program code operative to carry out each iteration of the cryptographic operation by utilizing selected key encryption masks and masked tables, the program code being operative to carry out the selection by rotating through the respective sets of key encryption masks and masked tables.

18. The computing device program product of claim 17 in which the program code operative to generate the masked tables is operative to generate input masking, the program code further comprising program code operative to define output masks for each of the masked tables, the values of the output masks being defined such that the output masks cancel when used in the cryptographic operations.

19. The computing device program product of claim 17 in which the program code operative to define the key encryption mask further comprises

a) program code operative to define a set of non-uniform initial mask values for application to the split mask values,

b) program code operative to define a set of non-uniform rotational mask values, the rotational mask values being applied after the initial mask values and the resulting masked values being available to replace the set of masked key values, and

c) program code operative to define a set of tuples of unmasking values defined such that in combination, the tuples of unmasking values cancel each of the initial mask values.