SUBSTITUTION TABLE MASKING FOR CRYPTOGRAPHIC PROCESSES

• US 20090086976A1
• Filed: 05/22/2008
• Published: 04/02/2009
• Est. Priority Date: 10/01/2007
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Research In Motion Limited (Blackberry Limited)
• Inventors: SCIAN, Anthony Fabian
• Granted Patent: US 8,553,877 B2
• Time in Patent Office: Days
• US Class Current: 380/277
• CPC Class Codes: H04L 2209/043 of tables, e.g. lookup, substitution or mapping
• 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/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

Abstract

A computing device-implemented method and system is provided for obtaining an interim masked substitution table value for a given input component in a cryptographic round, such as an AES cryptographic round, using a substitution table and a self-cancelling mask. A mask with a length equal to an entry in the substitution table is provided, wherein the mask comprises a plurality of mask components of equal length such that a bitwise logical inequality operation such as NOR on the mask components equals zero, and the substitution table is masked with this mask. For each of input component, an interim masked substitution table value is obtained from the substitution table thus masked.

Claims

1. A computing device-implemented method for obtaining an interim masked substitution table value for each input component of a set of input components of equal length in a cryptographic round utilizing a substitution table comprising a set of entries each of length equal to the length of each input component, the method comprising:

for each input component, obtaining the interim masked substitution table value corresponding to the input component from a masked substitution table, the masked substitution table comprising the substitution table wherein each entry therein is masked via a bitwise logical inequality operation with a first mask of the same length as each substitution table entry,

the first mask comprising a plurality of first mask components of equal length, such that a result of a bitwise logical inequality operation on the first mask components equals zero.

2. The method of claim 1, wherein the bitwise logical inequality operation is XOR.

3. The method of claim 2, wherein the cryptographic round comprises an AES-defined cryptographic round and a substitution table is provided in accordance with the AES.

4. The method of claim 1, wherein the set of input components comprises a plurality of n input components, the method further comprising:

defining the first mask to comprise a plurality of n first mask components of equal length; and

masking each substitution table entry with the first mask to provide the masked substitution table;

and wherein obtaining the interim masked substitution table value for each input component comprises;

obtaining from the masked substitution table a masked value corresponding to the input component, the masked value comprising n masked value components, and

storing the masked value as a unique one of n arrangements of the n masked value components, such that in the n arrangements, each of the n masked value components occurs in each of the n positions exactly once.

5. The method of claim 4, wherein the n arrangements comprise a cyclic group of rotations.

6. The method of claim 5, wherein n is four, and the cyclic group of rotations consists of a null rotation, a rot₁ rotation, a rot₂ rotation, and a rot₃ rotation.

7. The method of claim 1, further comprising combining all of the interim masked substitution table values obtained for all the respective input components of the set of input components, in a bitwise logical inequality operation, to obtain a substitution table output.

8. The method of claim 7, further comprising:

defining a second mask having a length equal to the length of a substitution table entry, the second mask comprising a plurality of n second mask components of equal length, such that a result of the bitwise logical inequality operation on the n second mask components equals zero,

masking the masked substitution table with the second mask to provide a further masked substitution table.

9. The method of claim 8, further comprising:

for each of a second set of n input components;

obtaining from the further masked substitution table a further masked value corresponding to the input component of the second set of n input components, and

applying to the further masked value a unique one of a cyclic group of rotations, to obtain a further interim masked substitution table value.

10. A computing device-implemented method for obtaining an interim masked substitution table value for each of a plurality of n input components of equal length in a cryptographic round utilizing a substitution table comprising a set of entries each of length equal to the length of each of the n input components, the method comprising:

storing a set of n masked substitution tables, each ith one of the n masked substitution tables corresponding to an ith one of the n input components, each entry of each one of the n masked substitution tables comprising a plurality of n masked substitution table entry components of equal length, each of said n masked substitution table entry components comprising a corresponding entry from the substitution table masked, via a bitwise logical inequality operation, with a first mask of the same length as each substitution table entry, the first mask comprising a plurality of first mask components of equal length such that a result of a bitwise logical inequality operation on the first mask components equals zero,

such that each entry of each one of the set of n masked substitution tables is stored as a unique one of n arrangements of the n masked substitution table entry components of a corresponding entry of the substitution table thus masked, such that in the n arrangements each of the n masked substitution table entry components occurs in each of n positions exactly once, and such that an ith one of the n arrangements corresponds to an ith one of the n input components; and

for each ith one of the n input components, obtaining the interim masked substitution table value corresponding to the ith input component from the ith one of the set of n masked substitution tables.

11. The method of claim 10, wherein the n arrangements comprise a cyclic group of rotations.

12. The method of claim 11, wherein n is four, and the cyclic group of rotations consists of a null rotation, a rot₁ rotation, a rot₂ rotation, and a rot₃ rotation.

13. A computing device-implemented method for obtaining a masked substitution table output for a given input in a cryptographic round utilizing a plurality of substitution tables, the input comprising a set of input components, the method comprising:

for each input component of the set of input components, obtaining a masked substitution table value corresponding to the input component, from a respective one of a plurality of masked substitution tables, each of the masked substitution tables comprising a unique one of the plurality of substitution tables masked, via a bitwise logical inequality operation, with a unique one of a plurality of masks, the plurality of masks being defined such that the result of a bitwise logical inequality operation on the plurality of masks equals zero.

14. The method of claim 13, wherein the bitwise logical inequality operation is XOR.

15. The method of claim 14, wherein the cryptographic round comprises an AES-defined cryptographic round.

16. The method of claim 13, further comprising:

combining all of the masked substitution table values obtained for all of the respective input components of the set of input components to provide a substitution table output corresponding to the given input.

17. The method of claim 13, further comprising providing the plurality of masks by:

generating all but one of the plurality of masks; and

generating the remaining of the plurality of masks such that the result of the bitwise logical inequality operation on the plurality of masks equals zero.

18. The method of claim 17, wherein generating all but one of the plurality of masks comprises generating all but one of the plurality of masks from one or more pseudo-random values.

19. The method of claim 13, further comprising providing the plurality of masks by:

providing a set of n mask components of equal length, wherein n is the number of masked substitution tables and wherein the result of a bitwise logical inequality operation on the n mask components equals zero; and

generating each of n masks as one of n arrangements of the n mask components in n unique positions, such that in the n arrangements, each of the n mask components occurs in each of the n positions exactly once, wherein the n arrangements comprise a cyclic group of rotations.

20. A computer readable medium storing computer readable instructions executable by a processor of a computing device for causing said computing device to:

for each input component of a set of input components of equal length in a cryptographic round utilizing a substitution table comprising a set of entries each length equal to the length of each input component, obtain an interim masked substitution table value corresponding to the input component from a masked substitution table, the masked substitution table comprising the substitution table wherein each entry therein is masked via a bitwise logical inequality operation with a first mask of the same length as each substitution table entry,

the first mask comprising a plurality of first mask components of equal length, such that a result of a bitwise logical inequality operation on the first mask components equals zero.

21. The computer readable medium of claim 20, wherein the set of input components comprises a plurality of n input components, the medium further storing computer readable instructions executable by a processor of a computing device for causing said computing device to:

defining the first mask to comprise a plurality of n first mask components of equal length; and

masking each substitution table entry with the first mask to provide the masked substitution table;

and wherein the computer readable instructions, when executed, further cause the processor to obtain the interim masked substitution table value for each input component by;

obtaining from the masked substitution table a masked value corresponding to the input component, the masked value comprising n masked value components, and

storing the masked value as a unique one of n arrangements of the n masked value components in n unique positions, such that in the n arrangements, each of the n masked value components occurs in each of the n positions exactly once.

22. A computer readable medium storing computer readable instructions executable by a processor of a computing device for causing said computing device to:

store a set of n masked substitution tables, each ith one of the n masked substitution tables corresponding to an ith one of n input components of equal length, each entry of each one of the n masked substitution tables comprising a plurality of n masked substitution table entry components of equal length, each of said n masked substitution table entry components comprising a corresponding entry from a substitution table comprising a set of entries each of length equal to the length of each of the n input components, the substitution table being masked, via a bitwise logical inequality operation, with a first mask of the same length as each substitution table entry, the first mask comprising a plurality of first mask components of equal length such that a result of a bitwise logical inequality operation on the first mask components equals zero,

such that each entry of each one of the set of n masked substitution tables is stored as a unique one of n arrangements of the n masked substitution table entry components of a corresponding entry of the substitution table thus masked, such that in the n arrangements each of the n masked substitution table entry components occurs in each of n positions exactly once, and such that an ith one of the n arrangements corresponds to an ith one of the n input components; and

for each ith one of the n input components, obtaining an interim masked substitution table value corresponding to the ith input component from the ith one of the set of n masked substitution tables.

23. A computer readable medium storing computer readable instructions executable by a processor of a computing device for causing said computing device to:

for each input component of a set of input components, obtain a masked substitution table value corresponding to the input component from a respective one of a plurality of masked substitution tables, each of the masked substitution tables comprising a unique one of the plurality of substitution tables masked, via a bitwise logical inequality operation, with a unique one of a plurality of masks, the plurality of masks being defined such that the result of a bitwise logical inequality operation on the plurality of masks equals zero.

24. A computing device comprising:

a memory for storing a masked substitution table;

a processor configured, for each input component of a set of input components of equal length in a cryptographic round utilizing a substitution table comprising a set of entries each length equal to the length of each input component, to obtain an interim masked substitution table value corresponding to the input component from the masked substitution table, the masked substitution table comprising the substitution table wherein each entry therein is masked via a bitwise logical inequality operation with a first mask of the same length as each substitution table entry,

the first mask comprising a plurality of first mask components of equal length, such that a result of a bitwise logical inequality operation on the first mask components equals zero.

25. A computing device comprising:

a memory for storing a set of n masked substitution tables, each ith one of the n masked substitution tables corresponding to an ith one of n input components of equal length, each entry of each one of the n masked substitution tables comprising a plurality of n masked substitution table entry components of equal length, each of said n masked substitution table entry components comprising a corresponding entry from a substitution table comprising a set of entries each of length equal to the length of each of the n input components, the substitution table being masked, via a bitwise logical inequality operation, with a first mask of the same length as each substitution table entry, the first mask comprising a plurality of first mask components of equal length such that a result of a bitwise logical inequality operation on the first mask components equals zero,

such that each entry of each one of the set of n masked substitution tables is stored as a unique one of n arrangements of the n masked substitution table entry components of a corresponding entry of the substitution table thus masked, such that in the n arrangements each of the n masked substitution table entry components occurs in each of n positions exactly once, and such that an ith one of the n arrangements corresponds to an ith one of the n input components; and

a processor configured, for each ith one of the n input components, to obtain an interim masked substitution table value corresponding to the ith input component from the ith one of the set of n masked substitution tables.

26. A computing device comprising:

a memory for storing a plurality of masked substitution tables;

a processor configured, for each input component of the set of input components, to obtain a masked substitution table value corresponding to the input component from a respective one of the plurality of masked substitution tables, each of the masked substitution tables comprising a unique one of a plurality of substitution tables masked, via a bitwise logical inequality operation, with a unique one of a plurality of masks, the plurality of masks being defined such that the result of a bitwise logical inequality operation on the plurality of masks equals zero.