System and method for protecting computer software from a white box attack

• US 20040139340A1
• Filed: 02/18/2004
• Published: 07/15/2004
• Est. Priority Date: 12/08/2000
• Status: Active Grant

• Current Assignee: Cloakware Incorporated (MultiChoice Group Ltd.)
• Original Assignee: Cloakware Incorporated (MultiChoice Group Ltd.)
• Inventors: Eisen, Philip A., Johnson, Harold J., Chow, Stanley T.
• Granted Patent: US 7,397,916 B2
• Time in Patent Office: Days
• US Class Current: 713/194
• CPC Class Codes: G06F 21/125 by manipulating the program code, e.g. source code, compiled code, interpreted code, machine code
• CPC Class Codes: G06F 21/14 against software analysis or reverse engineering, e.g. by obfuscation
• CPC Class Codes: 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
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/16 Obfuscation or hiding, e.g. involving white box
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• 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/0625 with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI
• 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

Existing encryption systems are designed to protect secret keys or other data under a “black box attack,” where the attacker may examine the algorithm, and various inputs and outputs, but has no visibility into the execution of the algotitm itself. However, it has been shown that the black box model is generally unrealistic, and that attack efficiency rises dramatically if the attacker can observe even minor aspects of the algorithm'"'"'s execution. The invention protects software from a “white-box attack”, where the attacker has total visibility into software implementation and execution. In general, this is done by encoding the software and widely diffusing sites of information transfer and/or combination and/or loss. Other embodiments of the invention include: the introduction of lossy subcomponents, processing inputs and outputs with random cryptographic functions, and representing algorithmic steps or components as tables, which permits encoding to be represented with arbitrary nonlinear bijections.

Claims

1. A method of modifying software algorithms to foil tracing and other static, dynamic, and statistical attacks comprising the steps of:

encoding said software algorithm; and

widely diffusing sites of information transfer and/or combination and/or loss.

2. The method as claimed in claim 1, further comprising the step of:

rendering one or more steps or components difficult to invert by the introduction of lossy subcomponents.

3. The method as claimed in claim 1, further comprising the step of:

processing the input of a function in said software algorithm by an additional, random cryptographic function.

4. The method as claimed in claim 1, further comprising the step of:

processing the output of a function in said software algorithm by an additional, random cryptographic function.

5. The method as claimed in claim 1, further comprising the step of:

preserving input information in the output of a function by combining a step or component and a copy operation into one step or component, in order to both provide the step or component and to cause the information to effectively bypass the step or component.

6. The method as claimed in claim 1, wherein said steps of encoding and diffusing comprises the steps of:

representing one or more algorithmic steps or components as tables, thereby permitting encodings to be completely arbitrary nonlinear bijections.

7. The method as claimed in claim 5, further comprising the step of:

decoding the output of said combination in two distinct ways;

effectively interpreting the combined step or component according to the original step or component; and

interpreting the combined step or component as a copy operation, so that copying and transformation are simultaneously achieved.

8. The method as claimed in claim 6, further comprising the step of:

diffusing a cryptographic key into other widely diffused components of the algorithm by partial evaluation.

9. The method as claimed in claim 6 in which said step of representing comprises the step of:

diffusing functions within said software algorithm by encoding the inputs and outputs of said functions using randomly chosen linear bijections as the encodings.

10. The method as claimed in claim 9, comprising the prior step of:

encoding the inputs and outputs of said functions using nonlinear encoding.

11. The method as claimed in claim 9, comprising the subsequent step of:

encoding the inputs and outputs of said functions using nonlinear encoding.

12. The method as claimed in claim 6 further comprising the step of:

encoding input table lookups using nonlinear bijections.

13. The method as claimed in claim 6 further comprising the step of:

encoding output table lookups using nonlinear bijections.

14. The method as claimed in claim 6 in which such encoding is rendered locally secure (that is, immune to local attack) by performing the step of:

converting lossy tables into bijective tables.

15. The method as claimed in claim 6 further comprising the step of:

splitting the steps or components of said software algorithm into several parts and representing said parts as separate tables, each of which can be encoded in an arbitrary fashion.

16. The method as claimed in claim 6 further comprising the step of:

diffusing and encoding functions expressible as a network of linear components, by de-linearizing the inputs and outputs of said linear components using encodings which are randomly chosen nonlinear bijections.

17. The method as claimed in claim 16 further comprising the step of:

diffusing and rendering the linear connective components of the cryptographic function by encoding inputs and/or outputs using random nonlinear bijections.

18. The method as claimed in claim 16 further comprising the prior step of:

subdividing larger linear functions into networks of smaller components.

19. The method as claimed in claim 18 in which said step of subdividing comprises the steps of:

blocking a matrix representation of said larger linear functions.

20. The method as claimed in claim 18, in which said step of subdividing comprises the steps of:

building a diffusing network in the shape of a full M by N switching/sorting network, such as a Banyan network or an Omega network;

determining paths for one or more individual pieces of information to use in traversing said network;

applying linear functions to the nodes of said network such that said paths are followed by said pieces of information and all other input information is diffused as much as possible across the available outputs; and

applying input and/or output encodings which are nonlinear bijections.

21. The method as claimed in claim 8, in which said software algorithm is the Data Encryption Standard (DES) algorithm, said method comprising the steps of:

hiding a DES cryptographic key through partial evaluation into the DES S-boxes, resulting in 16×

8=128 key-embedded s-boxes.

22. The method as claimed in claim 21, further comprising the prior step of:

rolling the 16 rounds of said DES algorithm out into sequential code.

23. The method as claimed in claim 8, in which said software algorithm is the Advanced Encryption Standard (AES) algorithm, said method comprising the steps of:

hiding an AES cryptographic key through partial evaluation into the AES S-boxes, resulting in 16×

10=160 key-embedded s-boxes.

24. The method as claimed in claim 23, further comprising the prior step of:

rolling the 16 rounds of said AES algorithm out into sequential code.

25. The method as claimed in either of claims 11 or 18, comprising the step of:

rendering said key-embedded DES S-boxes into lossless T-boxes by the addition of two bits of input, and four bits of output, where the output consists of the four bits of output from the lossy key-embedded DES s-box, followed by the first bit of input, then the sixth bit of input, and finally the new seventh and eighth bits of input.

26. The method as claimed in either of claims 5 or 25, further comprising the step of:

preserving the input information to a round of DES in the output via the two additional bits of input to the standard T-boxes, and through the creation of four additional T-boxes, the operation of which is a bijective linear transformation.

27. The method as claimed in claim 19, in which the linear connective components of DES, including the P permutation, the addition of left hand side data to right hand side data, the swapping of data halves, the placement of bits for the bypass operation, and the expansion function, are expressed individually, as matrices.

28. The method as claimed in claim 19, in which the linear connective components of DES, including the P permutation, the addition of left hand side data to right hand side data, the swapping of data halves, the placement of bits for the bypass operation, and the expansion function, are expressed in conjunction, as matrices.

29. The method as claimed in claim 19, in which the linear connective components of AES, including the ShiftRows and MixColumns transformations, are expressed individually, as matrices.

30. The method as claimed in claim 19, in which the linear connective components of AES, including the ShiftRows and MixColumns transformations, are expressed in conjunction, as matrices.

31. The method as claimed in any one of claims 27 through 30, further comprising the steps of:

diffusing the matrix representations of said linear connective components using encodings which are linear bijections, and in which said linear bijections are invertible using an additional linear connective component.

32. The method as claimed in any one of claims 27 through 30, further comprising the steps of:

computing said linear connective components using a blocked and encoded matrix representation, with further encoded lossy subcomponents optionally used to provide the addition and concatenation operations on the outputs of the block computations.

33. The method as claimed in claim 32, further comprising the step of:

choosing said output encodings of the linear connective component blocks of DES or AES in such a way that the encodings remain well-defined upon the addition of two encoded block outputs, thereby eliminating the need to represent the lossy addition subcomponents as lookup tables.

34. The method as claimed in either of claims 3 or 4, in which the input and output of said software algorithm is subjected to a linear bijection over the whole of the input or output, with representation and computation options as with any linear connective component.

77. A method as claimed in claim 1, wherein said encoding functions are bijections.

89. A system for executing the method of any one of claims 1 through 80.

90. An apparatus for executing the method of any one of claims 1 through 80.

91. The apparatus of claim 90, wherein said apparatus is a secure platform.

92. The apparatus of claim 90, wherein said apparatus is a Smart Card.

93. A computer readable memory medium for storing software code executable to perform the method steps of any one of claims 1 through 80.

94. A carrier signal incorporating software code executable to perform the method steps of any one of claims 1 through 80.

35. A method of protecting computer software comprising the steps of:

identifying functions and transforms substantive to the targeted software program;

generating new functions and transforms which alter the processing activity visible to the attacker; and

replacing those identified functions and transforms with the new functions and transforms in the software program.

36. The method as claimed in claim 35, wherein said step of generating comprises:

generating non-linear transforms, which are difficult for an attacker to reduce.

37. The method as claimed in claim 35, wherein said step of generating comprises:

generating new transforms that eliminate data.

38. The method as claimed in claim 35, wherein said step of generating comprises:

generating new transforms that eliminate processing steps;

thereby making processing activity disappear.

39. The method as claimed in claim 35, wherein said step of generating comprises:

generating new, spurious, processing activity, by concatenating random transforms to real ones, and performing input and output encodings that introduce processing activity completely unrelated to the original data.

40. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the steps of:

changing the specific implementation of the software algorithm to make it combinatorially difficult for the attacker to identify the hidden information, as the primary means for providing security, which is irrelevant in the black box case.

41. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the steps of:

reducing visible processing activity, by replacing transforms with new transforms that eliminate processing steps.

42. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the steps of:

generating new, spurious, processing activity, by concatenating random transforms to real transforms, introducing processing activity completely unrelated to the original data.

43. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the steps of:

generating new, spurious, processing activity, by performing encodings that introduce processing activity completely unrelated to the original data.

44. The method of claim 40, wherein said step of changing comprises:

replacing linear transformations in said computer software, with non-linear transformations, making reduction very difficult;

thereby protecting said software against an attacker who has control over the input to said software, access to the output of said software, and is able to monitor the execution of said software.

45. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the steps of:

substituting functions in said computer software with suitable non-linear bijections.

46. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the step of performing matrix encodings.

47. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the steps of generating an encoded network.

48. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the steps of:

replacing adjacent transforms A and B, with new transforms AX and X<sup>−

1</sup> B.

49. The method of claim 48 wherein said step of replacing comprises the steps of:

identifying successive transforms A and B within said software;

generating an encoding transform X;

replacing transform A within said software, with new transform AX; and

replacing transform B within said software, with new transform X<sup>−

1</sup>B.

50. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the steps of:

performing complementary encoding of operands of functions in said computer software.

51. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the step of performing input/output blocked encoding.

52. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the step of adding irrelevant data to real data.

53. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the step of adding vector-wise concatenations to said computer software code.

54. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the step of performing encoded function concatenations.

55. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the step of concatenating two existing matrices.

56. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the steps of:

separately decoding the outputs of an encoded bijective transform at two sites using different decoding functions, one of which obtains the result of said transform, and one of which inverts the encoded bijective transform to obtain its input, thereby simultaneously computing the transform and preserving its inputs.

57. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the steps of:

for a given transform;

identifying data values to be passed through said transform unchanged, calculating input values to said existing matrix which yield said identified data values to be passed through, when operated upon by said random matrix.

58. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the step of performing general bypass encoding.

59. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the steps of:

substituting functions in said computer software with suitable non-linear input/output (I/O) blocked bijections of said functions.

60. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the step of adding bit-wise concatenations to said computer software code.

61. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the step of split-path encoding functions in said computer software.

62. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the step of performing partial evaluation encoding.

63. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the step of incorporating confidential data into said linear transformations.

64. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the step of reducing visible processing activity, by replacing transforms with new transforms that eliminate data.

65. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the step of adding matrix-wise concatenations to said computer software code.

67. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the steps of:

partially evaluating an existing matrix, some of whose input bits are constant, and

replacing said matrix with the matrix resulting from said partial evaluation.

68. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the steps of:

defining the input bits to certain input bits of said existing matrix P as constant values; and

generating a partially evaluated matrix Q to replace said existing matrix P by defining each output of matrix Q.

69. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the step of performing simultaneous bypass encoding.

70. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the step of simultaneous by-pass encoding of functions in said computer software.

71. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the step of performing output splitting.

72. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the steps of eliminating unary constant vector add and constant vector multiply nodes entirely by composing them into their adjacent binary vector add nodes, thereby saving some space by eliminating their substitution boxes.

73. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the steps of:

avoiding blocking which produces blocks which contain little input information (such as zero blocks).

74. The method as claimed in claim 35, wherein said steps of generating and replacing comprise the steps of:

dividing matrix L into two linear mixing bijections, L1 and L2, and encoding the two functions separately into networks of substitution boxes.

84. The method of claim 35 wherein said computer software is a symmetric block cipher.

85. The method as claimed in claim 35 further comprising the step of unrolling rounds of an encryption/decryption algorithm

86. The method of claim 35 wherein said computer software uses substitution boxes.

87. The method of claim 35 wherein said linear transformations are vector to vector transformations.

88. The method of claim 35 wherein said linear transformations include Expansion and P-box permutations performed in DES (data encryption standard).

66. A method of obscuring comprising the steps of:

for a given transform;

determining the new, desired output values corresponding to certain input values; and

defining an encoded transformation which provides said new, desired output values corresponding to certain input values; and

replacing said given transform in said software, with said encoded transform.

75. A method of obscuring computer software comprising the step of:

concatenating functions in said computer software with one another.

76. A method of obscuring computer software comprising the step of:

split-path encoding of functions in said computer software.

78. A method of obscuring computer software comprising the step of:

output splitting of functions in said computer software.

79. A method of obscuring computer software comprising the step of:

replacing functions in said computer software with substitution boxes.

80. A method of obscuring computer software comprising the step of:

replacing functions in said computer software with networks of substitution boxes.

81. A method comprising:

adding redundant transforms into the data path of said software program; and

interchanging definitions between added matrices and existing matrices.

82. A method of obfuscating software comprising:

generating a random function;

composing a random function with an existing function; and

composing a subsequently applied function with an inverse of said random function.

83. A method of obfuscating software comprising:

generating a random matrix;

right multiplying said random matrix by an existing matrix; and

right multiplying a subsequently applied matrix by an inverse of said random matrix.

95. A method of protecting computer software comprising the steps of:

replacing linear transformations in said computer software, with non-linear transformations, making reduction very difficult.

96. A method of protecting computer software comprising the steps of:

reducing visible processing activity, by replacing transforms with new transforms that eliminate data.

97. A method of protecting computer software comprising the steps of:

reducing visible processing activity, by replacing transforms with new transforms that eliminate processing steps.

98. A method of protecting computer software comprising the steps of:

laying a software algorithm over a Banyan network of mixing or processing nodes.

99. A method of protecting computer software comprising the steps of:

generating new, spurious, processing activity, by concatenating random transforms to real transforms, introducing processing activity completely unrelated to the original data.

100. A method of protecting computer software comprising the steps of:

generating new, spurious, processing activity, by performing encodings that introduce processing activity completely unrelated to the original data.

101. A method of protecting computer software comprising the steps of:

effectively making the input and output unknown to the attacker by prepending and appending random or pseudo-random ciphers.