Among conventional methods for preventing a malicious analysis/tampering of a program that uses confidential information such as an encryption key, there is known a method for converting a program into an obfuscated program by modifying the control structure, process or the like of the program into a form with which such an analysis is difficult (for example, see Document 1). Here, the confidential information is such information that needs to be kept confidential from the third party.
Document 1 discloses a method for generating an obfuscated program by inserting copy creation type dummy code that is created by copying part of the original code, and does not have much effect on the program output results.
Here will be described a method of generating an obfuscated program by inserting a pseudo branch instruction and dummy block.
It is presumed here that an original program before obfuscation is composed of instruction group 1, instruction group 2, and instruction group 3, and that the three instruction groups are executed in the order.
In this obfuscation method, dummy variables, which are irrelevant to the execution of the original program, are added to the original program, and some program instruction groups, which rewrite the values of the dummy variables, are inserted into the execution code. Also, a pseudo branch instruction, whose branch destination is determined by a value of a dummy variable, is inserted between instruction group 1 and instruction group 2. This pseudo branch instruction contains a branch condition that always takes a constant truth value (for example, one that always takes a true value) depending on a value of a dummy variable that is determined when the program is executed. Further, the branch destination is set to be the instruction group 2 when the branch condition takes a true value, and is set to be a dummy block when the branch condition takes a false value,
The program that was obfuscated as described above is executed in the order of the instruction group 1, pseudo branch instruction, instruction group 2, and instruction group 3. Here, dummy blocks have also been added in the program. However, they are not executed when the program is executed in general use where a special operation, such as forcibly changing the program counter using a debugger or the like, is not executed.
The following describes a method of generating an obfuscated program by inserting the pseudo branch instruction.
It is presumed here that an original program before obfuscation is composed of instruction group 1, instruction group 2, and instruction group 3, and that the three instruction groups are executed in the order.
In this method, first a dummy variable is added into the original program. Next, a pseudo branch instruction, whose branch destination is determined by a value of a dummy variable, is inserted between instruction group 1 and instruction group 2. This pseudo branch instruction contains a branch condition that always takes a constant truth value (for example, one that always takes a true value) depending on a value of a dummy variable that is determined when the program is executed. Further, the branch destination is set to be the instruction group 2 when the branch condition takes a true value, and is set to be the instruction group 3 when the branch condition takes a false value,
The program that was obfuscated as described above is executed in the order of the instruction group 1, pseudo branch instruction, instruction group 2, and instruction group 3.
Document 1 discloses that with the above-described obfuscation, it becomes difficult to estimate an algorithm from the program and to estimate a location of a particular module. For example, when it is desired to protect an encryption key contained in an encryption algorithm program from an unauthorized analysis, it is possible to make difficult the estimation of a location of an encryption algorithm module.
However, even if the program control structure has been made complicated using such a method, the confidential information such as an encryption key exists somewhere in the program. As a result, when all the constant data existing in the program is collected, the confidential information is found in the collected constant data.
Accordingly, in the case of encryption algorithm, for example, an unauthorized analyzer can encrypt a plain text to obtain an encrypted text assuming that each piece of constant data existing in the program is an encryption key, and check whether the obtained encrypted text matches an actual encrypted text. By continuing this operation, the unauthorized analyzer can detect an authentic encryption key sooner or later.
With respect to this problem, Document 1 discloses a method of obfuscating a program by replacing a program instruction containing confidential information with a plurality of program instruction groups. Document 1 discloses, for example, that when “1234” contained in program instruction “d0=1234” is confidential information, the program instruction “d0=1234” is replaced with program instruction groups “d0=230”, “d0=d0+1000”, and “d0=d0+4”, and the program instruction groups are arranged separately in a distributed manner. With this method, even if all the constant data existing in the program is collected, it is impossible to detect the confidential information from the collected constant data. The plurality of program instructions generated by dividing the confidential information are called “divisional secrets”.    Document 1: Kamoshida, Matsumoto, Inoue, “On Constructing Tamper Resistant Software”, ISEC97-59    Document 2: Johaaes Koebler, Uwe Schoening, Jacobo Toran, “The Graph Isomorphism Problem”, Birkhaauser, 1993    Document 3: Seinosuke Toda, “Graph Isomorphism Problem”, College of Humanities and Sciences, Nihon University, 2001
USPTO Backgrounds
USPTO Backgrounds