Method for effective tamper resistance

• US 7,996,685 B2
• Filed: 06/06/2008
• Issued: 08/09/2011
• Est. Priority Date: 12/19/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jin, Hongxia, Lotspiech, Jeffrey Bruce, Myles, Ginger M.
• Primary Examiner(s): Srivastava; Vivek
• Assistant Examiner(s): TRUONG, THONG P
• Application Number:
  US12/135,052
• Publication Number:
  US 20090049308A1
• Time in Patent Office: 1,159 Days
• Field of Search: 713/156, 713/187, 713/194
• US Class Current: 713/189
• 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 offline tampering of a software program, implemented by a computer, comprising:

evolving a unique initial key value assigned to a copy of the software program when the copy of the software program executes using an integrity check and a one-way function that produces a new key value within a chosen mathematical subgroup, such that the new key value will stay within the subgroup unless tampering to the copy of the software program occurs; and

regulating behavior of the copy of the software program using the new key value, such that the integrity check fails if the evolved new key value is incorrect and the copy of the software program will not function correctly.

2. The method of claim 1, wherein the unique initial key is evolved at deterministic points within the copy of the software program.

3. The method of claim 1, wherein the unique initial key is evolved at non-deterministic points within the copy of the software program.

4. The method of claim 1 wherein key evolution is determined by k_i+1=k_i*(mod n) where phi(n) is a composite that is hard to factor and an initial key value k₀ 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ⁱ (mod n) wherein v_j is transformed into a member in the subgroup.

5. The method of claim 4 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.

6. The method of claim 4 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.

7. The method of claim 6 wherein k_i+1=k_i*(v_j XOR c_j) and c_j is a function of k_i.

8. The method of claim 7 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.

9. The method of claim 1 further comprising:

transforming the new key value into a constant in the copy of the software program, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect constant value.

10. The method of claim 1 further comprising:

encrypting crucial code in the copy of the software program using the new key value, so only the correctly calculated key can decrypt the code correctly for proper program execution.

11. The method of claim 1 further comprising:

determining a correct target address in a branch function using the new key value, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect target address.

12. The method of claim 1 further comprising

selectively executing edit scripts that transform software program code for the copy of the software program, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect edit script selection.

13. The method of claim 1 further comprising:

transforming the new key value into a constant in the copy of the software program, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect constant value;

encrypting crucial code in the copy of the software program using the new 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 new 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.

14. The method of claim 1 further comprising:

irretrievably deleting an integrity check value that resulted from the integrity check, to prevent future use of the unique initial key.

15. The method of claim 1, wherein if the integrity check fails, further comprising:

recording the integrity check value in a event log, and

transmitting the new key value and the event log to a software clearinghouse to verify that the copy of the software program has been tampered with.

16. A computer program product for preventing offline analysis and modification of software content for offline tamper resistance of software content, the computer program product usable with a programmable computer having readable program code embodied on a computer readable non-transitory storage medium therein, the readable program code comprising:

computer readable program code configured to evolve a unique initial key value assigned to a copy of the software program when the copy of the software program executes using an integrity check and a one-way function that produces a new key value within a chosen mathematical subgroup, such that the new key value will stay within the subgroup unless tampering to the copy of the software program occurs; and

computer readable program code configured to regulate behavior of the copy of the software program using the new key value, such that the integrity check fails if the evolved new key value is incorrect and the copy of the software program will not function correctly.

17. The computer program product of claim 16, wherein the unique initial key is evolved at deterministic points within the copy of the software program.

18. The computer program product of claim 16, wherein the unique initial key is evolved at non-deterministic points within the copy of the software program.

19. The computer program product of claim 16 wherein the evolving comprises key evolution that 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₀ 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ⁱ (mod n) wherein v_j is transformed into a member in the subgroup.

20. The computer program product of claim 19 wherein the 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.

21. The computer program product of claim 19 wherein the 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.

22. The computer program product of claim 21 wherein k_i+1=k_i*(v_j XOR c_j) and c_j is a function of k_i.

23. The computer program product of claim 22 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.

24. The computer program product of claim 16 further comprising:

computer readable program code configured to transform the new key value into a constant in the copy of the software program, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect constant value.

25. The computer program product of claim 16 further comprising:

computer readable program code configured to encrypt crucial code in the copy of the software program using the new key value, so only the correctly calculated key can decrypt the code correctly for proper program execution.

26. The computer program product of claim 16 further comprising:

computer readable program code configured to determine a correct target address in a branch function using the new key value, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect target address.

27. The computer program product of claim 16 further comprising

computer readable program code configured to selectively execute edit scripts that transform software program code for the copy of the software program, wherein program behavior is adversely affected by incorrect key evolution yielding an incorrect edit script selection.

28. The computer program product of claim 16, wherein if the integrity check fails, further comprising:

recording the integrity check value in a event log, and

transmitting the new key value and the event log to a software clearinghouse to verify that the copy of the software program has been tampered with.

29. The computer program product of claim 16, further comprising:

computer readable program code configured to irretrievably delete an integrity check value that resulted from the integrity check, to prevent future use of the unique initial key.