Tamper resistant methods and apparatus

BACKGROUND OF THE INVENTION

1.

Field of the Invention

The present invention relates to the field of system security. More specifically, the present invention relates to the tamper resistant methods and apparatus.

2.

Background Information

Many applications, e.g. financial transactions, unattended authorizations and content management, require the basic integrity of their operations to be assumed, or at least verified. While a number of security approaches such as encryption and decryption techniques are known in the art, unfortunately, the security approaches can be readily compromised, because these applications and the security approaches are implemented on systems with an open and accessible architecture, that renders both hardware and software including the security approaches observable and modifiable by a malevolent user or a malicious program.

Thus, a system based on open and accessible architecture is a fundamentally insecure platform, notwithstanding the employment of security measures. However, openness and accessibility offer a number of advantages, contributing to these systems' successes. Therefore, what is required are techniques that will render software execution virtually unobservable or unmodifiable on these fundamentally insecure platforms, notwithstanding their openness and accessibility.

Cohen F. B.: "OPERATING SYSTEM PROTECTION THROUGH PROGRAM EVOLUTION" COMPUTERS & SECURITY. INTERNATIONAL JOURNAL DEVOTED TO THE STUDY OF TECHNICAL AND FINANCIAL ASPECTS OF COMPUTER SECURITY, NL, ELSEVIER SCIENCE PUBLISHERS. AMSTERDAM, VOL. 12, NO. 6, 1 October 1993 (1993-10-01), pages 565-584, XP000415701 ISSN: 0167-4048 discloses protecting an operating system through program evolution by, for example, moving variables so that static examination and analysis of parameters in a program is prevented and the memory locations throughout a program are altered without affecting program execution. US-A-5347579 discloses modifying an archived diary entry by placing original text within compartment codes and by placing inserted text within insertion codes so that the original diary entry can be recreated from the modified diary entry. In this reference a program is loaded and sensitive elements in the program are decrypted. The decrypted data includes a secret, private key, a data encryption key and a manufacturers password and the decrypted data is placed in operating condition with the object code. Elements are encrypted with a conventional data encryption standard by the program manufacturer who includes the decryption code with its key in the program code. The purpose of the decryption key within program elements is to render it more difficult for someone to falsify authentication or to alter the archive file by decrypting, altering, and re-encrypting with another program. The program then jumps to the main part of the program where a file is selected.

US-A-5224160 discloses the use of a secret key in a symmetric cryptographic algorithm whereby a check number for each program is simultaneously formed and stored in the store of the system. The integrity of such a system is checked by recoding the programs and the check number thus obtained in each case is compared with the original, stored, check number.

The present invention seeks to provide a tamper resistant method and apparatus that renders software execution virtually unobservable or unmodifiable.

SUMMARY OF THE INVENTION

According to a first aspect of this invention there is provided an apparatus as claimed in claim 1 herein.

According to a second aspect of this invention there is provided a machine implemented method as claimed in claim 3 herein.

BRIEF DESCRIPTION OF DRAWINGS

The present invention will be described by way of embodiments, but not limitations, illustrated in the accompanying drawings in which like references denote similar elements, and in which: <ul id="ul0001" list-style="none" compact="compact"><li><b>Figure 1</b> is a block diagram illustrating a first aspect of the present invention for making a security sensitive program tamper resistant by distributing the program's secret(s) in time and in space;</li><li><b>Figure 2</b> is a block diagram illustrating one embodiment of the first aspect of the present invention including a subprogram generator for generating the subprograms that operate with corresponding subparts of the distributed secret(s);</li><li><b>Figure 3</b> is a flow diagram illustrating one embodiment of the operational flow of the subprogram generator of Figure 2;</li><li><b>Figure 4</b> is a block diagram illustrating a second aspect of the present invention for making a security sensitive program tamper resistant by obfuscating the various subparts of the security sensitive program;</li><li><b>Figure 5</b> is a block diagram illustrating one embodiment of a subpart of the obfuscated program;</li><li><b>Figure 6</b> is a block diagram illustrating one embodiment of the second aspect of the present invention including an obfuscation processor for generating the obfuscated program;</li><li><b>Figure 7</b> is a graphical diagram illustrating distribution of key period for the second aspect of the present invention;</li><li><b>Figures 8a - 8b</b> are flow diagrams illustrating one embodiment of the operational flow of the obfuscation processor of Figure 6;</li><li><b>Figure 9</b> is a flow diagram illustrating one embodiment of the operational logic of an obfuscated subprogram of the obfuscated program;</li><li><b>Figures 10 - 14</b> are diagrams illustrating a sample application of the second aspect of the present invention;</li><li><b>Figure 15</b> is a block diagram illustrating a third aspect of the present invention for making a security sensitive application tamper resistant;</li><li><b>Figure 16</b> is a block diagram illustrating a fourth aspect of the present invention for making a security sensitive system tamper resistant;</li><li><b>Figure 17</b> is a block diagram illustrating a fifth aspect of the present invention for making security sensitive industry tamper resistant; and</li><li><b>Figures 18 - 19</b> are block diagrams illustrating an example computer system and an embedded controller suitable for programming with the various aspects of the present invention.</li></ul>

DETAILED DESCRIPTION OF THE INVENTION

In the following description, various aspects of the present invention will be described. However, it will be apparent to those skilled in the art that the present invention may be practiced with only some or all aspects of the present invention. For purposes of explanation, specific numbers, materials and configurations are set forth in order to provide a thorough understanding of the present invention. However, it will also be apparent to one skilled in the art that the present invention may be practiced without the specific details. In other instances, well known features are omitted or simplified in order not to obscure the present invention.

Parts of the description will be presented in terms of operations performed by a computer system, using terms such as data, flags, bits, values, characters, strings, numbers and the like, consistent with the manner commonly employed by those skilled in the art to convey the substance of their work to others skilled in the art. As well understood by those skilled in the art, these quantities take the form of electrical, magnetic, or optical signals capable of being stored, transferred, combined, and otherwise manipulated through mechanical and electrical components of the computer system; and the term computer system include general purpose as well as special purpose data processing machines, systems, and the like, that are standalone, adjunct or embedded.

Various operations will be described as multiple discrete steps in turn in a manner that is most helpful in understanding the present invention, however, the order of description should not be construed as to imply that these operations are necessarily order dependent, in particular, the order of presentation.

Referring now to <b>Figure 1,</b> a block diagram illustrating a first aspect of the present invention is shown. In accordance with this first aspect of the present invention, security sensitive program <b>100</b> is made tamper resistant by distributing its secret in space as well as in time. The secret (not shown in totality) is "partitioned" into subparts <b>101,</b> and program <b>100</b> is unrolled into a number of subprograms <b>102</b> that operate with subparts <b>101;</b> for the illustrated embodiment, one subpart <b>101</b> per subprogram <b>102.</b> Subprograms <b>102</b> are then executed over a period of time. As a result, the complete secret cannot be observed or modified in any single point in space nor in any single point in time.

For example, consider the artificially simple "security sensitive" program for computing the result of X multiply by S, where S is the secret. Assuming S equals to 8, S can be divided into 4 subparts, with each subpart equals 2, and the "security sensitive" program can be unrolled into 4 subprograms with each program computing A = A + (X multiply by 2). Thus, the complete secret 8 can never be observed or modified in any point in space nor time.

As a further example, consider the "security sensitive" program for computing the result of (X to the power of S) modulo Y, where S again is the secret. If S equals 16, S can be divided into 8 subparts, with each subpart equals 2, and the "security sensitive" program can be unrolled into 8 subprograms with each program computing A = (A multiply by ((X to the power of 2) modulo Y)) modulo Y. Thus, the complete secret 16 can never be observed or modified in any point in space nor time.

As will be appreciated by those skilled in the art, the function (X to the power of S) modulo Y is the basis function employed in many asymmetric key (private/public key) schemes for encryption and decryption. Thus, by practicing this first aspect of the present invention, an encryption/decryption function can be made tamper resistant.

In one embodiment, the subprograms are further interleaved with unrelated tasks to further obscure the true nature of the tasks being performed by the unrolled subprograms. The tasks may even have no purpose to them.

<b>Figure 2</b> illustrates one embodiment of the first aspect of the present invention including a subprogram generator for generating the subprograms. For the illustrated embodiment, subprogram generator <b>104</b> is provided with the secret as input. Furthermore, subprogram generator <b>104</b> is provided with access to library <b>105</b> having entry, basis and prologue subprograms <b>106, 108,</b> and <b>109</b> for used in generating subprograms <b>102</b> of a particular security sensitive program in view of the secret provided. In other words, entry and basis subprograms <b>106</b> and <b>108</b> employed are different for different security sensitive programs. For the above illustrated examples, in the first case, entry and basis subprograms <b>106</b> and <b>108</b> will initialize and compute A = A + (X multiply by a subpart of S), whereas in the second case, entry and basis subprograms <b>106</b> and <b>108</b> will initialize and compute A = (A multiply by ((X to the power of a subpart of S) modulo Y)) modulo Y. Prologue subprogram 109 is used to perform post processing, e.g. outputting the computed results as decrypted content.

For the illustrated embodiment, entry subprogram <b>106</b> is used in particular to initialize an appropriate runtime table <b>110</b> for looking up basis values by basis subprogram <b>108,</b> and basis subprogram <b>108</b> is used to perform the basis computation using runtime table <b>110.</b> For the modulo function example discussed above, runtime table <b>110</b> is used to return basis values for (X to the power of a subpart of secret) modulo Y for various subpart values, and basis subprogram <b>108</b> is used to perform the basis computation of A = (A multiply by (basis value of a subpart of secret)) modulo Y, where A equals the accumulated intermediate results. A's initial value is 1.

For example, entry subprogram <b>106</b> may initialize a runtime table <b>110</b> of size three for storing the basis values of bv1, bv2 and bv3, where bv1, bv2 and bv3 equal (X to the power of 1) modulo Y, (X to the power of 2) modulo Y, and (X to the power of 3) modulo Y respectively. For the modulo function (X to the power 5) modulo Y, subprogram generator <b>104</b> may partition the secret 5 into two subparts with subpart values 3 and 2, and generate two basis programs <b>108</b> computing A = (A * Lkup(3)) modulo Y and A = (A * Lkup(2)) modulo Y respectively.

<b>Figure 3</b> illustrates one embodiment of the operational flow of subprogram generator <b>104</b> of <b>Figure 2.</b> For the illustrated embodiment, upon invocation, subprogram generator <b>104</b> first generates an instance of entry subprogram <b>106</b> for initializing at least an appropriate runtime lookup table <b>110</b> (Lkup) for returning the basis values of a modulo function for various subparts of a secret, and an accumulation variable (A) to an appropriate initial state, step <b>112.</b> Subprogram generator <b>104</b> then partitions the secret into subparts, step <b>114.</b> In one embodiment, the partition is performed to require the least number of basis programs, within the constraint of the basis values stored in runtime table <b>110.</b>

Next, subprogram generator <b>104</b> sets a subpart of the secret as the lookup index (LIDX), steps <b>116.</b> Then, subprogram generator <b>104</b> generates the current basis subprogram to compute A = [A multiply by Lkup (LIDX)] modulo Y, step <b>118.</b> Subprogram generator <b>104</b> repeats steps <b>116 - 118</b> for all subparts, until a basis program has been generated for each subpart of the secret, step <b>120.</b> Finally, subprogram generator <b>104</b> generates an instance of prologue subprogram <b>109</b> for performing post processing, as described earlier, step <b>122.</b>

<b>Figure 4</b> illustrates a second aspect of the present invention. In accordance with this second aspect of the present invention, security sensitive program <b>203</b> is made tamper resistant by obfuscating the program. Security sensitive program <b>203</b> is divided and processed into a number of obfuscated subprograms <b>204.</b> A plaintext (i.e. unmutated) appearance location schedule (i.e. where in memory) is selected for obfuscated subprograms <b>204.</b> For the illustrated embodiment, the plaintext appearance location schedule is formulated in terms of the memory cells <b>202</b> of two memory segments, memory segment <b>201</b> a and memory segment <b>201b.</b> Initially, except for the obfuscated subprogram <b>204</b> where the program's entry point is located, all other obfuscated subprograms <b>204</b> are stored in mutated states. Obfuscated subprograms <b>204</b> are recovered or made to appear in plaintext form at the desired memory cells <b>202,</b> one or more at a time, when they are needed for execution, and mutated again, once executions are completed. As will be described in more detail below, the initial mutated states, and the process of recovery are determined or performed, in accordance with one or more pseudo-randomly selected pattern of mutations. The pseudo-randomly selected pattern(s) of mutations is (are) determined using a predetermined mutation partnership function in conjunction with one or more ordered sets of pseudo-random keys. As a result, obfuscated subprograms <b>204</b> cyclically mutate back to their respective initial states after each execution pass. Actually, obfuscated subprograms <b>204</b> implementing the same loop also cyclically mutate back to the loop entry states after each pass through the loop.

For the illustrated embodiment, each obfuscated subprogram <b>204</b> and each cell <b>202</b> are of the same size, and first memory segment <b>201a</b> is located in high memory, whereas second memory segment <b>201b</b> is located in low memory. Furthermore, there are even number of obfuscated subprograms <b>204,</b> employing dummy subprogram if necessary.

<b>Figure 5</b> illustrated one embodiment of subprogram <b>204.</b> In accordance with the present invention, for the illustrated embodiment, in addition to original subprogram <b>102,</b> obfuscated subprogram <b>204</b> is provided with mutation partner identification function <b>206,</b> mutation function <b>207,</b> partner key <b>208</b> and jump block <b>209.</b> Original subprogram <b>102</b> performs a portion of the functions performed by program <b>200.</b> Original subprogram <b>102</b> may be an entry/basis/prologue subprogram <b>106/108/109</b> in accordance with the first aspect of the present invention. Mutation partner identification function <b>206</b> is used to identify the partner memory cells <b>202</b> for all memory cell <b>202</b> at each mutation round. In one embodiment, the partner identification function <b>206</b> is the function: Partner Cell ID = Cell ID XOR Pseudo-Random Key. For a pseudo-random key, mutation partner identification function <b>206</b> will identify a memory cell <b>202</b> in the second memory segment <b>201b</b> as the partner memory cell for of a memory cell <b>202</b> in the first memory segment <b>201a</b>, and vice versa. Only ordered sets of pseudo-random keys that will provide the required periods for the program and its loops will be employed. The length of a period is a function of the pseudo-random keys' set size (also referred to as key length). Mutation function <b>207</b> is used to mutate the content of the various memory cells <b>202.</b> In one embodiment, mutation function <b>207</b> XORs the content of each memory cell <b>202</b> in first memory segment <b>201 a</b> into the partner memory cell <b>202</b> in second memory segment <b>201b</b> in an odd mutation round, and XORS the content of each memory cell <b>202</b> in second memory segment <b>201b</b> into the partner memory cell <b>202</b> in first memory segment <b>201a</b> in an even mutation round. Partner key <b>208</b> is the pseudo-random key to be used by mutation partner identification function <b>206</b> to identify mutation partners of the various memory cells <b>202</b> for a mutation round. Jump block <b>209</b> transfers execution control to the next obfuscated subprogram <b>204,</b> which at the time of transfer, has been recovered into plaintext through the pseudo-random pattern of mutations.

In one embodiment, an obfuscated subprogram <b>204</b> may also include other functions being performed for other purposes or simply unrelated functions being performed to further obscure the subpart functions being performed.

<b>Figure 6</b> illustrates one embodiment of the second aspect of the present invention including an obfuscation processor for processing and transforming subprograms into obfuscated subprograms. For the illustrated embodiment, obfuscation processor <b>214</b> is provided with program <b>200</b> as inputs. Furthermore, obfuscation processor <b>214</b> is provided with access to pseudo-random keys' key length lookup table <b>212,</b> mutation partner identification function <b>206,</b> and mutation function <b>207.</b> For the illustrated embodiment, obfuscation processor <b>214</b> also uses two working matrices <b>213</b> during generation of obfuscated program <b>203</b>.

Key length lookup table <b>212</b> provides obfuscation processor <b>214</b> with key lengths that provide the required periods by the program and its loops. Key lengths that will provide the required periods is a function of the mutation technique and the partnership function. <b>Figure 7</b> illustrates various key lengths that will provide various periods for the first and second memory segment mutation technique and the partnership function described above.

Referring back to <b>Figure 6,</b> mutation partner identification function <b>206</b> identifies a mutation partner memory cell <b>202</b> for each memory cell <b>202.</b> In one embodiment, mutation partner identification function <b>206</b> identifies mutation partner memory cells in accordance with the "XOR" mutation partner identification function described earlier. Mutation function <b>207</b> mutates all memory cells <b>202.</b> In one embodiment, mutation function <b>207</b> mutates memory cells <b>202</b> in accordance with the two memory segments, odd and even round technique described earlier.

For the illustrated embodiment, working matrices <b>213</b> include two matrices M1 and M2. Working matrix M1 stores the Boolean functions of the current state of the various memory cells <b>202</b> in terms of the initial values of memory cells <b>202.</b> Working matrix M2 stores the Boolean functions for recovering the plaintext of the various obfuscated subprograms <b>204</b> in terms of the initial values of memory cells <b>202.</b>

Referring now to <b>Figures 8a - 8b,</b> two block diagrams illustrating one embodiment of obfuscation processor <b>214</b> are shown. For the illustrated embodiment, as shown in <b>Fig. 8a</b> in response to a program input (in object form), obfuscation processor <b>214</b> analyzes the program, step <b>216.</b> In particular, obfuscation processor <b>214</b> analyzes branch flow of the program, identifying loops within the program, using conventional compiler optimization techniques known in the art. For the purpose of this application, any execution control transfer, such as a call and subsequent return, is also considered a "loop".

Next, obfuscation processor <b>214</b> may perform an optional step of peephole randomization, step <b>218.</b> During this step, a peephole randomization pass over the program and replaces code patterns with random equivalent patterns chosen from an optional dictionary of such patterns. Whether it is performed depends on whether the machine architecture of the instructions provide alternate ways of accomplishing the same task.

Then, obfuscation processor <b>214</b> restructures and partitions the program <b>200</b> into a number of equal size subprograms <b>204</b> organized by their loop levels, padding the subprograms <b>204</b> if necessary, based on the analysis results, step <b>220</b>. Except for very simple program with a single execution path, virtually all programs <b>200</b> will require some amount of restructuring. Restructuring includes e.g. removing as well as adding branches, and replicating instructions in different loop levels. Restructuring is also performed using conventional compiler optimization techniques.

Finally, obfuscation processor <b>214</b> determines the subprograms' plaintext appearance location schedule, and the initial state values for the various memory cells <b>202,</b> step <b>221.</b>

<b>Fig. 8b</b> illustrates step <b>221</b> in further detail. As shown, obfuscation processor <b>214</b> first initializes first working matrix M1, step <b>222.</b> Then, obfuscation processor <b>214</b> selects a memory cell for the program's entry subprogram to appear in plaintext, step <b>223.</b> In one embodiment, the memory cell <b>202</b> is arbitrarily selected (within the proper memory segment <b>201a</b> or <b>201b).</b> Once selected, obfuscation processor <b>214</b> updates the second working matrix M2, step <b>224.</b>

Next, obfuscation processor <b>214</b> selects an appropriate key length based on the procedure's period requirement, accessing key length table <b>212,</b> step <b>226.</b> Obfuscation processor <b>214</b> then generates an ordered set of pseudo-random keys based on the selected key length, step <b>228.</b> For example, if key length equals 5 is selected among the key lengths that will provide a required period of 30, obfuscation processor <b>214</b> may randomly select 17, 18, 20, 24 and 16 as the ordered pseudo-random keys.

Next, obfuscation processor <b>214</b> determines the partner memory cells <b>202</b> for all memory cells <b>202</b> using the predetermined mutation partner identification function <b>206</b> and the next key in the selected set of ordered pseudo-random keys, step <b>230.</b> Upon making the determination, obfuscation processor <b>214</b> simulates a mutation, and updates M1 to reflect the results of the mutation, step <b>232.</b>

Once mutated, obfuscation processor <b>214</b> selects a memory cell for the next subprogram <b>204</b> to appear in plaintext, step <b>234.</b> Having done so, obfuscation processor <b>214</b> updates M2, and incrementally invert M2 using the Guassian Method, step <b>235.</b> In one embodiment, instead of incremental inversion, obfuscation processor <b>214</b> may just verify M2 remains invertable instead. If M2 is not invertable, obfuscation processor <b>214</b> cancels the memory cell selection, and restores M2 to its prior state, step <b>237.</b> Obfuscation processor <b>214</b> repeats steps <b>234 - 236</b> to select another memory cell <b>202.</b> Eventually, obfuscation processor <b>214</b> becomes successful.

Once succeeded, obfuscation processor <b>214</b> determines if there was a loop level change, step <b>238.</b> If there was a loop level change, obfuscation processor <b>214</b> further determines if the loop level change is down level or up level change, i.e. the subprogram is an entry subprogram of a new loop level or a return point of a higher loop level, step <b>239.</b> If the loop level change is "down", obfuscation processor <b>214</b> selects another appropriate key length based on the new loop's period requirement, accessing key length table <b>212,</b> step <b>241.</b> Obfuscation processor <b>214</b> then generates a new ordered set of pseudo-random keys based on the newly selected key length, step <b>242.</b> The newly generated ordered set of pseudo-random keys becomes the "top" set of pseudo-random keys. On the other hand, if the loop level change id "up", obfuscation processor <b>214</b> restores an immediately "lower" set of pseudo random keys to be the "top" set of pseudo-random keys, step <b>240.</b>

Upon properly organizing the "top" set of pseudo-random keys or upon determining there's no loop level change, obfuscation processor <b>214</b> again determines the partner memory cells <b>202</b> for all memory cells <b>202</b> using the predetermined mutation partner identification function <b>206</b> and the next key in the "top" set of ordered pseudo-random keys, step <b>243.</b> Upon making the determination, obfuscation processor <b>214</b> simulates a mutation, and updates M1 to reflect the results of the mutation, step <b>244.</b>

Once mutated, obfuscation processor <b>214</b> determines if there are more subprograms <b>204</b> to process, step <b>245.</b> If there are more subprograms <b>204</b> to process, obfuscation processor <b>214</b> returns to step <b>234</b> and proceeds as described eartier. Otherwise, obfuscation processor <b>214</b> inserts the mutation partner identification function <b>206,</b> the partner key to be used to identify mutation partner memory cells, the mutation function, the jump block, and the address of the next subprogram <b>204</b> into each of the obfuscated subprograms <b>204,</b> step <b>246.</b> Finally, obfuscation processor <b>214</b> computes the initial values of the various obfuscated subprograms <b>204,</b> and outputs them, steps <b>247 - 248.</b>

<b>Figure 9</b> illustrates one embodiment of the operational flow of an obfuscated subprogram <b>204.</b> For the illustrated embodiment, obfuscated subprogram <b>204</b> first executes the functions of the original subprogram, step <b>250.</b> For embodiments including additional and/or unrelated functions, they may be executed also. Then obfuscated subprogram <b>204</b> executes mutation partner identification function <b>206</b> to identify the mutation memory cell partners for all memory cells <b>202</b> using the stored partner key, step <b>252.</b> Having identified the mutation partners, obfuscated subprogram <b>204</b> executes mutation function <b>207</b> to mutate the memory cells based on the identified partnership.

Next, depending on whether obfuscated subprogram <b>204</b> is the last subprogram in an execution pass, obfuscated subprogram <b>204</b> either jumps to the next obfuscated subprogram (which should be in plaintext) or returns to the "caller". Note that if obfuscated subprogram <b>204</b> returns to the "caller", all other obfuscated subprograms <b>204</b> are in their respective initial states.

<b>Figures 10 - 14</b> illustrate a sample application of this second aspect of the present invention. <b>Figure 10</b> illustrates a sample security sensitive program <b>200</b> having six subprograms SPGM0 - SPGM5 implementing a simple single level logic, for ease of explanation, with contrived plaintext values of "000", "001", "010", "011", "100" and "111". Thus, the required period is 6. For ease of explanation, a keylength of one will be used, and the pseudo-random key selected is 3. Furthermore, the mutation partnership identification function is simply Partner Cell ID = Cell ID + 3, i.e. cell 0 always pairs with cell 3, cell 1 pairs with cell 4, and cell 2 pairs with cell 5.

<b>Figure 10</b> further illustrates at invocation (mutation 0), memory cells (c0 - c5) contains initial values (iv0 - iv5), as reflected by M1. Assuming, cell c0 is chosen for SPGM0, M2 is updated to reflect that the Boolean function for recovering the plaintext of SPGM0 is simply iv0. <b>Figure 10</b> further illustrates the values stored in memory cells (c0 - c5) after the first mutation. Note that for the illustrated mutation technique, only the content of the memory cells (c3 - c5) have changed. M1 is updated to reflect the current state. Assuming, cell c3 is chosen for SPGM1, M2 is updated to reflect that the Boolean function for recovering the plaintext of SPGM1 is simply iv0 XOR iv3. Note that for convenience of manipulation, the columns of M2 have been swapped.

<b>Figure 11</b> illustrates the values stored in memory cells (c0 - c5) after the second, third and fourth mutations. As shown, the content of half of the memory cells (c0 - c5) changed alternatingly after each mutation. In each case, M1 is updated to reflect the current state. Assuming, cells c1, c4 and c2 are chosen for SPGM2, SPGM3 and SPGM4 respectively after the second, third and fourth mutations respectively, in each case M2 is updated to reflect that the Boolean functions for recovering the plaintexts of SPGM2, SPGM3 and SPGM4, i.e. iv4, iv1, and iv2 XOR iv5.

<b>Figure 12</b> illustrates the values stored in memory cells (c0 - c5) after the fifth mutation. As shown, the content of memory cells (c3 - c5) changed as in previous odd rounds of mutation. M1 is updated to reflect the current state. Assuming, cell c5 is chosen for SPGM5, M2 is updated to reflect that the Boolean function for recovering the plaintext of SPGM5 is iv5.

<b>Figure 13</b> illustrates how the initial values iv0 - iv5 are calculated from the inverse of M2, since M2 x ivs = SPGMs, ivs = M2-1 x SPGMs. Note that a "1" in M2-1 denotes the corresponding SPGM is selected, whereas a "0" in M2-1 denotes the corresponding SPGM is not selected, for computing the initial values (iv0 - iv5).

<b>Figure 14</b> illustrates the content of the memory cells of the above example during execution. Note that at any point in time, at most only two of the subprograms are observable in their plaintext forms. Note that the pairing of mutation partners is fixed only because of the single pseudo-random key and the simple mutation partner function employed, for ease of explanation. Note also that with another mutation, the content of the memory cells are back to their initial states. In other words, after each execution pass, the subprograms are in their initial states, ready for another invocation.

As will be appreciated by those skilled in the art, the above example is unrealistically simple for the purpose of explanation. The plaintext of a subprogram contains many more "0" and "1" bits, making it virtually impossible to distinguish memory cell storing an obfuscated subprogram in a mutated state from a memory cell storing an obfuscated subprogram in plaintext form. Thus, it is virtually impossible to infer the plaintext appearance location schedule from observing the mutations during execution.

<b>Figure 15</b> illustrates a third aspect of the present invention. In accordance with this aspect of the present invention, security sensitive application <b>300</b> may be made tamper resistant by isolating its security sensitive functions <b>302</b> and making them tamper proof by incorporating the first and/or second aspects of the present invention described above.

In employing the above described second aspect of the present invention, different sets of pseudo-random keys will produce a different pattern of mutations, even with the same mutation partner identification function. Thus, copies of the security sensitive application installed on different systems may be made unique by employing a different pattern of mutations through different sets of pseudo-random keys. Thus, the security sensitive applications installed in different systems are further resistant from class attack, even if the obfuscation scheme is understood from observation on one system.

<b>Figure 16</b> illustrates a fourth aspect of the present invention. In accordance with this aspect of the present invention, a security sensitive system <b>400</b> may be made tamper resistant by making its security sensitive applications <b>400a</b> and <b>400b</b> tamper resistant in accordance with the first, second and/or third aspects of the present invention described above. Furthermore, security of system <b>400</b> may be further strengthened by providing system integrity verification program (SIVP) <b>404</b> having a number of integrity verification kernels (IVKs). For the illustrated embodiment, a first and a second level IVK <b>406a</b> and <b>406b.</b> First level IVK <b>406a</b> has a published extemal interface for other tamper resistant security sensitive functions (SSFs) <b>402a - 402b</b> of the security sensitive applications <b>400a - 400b</b> to call. Both IVKs are made tamper resistant in accordance with the first and the second aspects of the present invention described earlier. Together, the tamper resistant SSFs <b>402a - 402b</b> and IVKs <b>406a - 406b</b> implement an interlocking trust mechanism.

In accordance with the interlocking trust mechanism, for the illustrated embodiment, tamper resistant SSF1 and SSF2 <b>402a - 402b</b> are responsible for the integrity of security sensitive applications <b>400a - 400b</b> respectively. IVK1 and IVK2 <b>406a - 406b</b> are responsible for the integrity of SIVP <b>404.</b> Upon verifying the integrity of security sensitive application 400a or 400b it is responsible for, SSF1/SSF2 <b>402a - 402b</b> will call IVK1 <b>406a.</b> In response, IVK1 <b>406a</b> will verify the integrity of SIVP <b>404.</b> Upon successfully doing so, IVK1 <b>406a</b> calls IVK2 <b>406b,</b> which in response, will also verify the integrity of SIVP <b>404.</b>

Thus, in order to tamper with security sensitive application <b>400a,</b> SSF1 <b>402a,</b> IVK1 <b>406a</b> and IVK2 <b>406b</b> must be tamper with at the same time. However, because IVK1 and IVK2 <b>406a - 406b</b> are also used by SSF2 and any other SSFs on the system, all other SSFs must be tamper with at the same time.

<b>Figure 17</b> illustrates a fifth aspect of the present invention. In accordance with this aspect of the present invention, content industry association <b>500,</b> content manufacturers <b>502,</b> content reader manufacturers <b>510</b> and content player manufacturer <b>506</b> may jointly implement a coordinated encryption/decryption scheme, with content players <b>508</b> manufactured by content player manufacturers <b>506</b> employing playing software that include content decryption function made tamper resistant in accordance with the above described various aspects of the present invention.

Content industry association <b>500</b> owns and holds secret private encryption key Kciapri. Content industry association <b>500</b> encrypts content manufacturer's secret content encryption key Kc and content player manufacturer's public encryption Kppub for the respective manufacturers <b>502</b> and <b>506</b> using Kciapri, i.e. Kciapri[Kc] and Kciapri[Kppub].

Content manufacturer <b>502</b> encrypts its content product Kc[ctnt] and includes with the content product Kciapri[Kc]. Content reader manufacturer <b>510</b> includes with its content reader product <b>512</b> the public key of content industry association Kciapub, whereas content player manufacturer 506 includes with its content player product <b>508</b> content player manufacturer's secret private play key Kppri, content industry association's public key Kciapub, and the encrypted content player public key Kciapri[Kppub].

During operation, content reader product <b>512</b> reads encrypted content Kc[ctnt] and the encrypted content encryption key Kciapri[Kc]. Content reader product <b>512</b> decrypts Kc using Kciapub. Concurrently, content player product <b>508</b> recovers its public key Kppub by decrypting Kciapri[Kppub] using content industry association's public key Kciapub. Content reader product <b>512</b> and content player product <b>508</b> are also in communication with each other. Upon recovering its own public key, content player product <b>508</b> provides it to content reader product <b>512.</b> Content reader product <b>512</b> uses the provided player public key Kppub to encrypt the recovered content encryption key Kc, generating Kppub[Kc], which is returned to content player product <b>508.</b> In response, content player product <b>508</b> recovers content encrypt key Kc by decrypting Kppub[Kc] using its own private key Kppri.

Thus, as content reader product <b>512</b> reads encrypted content Kc[ctnt], and forwards them to content player product <b>508,</b> content player product <b>508</b> decrypts them with the recovered Kc, generating the unencrypted content (ctnt). In accordance with the above described aspects of the present invention, the decryption functions for recovering the content player's manufacturer's public key, and recovering the content encryption key Kc are made tamper resistant.

As will be appreciated by those skilled in the art, in addition to being made tamper resistant, by virtue of the interlocking trust, tampering with the content player product's decryption functions will require tampering of the content industry association, content manufacturer and content reader manufacturer's encryption/decryption functions, thus making it virtually impossible to compromise the various encryption/decryption functions' integrity.

As will be also appreciated by those skilled in the art, a manufacturer may play more than one role in the above described tamper resistant industry security scheme, e.g. manufacturing both the content reader and the content player products, as separate or combined products.

<b>Figure 18</b> illustrates a sample computer system suitable to be programmed with security sensitive programs/applications with or without SIVP, including industry wise security mechanism, made tamper resistant in accordance with the first, second, third, fourth and/or fifth aspect of the present invention. Sample computer system <b>600</b> includes CPU <b>602</b> and cache memory <b>604</b> coupled to each other through processor bus <b>605.</b> Sample computer system <b>600</b> also includes high performance I/O bus <b>608</b> and standard I/O bus <b>618.</b> Processor bus <b>605</b> and high performance I/O bus <b>608</b> are bridged by host bridge <b>606,</b> whereas high performance I/O bus <b>608</b> and standard I/O bus <b>618</b> are bridged by bus bridge <b>610.</b> Coupled to high performance I/O bus <b>608</b> are main memory <b>612,</b> and video memory <b>614.</b> Coupled to video memory <b>614</b> is video display <b>616.</b> Coupled to standard I/O bus <b>618</b> are mass storage <b>620,</b> and keyboard and pointing devices <b>622.</b>

These elements perform their conventional functions. In particular, mass storage <b>620</b> is used to provide permanent storage for the executable instructions of the various tamper resistant programs/applications, whereas main memory <b>612</b> is used to temporarily store the executable instructions tamper resistant programs/applications during execution by CPU <b>602.</b>

<b>Figure 19</b> illustrates a sample embedded controller suitable to be programmed with security sensitive programs for a security sensitive apparatus, made tamper resistant in accordance with the first, second, third, fourth and/or fifth aspect of the present invention. Sample embedded system <b>700</b> includes CPU <b>702,</b> main memory <b>704,</b> ROM <b>706</b> and I/O controller <b>708</b> coupled to each other through system bus <b>710.</b> These elements also perform their conventional functions. In particular, ROM <b>706</b> may be used to provide permanent and execute-in-place storage for the executable instructions of the various tamper resistant programs, whereas main memory <b>704</b> may used to provide temporary storage for various working data during execution of the executable instructions of the tamper resistant programs by CPU <b>702.</b>

Thus, various tamper resistant methods and apparatus have been described. While the methods and apparatus of the present invention have been described in terms of the above illustrated embodiments, those skilled in the art will recognize that the invention is not limited to the embodiments described. The present invention can be practiced with modification and alteration within the scope of the appended claims. The description is thus to be regarded as illustrative instead of restrictive on the present invention.