Method for effective tamper resistance

Abstract

A system, method, and computer program product for preventing a malicious user from analyzing and modifying software content. The one-way functions used in prior art systems using dynamically evolving audit logs or self-modifying applications are replaced with a one-way function based on group theory. With this modification, untampered key evolution will occur inside a defined mathematical group such that all valid key values form a subgroup. However, if the program is altered, the key will evolve incorrectly and will no longer be a member of the subgroup. Once the key value is outside of the subgroup, it is not possible to return it to the subgroup. The present invention provides a limited total number of valid keys. The key evolution points are not restricted to locations along the deterministic path, so the key can be used in various novel ways to regulate the program's behavior, including in non-deterministic execution paths.

1 . A method for preventing analysis and modification of software content, comprising: evolving keys using a one-way function that produces key values within a chosen
 mathematical subgroup, so that evolved key values will stay within the subgroup unless tampering occurs; and   regulating software program behavior with the evolved keys.   
   
   
       2 . The method of  claim 1  further comprising:
 evolving integrity check values along with the keys.   
   
   
       3 . The method of  claim 2  further comprising:
 evolving at least, one of keys and integrity check values at deterministic points within a software program.   
   
   
       4 . The method of  claim 2  further comprising:
 evolving at least one of keys and integrity check values at non-deterministic points within a software program,   
   
   
       5 . The method of  claim 2  wherein key evolution is determined by k i+1 =k i v j (mod n) where phi(n) is a composite that is hard to factor and an initial key value k 0  is a value in the subgroup defined by h b (mod n) where j is an element in the integer set Z and h=g a  (mod n) and g is a generator for the group defined by g i (mod n) wherein v j  is transformed into a member in the subgroup. 
   
   
       6 . The method of  claim 5  wherein key evolution is determined by k i+1 =k i *v j  (mod n) where n=p*q and p and q are two large primes. 
   
   
       7 . The method of  claim 5  wherein key evolution is determined by k i+1 =k i *v j (mod n), and v j  is transformed into a member in the subgroup by XORing another value c j =v j  XOR g e  where e is an element in Integer set Z. 
   
   
       8 . The method of  claim 7  wherein k i+1 =k i *(v j  XOR c j ) and c j  is a function of k i . 
   
   
       9 . The method of  claim 8  wherein k i+1 =k i *(v j  XOR c j ) where c j =k i  XOR a value entry obtained from a table, and at table index i, the entry is k i  XOR c j . 
   
   
       10 . The method of  claim 1  further comprising:
 transforming the key value into a constant in the software program, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect constant value.   
   
   
       11 . The method of  claim 1  further comprising:
 encrypting crucial code in the software program using the key value, so only the correctly calculated key can decrypt the code correctly for proper program execution.   
   
   
       12 . The method of  claim 1  further comprising:
 determining a correct target address in a branch function using the key value, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect target address.   
   
   
       13 . The method of  claim 1  further comprising
 selectively executing edit scripts that transform software program code, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect edit script selection.   
   
   
       14 . The method of  claim 1  further comprising at least two of:
 transforming the key value into a constant in the software program, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect constant value;   encrypting crucial code in the software program using the key value, so only the correctly calculated key can decrypt the code correctly for proper program execution;   determining a correct target address in a branch function using the key value, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect target address; and   selectively executing edit scripts that transform software program code, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect edit script selection.   
   
   
       15 . The method of  claim 1  further comprising:
 calculating an integrity check value;   using the integrity check value to evolve a key; and   irretrievably deleting the integrity check value to prevent its future use.   
   
   
       16 . A method for preventing analysis and modification of software content, comprising:
 evolving keys using a one-way function that produces key values within a chosen mathematical subgroup, so that evolved key values will stay within the subgroup unless tampering occurs;   recording specific software program execution events in a dynamically evolving event log having values dependent on an evolving key and on previous log values; and   transmitting the event log to a clearinghouse for detection of tampering.   
   
   
       17 . The method of  claim 16  further comprising:
 calculating event log values that also depend on integrity check values.   
   
   
       18 . A computer program product comprising a machine-readable storage medium tangibly embodying program instructions thereon for preventing analysis and modification of software content, the instructions comprising:
 a first code means for evolving keys using a one-way function that produces key values within a chosen mathematical subgroup, so that evolved key values will stay within the subgroup unless tampering occurs; and   a second code means for regulating software program behavior with the evolved keys.   
   
   
       19 . The product of  claim 18  further comprising:
 a third code means for evolving integrity check values along with the keys.   
   
   
       20 . The product of  claim 19  further comprising:
 a fourth code means for evolving at least one of keys and integrity check values at deterministic points within a software program.   
   
   
       21 . The product of  claim 19  further comprising:
 a fourth code means for evolving at least one of keys and integrity check values at non-deterministic points within a software program.   
   
   
       22 . The product of  claim 19  wherein key evolution is determined by k i+1 =k i v j (mod n) where phi(n) is a composite that is hard to factor and an initial key value k 0  is a value in the subgroup defined by h b (mod n) where j is an element in the integer set Z and h=g a  (mod n) and g is a generator for the group defined by g i (mod n) wherein v j  is transformed into a member in the subgroup. 
   
   
       23 . The product of  claim 22  wherein key evolution is determined by k i+1 =k i *v j (mod n) where n=p*q and p and q are two large primes. 
   
   
       24 . The product of  claim 22  wherein key evolution is determined by k i+1 =k i *v j (mod n), and v j  is transformed into a member in the subgroup by XORing another value c j =v j  XOR g e  where e is an element in Integer set Z. 
   
   
       25 . The product of  claim 24  wherein k i+1 =k i *(v j  XOR c j ) and c j  is a function of k i . 
   
   
       26 . The product of  claim 25  wherein k i+1 =k i *(v j  XOR c j ) where c j =k i  XOR a value entry obtained from a table, and at table index i, the entry is h XOR c j . 
   
   
       27 . The product of  claim 18  further comprising:
 a third code means for transforming the key value info a constant in the software program, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect, constant value.   
   
   
       28 . The product of  claim 18  further comprising:
 a third code means for encrypting crucial code in the software program using the key value, so only the correctly calculated key can decrypt the code correctly for proper program execution.   
   
   
       29 . The product of  claim 18  further comprising:
 a third code means for determining a correct target address in a branch function using the key value, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect target address.   
   
   
       30 . The product of  claim 18  further comprising
 a third code means for selectively executing edit scripts that transform software program code, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect edit script selection.   
   
   
       31 . The product of  claim 18  further comprising at least two of:
 a third code means for transformina the key value into a constant in the software program, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect constant value;   a fourth code means for encrypting crucial code in the software program using the key value, so only the correctly calculated key can decrypt the code correctly for proper program execution;   a fifth code means for determining a correct target address in a branch function using the key value, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect target address; and   a sixth code means for selectively executing edit scripts that transform software program code, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect edit script selection.   
   
   
       32 . The product of  claim 18  further comprising:
 a third code means for calculating an integrity check value;   a fourth code means for using the integrity check value to evolve a key; and   a fifth code means for irretrievably deleting the integrity check value to prevent its future use.   
   
   
       33 . A product for preventing analysis and modification of software content, comprising:
 evolving keys using a one-way function that produces key values within a chosen mathematical subgroup, so that evolved key values will stay within the subgroup unless tampering occurs;   recording specific software program execution events in a dynamically evolving event log having values dependent on an evolving key and on previous log values; and   transmitting the event log to a clearinghouse for detection of tampering.   
   
   
       34 . The product of  claim 33  further comprising:
 calculating event log values that also depend on integrity check values.   
   
   
       35 . A. system for preventing analysis and modification of software content, comprising:
 means for evolving keys using a one-way function that produces key values within a chosen mathematical subgroup, so that evolved key values will stay within the subgroup unless tampering occurs; and   means for regulating software program behavior with the evolved keys.   
   
   
       36 . A system for preventing analysis and modification of software content, comprising:
 means for evolving keys using a one-way function that produces key values within a chosen mathematical subgroup, so that evolved key values will stay within the subgroup unless tampering occurs;   means for recording specific software program execution events in a dynamically evolving event log having values dependent on an evolving key and on previous log values; and   means for transmitting the event log to a clearinghouse for detection of tampering.