Electrical computers and digital processing systems: support – Data processing protection using cryptography – Computer instruction/address encryption
Reexamination Certificate
1998-03-25
2001-02-20
Peeso, Thomas R. (Department: 2767)
Electrical computers and digital processing systems: support
Data processing protection using cryptography
Computer instruction/address encryption
C713S187000, C713S189000, C713S193000, C705S055000
Reexamination Certificate
active
06192475
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of software security or protecting software from unauthorized use and from unauthorized analysis or modification, including reverse engineering.
BACKGROUND OF THE INVENTION
Unauthorized software use, or software piracy, has cost software producers and distributors billions of dollars worldwide. Consequently, there have been a number of methods developed to prevent software piracy.
One of the early approaches was to use various schemes to prevent copying of software. The was not popular with legitimate users, who wished to make backup copies. Further, these anti-copy schemes were based on methods that were so simple that programs were developed and sold that disabled the anti-copy mechanisms, thereby allowing unlimited copying. The whole approach was eventually dropped.
Another approach that is currently in use, involves a hardware key, sometimes referred to as a dongle. The dongle must be plugged into a port on the computer that is to run the software application in question. Functions are hidden within the application to be controlled that interrogate a key or keys in the dongle to verify authorization. The inconvenience of distributing and managing the dongle hardware devices has limited the use of this method to a very small market. Further, the method is not very secure since it is easy for an expert to find and bypass the software functions that interrogate the dongle.
Another approach has developed within the environment of local business networks; that is electronic license management. Within a network of computers, one particular computer is designated and set up as the license server for the whole network. This license server acts somewhat like the dongle described above, in that it provides keys and authorization information to other computers on the network. Protected applications contain hidden functions that interrogate the license server to verify authorization. These systems are not very popular since when there are network problems or when the license server itself fails, all associated applications stop working throughout the network. Further, like the dongle system, it is easy for an expert to find and bypass the interrogation functions hidden in the application.
Further, none of the above systems provide any protection against reverse engineering or unauthorized analysis and modification. These current anti-piracy systems provide no impediment to common reverse engineering techniques that can be used to discover confidential designs or to allow unauthorized modifications to the software.
An apparent solution, with some real security, might come from using technology developed for encrypting text. Executable software can be treated as binary text and encrypted using this well-known technology. The problem is that such encrypted software cannot execute or run. The only way to run it is to decrypt it back to its original form. Of course, once that is done, it can be copied or pirated.
SUMMARY OF THE INVENTION
It is the object of this invention to provide an improved process and method of encrypting software applications. The present invention comprises a method and apparatus of encrypting software applications, called cloaking, so that the cloaked applications can run or execute correctly when supplied with the correct key or keys. Further, when software has been cloaked, the task of decrypting it back to its original form, which can run without the need for keys, can be shown to be computationally intractable. In simple terms, you cannot decrypt it. In addition the software application is protected against reverse engineering and other unauthorized analysis or modification, even when keys are known. Further, the cloaked application will run at or near the speed of the original unencrypted application.
The cloaked software can be copied or distributed without the need for any keys, but it must have keys to execute properly. Although, if only reverse engineering protection is desired, the key values can be built in to the program.
The basic process of software cloaking is analogous to the compilation or binary translation process. The cloaking process entails:
reading in a standard representation of a program and translating it to an internal form
analyzing and then cloaking the internal form
translating the modified internal form into a standard representation and writing it out
In software cloaking, the modification of the internal form consists in the encryption of some or all of the load or store operations in the program Encrypting a load or store operation entails replacing its addressing expression with a different one that is augmented with additional index expressions like an array reference. For example, the memory operand x will be replaced by one in the form A(f
1
(v
1
), . . . , f
n
(v
n
), where the subscript functions, f
i
(v
I
), are linear functions of index variables. The calculation of these subscript functions in the program involves using special addressing values, including keys and possibly system identifiers, such that the various augmented memory operands will have the same overall effect as the original ones only when these special addressing values are correct. It is also possible to replace one array reference by another, augmented with additional index expressions.
The effect of this is as follows. Say the original program creates a value and stores it in a memory operand x. Later when the original program needs this value, it will load it from memory operand x. The cloaking process modifies the memory operand of the store to, say, A(f(i)) and the memory operand of the load to A(g)j), where i and j are index variables. In general, the new array reference forms will be more complex than these. With the proper addressing values, including keys or system identifiers, the store to A(f(i)) and the load from A(g(j)) will refer to the same memory location, even though that location will, in general, be different from that of x. Without the proper addressing values, the store to A(f(i)) will refer to a one memory location and the load from A(g)j) will refer to a different location. Consequently, the load will retrieve the wrong value. Conversely, without the proper addressing values, two different memory operands could refer to the same memory location, again resulting in incorrect values.
During normal, non-cloaked, program operation, a single non-array scalar variable is used repeatedly to hold values: the single variable is set to a value, used one or more times and then later reset with a new value and then that value is used and so on, all using the same storage location. These new values are always placed in the same location, so they are easy to analyze. After cloaking, new values are placed in constantly changing locations and further the uses of these values are done using addressing expressions that look like they are not related to the addressing expression that was used to set the value. Actually determining when addressing expressions refer to the same memory location, for the constantly changing index values in this context, requires solving a very difficult array dependence problem. This problem is known to be computationally intractable, specifically in technical terms, NP-complete. This implies that, with software cloaking, the problem of decryption can be made as difficult as desired.
REFERENCES:
patent: 4471163 (1984-09-01), Donald et al.
patent: 4558176 (1985-12-01), Arnold et al.
patent: 4562305 (1985-12-01), Gaffney, Jr.
patent: 4565901 (1986-01-01), Best
patent: 4571678 (1986-02-01), Chaitin
patent: 4584641 (1986-04-01), Guglielmino
patent: 4593353 (1986-06-01), Pickholtz
patent: 4644493 (1987-02-01), Chandra et al.
patent: 4796220 (1989-01-01), Wolfe
patent: 5109413 (1992-04-01), Comerford et al.
patent: 5123045 (1992-06-01), Ostrovsky et al.
patent: 5199066 (1993-03-01), Logan
patent: 5222133 (1993-06-01), Chou et al.
patent: 5249295 (1993-09-01), Briggs et al.
patent: 5295187 (1994-03-01), Miyoshi
patent: 5337357 (1994-08-01), Chou et al.
patent: 5343527
Jack Todd
LeBlanc Stephen J.
Peeso Thomas R.
The Law Offices of Jonathan Alan Quine
LandOfFree
System and method for cloaking software does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for cloaking software, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for cloaking software will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2613597