Method for Effective Tamper Resistance

• US 20090049308A1
• Filed: 06/06/2008
• Published: 02/19/2009
• Est. Priority Date: 12/19/2006
• Status: Active Grant

• Current Assignee: Ginger M. Myles, Hongxia Jin, Jeffrey Bruce Lotspiech
• Original Assignee: Ginger M. Myles, Hongxia Jin, Jeffrey Bruce Lotspiech
• Inventors: Jin, Hongxia, Lotspiech, Jeffrey Bruce, Myles, Ginger M.
• Granted Patent: US 7,996,685 B2
• Time in Patent Office: Days
• US Class Current: 713/187
• CPC Class Codes: G06F 21/14 against software analysis or reverse engineering, e.g. by obfuscation

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.

Claims

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 ki+1=ki vj (mod n) where phi(n) is a composite that is hard to factor and an initial key value k0 is a value in the subgroup defined by hb(mod n) where j is an element in the integer set Z and h=ga (mod n) and g is a generator for the group defined by gi (mod n) wherein vj is transformed into a member in the subgroup.

6. The method of claim 5 wherein key evolution is determined by ki+1=ki*vj (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 ki+1=ki*vj (mod n), and vj is transformed into a member in the subgroup by XORing another value cj=vj XOR ge where e is an element in Integer set Z.

8. The method of claim 7 wherein ki+1=ki*(vj XOR c j) and c j is a function of k i.

9. The method of claim 8 wherein ki+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 ki XOR c j.

10. The method of claim 1 further comprising:

transforming each of the key values 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 each of the key values, 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 each of the key values, 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 each of the key values 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 each of the key values, 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 each of the key values, 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 the evolving comprises key evolution that is determined by ki+1=ki vj (mod n) where phi(n) is a composite that is hard to factor and an initial key value k0 is a value in the subgroup defined by hb(mod n) where j is an element in the integer set Z and h=ga (mod n) and g is a generator for the group defined by gi (mod n) wherein vj is transformed into a member in the subgroup.

23. The product of claim 22 wherein the key evolution is determined by ki+1=ki*vj (mod n) where n=p*q and p and q are two large primes.

24. The product of claim 22 wherein the key evolution is determined by ki+1=ki*vj (mod n), and vj is transformed into a member in the subgroup by XORing another value cj=vj XOR ge where e is an element in Integer set Z.

25. The product of claim 24 wherein ki+1=ki*(vj XOR c j) and c j is a function of k i.

26. The product of claim 25 wherein ki+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 ki XOR c j.

27. The product of claim 18 further comprising:

a third code means for transforming each of the key values into 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 each of the key values, 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 each of the key values, 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 transforming each of the key values 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 each of key values, 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 each of key values, 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. (canceled)