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

• US 7,397,916 B2
• Filed: 12/10/2001
• Issued: 07/08/2008
• Est. Priority Date: 12/08/2000
• Status: Expired due to Fees

• Current Assignee: Cloakware Incorporated (MultiChoice Group Ltd.)
• Original Assignee: Cloakware Incorporated (MultiChoice Group Ltd.)
• Inventors: Johnson, Harold J., Chow, Stanley T., Eisen, Philip A.
• Primary Examiner(s): Zand; Kambiz
• Assistant Examiner(s): Simitoski; Michael J.
• Application Number:
  US10/433,966
• Publication Number:
  US 20040139340A1
• Time in Patent Office: 2,402 Days
• Field of Search: 380/28, 713/194, 713/190
• US Class Current: 380/28
• 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 a software algorithm to foil tracing and other static, dynamic, and statistical attacks comprising the steps of:

(a) identifying a step in the software algorithm which comprises a simple function representable as a lookup table whereby the simple function is computable by a table lookup;

(b) converting the simple function to a lookup table, whereby the lookup table, when indexed by an input to the simple function or by a bit-string concatenation of multiple inputs to the simple function, returns an element which is a corresponding output of the simple function or a bit-string concatenation of multiple outputs of the simple function;

(c) replacing the lookup table by one of a new lookup table and a non-looping computation by computing the net final result of the functional composition of the identified simple function itself and one of, or both of, the following;

(i) a randomly chosen, nonlinear bijection on the input or the concatenation of multiple inputs of the identified simple function, whereby each input is subjected to a single bijective encoding; and

,

(ii) a randomly chosen, nonlinear bijection on the output or the concatenation of multiple outputs of the identified simple function, whereby each output subjected to a single bijective encoding;

whereby the new lookup table or non-looping computation employs input encoding (i), and/or output encoding (ii), and the original computation no longer exists as a lookup table or non-looping computation and instead, only a modified computation computing a related function employing encoded input(s) and/or encoded output(s) exists, the identified simple function thereby being modified; and

,

(d) adjusting a context of the modified simple function whereby the context comprises computer code providing input(s) to the simple function and accepting output(s) of the simple function, and the modified simple function is also modified to provide input(s) with the same encoding(s) as employed for input(s) in the input- and/or output-encoded lookup table or non-looping computation of (c) above, and/or to accept a output(s) with the same encoding(s) as employed for output(s) in the input- and/or output-encoded lookup table or non-looping computation of (c) above.

2. The method of claim 1 whereby the identifying of the simple function representable as a lookup table is repeated for multiple simple function within the software algorithm, and each of those identified simple functions is converted to encoded lookup tables or non-looping computations and processed according to steps (b), (c) and (d) of claim 1.

3. The method of claim 2 whereby a group of such simple functions are within the software algorithm prior to the modifying of the software algorithm, each such simple function having an input or an output, which is an output or an input, respectively, of another of the simple functions in the group, and for which the simple functions of the group are connected by means of the output of one being an input to another, the encodings of step (c) being chosen so that the conversion of each simple function of the group is constrained to produce choices for which the output encoding matches the corresponding input encoding.

4. The method of claim 3, further comprising the step of preserving input information in the outputs of the identified simple functions of the group by combining a step or component comprising one identified simple function and a copy operation comprising another identified simple function into one step or component, thereby producing a combined simple function performing the functionality of both the step or component and the copy, with the information thereby bypassing the step or component.

5. The method of claim 4, further comprising the step of employing two distinct encodings of the outputs of the combination whereby one such encoding interprets the combined step or component according to the original step or component;

the other encoding interpreting the combined step or component as a copy operation, whereby copying and transformation are simultaneously achieved.

6. The method of claim 3 whereby the group of simple functions comprises a function expressible as a network of linear functions which are, by the random choices of input and output encodings of step (c) de-linearized.

7. The method of claim 6 whereby the network of linear functions performs the computation of a matrix-based function and components of the network comprise functions obtained by blocking the matrix into smaller submatrices.

8. The method of claim 7 whereby, in addition to encoding the simple functions individually, a group of simple functions comprising a network of linear functions derived from the matrix blocking are further protected by encoding the matrix prior to the matrix blocking, the matrix encoding performed by composing the matrix with a linear bijection matrix for input-vector encoding and/or a linear bijection matrix for output-vector encoding and converting it into a network of linear functions comprising a group of simple functions.

9. The method of claim 8 whereby the linear bijections which perform input- and/or output-vector encoding are employed for input and/or output whitening for a cipher.

10. The method of claim 3 whereby the input-output-connected group of simple functions computes a function which is further protected by a prior addition of a network of functions which processes the inputs and/or outputs of the network of functions to encode its inputs and/or outputs to cause the network of functions to have a topology that is a full M by N switching network in which a data path connects every one of the M inputs of the network of functions to every one of the N outputs of the network of functions.

11. The method of claim 3 whereby the software algorithm is first protected by partial evaluation with respect to some or all of its constant inputs or parameters, by diffusing the inputs or parameters into other parts of the software algorithm.

12. The method of claim 11 whereby one such constant input or parameter is a cryptographic key and the software algorithm comprises a cipher.