Home
Patent Search
IMT Blog
REGISTER
|
SIGN IN
United States Patent
4558176
Arnold , ; et al.
December 10, 1985
Title
Computer systems to inhibit unauthorized copying, unauthorized usage, and automated cracking of protected software
Abstract
A method and apparatus are provided for inhibiting unauthorized copying, unauthorized usage and automated cracking of proprietary software used in computer systems. The computer systems execute protected programs, which are protected by encapsulation and/or encryption. To provide security against unauthorized copying of software, means are provided that detect and inhibit automated cracking of protected programs. These means will destroy or make inaccessible information in the CPU during conditions when automated cracking could occur. These means will also store interrupt contexts in secret to prevent implementation of automated cracking. Additional features may be provided to allow operation as a general purpose computer system, where protected programs are distributed using public key cryptography and a means is provided to convert from this distribution form to the protected execution form.
Inventors:
Arnold; Mark G.
(Laramie,
WY
)
, Winkel; Mark D.
(Loveland,
CO
)
Appl. No.:
420562
Filed:
September 20, 1982
Current U.S. Class:
713/190
380/29
705/51
Field of Search:
178/22.08,22.09 364/200,300,900 340/825.34
U.S. Patent Documents
3958081
June 1976
Ehrsam et al.
3996449
December 1976
Attanasio et al.
4087856
May 1978
Attanasio
4120030
October 1978
Johnstone
4168396
September 1979
Best
4183085
January 1980
Roberts et al.
4193131
March 1980
Lennon et al.
4200770
April 1980
Hellman et al.
4238854
December 1980
Ehrsam et al.
4246638
January 1981
Thomas
4278837
July 1981
Best
4306289
December 1981
Lumley
4319079
March 1982
Best
4446519
May 1984
Thomas
4454594
June 1984
Heffron et al.
4458315
July 1984
Uchenick
4471163
September 1984
Donald et al.
Other References
Diffie et al., "Privacy & Authentication: An Introduction to Cryptography", IEEE Trans. Inform. Theory, Mar. 1979, pp. 397-427. .
Kunheim, Alan, Cryptograph: A Primer, 1981, pp. 6-8, 285, 286, 294, 334, 335..~
Primary Examiner:
Cangialosi; Salvatore
Assistant Examiner:
Steinberger; Brian
Claims
We claim:
1. A general purpose computer system for executing a plurality of encrypted software packages having provisions that inhibit unauthorized usage of encrypted software instructions comprising:
storage means for storing information;
processing means for executing re-encrypted software instructions from the current package using an execution key common to all re-encrypted software instructions, and for executing unencrypted software instructions;
said processing means including register/flag means for storing information being processed by said processing means under the control of said software instructions;
translation means, coupled to said processing means, operative for re-encrypting said plurality of encrypted software packages using said execution key to form a plurality of re-encrypted software packages;
said translation means including multiple translation prevention means for preventing said translation means from storing a second re-encrypted software package into locations of said storage means occupied by a first re-encrypted software package;
secure communication means, coupled to said processing means and said translation means, operative for buffering information between said processing means and said translation means, including information describing the region of said storage means occupied by said plurality of re-encrypted software packages;
said processing means including destruction means for destroying said execution key and the contents of said register/flag means upon receiving a destroy signal;
package description means for indicating the region of said storage means occupied by said current package;
violation recognition means, coupled to said destruction means, operative for generating said destroy signal if a re-encrypted software instruction came from a region of said storage means other than the region of said storage means indicated by said package description means; and
branch allowing means, coupled to said violation recognition means and to said package description means, operative for preventing said violation recognition means from generating said destroy signal when a re-encrypted software instruction executing in said processing means is a handshake instruction originating from a region of said storage means other than the region of said storage means indicated by said package description means, and further for establishing the region of said storage means that contains said handshake instruction as the current package in said package description means, and additionally for erasing a portion of the information contained in said register/flag means.
2. The device of claim 1, wherein said multiple translation prevention means includes:
translation stop register means for holding the address of the highest location at which said translation means stored a re-encrypted software instruction of said first re-encrypted software package;
translation address register means, for holdlng the address of the location at which a re-encrypted software instruction from said second re-encrypted soft-ware package is to be stored by said translation means;
comparator means, coupled to said translation stop register means and to said translation address register means, operative for testing if the value in said translation address register means is less than the value in said translation stop register means; and
storage prevention means, coupled to said comparator means, operative for preventing said translation means from storing a re-encrypted software instruction when said comparator means indicates that the value in said translation address register means is less than the value in said translation stop register means.
3. The device of claim 1, wherein said package description means comprises:
lower bounds memory means for storing a plurality of lowest addresses corresponding to each of said plurality of re-encrypted software packages residing in said storage means;
upper bounds memory means for storing a plurality of highest addresses corresponding to each of said plurality of re-encrypted software packages residing in said storage means;
lower transmitting means, coupled to said lower bound memory means, operative for transmitting from said lower bounds memory means the lowest address in the region of said storage means that contains said current package;
upper transmitting means, coupled to said upper bounds memory means, operative for transmitting from said upper bounds memory means the highest address in the region of said storage means that contains said current package; and
reload prevention means, coupled to said lower bounds memory means and to said upper bounds memory means, operative for preventing said lower bounds memory means from being loaded more than once, and for additionally preventing said upper bounds memory means from being loaded more than once.
4. the device of claim 3, wherein said violation recognition means comprises:
bounds testing means, coupled to said lower transmitting means and to said upper transmitting means, operative for testing if the address of the re-encrypted software instruction currently being executed by said processing means is within the region defined by said lowest address from said lower transmitting means and said upper address from said upper transmitting means, thereby generating an in-bounds signal; and
bounds destruction means, coupled to said destruction means and to said bounds testing means, operative for generating said destroy signal when said bounds testing means fails to produce an in-bounds signal during the execution of a re-encrypted software instruction by said processing means.
5. The device of claim 4, wherein said branch allowing means further comprises:
bounds re-establishing means, coupled to said lower bounds memory means, to said upper bounds memory means, to said lower transmitting means, and to said upper transmitting means, operative for replacing a first lower bound in said lower transmitting means with a second lower bound from said lower bounds memory means when said processing means changes control from a first package to a second package, and for additionally replacing a first upper bound in said upper transmitting means with a second upper bound from said upper bounds memory means when said processing means changes control from said first package to said second package;
control stack means for storing a plurality of return addresses in secret;
package calling means, coupled to said control stack means and to said bounds re-establishing means, operative for storing into said control stack means the address of the re-encrypted software instruction immeditely following a package call instruction, and for additionally causing said processing means to branch to the target address of the package call instruction;
call permitting means, coupled to said bounds destruction means and to said bounds re-establishing means, operative for preventing said bounds destruction means from generating a destroy signal when the current re-encrypted software instruction being executed by said processing means is a handshake instruction branched to by a package call instruction, and for additionally causing said bounds re-establishing means to replace the bounds in said package description means with the bounds of the region containing the handshake instruction that lies at the target address of said package call instruction; and
package returning means, coupled to said control stack means and to said bounds re-establishing means, operative for recalling and removing the last return address from said control stack means, and for additionally causing said processing means to branch to the return address recalled from said control stack means, and for causing said bounds re-establishing means to replace the bounds in said package description means with the bounds of the region inside of which the return address lies.
6. The device of claim 5 wherein said upper bounds memory means and said lower bounds memory means consist of a combined bounds memory means whereby said plurality of re-encrypted software packages are required to be stored contiguously in said storage means, and whereby each value in said combined bounds memory means represents both the upper bound of one package and one less than the lower bound of the next package.
7. The device of claim 5 wherein said bounds re-establishing means consists of searching means operative for searching said upper bounds memory means and said lower bounds memory means, and for finding an upper bound and corresponding lower bound which define a region of said storage means inside of which the re-encrypted software instruction currently being executed by said processing means resides.
8. The device of claim 7, wherein said bounds testing means further comprises:
above bounds testing means for testing if the address of the re-encrypted software instruction currently being executed by said processing means is above the value in said upper transmitting means, thereby producing an above-bounds signal; and
below bounds testing means for testing if the address of the re-encrypted software instruction currently being executed by said processing means is below the value in said lower transmitting means, thereby producing a below-bounds signal.
9. The device of claim 8, wherein said searching means consists of a successive approximation register means, coupled to said bounds testing means, to said upper bounds memory means and to said lower bounds memory means, operative for searching said upper bounds memory means and said lower bounds memory means using a binary search technique, whereby said successive approximation register determines the order of the items to be search in accordance with said in-bounds signal, said above-bounds signal, and said below-bounds signal produced by said bounds testing means, and whereby the values in said upper bounds memory means and said lower bounds memory means are stored in sorted order.
10. The device of claim 1, further comprising:
switching means, coupled to said processing means, operative for switching to execution of unencrypted software instructions when said processing means executes a re-encrypted switch instruction, and additionally for switching to execution of re-encrypted software instructions when said processing means executes an unencrypted switch instruction; and
switch re-establishing means, coupled to said processing means and to said package description means, operative for establishing the region of said storage means that contains said unencrypted switch instruction as said current package, and additionally for clearing at least a portion of the information in said register/flag means when said processing means executes a switch instruction.
11. A method for executing a plurality of encrypted software packages on a processor having a program counter, registers/flags, a decryption unit, and a storage unit, comprising the steps of:
selecting an execution key;
initializing a bounds memory, capable of holding lower bounds and upper bounds, to an empty condition;
choosing a load address;
translating one of said encrypted software packages, to form a reencrypted software package, whereby said re-encrypted software package is composed of a plurality of re-encrypted software instructions that are decryptable using said execution key;
storing said re-encrypted software package in a region of said storage unit beginning at said load address;
terminating said storing step if any re-encrypted software instructions were previously stored in said region;
recording the highest address of said region;
inserting in said bounds memory said load address as the lower bound corresponding to said re-encrypted software package, and said highest address as the upper bound corresponding to said re-encrypted software package;
repeating said steps of choosing, translating, storing, terminating, recording, and inserting for each of said plurality of encrypted software packages, to form a plurality of re-encrypted software packages;
establishing a current lower bound and a current upper bound from said bounds memory;
decrypting the re-encrypted software instruction pointed to by said program counter, using said decryption unit with said execution key, to form an unencrypted software instruction;
executing said unencrypted software instruction, to to perform useful results, and to form a new value in said program counter;
destroying said execution key and said registers/flags if said unencrypted software instruction is not a handshake instruction, and said program counter is above said current upper bound or below said current lower bound;
searching said bounds memory for a zone of said storage unit that surrounds the location pointed to by said program counter, if said unencrypted software instruction is a handshake instruction and said program counter is above said current upper bound or below said current lower bound, to form new values for said current lower bound, and said current upper bound; and
repeating said steps of decrypting, executing, destroying, and searching.
12. The process of claim 11 further comprising the step of relocating said encrypted software package, to form a relocated re-encrypted software package.
Description
FIELD OF THE INVENTION
This invention relates to digital computers and more particularly, to computer systems incorporating cryptographic and/or architectural features to inhibit unauthorized copying, unauthorized usage, and automated cracking of proprietary software.
BACKGROUND AND SUMMARY OF THE INVENTION
The burgeoning growth of the computer industry has brought with it a concomitant increase in unauthorized copying and usage of commercially successful proprietary software. This theft of software, known as software piracy, is of growing concern to industry. Vendors of software for general purpose computers lose millions of dollars of revenue annually as a result of software piracy. Software piracy also concerns manufacturers of equipment that use a computer as a dedicated controller, such as a video game.
Legal means for preventing software piracy have largely failed because of the problems of enforcement. The only practical way to protect proprietary software is to design computers with special features so that it is much cheaper to buy the proprietary software than to copy or crack it. Methods for preventing software piracy that have relied solely on software methods offer little protection. For example, the common technique of storing the program in an unusual format on a diskette can be circumvented through the use of a copy-all program.
Computer designs for discouraging software piracy that incorporate rudimentary encryption techniques which do not greatly increase the difficulty of copying proprietary software are known in the prior art, typified by the teachings of U.S. Pat. Nos. 4,168,396, 4,246,638, and 4,319,079. The prior art will not protect proprietary programs against software piracy since prior art interrupt and architectural features make the prior art susceptible to automated cracking techniques. These techniques allow a software pirate to crack proprietary software run on prior art computers so the software can be copied at a cost lower than the purchase price of the software. Another disadvantage of the prior art is that encryption must be done by the manufacturer of the computer, who will have a monopoly on this service. A further disadvantage of the prior art is that each protected program must run on a separate computer, which defeats the usefulness of a general purpose computer system.
While cryptographic systems that provide secure communications between computer systems are also known in the prior art as exemplified by U.S. Pat. Nos. 3,958,081, 4,200,770, and 4,238,854, they are limited in that they do not prevent software piracy.
While a third type of computer system that incorporates hardware features to insure operating system security are well known in the prior art as exemplified by U.S. Pat. No. 4,087,856, such systems are also limited in that they do not prevent software piracy.
Accordingly, it is an object of the present invention to inhibit unauthorized copying and usage of proprietary software by incorporating special hardware features in the design of a computer.
Another object of the present invention is to allow the user to protect proprietary software, thereby eliminating the previous need for an intermediary, such as the manufacturer of the computer, to protect the software.
Still another object of the present invention is to allow a user to combine protected proprietary software with unprotected programs, as well as to combine different protected proprietary programs rightfully obtained from others, for use on a general purpose computer system.
Still a further object of the present invention is to insure that protected software will load and execute with reasonable speed.
Still another object of the present invention is to retain compatability with current hardware and software practices.
Still a further object of the present invention is to allow the user to make as many backup copies of a protected program as he wishes for use on his general purpose computer system.
Still another object of the present invention is to allow the user of a general purpose computer system to customize a protected program in a way that does not reduce the security of the protection method.
Still a further object of the present invention is to allow a dedicated computer system to execute a protected program directly from a read only memory.
Still another object of the present invention is to minimize the amount of extra hardware required for protection of software in a dedicated computer system.
Still a further object of the present invention is to insure that the hardware required for protection of proprietary software is inexpensive and easy to fabricate.
These and other objects are accomplished in accordance with the illustrated preferred embodiments of the present invention by protecting proprietary software for use on a general purpose computer system with encryption. The protected programs are executed on a computer system that includes: a device for translating between a distribution encryption form of a protected program to an execution encryption form of the program, a device for executing the execution form of the program and also unprotected programs, and a device to detect and inhibit actions indicative of automated cracking techniques. The distribution encryption form of protected proprietary software utilizes public key cryptography thereby permitting anyone to protect software. The distribution encryption is unique for each general purpose computer system that uses the invention. The translation device is capable of translating many protected proprietary programs into the same execution encryption thereby allowing the user of a general purpose computer system to combine proprietary software rightfully obtained from others. The program execution device is capable of executing protected (encrypted) and unprotected (unencrypted) programs. Special hardware is provided to detect conditions that are likely to occur when the user attempts to implement automated cracking. Upon detection of these conditions, the hardware alters the state of the computer system, thereby invalidating any information the pirate might have gained. The hardware also causes a delay, which slows the automated cracking process so much that it requires several years to complete.
In accordance with another embodiment of the present invention, proprietary programs for use on a dedicated application computer system are protected by encryption and are executed on a computer system including: a device for executing the protected program and a device to detect and inhibit actions indicative of automated cracking techniques. The program execution device may be capable of executing both encrypted and unencrypted programs or the program execution device may be designed so it can only execute encrypted programs. Special hardware is provided to detect conditions that are likely to occur when a pirate attempts to implement automated cracking. Upon detection of these conditions the special hardware permanently alters a write once memory which makes the program execution device inoperative from then on, thereby invalidating any information the pirate might have gained. Alternatively, crucial parts of proprietary programs for use on a dedicated application computer system are protected by physical encapsulation and are executed on a computer system including: a device for executing the protected program, and a device to detect and inhibit actions indicative of automated cracking techniques. The program execution device can fetch instructions from either an internal, physically isolated memory means or the external memory. Special hardware is provided to detect conditions that are likely to occur when a pirate attempts to implement automated cracking of those instructions that reside in the internal physically encapsulated memory means. Upon detection of these conditions the special hardware prevents the execution of further instructions, thereby invalidating any information the pirate might have gained. The dedicated application computer system that protects with encryption and the dedicated application computer system that protects with encapsulation share many common features and therefore may be combined into a dedicated application computer system that allows the designer to select which protection method (encryption or encapsulation) will be used.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagram of a general purpose computer system with separate translation (PUBRAN) hardware and program execution (CPU) hardware, constructed in accordance with the preferred embodiment of the present invention.
FIG. 2 is a block diagram of the translation (PUBRAN) hardware used in the general purpose computer system of FIG. 1.
FIG. 3 is a block diagram of the RELOC unit used in the translation (PUBRAN) hardware of FIG. 2.
FIG. 4 is a block diagram of the DMA ADDRESS UNIT used in the translation (PUBRAN) hardware of FIG. 2.
FIG. 5 is a block diagram of the program execution (CPU) hardware used in FIG. 1.
FIG. 6 is a block diagram of the upper lower bounds test unit (ULBTU) used in the program execution (CPU) hardware of FIG. 5.
FIG. 7 is a block diagram of a dedicated application computer system that can execute programs protected with either encryption or encapsulation, and where the program may be stored in a read only memory (ROM), constructed in accordance with a second embodiment of the present invention.
FIG. 8 is a block diagram of the program execution (CPU) hardware used in FIG. 7.
FIG. 9 is a circuit diagram of a possible embodiment of the write once memory used in FIG. 8.
FIG. 10 is a block diagram of the ULBTU used in FIG. 8.
FIG. 11 is a block diagram of the SIR (encapsulation) used in FIG. 7.
FIG. 12A is a flowchart of an instruction test procedure.
FIG. 12B is a flowchart showing the details of the analyze step of FIG. 12A.
GENERAL DESCRIPTION INTRODUCTION TO THE PREFERRED EMBODIMENT
The preferred embodiment of the invention is a general purpose computer system having three primary features: the ability to execute encrypted programs, the ability to translate from the distribution form of a program to its execution form, and the ability to detect and inhibit cracking efforts. The corresponding names for these features are: the security CPU (Central Processing Unit), the PUBRAN Hardware, and the Destroy Key feature. The interaction of these components provides the requisite security and allows operation as a general purpose computer.
The security CPU has two modes of operation. In the unencrypted mode, it executes unencrypted programs and is fairly similar to prior art CPUs. In the encrypted mode, it executes encrypted programs. Since these programs are decrypted only inside the security CPU, which is enclosed in an impenetrable package (e.g., a microprocessor integrated circuit), the potential software pirate will not have access to the decrypted form of the program. He will be able to copy the encrypted program, but this will not help him make a usable copy since each microprocessor has a different decryption function. The unauthorized copy of a program will not execute on another computer. The decryption function is chosen so that it is difficult to mount a cryptanalytic attack. Therefore, it costs more to crack a program than to purchase it, and so the basic principle of protection is not contradicted.
It is desirable for protected programs to have reasonable execution speeds. This implies that the execution time decryption must be done quickly. Therefore, the form of the program that is executed must have been encrypted with a small block substitution cipher. Unfortunately, such ciphers are not secure enough for program distribution. Thus, two encryption formats are required: distribution encryption and execution encryption.
The distribution encryption does not utilize traditional encryption methods, but instead uses public key cryptography, which avoids the need for monopolies on encryption. Traditional methods use the same key for encryption and decryption. If the computer owner knew the key for his computer, he would be able to decrypt programs and make unauthorized copies. To prevent this, some intermediary such as the computer manufacturer, would have to be trusted with the encryption and decryption key for all such computers. This would create a monopoly on encryption.
Public key cryptographic systems avoid this problem by permitting secure communication directly between two parties. These cryptosystems utilize two keys: an encryption key and a decryption key. The encryption key is made public but the decryption key is kept private. Knowing the encryption key does not feasibly allow one to determine what the decryption key is. This implies that a software vendor can encrypt a program for a customer's computer without going through an intermediary. Methods of public key cryptography are given in "Privacy and Authentication: An Introduction to Cryptography," IEEE Trans. Inform. Theory, March 1979, pp. 397-427. Block ciphers, such as the Data Encryption Standard (DES) are also described.
In the preferred embodiment, the distribution format consists of two parts: a public key preamble, followed by the program encrypted using a large block cipher, such as DES. The software vendor will first select a DES key which will be used to encrypt the program. Then the vendor forms the public key preamble by encrypting the DES key using a public key algorithm with the public encryption key for the customer's computer. (Note that each computer will have a unique decryption key built into it and a corresponding encryption key that is made public.) This system provides good security while making distribution easy and permitting reasonable program load time.
The preferred execution encryption is a polyalphabetic nonperiodic, byte substitution cipher. This is also known as an address dependent byte substitution cipher. This allows protected programs to execute as fast as unprotected programs.
The present invention has a mechanism for converting from the distribution format to the execution format, which is called the PUBRAN hardware. It translates from the PUBlic key distribution form to the RANdom key execution form. Every time software is loaded, the PUBRAN hardware selects a new random key that is used to re-encrypt the software into the execution form. To accomplish this the present invention includes one or more WARMSTART instructions which cause the PUBRAN hardware to select a new random key. Also, the PUBRAN hardware selects a new random key when power is applied to the system.
The present invention also has a mechanism, called the "PUBRAN Only Once" (multiple translation prevention) feature, which insures that software that is loaded using the same execution key will not overlap in the same address space. If the "PUBRAN Only Once" feature were not used, or if a constant execution key were used, the system could be cracked quite quickly. For example, consider an eight bit computer with 64K bytes of address space. The software pirate would first have the PUBRAN hardware encrypt a "program" consisting of 64K bytes, each of which is zero. He would save the PUBRAN's output. He would then repeat the process with program consisting of 64K twos, 64K threes, etc. until he has encrypted all possible values at every memory location (i.e., after he has encrypted 64K bytes of 255's.) Once this is done, he will have created a decryption table that he can use to decrypt any program he desires. This type of attack is precluded by the PUBRAN hardware's selection of a random execution key and the "PUBRAN Only Once" feature. These insure that information gained at one load time will not be valid for the next load time.
The third and last primary feature of the invention is the Destroy Key mechanism. This causes the information in the CPU (i.e., the contents of registers and the execution key) to be destroyed upon detection of conditions that are likely to occur when a user attempts to crack a protected program. Execution of an unused opcode is one of several conditions that can trigger the destroy key feature.
A surprising result of the design of prior art CPUs is that they are susceptible to automated cracking procedures, one of which hereinafter is called an instruction test. An instruction test is a program that determines what an instruction is by examining the effects of its execution under controlled conditions. It involves: setting up preconditions (i.e., setting up registers and flags), executing the encrypted instruction in question, immediately dumping the postconditions (i.e., the registers and flags after the unknown instruction executes) and analyzing the changes in the status of the computer. Since the invention utilizes an address dependent execution encryption, the instruction to be tested must be executed at the address where it was loaded. Consequently, it may be necessary to modify some of the protected program to insert the instructions which set up the preconditions and the instructions to dump the postconditions. In doing this the pirate cannot be sure his modification will avoid an unused opcode. Execution of an unused opcode will destroy the execution key. In such a case, the pirate would be forced to reload the software and start all over. The invention is designed such that there is a high probability that modification will activate the Destroy Key mechanism and force reloading. In addition, the load time is long enough so that pirate will spend more time cracking a program than he would spend writing a similar program.
The essence of the first embodiment of the invention is a computer system having: (1) the capability to execute unencrypted and encrypted programs, (2) the capability to translate a program from its secure public key distribution form (encrypted software instructions) to the fast execution form (re-encrypted software instructions) using randomly chosen keys, and (3) the capability to detect and inhibit cracking of protected programs.
INTRODUCTION TO THE SECOND EMBODIMENT
There are many applications of computers where the program to be protected against software piracy resides in ROM. The system just described could accommodate such a program in ROM; however, the nature of the PUBRAN hardware and the random execution key require that the program be translated from ROM into RAM before it can be executed. In a general purpose computer system, this will not add additional hardware, since a large amount of RAM must be provided for user programmable memory. However, there are many applications of microcomputers which are not general purpose computer systems, but are dedicated controllers with a minimum of extra hardware. Many of these systems have highly valuable proprietary programs in ROM--video games, for example. For such dedicated applications there is a second embodiment of the invention which eliminates many of the features of the first embodiment in order to reduce the hardware requirements for the CPU and also allow direct execution of programs that reside in ROM.
There are two ways to implement the second embodiment. The first is to use encryption to protect a proprietary program which resides in a ROM that is external to the dedicated application CPU. The second way is to use encapsulation to protect that portion of a proprietary program which resides in a ROM that is fabricated on the same integrated circuit as the dedicated application CPU. A surprising result of prior art computer design is that even total encapsulation of a proprietary program is not enough to protect against software piracy, because both encrypted and encapsulated programs are susceptible to automated cracking techniques, such as the instruction test.
This introduction to the second embodiment will consider how the features of the first embodiment can be modified to implement protection by encryption in a dedicated application CPU. This introduction to the second embodiment concludes with an explanation of how encapsulation can be used as a protection method.
ENCRYPTION AS A PROTECTION METHOD
In the first embodiment of the invention there must be RAM into which the PUBRAN hardware can store the reencrypted program, which was encrypted using the randomly chosen execution key. In order to allow direct execution of programs stored in ROM, the PUBRAN hardware must be eliminated. Additional features must be added to the CPU, while others must be removed, in order to compensate for the security problems introduced by the elimination of the PUBRAN hardware. Since there is no PUBRAN hardware in the second embodiment, the hardware in the CPU for secret communications between the PUBRAN hardware and the CPU can be eliminated. There is no bus provided for the CPU to receive a random key, and instead the key must be programmed into an internal ROM (or other non-volatile memory) inside the CPU.
The primary feature that inhibits automated cracking of a protected program in the first embodiment of the invention is the destroy key feature. This causes the CPU to destroy the information in the registers of the CPU as well as the contents of the execution (random) key register. For example, the destroy key feature could trigger a clear on all of these registers. In the second embodiment of the invention, with a ROM holding the execution key, there will have to be an extra feature to implement the destroy key mechanism.
This extra feature has a single bit write once, read always, non-volatile memory. An example of such a memory is a fuse in a fusible link ROM. For reasons of security and power consumption, a more complicated implementation may be required, but conceptually a write once memory can be thought of as a fuse. When the CPU issues the destroy key signal (for instance, as the result of execution of an illegal instruction) the second embodiment of the invention will have the CPU destroy the registers and flags as it would in the first embodiment. However, instead of trying to destroy the information in the execution key ROM, the second embodiment will set the write once memory. For example, if a fuse were used, the destroy key signal would cause the fuse to be permanently blown. This action will thereafter indicate that the destroy key feature was invoked on that particular CPU.
In order to provide at least as much security as the random key of the first embodiment, the write once memory in the second embodiment is tested whenever the CPU attempts to execute an instruction. If the bit from the write once memory indicates that the destroy key feature was invoked, the CPU will refuse to execute any instructions. If the CPU is powered down, the bit in the write once memory is retained, so that when it is powered back up the CPU will still refuse to execute any instructions.
While this write once memory provides at least as much security as the first embodiment, it has a side effect that is unacceptable on a general purpose computer system: software errors can physically destroy the hardware. For this reason the second embodiment can only be used in dedicated applications.
ENCAPSULATION AS A PROTECTION METHOD
The discussion thus far has assumed that encryption will be used to protect the instructions in a proprietary program, however, there is a more direct way to protect the instructions: encapsulation of a memory for storing the protected program in the same integrated circuit as the CPU. Encapsulation could be used for either a general purpose computer system, in which case the encapsulated storage means would be RAM, or for a dedicated application computer system, in which case the encapsulated storage means could be ROM. Since the size of the encapsulated memory is limited due to the fact it will be fabricated on the same integrated circuit as the CPU, encapsulation is more practical for a dedicated application computer system than for a general purpose computer system, which would tend to have larger programs.
Even in a dedicated application computer system, the program size could easily exceed the size of the internal encapsulated ROM. To over come this restriction, means must be provided to allow execution of unprotected instructions from outside the internal encapsulated ROM. However, in allowing execution of unprotected instructions, the opportunity for a software pirate to implement an automated cracking procedure is also allowed in the absence of a means to inhibit automated cracking.
The means that detects and inhibits automated cracking in a computer system using encapsulation as the protection method need not check for illegal instructions, since the software pirate is not able to modify the contents of the internal ROM. However, a surprising result of the design of prior art CPUs is that they are susceptible to an instruction test procedure, even when the program is encapsulated inside an internal ROM. An instruction test is a program that determines what an instruction is by examining the effects of its execution under controlled conditions. It involves: setting up preconditions, executing the encapsulated instruction in question, dumping the postconditions, and analyzing the changes in the status of the computer. In order to set up an instruction test, a software pirate must be able to branch to an encapsulated instruction, allow execution of the instruction and branch back to the instruction test program (which will be unprotected). The way the software pirate would implement the requirements of an instruction test involves interrupts and branch instructions. Therefore, the means which detects and inhibits automated cracking of an encapsulated program must restrict the way in which branches and interrupts can occur. The Destroy Key feature of a computer system that uses encryption as the protection method will also restrict branches and interrupts, however it will add additional restrictions beyond those required in a system that uses only encapsulation.
DISCUSSION OF THE INVENTION
The present invention is complex and consists of many interrelated features. There are many trade-offs that can be made when implementing the present invention. The purpose of this section is to give the rationale behind the embodiments of the present invention and also to indicate alternative designs.
The description of the present invention begins by examining some software piracy methods, also known as cracking techniques, that a software pirate would use. This is followed by a discussion of the features common to all embodiments that are needed to inhibit such attacks. A discussion of the preferred embodiments will then explain why various features are required and how the invention is operated. It will also describe alternative methods of implementing the invention. Additional formulas and related technical information are also provided.
SOFTWARE PIRACY METHODS
As was previously noted, protection of software against piracy can only be achieved by incorporating special hardware into the design of computers. This hardware will require that software be customized for a specific computer. This is typically done by encryption and/or encapsulation. By themselves, such protection methods are inadequate since there are several automated cracking techniques that a pirate can use to crack protected programs. Two of the most powerful automated cracking techniques are the execution history and the instruction test. A study of these two techniques illustrates why the features of the present invention are required and how they inhibit automated cracking attacks.
The first automated cracking method is the execution history attack. An execution history is simply a record of all signals received by and emanating from the central processing unit (CPU). The essence of the execution history attack is that protected instructions can be discerned by observing the effects of their execution. Obviously, this method allows the pirate to crack only that part of the protected software that was executed. This attack can be accomplished with current technology at a price that is within the resources of most organizations and many individuals. The way a software pirate could obtain an execution history would be to use a separate computer, known as a probe computer, to monitor the activities of the security computer. The probe computer should be capable of: recording the state of all signals emanating from the security computer, feeding signals to the security computer (e.g. interrupts, halt, I/O) and modifying memory (this might involve swapping in another bank of memory). It could be programmed to analyze the protected program and perform automated attacks. It should be noted that a logic analyzer can serve as a simple probe computer.
The second automated cracking method is the instruction test attack. This attack is an extension of the execution history attack. Its basic premise still is that cracking of a protected instruction can be done by observing the effects of its execution, however this is not done in one step but rather in four steps. The first step is to establish the precondition. This involves setting flags, loading registers, providing timing signals or whatever else is required to put the security computer in a desired state. Secondly, the protected instruction is executed thereby altering the state of the computer. The third step is to completely dump the status of the computer, thereby forming the postcondition. This is usually accomplished by stores from registers to memory. Finally, the postcondition is then analyzed to infer what the protected instruction was. This is done by comparing the observed change in the status of the computer, caused by executing the protected instruction, with the known changes caused by each instruction in the instruction set. If the results are ambiguous, then a different precondition is set up and the process is repeated until there is only one instruction that can account for the observed change in the computer's status. The pirate then knows that this single instruction is actually the same as the protected instruction.
An unexpected feature of prior art computers is that the instruction test is quite effective in cracking protected software and can be accomplished with a rather short program. This, coupled with a probe computer, permits significant automated cracking of protected software. A further characteristic of the instruction test is that the pirate has complete control over which protected instructions are cracked. This is unlike the execution history where the pirate can only gain information about those sections of the program that were executed.
An important characteristic of the instruction test is that the pirate must have control of branching. For example, cracking a protected instruction might require setting up three preconditions to disambiguate it. Clearly, the software pirate requires branch control so that he can stop the execution flow, set up the next precondition and then reexecute the protected instruction in question. This branch control will rely on causing interrupts and/or selective modification of the protected program (when possible).
Referring to FIG. 12A, an instruction test procedure cracks a protected instruction by repeatedly executing the protected instruction under different preconditions and analyzing the results of execution. A software pirate could use an instruction test procedure, such as the one described, to circumvent prior art protection methods. The instruction test begins at step 700 by initializing the set of instructions to the set of all legal instructions in the instruction set of the computer running the protected program. At step 701, one of a list of preconditions is established in the registers and flags of the computer running the protected program. A surprising result of the design of prior art computers is that a software pirate can easily determine a short list of preconditions that will identify all unambiguous instructions in the instruction set of the computer running the protected program. The software pirate is able to create the list of preconditions based solely on the information contained in the published description of the instruction set.
Once one of these preconditions has been established in the registers and flags, the instruction test proceeds to step 702, at which time the protected instruction is executed. This usually involves the use of branching and/or interrupts (lines
710 and 711) to cause the protected instruction to be executed in isolation. After the protected instructions has executed, the contents of the registers and flags will have been modified.
At step 703 the modified contents of the registers and flags are dumped out of the computer running the protected program, thereby forming a postcondition. At step 704 the postcondition is analyzed to determine the identity of the protected instruction. This analysis proceeds by removing, from the set, those instructions that cannot account for the generation of the postcondition.
Since more than one precondition may be required to identify an instruction, step 705 tests if there are preconditions that have not yet been used. If there are any unused preconditions, control returns back to step 701. When there are no preconditions left from the list of preconditions, the protected instruction will have been identified, since it will be the only remaining element of the set. At step 706 this remaining instruction is given as the result of the instruction test of the particular protected instruction. If the software pirate desires to crack other protected instructions in the protected program, the instruction test procedure must be repeated starting at step 700, using another protected instruction.
Referring to FIGS. 12A and 12B, the analyze step 704 of the instruction test procedure flowchart removes candidate instructions from the set based on the precondition and the postcondition. At step 720, the next instruction in the set which has not yet been examined by the analyze routine is selected as a candidate for the protected instruction. At step 721 the result of this new candidate instruction is computed. There are several ways the result of the candidate instruction can be computed. Since the result of the candidate instruction is a function of the instruction and the same precondition used when executing the protected instruction, one way would be to use a table lookup method. A better way is to execute the candidate instruction after having set up the precondition in the registers and flags, thereby forming the result. This is analogous to steps 701, 702 and 703, however interrupts and/or branching (lines 710 and 711) may not be required since the candidate instruction is not a protected instruction.
Once the result of the candidate instruction has been computed, the flowchart proceeds to step 722. Step 722 tests if the result of the candidate instruction is not equal to the postcondition of the protected instruction. If the result is not equal to the postcondition, the candidate instruction is removed from the set. The current candidate instruction could not have accounted for the postcondition of the protected instruction, and so the current candidate instruction should not be considered as a candidate in the future. If the result of the candidate instruction is equal to the postcondition of the protected instruction, the candidate instruction remains in the set, however this does not mean that the candidate instruction is equivalent to the protected instruction. The candidate instruction simply remains a candidate at this point. Whether or not the candidate was removed from the set, the flowchart proceeds to step 724.
Step 724 tests if there are any instructions in the set which have not yet been selected as candidates during this execution of the analyze routine. If there are, the flowchart proceeds to step 720, where the next one of these untested candidates is selected. If all candidate instructions have been tested, control returns back to step 705. The net effect of executing the analyze portion of the flowchart is to remove all instructions from the set that cannot be candidates for the protected instruction, based on the current precondition and postcondition.
An instruction test is typically run under the control of a probe computer, which is used to create interrupts, swap memories, modify selected memory locations, and so forth. In such a system, the probe computer is responsible for all aspects of the instruction test other than executing the protected instruction and communicating the preconditions and postconditions. In other words, only step 702 and branching on lines 710 and 711 must be executed completely on the security computer. Steps 701
and 703 involve communication between the probe computer and the security computer.
COMMON PROTECTION FEATURES
All embodiments of the present invention have certain common features which are necessary to prevent the execution history attack and the instruction test attack. The discussion of these common features starts with those features designed to inhibit the execution history attack, then those designed to inhibit the instruction test attack, and concludes with those designed to inhibit both attacks.
The principle of the execution history attack is that protected instructions can be discerned by observing the effects of their execution. The first line of defense against this attack is to make it difficult to observe the inner workings of the CPU. Therefore, the present invention requires that the CPU be enclosed in an impenetrable package. Any attempt to pry open the package should destroy the CPU. An example of this is the standard epoxy package commonly used to encase integrated circuits, such as microprocessors. In addition to resisting mechanical entry, the package should be impervious to attack by chemicals, radiation, electric fields, magnetic fields, and so forth.
The efficacy of the execution history attack also depends upon the visibility of the instructions. An instruction is visible if its execution produces readily detectable effects. For example, all input/output instructions can be found by watching the I/O lines. Therefore, the present invention is designed so that instruction execution provides as little information as possible. The best architecture is one that has many registers in the CPU since instructions that manipulate things completely internal to the CPU (such as registers) will present few indications of their action. Note that for CPUs utilizing a stack architecture, it is imperative that the top levels of the stack reside in a memory internal to the CPU. Regardless of the architecture, all flags must be kept internal to the CPU. The flags (also known as condition codes, status bits, or program status words) are affected by many instructions and thus are a potent tool for determining the identity of a protected instruction.
Another way to reduce the visibility of instructions is to insure that their execution times are not unique. If each instruction took a different amount of time to execute, then the execution history could identify each protected instruction simply by measuring the time required for each instruction to execute. To avoid this problem, instructions should be classified in a small number of groups. All instructions in a particular group should have the same execution time. Note that this might require increasing the execution time of some instructions slightly.
A consequence of the execution history is that it makes it difficult to protect temporary variables. The only secure way to do this is to use a special scratch pad RAM internal to the CPU. This RAM would be used only for storing those temporary variables that are to be protected. This approach suffers from two problems, namely: only a limited number of temporary variables can be stored in the RAM, and the cost of manufacturing the present invention will be higher due to the added complexity of incorporating the RAM in the CPU.
Temporary variables could also be protected by encryption, although this also has disadvantages. A secure encryption scheme (such as DES) would involve substantial overhead time whenever a temporary was accessed. If smaller ciphers are used, then the changing value of the temporary will allow quick cracking of the cipher. This would certainly be the case if the pirate could find a loop index that was stored in memory after each iteration of the loop.
For reasons of economy and efficiency, the data protection features described above are not used in the preferred embodiments. For those applications demanding additional security, it would be possible to incorporate these features.
Another attack is the instruction test attack. An instruction test attack requires that the pirate have the ability to create branches in the execution flow by using interrupts or selective modification of the protected program. The present invention inhibits the instruction test by insuring that modification of execution flow will cause conditions that can be detected with a high degree of probability. Once such a condition has been detected, the status of the computer will be altered. This could be implemented so that the computer is rendered permanently inoperable or temporarily inoperable. In the latter case, it is best to incorporate an artificial delay before the computer can re-execute the protected software that was being cracked. If this delay time is properly chosen, the total time required to complete the automated cracking will be so long that it will not be economically worthwhile for a software pirate to crack the protected program.
The execution history and the instruction test both illustrate the need for having a secure control stack. If the control stack is accessible to external observation, it will permit the pirate to locate subroutines and determine their probable function. If the control stack could be modified, it would be an important method for the pirate to create the branching necessary for the instruction test. Therefore, the present invention insures the security of the control stack by encapsulating it in the CPU, where it will be inaccessible to external observation and modification. This stack will have enough levels to be able to handle typical programs and programs with limited recursion. An alternative design could be used to prevent control stack overflow for programs that are highly recursive. This would be done with a dynamically managed content addressable memory.
The execution history and the instruction test attacks also demonstrate the need for keeping the status of the CPU secure during interrupts. Prior art interrupt mechanisms usually store the complete status of the CPU in an external memory that a pirate could access directly. A pirate could readily crack protected programs on such machines simply by causing an interrupt after each instruction executes. This would display the contents of all registers and status flags. With this information, it would be a trivial task to determine what instructions were executed.
It might appear that secure status on interrupt could be achieved by encrypting the status before it is stored in the memory. However, the requisite security could only be achieved with a large block cipher (such as DES). Such ciphers usually have slow encryption speeds and consequently a computer utilizing them would not respond quickly to an interrupt. Small block ciphers offer faster encryption but are not secure. This is especially true if the pirate is creating interrupts, in which case the pirate knows two things: the address of the instruction to be executed upon return from the interrupt, and the encrypted return address placed on the control stack by the interrupt. In other words, the pirate knows the cleartext and encrypted form of the return address. Consequently, the encryption function is easily cracked simply by causing an interrupt after executing each instruction.
The best way to provide secure interrupt contexts is to store the interrupt context (including the return address) in a special RAM internal to the CPU. This memory is called the Interrupt Context Memory (ICM). Note that the ICM need only store the contexts of those interrupts that occur during execution of protected software. Since the ICM is internal to the CPU, it will be inaccessible to the pirate. Also note that all registers and flags should be altered after the interrupt context is stored in the ICM. If this were not done, then all the pirate would have to do is write his own interrupt routine to dump the registers and flags. In summary, any interrupt routine running on the present invention should not be able to access the status of the computer at the time of the interrupt.
The ICM could be designed in a number of ways. One would be to have special memory locations in the ICM for each level or type of interrupt. In other words, the highest priority interrupt would have a reserved place for its interrupt context, the next lowest interrupt would have a different reserved spot in the ICM and so forth. Although such a design is suitable for many applications, there are applications where a different ICM design would be required. For example, consider a multi-tasking operating system that uses an interval timer to activate and suspend processes. Where a timer interrupt occurs, the active process would be suspended, and its interrupt context would overwrite the interrupt context of a previously suspended process. Consequently, there would be no way to reactivate the previously suspended process.
A better design is to have the ICM contain storage for a certain number of interrupts. This storage is allocated not by interrupt priority or by the type of interrupt but rather to each successive interrupt. When an interrupt context is stored, it is associated with an environment number. This number is left in one of the registers. Restoration of an interrupt is done by executing a special instruction which specifies which interrupt environment number is to be restored (e.g. RESINT 5). The ICM is finite and thus a limit is imposed on the number of concurrent processes.
A third possible ICM design would allow only one interrupt from a protected program. This would be the least expensive and also the most inflexible way to implement an ICM.
In any design, the ICM should also be designed so that an interrupt context is not restored more than once. This could be accomplished by having a tag bit that would be set on the storing of an interrupt context and cleared on restoration of the interrupt context. Such a design would prohibit creation of loops via interrupts. This is important since many of the techniques a pirate would use for writing instruction tests would require such looping.
DISCUSSION OF THE FIRST EMBODIMENT
The common protection features described above, and summarized in Table I, must be augmented with additional protection mechanisms as required by the architecture and application of the security computer. For a general purpose security computer, these mechanisms must protect proprietary software and still permit the user to make back up copies. The user should also be able to execute unprotected programs and combine programs (protected or unprotected) rightfully obtained from others. The user should be able to protect software that he has created. These protection features must allow reasonable execution speed and also inhibit automated cracking.
These requirements are met in part by the system in the section entitled "Introduction to the First Embodiment." Of the features introduced in that section and summarized in Table II, the primary ones are: a CPU which executes encrypted programs, a public key cryptosystem for secure program distribution, a PUBRAN unit to translate the distribution form into an execution form, and features to destroy the state of the computer upon detection of conditions indicative of automated cracking.
TABLE I ______________________________________ Features Common to All Embodiments of the Present Invention Associated Protection Type of Attack Features in the CPU ______________________________________ Execution History impenetrable packaging many internal registers designed so that few instructions have unique execution times Instruction Test destroy mechanism renders the computer either permanently or temporarily inoperable Features Required by secure control stacks both the Execution History interrupt context memory Attack and the Instruction Test Attack ______________________________________
The details of these mechanisms are given in Table II and will be discussed below. The explanation starts with a review of how the fundamental security features preclude an exhaustive mapping attack. Ways to inhibit the instruction test attack and other related attacks are then discussed, followed by a description of miscellaneous aspects of the present invention. Notes on operation and usage conclude the discussion of the general purpose security computer.
EXHAUSTIVE MAPPING ATTACKS ON THE FIRST EMBODIMENT
An exhaustive mapping attack is one in which a pirate tries to compile a complete table of the encryption function, which he then uses to decrypt the encrypted software. This type of attack is precluded by the design of the present invention, which insures that neither the PUBRAN translation hardware nor the execution encryption can be exploited to create such a table.
The PUBRAN translation hardware cannot be subverted due to the synergistic interaction of three features: the address dependant execution encryption, the PUBRAN Only Once, and the generation of random execution keys. As was mentioned in the "Introduction to the Preferred Embodiment", a pirate could attempt to create an exhaustive mapping table by writing nonsense programs which would be loaded onto his general purpose security computer.
TABLE II __________________________________________________________________________ Features of the first embodiment (in addition to those given in Table I) CPU Translation (PUBRAN) Hardware Software Distribution __________________________________________________________________________ executes encrypted and unencrypted translates from secure distribution body of program encrypted software to execution form in a large block cipher SWITCH instruction requires LEE and PUBRAN instruction (e.g. DES) switches between execution modes small block cipher for fast execution unique public encryption key and preamble utilizing decryption key public key cryptosystems Preamble contains: address dependent execution cipher generates random crytographic key encryption key for execution cipher body of program checks for nonrandom performance WARMSART (load) contents of the execution key to external fields times register and other registers are accomplished by the WARMSTART program length destroyed for following conditons: instruction illegal/unused instructions branch out of program bounds. performs relocation with RELOC units Checked by ULBTU hardware. branch out of relative branch establishes and maintains program large block cipher is range PSTOP register address dependent implements "PUBRAN Only Once" (multiple translation prevention means) secure communication means between CPU and Translation Hardware internal bus if computer system is fabricated on one chip if CPU and translation hardware are seperate chips, then communication is done with a "one time pad" (OTPRNG hardware, etc.) variable load (WARMSTART) times CVC, HSK, RETCVC instructions for public key cryptosystem is used for placing interpackage communication and control manufacturer's digital signature on the translation unit separate encryption functions for each instruction field __________________________________________________________________________
A table could readily be compiled simply by associating the instructions (or data) in the nonsense program with their execution encrypted form. A pirate might think that a nonsense program consisting of the 256 hexadecimal numbers OOH to FFH (assuming a byte architecture) would allow compilation of a complete table. This is not true due to the address dependency of the execution encryption. Since each location has a different encryption function, a complete table would require loading all
256 possible values into all memory locations. This is prohibited by the PUBRAN Only Once feature which does not permit overwriting a previously loaded memory location until a new random execution key is generated. Generation of a new random key invalidates the partial table created from a previous load, thereby thwarting the pirate's exhaustive mapping attack.
Prevention of exhaustive mapping attacks also requires that different instruction fields be encrypted with different encryption functions. Consider what would happen if the same encryption function was used for instruction opcodes and operand addresses. A pirate would first locate a load instruction, since execution of a load allows the pirate to compile a table giving the encryption function for the load's operand field. This table could be created by saving the encrypted operand field on a disk file, executing the load instruction, and observing what address is placed on the address bus. If the pirate can set up a loop around the load instruction, then he can try all possible patterns for the encrypted operand address and see the corresponding cleartext address on the address bus. In other words, the pirate will have created a table giving the encryption function for the location containing the operand address. However, since only one encryption function was used, the table is also the encryption function for instruction opcodes. Thus the table could be used to encrypt a load instruction for the location that was cracked. The whole process is then applied to this new load instruction. It would only be a matter of minutes before all of memory was cracked. This clearly points out the need for using different encryption functions for different fields.
INSTRUCTION TEST ATTACKS ON THE FIRST EMBODIMENT
The instruction test attack is another potent attack that a general purpose security computer must withstand. Instruction test attacks are readily implemented on prior art computers simply by moving the instruction in question into a specific location and then jumping to that location. This will not work on a general purpose security computer due to the address dependent execution cipher. On a security computer, an instruction test attack must branch to the encrypted instruction in question, execute the instruction and return to the rest of the instruction test attack. On a general purpose security computer system, there are three ways that a pirate could try to create the modifications required for such branching. The first is to attempt to patch the protected program by loading over it with the appropriate program. The features that prohibit exhaustive mapping attacks also protect against this. The second is to bypass the PUBRAN translation hardware and directly modify locations in the encrypted program (with the aid of a probe computer). This is a trial and error process which will create conditions that can be detected, thereby causing activation of the destroy key mechanism. The third and last method is to write the instruction test attack as a separate program which will be loaded concurrently with the encrypted program that is to be cracked. Protection against this attack requires special features which place restrictions on interaction of programs. The features necessary to prevent implementing the instruction test attack via these three approaches are described below.
Implementing the instruction test attack by overlaying an encrypted program is prevented by the PUBRAN Only Once, the random execution key, and the address dependent execution encryption. The PUBRAN Only Once feature insures that a random key for execution encryption/decryption is selected before a program can be loaded over a currently loaded program. This means that a pirate cannot modify a program by trying to load another program over it. The only way to load a program over another program is to reinitialize the PUBRAN hardware by executing a WARMSTART instruction. This causes the PUBRAN unit to generate a new random key, which means that the CPU will not be able to execute programs previously loaded into memory, since they were encrypted with the old execution key.
The random cryptographic key used for the execution format guarantees that information obtained by attacks at one load time will not be applicable at later load times. This prohibits the pirate from inserting a program segment (e.g., instruction test) into a protected program with the following procedure: (1) the pirate has the PUBRAN hardware load the program segment; (2) the pirate saves the re-encrypted instructions in external storage; (3) the pirate re-initializes the PUBRAN hardware by executing a WARMSTART instruction; (4) the pirate has the PUBRAN hardware load the protected program; (5) the pirate alters the protected program by swapping in the modifications from external storage, thereby bypassing the protection provided by other parts of the system. Since the WARMSTART instruction causes a new key to be selected, the pirate cannot use the above procedure.
The address dependent execution cipher insures that the execution of the program, which involves decryption internal to the CPU, can be done only at the location at which the program was loaded. Shifting the program around in memory will prevent it from being decrypted properly and thus the program will not execute properly. This prevents the pirate from modifying the program by: (1) loading the program at one location, (2) loading modifications at another location, and (3) patching the program by moving the modifications into it.
Protection from the instruction test attack, implemented by directly modifying memory locations, requires all of the mechanisms mentioned in the "Common Protection Features" section. It also requires making it highly improbable that a pirate could bootstrap an instruction test attack by modifying memory locations. The goal is to make it so difficult that, on the average, it would take many years to crack a program. This is best done by limiting the rate at which modifications can be made. The present invention accomplishes this with the destroy key feature. Additional security can be achieved by incorporating a variable load time into the PUBRAN hardware.
The destroy key mechanism destroys, or alters, the CPU's execution key and internal state upon activation. This means that the pirate will have to reload the protected program and start all over with his attack. The destroy key mechanism is activated whenever conditions indicative of an attack are detected while the CPU is in encrypted execution mode. These special conditions are the occurrence of: an illegal instruction, a branch out of package bounds, a branch out of relative branch bounds, and indirect branches.
A feature of the present invention is that there are a number of instruction opcodes which cause activation of the destroy key mechanism when the CPU is in encrypted execution mode. In unencrypted execution mode, these opcodes may be treated as NOPs (no operation) or other legitimate instructions. However, if they are not treated as NOPs, they should be little used instructions since it would be undesirable to have a class of instructions that could be used in unencrypted mode but not encrypted mode.
The illegal instructions make it difficult for a pirate to modify an encrypted program. If he makes a modification, he runs the risk that the modification will be interpreted as an illegal instruction. In such a case, the execution key would be destroyed, thus forcing the pirate to reload the software that he is trying to crack. The PUBRAN hardware would reload it with a different random key which means that the encrypted form of the illegal instructions would have changed. Consequently, the pirate would not even be able to avoid the illegal instructions by a process of elimination. Every time he is forced to reload, he starts from scratch.
The probability that the pirate will make a successful modification is controlled by the number of illegal and warmstart instructions and the number of locations that must be modified to create an attack. For example, 2.6.times.10.sup.10 trials would be required to modify 10 locations in an encrypted program for a computer that had 9 illegal instructions and one WARMSTART instruction in its instruction set. More information on this is given in the section entitled "Modification Probabilities."
Illegal instructions are useful for inhibiting instruction test attacks, however it is possible for a pirate to successfully implement an instruction test program on a prior art computer that is augmented with illegal instructions. Therefore, the present invention includes features which inhibit such methods. One such feature activates the destroy key mechanism whenever an attempt is made to branch out of the bounds of an encrypted program. (Note that branches are not restricted in unencrypted mode.) The branch out of bounds could be implemented by examining the address field of all branch instructions or by comparing the contents of the program counter with the package bounds before fetching the next instruction. The latter method is preferred since it detects all conditions that attempt to execute outside of program bounds, such as relative branches or just sequential execution to the end of the package. (The only exceptions are some special instructions that facilitate interpackage communications. These will be covered toward the end of this section.)
This greatly enhances the security of the present invention by increasing the chance that the destroy key feature will be activated. For example, consider a 16K program that runs on a security computer having a 64K address space. The probability of successfully modifying an absolute branch address without triggering the destroy key feature will be one out of 49,153. If ten absolute branches had to be modified at the same time, the probability of success would be one out of
8.2.times.10.sup.46.
The branch out of bounds feature requires some additional hardware in the CPU to store package bounds and also to determine if execution has branched out of bounds. The package bounds information is obtained from the PUBRAN hardware which keeps track of the program bounds in order to implement the PUBRAN Only Once feature.
For adequate security, the branch out of bounds feature requires that absolute branch addresses be encrypted as a large unit such as sixteen bits. This insures that a modified branch address will most likely cause a branch out of package bounds. Encryption of addresses on a byte level would offer some security but is not preferred. A pirate could modify the low order byte of an address with relative impunity since this would only cause the modified branch target to be at most 256 locations from the original branch target. Most programs are larger than 256 instructions, and so the pirate would run little risk of branching out of the program's bounds if encryption of branch addresses is only done on a byte level. If the branch addresses are sufficiently long, then it is possible to encrypt them in units, however the low order unit should still contain a large number of bits. For example, a 24 bit address could be encrypted with a high order byte of 8 bits and a low order word of 16 bits. (Note that although absolute branches were discussed here, the same argument would apply for any branch instruction that has large address fields. For example, relative branch addresses should be encrypted as a single unit on computers that use a 16 bit relative branch.) Additionally, branch address modifications can cause illegal instructions to be executed, which in turn will activate the destroy key mechanism. Suppose that a pirate has modified an absolute branch without causing a branch out of bounds. If the modified branch points to an instruction in the program, then no illegal instructions will be encountered. If the branch points to the program's data, then the data will be treated as instructions, which the CPU will try to execute. There is a chance that this will lead to execution of an illegal instruction. A similar situation can occur with instruction misalignment on computers that have variable length instructions. For example, consider branch address modification on a computer that has single, double, and triple byte instructions. A modified branch inside the package might not point to the beginning of an instruction but rather to the middle or end of the instruction (e.g., operand or address fields). This misalignment could cause the CPU to execute an illegal instruction.
Branch out of relative branch range is another feature that may be implemented to provide additional security. Relative branches, which typically use an 8 bit address, can provide enough branch control to implement an instruction test attack. The limited range of a relative branch (typically .+-.127) means that modifications of a relative branch will seldom cause an out of package bounds condition (unless the relative branch instruction is close to the beginning or end of the program.) The remedy for this is to restrict the range of a relative branch. Any branch out of the range would activate the destroy key feature. For example, the present invention could be implemented with an 8 bit two's complement relative branch with a valid range of .+-.120. This means a relative branch address that decrypted within the ranges 127 to 121, and -128 to -121 would activate the destroy key feature.
In order to allow a non-pirate user to combine unencrypted software (such as an I/O driver) directly with encrypted software, the present invention includes a SWITCH instruction, which changes the execution mode from encrypted to unencrypted, or vice versa. An unexpected consequence of including such a simple SWITCH instruction in the present invention would be to allow a software pirate to implement an instruction test easily. If a pirate were able to place a SWITCH instruction in a protected program by modification, he could follow the SWITCH with whatever unencrypted software he desires. Therefore, it is imperative that the SWITCH instruction be implemented in one of the following two ways. The first method is to have the SWITCH instruction clear all registers in the computer before changing modes. This prohibits a pirate from dumping the status of the CPU immediately after the SWITCH and determining what the preceeding instructions are. This also means that memory will have to be used for transfer of information between encrypted and unencrypted programs. The second implementation requires the SWITCH instruction to have an opcode that is many bits long. The length of the opcode should be such that it is as difficult to create a SWITCH instruction by modification of an encrypted program as it is to create a complete instruction test attack by modification. An opcode length of 64 bits is probably sufficient and could be implemented as eight bytes. The probability of successfully creating a 64 bit SWITCH instruction is one out of 2.sup.64, since on a byte architecture the first byte determines that the instruction is a SWITCH, and the last seven bytes (56 bits) determine whether the destroy key mechanism will be activated. All but one combination of the last 56 bits of the SWITCH instruction will activate the destroy key. If greater security is required, a longer opcode length could be chosen. The preferred embodiment of the general purpose security computer implements both the clearing of the registers by the SWITCH instruction, and the long (64 bit) opcode length for the SWITCH instruction.
Another feature for improving security would impose restrictions on indirect branches when in encrypted execution mode. The problem with indirect branches is that their dynamic nature virtually makes them cleartext instructions, and consequently they may provide enough control for a pirate to create an instruction test attack. The remedy used in the preferred embodiment is to prohibit indirect branches in encrypted execution mode. Another remedy is to require special handshake instructions at the target of each indirect branch.
In review, there are several ways to design a security CPU so that modifications to a protected (encrypted) program will create conditions that activate the destroy key feature. The most important of these features are illegal instructions and branch out of program (package) bounds. The preferred embodiment also activates the destroy key feature on branch out of relative branch range (bounds), incorrect bit(s) in a SWITCH instruction, and indirect branches in encrypted mode. An important aspect of the present invention is that the basic security features of the invention force a pirate to modify an encrypted program. This will involve modification of instructions and/or branch addresses and will usually create conditions that will activate the destroy key mechanism.
Additional hardware in the PUBRAN unit greatly enhances security provided by the destroy key mechanism. By itself, the destroy key feature just guarantees that the pirate will have to reload the software fairly often which will not be a severe limitation if it takes a short time to load the software via the PUBRAN hardware. Consequently, it is desirable that the PUBRAN load time be long enough that a pirate could not expect to crack the program until after a couple of years have passed. There are three ways to manage the load time of the PUBRAN hardware. The first is to do nothing which would be appropriate if the PUBRAN hardware is inherently slow. Secondly, the PUBRAN could be manufactured so that it insures all loads will be at least a minimum time. For example, a program might be physically loaded in one second but the PUBRAN would not indicate that the load had completed until after ten seconds. The disadvantage with this approach is that it leaves the security of a protected program in the hands of the PUBRAN manufacturer and not the software developer. The third method is to have variable PUBRAN times. The delay time would be contained in the public key preamble of the distribution form of the program. This is the preferred design since each software developer can control the trade off between load times and security.
SECURE PACKAGE COMBINING IN THE FIRST EMBODIMENT
An object of the present invention is to permit appropriate software packages to be combined, yet still provide protection against the instruction test attack implemented as a separate program. To provide this protection, it is necessary that transfer of control from one package to another occur only at defined entry and exit points.
It is possible to combine packages by SWITCHing to unencrypted execution mode and then branching to the appropriate package. (In the present invention, the branch out of bounds condition occurs only in encrypted execution mode.) This method provides optimal security when the SWITCH instruction is implemented as a multibyte instruction which also clears the registers and flags of the CPU before changing execution mode. The entry point for an encrypted package would then start with a SWITCH. If a pirate wanted to create a new entry point, he would have to use trial and error to create a SWITCH by modifying the proper locations. This modification would most likely fail and cause activation of the destroy key mechanism. Clearing the registers and flags on the SWITCH will hinder a pirate's efforts. This method of transferring control from one package to another has the nice feature of unencrypted branches which permits linking as in prior art computers.
Although transfer of control between packages can be done solely with the SWITCH and branch instructions, the present invention is easier to conceptualize (and thus program) by including special instructions, namely: HSK, CVC, and RETCVC. The handshake instruction, HSK, defines an entry point and is essentially a multibyte NOP. It consists of enough bytes, about eight, to make it difficult to create by modification. The Cross Vendor Call instruction, CVC, is a special form of the call instruction that permits one package to call another package without causing a branch out of bounds condition. A CVC to a location internal to the current package should activate the destroy key mechanism. The address field of the CVC is unencrypted and thus permits linking of packages as in prior art computers. If an HSK is not executed immediately after a CVC, the destroy key feature is activated. For good security, the CVC instruction should also clear the register and flags. In addition, the return addresses for the CVC should be kept in a secure control stack. This prevents a pirate from branching to any location of a package by modifying a return address and then executing a RETCVC. The RETCVC, Return from Cross Vendor Call, causes execution flow to return to the calling package without causing a branch out of bounds condition. As was mentioned above, this requires using a control stack that cannot be modified by a pirate. This secure CVC control stack could be implemented as a special stack separate from the standard control stack used for calls. However, it is preferable to have just one secure control stack that would be used for standard calls and also for CVC calls.
An important task that must be done when transferring control from one program to another, is to update the registers in the CPU that contain the upper and lower bounds for the currently executing program. Actually, this is only of concern when transferring control to an encrypted program or when SWITCHing to encrypted execution mode. There are a number of ways to implement this. The simplest is to do a linear search of the program bounds table (which is made available by the PUBRAN hardware), however this will be slow. A faster method is to use a successive approximation search (binary search). This is the method used in the preferred embodiment and described further in the detailed description of the first embodiment.
There are a number of variations to the above methods of cross package branching and communication. A minor one is to require that an HSK follow all CVCs and that the RETCVC check for an HSK. This would eliminate the need for a secure CVC control stack. Another is to provide a special register that points to a buffer containing information to be passed to another package when a CVC is executed. This register would not be cleared when the CVC was executed. Such a register would facilitate interfacing two encrypted programs (packages). A more fundamental variation is to do away with CVCs and simply redefine the branch out of bounds condition to be any branch outside of the current package bounds, that does not branch to an HSK instruction. This can be implemented with a minimum of hardware but does have the disadvantage that linking cannot be done if encrypted branches are used. Linking would require the aforementioned technique of SWITCHing to normal mode and then branching.
OTHER ATTACKS ON THE FIRST EMBODIMENT
The preceeding mechanisms and methods inhibit creation of instruction test attacks but do not guard against other attacks. The most glaring concerns communication between the PUBRAN hardware and the CPU. This is not a problem if the PUBRAN unit and the CPU are manufactured as a single integrated circuit. However, due to ease of fabrication, it may be preferrable to manufacture the PUBRAN unit and the CPU as separate devices which communicate via a secure channel.
If the communications channel were not cryptographically secure, then a pirate would be able to connect one PUBRAN unit to many CPUs. This should be prevented, since it allows the pirate to do parallel cracking, which can drastically reduce the time needed to crack an encrypted program. Also, an insecure channel allows the pirate effectively to create load modules. On a prior art computer, a load module is a dump of memory that can be quickly reloaded and executed. However, to create a load module for the present invention requires some way to restore the execution key back into the CPU without doing a PUBRAN operation. Load modules are to be avoided since they allow modification to be a linear process. For example, consider creating a desired modification of n instructions on a computer with a byte architecture and ten illegal instructions. If the modifications must be made in memory, it will take on the order of 10.sup.n reloads before success is achieved (on the average). Modifying a load module is considerably easier since an incorrect modification does not destroy all the previous modifications. A pirate would simply reload the load module and try again on the modification that was incorrect. After achieving success on that modification, he would concentrate on the next location to modify. In a worst case, such a process would require only 256n reloads before the desired modification is completed.
Secure communications are achieved in the present invention by special hardware in the CPU and the PUBRAN unit which implements a One Time Pad communications channel. The CPU generates a random string of numbers, for use as the one time pad, whenever the PUBRAN unit is initialized (e.g., execution of a WARMSTART instruction). A copy of this random number string is then sent to the PUBRAN chip via a fairly secure cipher such as DES. The PUBRAN chip then uses this random number string as the One Time Pad to encrypt the random execution key and bounds information which is then sent to the CPU. The CPU will then use its copy of the random number string to decrypt the information from the PUBRAN. Proper transmission will occur only if the PUBRAN chip is connected to the CPU. A pirate will not be able to connect one PUBRAN chip to many CPUs since each CPU will have chosen a different random number string for the one time pad. Since the PUBRAN chip can only use one one time pad, the PUBRAN chip can communicate with at most one CPU. The one time pad communications channel also prohibits a pirate from using load modules. A pirate might attempt to create a load module by saving an image of memory and also recording the communications between the CPU and the PUBRAN unit. He might then try to load the load module by writing the memory image back into memory and replaying the signals originally sent from the PUBRAN chip back to the CPU. Such an approach will not work because the CPU will have selected a different one time pad on start up and consequently it will be unable to decrypt the recorded PUBRAN signals. In short, these secure communication features, which are needed only if the PUBRAN unit and the CPU are separate devices, eliminate the threat of parallel attacks.
A problem related to load modules, arises if the distribution form of the program is not secure. The most secure method would be to use public key cryptography for the complete program. However, since this would yield excessively slow load times, it is better to use the public key cryptography for just the preamble. The preamble contains the vendor selected load time, package length, and vendor distribution key. This key is the key that the vendor used when encrypting the body of the program (including relocation information) with a block cipher. The cipher must not be a byte substitution cipher since that is equivalent to a load mcdule. Instead, the cipher must be a large block cipher (product cipher) such as DES. These ciphers insure that a pirate cannot modify an instruction without modifying the adjoining instructions coded for by that block. It is quite probable that this will result in illegal instructions. Additional protection can be achieved if an address dependent large block cipher is used since this prohibits a pirate from interchanging blocks in the distribution form of the program.
Software simulation is the final attack to be analyzed. It would be possible for a pirate to write a program that simulates a security CPU and PUBRAN chip. The pirate could then crack any software customized for his simulated security computer. This attack is eliminated by requiring the manufacturer's digital signature on every PUBRAN unit. This signature would be verified by the software vendor before sending software to the user. The digital signature requires that the manufacturer associate two numbers with every PUBRAN unit. The first is an identifying number. The second is the result of applying the manufacturer's private decryption function to the identifying number. To verify the manufacturer's digital signature, a software vendor would apply the manufacturer's public encryption function to the second number. If it does not yield the identifying number, then the vendor knows that the PUBRAN unit was not made by the manufacturer and thus does not send any software to the user. Note that the CPU need not have any identifying numbers if it is not in the same package as the PUBRAN unit (i.e., separate chips). Also note that the identifying number could be the PUBRAN unit's public encryption function. (The PUBRAN unit's private decryption function is burned into it during manufacture.) If the identifying number is not the PUBRAN unit's public encryption function, then the encryption function will appear as a third number associated with the PUBRAN unit. These two or three numbers could be burned into a ROM inside the PUBRAN, or printed on paper as either numerals or barcode.
OPERATION OF THE FIRST EMBODIMENT
The following describes how the first embodiment of the present invention is used and operated. As has been noted elsewhere, the first embodiment consists of a general purpose security CPU that executes encrypted and unencrypted programs, and the PUBRAN hardware, which translates from a secure distribution format to the execution encryption used by the general purpose security CPU. The PUBRAN hardware has a public encryption key and a private decryption key. The latter is burned into the PUBRAN unit at the time of manufacture. The manufacturer also provides a digital signature number with the PUBRAN unit.
When the user orders software, he sends the PUBRAN's public encryption key, the serial number, and manufacturer's digital signature number to the software vendor. The software vendor then checks the digital signature to determine if the user is using a software simulator or a bonafide PUBRAN unit made by the manufacturer. In the latter case, the software vendor will customize the software for the user's PUBRAN unit and then send it to the user. The format for secure program distribution consists of the body of the program which is encrypted in an address dependent large block cipher (e.g., a product cipher such as DES). This is preceded by a public key preamble containing the encryption/decryption key for the large block cipher. Standard media, such as floppy diskettes, are used for distribution.
To run the software, the user first turns on his computer which will cause the PUBRAN unit to select a new random execution encryption key. This is then communicated to the CPU. Then the operating system would be booted (loaded and executed). Next, the user issues commands to the operating system to load the software package and execute it. This would involve execution of a LEE instruction which loads the public key preamble into the PUBRAN unit. Subsequent execution of a PUBRAN instruction, causes the PUBRAN hardware to translate software from distribution form to execution form. If an attempt is made to overlay a previously loaded program, execution of the PUBRAN instruction creates an error which is detected by the operating system, which in turn notifies the user. If the user insists on overlaying the previously loaded programs, then the operating system will execute a WARMSTART instruction which causea a new random execution key to be generated. (Note that if the operating system itself is encrypted, then it must also be rebooted.) This process is shown in greater detail in Table III.
Any attempt to pirate software will create conditions that will render the computer system temporarily inoperable. This will require the pirate to reload the software and try again. The system is designed such that on the average, many years would be required to pirate a package. The mechanisms that accomplish this have been described in the preceeding discussion in general terms so as to prepare the reader for the more thorough presentation in the section entitled, "First Embodiment - General Purpose Computer System."
TABLE III ______________________________________ System Startup -Startup and loading of a general purpose security computer, which utilizes a separate PUBRAN chip, is given in the following table. Note that OS is an abbreviation for Operating System. Step PUBRAN Chip # Action CPU Activity Activity ______________________________________ 1 powerup generates one generates random (or WARM- time pad key for execution START) encryption/ decryption 2 one time pad sent to PUBRAN chip 3 PUBRAN chip uses one time pad to send execution key to CPU 4 CPU wakes up in normal mode. Executes from bootstrap ROM 5 bootstrap buffers encrypted operating system into unused portion of memory 6 bootstrap executes LEE instruction
7 PUBRAN chip decrypts the public key preamble to retrieve DES key used for distribution encryption of OS 8 bootstrap executes PUBRAN instruction 9 PUBRAN chip then translates from distribution encryp- tion to execution encryption. 9.1
generates and sends The OS is loaded another one time pad into appropriate memory region 10 PUBRAN chip uses one time pad to send package bounds information to CPU 11 User has application program OS load is buffered into application memory programs 12 OS executes LEE instruction 13 PUBRAN chip de- crypts the public key preamble to retrieve DES key used for distri- bution encryption of application program 14 OS executes PUBRAN instruction 15 PUBRAN chip then translates from distribution encryption to execution encryp- tion. The appli- cation program is loaded into appropriate memory region. 16 generates and sends another one time pad 17 PUBRAN chip uses one time pad to send package bounds information to CPU
18 User steps 11-14 steps 11-14 repeated accident- repeated ally tries to load over existing package 19 PUBRAN chip indi- cates that the memory region already contains a loaded package (this is PUBRAN Only Once feature) 20 OS gives error message to user 21 User wants OS executes PUBRAN clears to erase WARMSTART bounds registers all packages instruction. CPU clears bounds registers 22 start at step 1 start at step 1 ______________________________________
DISCUSSION OF THE SECOND EMBODIMENT
The present invention can also be embodied as a dedicated security computer. Such computers are widely used for controlling devices such as computer terminals (CRTs) and video games. Since these computers are dedicated to executing just one program, which is typically contained in a ROM or PROM, there is no need for the PUBRAN hardware. Elimination of the PUBRAN hardware makes fabrication easier but does require changes in the design of the CPU. The first change to be discussed is the destroy key mechanism. This is followed by an explanation of how encryption or encapsulation can be used to protect proprietary programs. The last item covered is the Interrupt Context Memory.
The destroy key mechanism on the dedicated security computer must render the computer forever inoperable from the moment it detects a condition indicative of automated cracking. This provides the maximum security against a pirate's attack. This total destroy is typically not used on the general purpose security computer since a user would not want his computer destroyed by a bug in a vendor's program. However, in the case of a dedicated application, conditions causing a destroy key will be the result of a pirate's attempt to steal the software. Permanently disabling the CPU is the best way to stop the pirate.
The dedicated security CPU, when it is configured to protect by encryption, is very similar to the general purpose security computer. However, since there is no PUBRAN hardware, a large block cipher (e.g. DES) is not used for software distribution. Instead the software developer encrypts his software with an address dependent byte cipher and burns this into a programmable read only memory (PROM). The encryption key for this cipher is then burned into the CPU for use as the execution key. The lowest address and highest address for the program would also be burned into the CPU for use as the package bounds. The destroy key mechanism would be activated for all conditions described for the general purpose security CPU. The dedicated CPU would be manufactured as one integrated circuit.
Protection by encapsulation is the other possible configuraton for the dedicated security computer. In this configuration, all, or at least a significant portion, of the program is burned into a ROM internal to the CPU. The rest of the program is burned into external ROM. Note that all of the software is cleartext (i.e., unencrypted). When the CPU is executing instructions from the internal ROM, it disables all external busses so as not to divulge where it is executing in the internal ROM. Every entry point to the software in the internal ROM must start with a special handshake instruction (HSK). If the HSK instruction is not executed immediately after branching to the interal ROM, then the destroy key mechanism is activated. This prohibits the pirate from deducing the contents of the internal ROM by branching to every instruction. Since a pirate cannot modify the contents of the internal ROM, the HSK instruction can be a single byte instruction. (A multibyte HSK instruction is used in the general purpose security computer since it is difficult to create by modification.) The CPU prohibits execution of instructions from external memory that attempt to fetch values from the internal ROM. Otherwise, the pirate could simply dump the internal ROM.
As with the general purpose security computer, an Interrupt Context Memory (ICM) is required for the dedicated application security computer. The ICM is implemented as it is for the general purpose security computer, although it need not be as extensive. Capability to store one or two interrupt contexts would be sufficient for many applications. The ICM could be eliminated if the CPU architecture did not handle interrupts (i.e., polled I/O design).
MODIFICATION PROBABILITIES
A basic feature of the present invention is that any attempt to pirate an encrypted program will require modification (e.g., an instruction test). The design of the present invention is such that there is a high probability that modification will create conditions that in turn will activate the destroy key mechanism. Thus, the security provided by the present invention is best discussed in terms of probability theory. The first set of equations that are developed apply to modification of instructions. Then formulas for branch address modification are derived, followed by an analysis of order independent and multiple modifications. The closing section analyzes how branch modifications that did not directly change the key can indirectly change the key due to instruction misalignment.
The formulas presented below, which set a lower limit on the security provided by the present invention, were developed using worst case analysis. The worst case is to assume that a pirate has a hypothetical ideal instruction test at his disposal. This ideal instruction test can execute any encrypted instruction and unambiguously determine what the cleartext form of the instruction is without activating the destroy key mechanism. This is truly the worst case, for if a pirate actually had an ideal instruction test available, he would have no need to try to create an instruction test by modification. In practice, a pirate would have to go through a bootstrapping process where a partially working instruction test is used to develop a more complete instruction test. This will involve substantially more errors than will the hypothetical ideal instruction test, and thus in reality a pirate faces even worse odds than dictated by the following formulas.
Consider an attempt to modify one instruction in an encrypted program. Success, as viewed by the pirate, is defined as replacing the instruction with the desired one (also known as the target instruction). Failure is obviously defined as replacement with an instruction that will cause the execution key to be altered. This occurs when a WARMSTART or illegal/unused instruction is executed. Execution of a WARMSTART causes the PUBRAN hardware to generate a new random key whereas an illegal/unused instruction destroys the key. (Note that although the preferred embodiment utilizes many illegal/unused instructions and only one WARMSTART instruction, it is possible to implement the present invention with multiple WARMSTART instructions and no illegal/unused instructions.) In mathematical terms, the number of instructions, I, that will cause the execution key to be altered is:
where N.sub.I represents the number of illegal/unused instructions in the instruction set and N.sub.W is the number of WARMSTART instructions in the instruction set.
The trial and error approach employed by the pirate will stop whenever the target instruction or an instruction that alters the execution key is encountered. Consequently, the probability of success, q, is simply: ##EQU1## The obvious extension of this is to permit success to be defined as replacement by any element in a set of desired instructions. For this case, the probability of success, q, is: ##EQU2## where T is the number of instructions in the target set.
Similar equations hold for modification of branch addresses. For an absolute branch, an illegal address is defined as an address outside of the program's bounds. Therefore, the number of illegal addresses, I.sub.BA, is given by:
where M is the total address space for the computer, and L is the size of the encrypted program. The probability, q.sub.BA for successfully modifying a branch address to a desired value is: ##EQU3## The following formula applies when modifying a branch address to any of a number of desired values: ##EQU4##
The above formulas pertain only to modification of one instruction or address to a desired value. A realistic attack would involve modifying many instructions and branch addresses. The probability that the pirate will succeed can be represented by q, which in turn is described by the appropriate combination of the above formulas. Note that if the pirate fails, the execution key will be destroyed. This will force the pirate to restart the computer by executing a WARMSTART instruction (which will select a new random key). In this case, information from the preceding attack will not be of value in the current attack. Successive test sequences are independent. Therefore, cracking the system can be modeled as flipping a biased coin which has a probability, q, of landing heads up. Probability theory shows that the average waiting time for a head, is simply 1/q. In other words, on the average, (1/q)-1 tails will be flipped and on the (1/q)th flip, one will get a head. When this is applied to cracking a program on the present invention, this states that on the average, the number of WARMSTARTS, W, before successful modification is:
Consequently, if the number of illegal instructions or illegal branches is large, the time spent reloading the encrypted program (i.e., executing WARMSTARTS) will limit the number of possibilities that can be tested. Specifically, the time required, t, will be:
where t.sub.w is the time to perform one WARMSTART.
The above formulas pertain only to modification of one instruction or address. If the pirate must modify multiple locations, then the probability of success decreases. Furthermore, assume that the modifications are order independent. This means that each location to be modified must be modified to a specific value, regardless of other modifications. The following two formulas apply to multiple modification of either instructions or branch addresses. They can readily be extended to handle concurrent multiple modification of instructions and branch addresses. The probability of successfully making multiple order independent modifications, q.sub.OI, is given by:
where N is the number of modifications to be made. The average number of WARMSTARTS, W.sub.OI, is:
Multiple modifications can also be made order dependent. For example, a pirate might just desire to create a set of load instructions that can be in any sequence. The equations that apply for order dependent instruction modification are: ##EQU5## and
Similar equations can be developed for order dependent address modification.
Although the preceeding formulas describe the probabilities for success, one could also consider the probabilities for failure. For example, the probability, p, that a pirate fails on a branch address modification is:
PROBABILITY THAT MISALIGNMENT CAUSES DESTROY KEY
When a software pirate modifies a branch address in an encrypted program, the probability that his modification will cause a branch out of bounds, which destroys the execution key, is given by p from (13). If the instruction set contains instructions of varying length, there is an additional way in which a pirate's modification of a branch address can cause the execution key to be destroyed. This situation occurs when an in-bounds branch causes instruction misalignment which terminates with the execution of a destroy key instruction.
This discussion will be limited to a