Method and Apparatus for Securing Executable Programs Against Copying

The present invention relates to the field of securing executable programs against copying. More specifically, in one embodiment the invention provides security against copying in an open hardware system where access to the processor executing the program and the memory holding the program is assumed.

Securing computer programs (software) against unauthorized copying has been a concern of software developers since software was sold as a separate product. The difficulty lies in the fact that software is easily copied and any copy protection or prevention scheme must allow for the eventual copying of portions of the software if it is to be executed. Unless the software is secured in a chip (integrated circuit) which also contains the microprocessor which will execute the software, the executed portions of the software must pass from the distribution media to the processor along circuit lines which are monitorable. Thus, for a program to be secure and still be useful to its intended user, the program cannot be readily copyable in its generally available form or in the form in which it is executed by the intended user.

Recently, with the increasing need for technical support from a program's developer, the desire for complete documentation, and the fear of viruses, unauthorized copying of some software, especially critical business software, has diminished. However, where software needs no support or documentation and is used on systems where viruses cannot be transmitted, such as video game systems using video game cartridges with game software stored in read-only memory (ROM), unauthorized copying is still prevalent. All that is needed is an understanding of the circuitry used in the game cartridge and a copy of the game program.

An additional concern of the makers of video games, who typically make video game consoles and wish to limit their use to games produced by licensed software producers, is not software copying, but video game console copying to produce consoles which will execute authorized game cartridges or unauthorized, but compatible, game cartridges.

In an unprotected system, a copyist (i.e., a "software pirate" or other unauthorized analyzer or copier of the software) can easily copy program code if it is accessible. Program data, as used herein refers to the data necessary to run the program, which includes instructions (program code), tables of values and image data used to generate screen images. Even if the program data is not easily accessible in its distributed form, a copyist might obtain it by observing a bus between the storage media which holds the program data and the processor to determine the program code. Thus, encryption of the program data alone does not provide real protection, since it must be decoded eventually to be used. Where the program data is stored on video game cartridges and the processor is on a video game console, analyzing the program data is simplified, since the interface between the storage media and the processor is readily available without any hidden communication. In many video game consoles, the entire bus of the CPU is readily available for analysis. This particular problem, of course, extends to all forms of program storage media which are detachable, not just video game cartridges.

Many copy protection systems are a deterrent to casual copyists, but not to determined copyists, who might be willing to spend large sums of money and time to break a copy protection scheme in order to be able to manufacture large numbers of unauthorized copies of a program. For some casual copyists, it is enough to include software-only copy protection, such as the use of secret files or codes not normally accessed or observed by a casual copyist. Many casual copyists will also forgo copying when copying involves construction of cartridges, since this requires the ability to make plastic cases and circuit boards. However, the most determined copyists of cartridges are those who plan to make large numbers of cartridges for sale and thus have the ability to make cartridges once the program data is copied.

Software-only copy protection systems, which might use an undocumented portion of the program data media to store hidden codes, generally rely on "security through obscurity" to prevent only those who are not aware of the copy methods from making workable copies. Therefore, when the goal is to stop large-scale and educated copyists, software-only protection is not viable. Fortunately, where the program data is distributed on media containing hardware elements, as is the case with video game cartridges, hardware copy protection can be included on the cartridge.

Many hardware protection systems rely on the presence of a hardware circuit or device which signals the existence of an authorized copy of the program. The program, when executed, runs a routine to check for the existence of the authorization device. If the authorization device is not present, the program refuses to continue or performs some other undesirable action. These protection systems are open to two methods of attack, both of which could render the protection ineffective.

In a first type of attack, a copyist would analyze the circuitry of the hardware authorization device to determine its essential elements and from that information make duplicate, unauthorized authorization devices. Even if the details of the authorization device are buried in a custom integrated circuit, the integrated circuit could be examined under a microscope layer-by-layer using a chemical peeling process to resolve the circuit features. The operation of the authorization device might also be observed by slowing down or speeding up both the authorization device circuitry and the processor to aid in the detailed analysis of one operation or the high-speed analysis of many passes over the program.

In a second type of attack, the copyist attempts to modify the software routines which check for the exists of the authorization device so that the routines always report back that the authorization device is in place, whether or not it actually is. With a readily-available logic analyzer attached to a microprocessor running a program, a copyist can run the processor at a slow speed and have the logic analyzer record all instructions executed by the microprocessor and all the data traffic to and from the microprocessor, then use this information to determine the flow of the program. If the flow of the program is recorded both with the authorization device in place (simulating an authorized use) and without the authorization device in place (simulating an unauthorized use), the copyist can compare the flows and determine where in the program the decision is made as to whether the authorization device is in place. Once that location is determined, the software at that location could be modified so that the routine which tests for the presence of the authorization device never fails. This can often be done by replacing one conditional jump instruction with an unconditional jump or a NOP (null operation).

Therefore, what is needed is an apparatus which allows a processor to execute program code, over a possibly insecure bus, while requiring an impractical amount of work on the part of a copyist to reproduce the program data for use apart from the apparatus or to reproduce the apparatus.

The present invention provides a secure system for executing program code in an insecure environment while making it impractical to determine how to copy the program code or associated data. In one embodiment of a secure system according to the present invention, a program memory contains encrypted program data (program instructions, data tables, digitized images, etc.) and security circuitry contained within an integrated circuit is provided for extracting the program data as it is needed by a processor. In various embodiments, the processor is a central processing unit (CPU), a video pixel processor or other low-level CPU requiring program data. A portion of the processing steps which would be done by the processor in an insecure system is performed in this secure system within the secure circuitry using portions of the decrypted program data which are not provided to the processor. Program data is parsed based on a proper request to the security chip from the processor. The security chip tracks which sections of the program memory are proper for the processor to be requesting based which program code in being executed. The security circuitry includes a key register in which a key value, needed to decrypt the program code, is stored. For security, a different key value can be used for each different program.

Where a risk of chip peeling exists, the key might be stored in volatile memory powered by a battery or stored as charge on capacitor, positioned and/or distributed on the security chip surface such that a chip peel breaks the source of power to the volatile memory well before the volatile memory can be reached.

In a specific embodiment, the security chip extracts the branch statements from the program instructions and stores them in an internal branch table after decryption and before providing the instructions to the processor. In a preferred embodiment, the branch statements are separated before being encrypted and stored in the program memory. Because the possible flows of the program are known from the branch table, the branch table only need contain a listing of the branches which are imminent, thereby saving memory.

In various embodiments, the encryption is complex conventional encryption while in others, to save hardware, is simpler encryption such as XOR'ing with the output of a pseudorandom number generator (PRNG). A number of additional security measures can be applied where needed. For example, if the security chip is positioned to read the processor bus, a tap of the processor bus can be provided so that the security chip can monitor all instruction fetches and data fetches from memory. For example, since the security chip provides all the branch information, the program flow between branches is linear and deterministic. Thus, the security module could perform a checksum on all the bus activity between branches, compare it to a precompiled checksum and refuse to provide more branch information if the checksums do not match, as would be the case if the instructions provided to the processor had been modified in some way.

The security chip could also include a real-time clock, RC (resistor-capacitor) time constant circuit, or other dynamic logic circuit to confirm that the processor is executing instructions at an expected rate. This prevents a processor from being accelerated to speed up the process of running the program through all the possibilities needed to build an unauthorized branch table or from being slowed to perform hardware analysis.

Furthermore, because the security chip maintains the branch table, it can calculate what the next branch is, so that the processor only need provide the values neetled to evaluate whether to take a conditional branch. In order to handle return instructions, the security chip also maintains the program stack for the processor. This security feature prevents the processor from requesting unexpected branch information.

To make a chosen text attack on the encrypted program data more difficult, the program data could be compressed first to remove patterns in the data.

The encryption and decryption could be done as conventional encryption/decryption. However, where low hardware cost is a priority, the encryptor could be just a data scrambler which rearranges the order of the bits or bytes of the program data according to the output of a PRNG. The data decryptor is then just a series of buffers, a multiplexer and a demultiplexer. Where the security chip includes decompression, the buffers might already exist in the decompressor. If the scrambler is used in addition to other encryption, a chosen text attack is made more difficult, since the position of any word or bit in the data cannot be inferred. The PRNG is seeded by the key value or some agreed upon value dependent on the key. Because the file is compressed, less robust encryption can be used. To further defend against analyses in which many different sections of the encrypted program data are compared with the corresponding decrypted data to determine the key value, a secondary key value which varies from section to section could be used. The secondary key value could be a value generated from data stored with the program data and the main key value. Alternatively, a table of secondary keys could be stored with the program data or in the security chip, with the main key value used to select keys from the table.

In some applications, it is also desirable to prevent the operation of an authorized game cartridge on an unauthorized game console. For these applications, the game console is provided with a difficult to copy element and the security chip on the game cartridge requires this element to be present before operating.

A further understanding of the nature and advantages of the inventions herein may be realized by reference to the remaining portions of the specification and the attached drawings.

FIG. 1 is a block diagram of a computer system according to the present invention wherein program data resides on a cartridge connected to a processor over a plug-in bus including a security chip on the cartridge;

FIG. 2 is a more derailed block diagram of the security chip;

FIG. 3 is a block diagram of a system used to encrypt programs onto encrypted memories which are used in the cartridges;

FIGS. 4A and 4B together show a flow chart of an execution of a program by the processor;

FIG. 5 is a block diagram of a branch unit;

FIG. 6 is a block diagram of a dam stream scrambler; and

FIG. 7 is a block diagram of a pseudorandom number generator.

FIG. 1 shows a common application for the present invention, namely video games. It should be apparent after reading this disclosure that the invention is not limited to video games or programs stored on cartridges. In FIG. 1, a game console 10 is shown with a game cartridge 12 about to be mated to game console 10 via a bus 14. We assume herein that a copyist is able to read the game program and game data as it is stored in game cartridge 12 and is also knows everything that goes on in game console 10. According to the preferred practice in the design of security devices, we also assume that the copyist knows all the derails of any security circuits and algorithms except for any keys or passwords. Because the primary goal of the system is to allow a legitimate user to run the program, it is impossible to prevent the copyist from determining the outcome and flow of the program by running it with a given set of input data. Thus, the goal of the security of this system is to require that the program actually be run, at normal speed, and limit the amount of information about the program which can be inferred from one execution of the program with one input data set. The impracticality of determining the actual program code and data is based on the fact that the number of input data sets which would have to be run against the system is so high that the time needed to perform such an analysis is greater than, or comparable to, the time span in which the bulk of the legitimate sales of the program are made.

Game console 10 is shown with a processor 20, local memory 22, an output interface to a video display 16, an input interface from input devices 18, and a circuit clock 24. Game console 10 might include other elements not shown. The input devices 18 are shown generically, since they are not the subject of the present invention, but might include keyboards, joysticks, touch pads or sensor arrays. Video display 16 is typically a pixelated display (e.g., a raster monitor) which displays a two-dimensional array of pixels colored as indicated by processor 20 or an intermediate video memory (not shown). Local memory 22 stores variables used in the execution of the program as well as a current page of instructions of the program. Local memory 22 need not store the entire program at once, since the program can be paged into local memory 22 as needed. As should be apparent from this description, the security system is described with reference to processor 20, the CPU of game system, however the present invention might also be used with a video processor, image processor or other processor present in the system.

Game cartridge 12 is shown with a security chip 30 and a ROM 32. Other forms of storage can be substituted for ROM 32, such as CD-ROM (compact disk ROM), diskette, flash memory, or even remote programs accessed via a network. ROM 32 contains the game program in an encrypted form. The game program so stored comprises program executable cede, data tables, graphic images and other related objects which are necessary or related to the operation of the game embodied by the cartridge. In a preferred embodiment, security chip 30 is a single integrated circuit with no secure data streams flowing on externally accessible pins.

The present invention cannot protect against all attacks. For example, if a copyist obtains the game program in its unencrypted form from an unscrupulous employee of the game maker, the present invention will not prevent the copyist from distributing the game in that form. It is assumed here that the unauthorized copyist only has access to a game console and a number of game cartridges. With this limited access, the copyist will attempt to analyze the operation of the console and cartridges using various analysis and control tools shown as tools 40 in FIG. 1. An analysis tool records signals, while a control tool changes the signals, often while an analysis tool is recording signals. Such tools include microprocessor trace analyzers, waveform generators, oscilloscopes, etc. FIG. 1 shows various places within the game console 10 and game cartridge 12 the copyist could tap to analyze and control signals. Significantly, the copyist cannot tap onto internal lines of security chip 30 without chemically peeling the security chip and working on a microscopic level.

A tap 41 to circuit clock 24 might be used to slow down the processing speed of game console 10 to more easily analyze its operation, or used to speed up circuit clock 24 to more quickly execute many instructions to test different variations of the program. To render this tap ineffective, security chip 30 might also maintain a clock whose speed is determined internal to security chip 30 and refuse to decrypt program data from ROM 32 if circuit clock 24 does not run at the correct speed.

A tap 42 to ROM 32 provides the copyist with the contents of ROM 32, but these contents are not useful without the decryption provided by security chip 30. A tap 44 on the data traffic on bus 14 or a tap 43 on the data traffic between processor 20 and local memory 22 might provide decrypted program information, but would only provide the instance of the program sequence which applies to one execution of the game instead of a sequence which is usable for different sets of input. Furthermore, that information does not include branching instructions, as those are not sent to the processor, but are executed in security chip 30.

The same is true for a tap 45 on the video display. While tap 45 might be able to record all the video signals, they would only correspond to one particular playing of the game. For example, if a game level containing unique graphics is never reached, the graphics at that game level will never be sent to video display 16 and therefore cannot be obtained by tap 45.

A determined copyist might use a tap 46 on the signals between input devices 18 and processor 20 to insert signals simulating different outcomes and events in the game. With enough different paths, a copyist might be able to determine all the possibilities and work backwards to reconstruct the game program, but because the speed of the processor cannot be increased and due to the sheer number of possibilities, the copyist is not likely to be able to do this between the time a game is released to the public and the game sells enough copies to diffuse the copyist's potential market.

Thus, even with all these taps, a copyist having access to only game console 10 and game cartridge 12 cannot make a full, usable copy of the game program. A determined copyist might tap into the internals of security chip 30 itself, which would require careful removal of the casing of the security chip and a layer-by-layer analysis of security chip 30. However, even knowing the entire internal circuitry of security chip 30, the copyist will not obtain the volatile settings of the key needed for decryption of ROM 32, since the memory holding the key is designed to lose power as layers are removed. If the memory is many layers below the layers required for power, the memory will be erased before its layer is available for analysis. In order to defeat security chip 30, the copyist must be able to analyze the contents of ROM 32 and the output of the security chip to derive the key. In addition to the key being different for each different game (not necessarily each game cartridge containing that game), security chip 30 contains other features which make the cracking of the encryption without access to the internals of security chip 30 more difficult.

FIG. 2 shows security chip 30 in more detail, including a bus unit 50 which couples security chip 30 to bus 14 and passes requests for program data to a translator 52. Translator 52 converts the address of the access request into an address location, or range of locations, in ROM 32. This address is sent over an address bus 54 to ROM 32, which returns the data on data bus 56. Alternatively, some locations of ROM 32 might be cached in cache 60, in which case translator 52 routes address information to cache 60, which in turn supplies the cached data.

Both sources of data are coupled to an input of a decryptor 62, which decrypts the data from ROM 32 using a key value supplied from a key register 64. As explained below, different configurations for decryptor 62 are possible depending on the degree of security needed. Since the decryptor 62 is constrained to be, more or less, the inverse of the an encryptor used to encrypt the program data, the different configurations are discussed below in connection with the encryptor.

The output of decryptor 62 feeds to the input of a decompressor 68, which is optional. Decompressor 68 in turn passes the data to a router 70. Router 70 includes an output for clear ROM data and an output for hidden data. The clear ROM data is unencrypted program code and data objects, but without branch information. The hidden data contains the branch information as well as other variables, such as checksums and expected execution times.

The hidden data output is coupled to an input of a computational unit 72, which handles the overall control of security chip 30. Computational unit 72 also includes a port for reading from, and writing to, private tables 74, an input for reading from a real-time clock 76, an input for receiving branch requests from bus unit 50, an output for branch responses coupled to bus unit 50, an input from bus unit 50 for bus taps which provide information about activity occurring over a processor bus or bus 14, and a port for receiving and responding to queries from bus unit 50 about the propriety of requests for program data. The detailed operation of security chip 30 is described below in connection with FIG. 4.

FIG. 3 is a block diagram of a system 100 used to encrypt a game program 112 onto an encrypted ROM 32 to be used in game cartridge 12. System 100 includes storage for game program 112 coupled to a branch separator 102 which outputs a secure program 114, a branch table 116, a file of checksum data 118 and a file of timing data 120. Storage is provided for these output data sets and that storage is coupled to a compressor 104, which is optional but preferred. The output of compressor 104 is coupled to an input of an encryptor 108, which also has an input for receiving a key value from a key register 110. The output of encryptor 108 forms the contents of ROM 32.

As explained above, game program 112 comprises program executable code, data tables, graphic images and other related objects. A short example of program executable code, useful for explanation purposes only, is shown in Table 1. The program represented in Table 1 is a "clear" program in that all the information needed to run this program for any possible input is apparent from the program alone. Indeed, it should be apparent from Table 1 that the program does nothing more than move the first ten entries of the array a›! into the corresponding locations in b›! for any possible input values (e.g., the values in a›!).

The C program corresponding to the program of Table 1 is:

main {

for (i=0; i<10; i++)

move(i);

void move (int i) {

b›i!=a›i!;

}

If the program of Table 1 were supplied to branch separator 102, the secure program shown in Table 2 and the branch table shown in Table 3 would result.

In generating the secure program, the order of the instructions could have been retained, so that the line numbers are in sequential order. However, if they were in order, the analysis of the addresses being passed to security chip 30 would indicate where jumps are being taken and not taken. For example, if the line numbers were in order in the secure program of Table 2, a request for jump address n, followed by a request for jump address n+1 would indicate that the jump associated with address n was not taken (otherwise a jump address other than n+1 would be the next jump address). To prevent this kind of analysis, the order of the lines in the secure program are scrambled. Since a true and false address is stored for each conditional jump, the code following a jump not taken does not need to sequentially follow the jump.

Appendices A, B and C are listings of longer examples of a clear program, its corresponding secure program and branch table, respectively. Appendix D is a listing of a program used in a software implementation of branch separator 102 (FIG. 3). That program is written in the "awk" language which is commonly available on computers running the Unix operating system. As should be apparent, the program in Appendix B cannot be executed without the occasional reference to the branch table of Appendix C.

In some embodiments, branch separator 102 also calculates a checksum for the several instructions executed between each reference to the branch table. Since these several instructions do not contain any branches, they must be executed in the same order every time, and their checksum is easy to calculate. These checksums are stored as checksum data 118. Similarly, in some embodiments, the execution time for the several instructions can be calculated and stored as timing data 120.

If more security against analysis is needed, instead of having the branches performed by security chip 30, security chip 30 could generate interrupts to implement taken branches. If this is done, a copyist would not detect branches not taken.

After secure program 114, branch table 116, checksum data 118 and timing data 120 are generated, if used, this information is compressed by compressor 104. In one embodiment, compressor 104 is the entropy coder shown in U.S. Pat. No. 5,381,145, issued to Allen, Boliek, and Schwartz, and entitled "Method and Apparatus for Parallel Encoding and Decoding of Data." Compression is used not only to allow more data to be stored in a fixed sized ROM, but is used to remove any patterns which might be present in the data, thereby making decryption without the key more difficult.

Encryptor 108 can take several forms. Where security is more of a priority than keeping the hardware cost low, encryptor 108 could be a Data Encryption Standard (DES) encryptor, triple-DES, or a more secure encryption system as is known in the art of data security. Various embodiments of encryptor 108 can be used, depending on the laws of the country in which the game is sold and the country of its intended use, as well as a balancing of security needs and computational limitations. Where security of the encryption process is less of a priority than keeping hardware costs down, several simple encryption circuits might be used. In one embodiment, encryption is merely the process of exclusive "OR"ing (XOR) the clear data with a stream of output bits from a pseudorandom number generator (PRNG). In another embodiment, the order of the clear data is reordered based on the output of the PRNG. With an incremental addition to the hardware cost, both of these methods could be used together.

The simple encryption is low-cost, since a PRNG can be easily build out of a few gates. See, for example, FIG. 7 for a PRNG constructed from a shift register. FIG. 6 shows a detailed diagram of the internal structure of for a data scrambler 106. Data scrambler 106 uses a number of buffers, but the incremental cost of these buffers is zero where the buffers already exist as part of compressor 104.

In another low-cost variation, the encryption is combined with the compression. In this variation, the compression is entropy compression, which uses tables of probability estimates to determine optimal codes to use. Since memory for these table is needed for compression anyway, using them for encryption adds no extra hardware. They are used for encryption by seeding them, initially or during the compression process, according to the key value or numbers based on the key value. An added benefit of this encryption scheme is that it prevents a known plaintext attack on the encryption process since the compression process does not necessarily remove patterns in the data being compressed until the probability tables have had a chance to build up. With the key value providing the initialization for the probability tables, the compression process cannot as easily be analyzed.

After being encrypted and possibly compressed, the output of encryptor 108 is stored in the encrypted ROM 32. The operation of game console 10 and game cartridge 12 using encrypted ROM 32 will now be described, with reference to FIGS. 1-4. FIG. 4 comprises FIG. 4A and 4B, and together they show the steps taken by processor 20 and security chip 30 to execute a portion of the game program in a secure manner, beginning with a request for a page of instructions and/or data (Step S1).

For ease of implementation, the program data could be arranged in separately compressed data sets, with processor 20 requesting a page by specifying a pointer to a compressed data set, or just a selection of one page from a limited set of pages based on the last decoded page. For more security, each data set could be identified by a random ID associated with it at the time the program is encrypted.

The request for a page is passed over bus 14 to bus unit 50, which in turn queries computational unit 72 as to whether the request was proper (Step S2). Since computational unit 72 maintains the branch table, it can easily determine which instructions should and should not be requested by processor 20. This feature prevents a copyist from controlling the processor 20 such that it requests each and every block of the program in a known order so that the copyist can assemble the entire program in the clear. If the request was not proper, computational unit 72 halts processor 20 (Step S3). Alternatively, computational unit 72 could cause some other effect, such as the erasure of the key value, erasure of ROM 32, cause the slow degradation of the data over time, or other steps to frustrate further analysis. In some embodiments, computational unit 72 responds to a detected attack by altering the flow of the game such that if the copyist succeeds in deducing the flow of the game program, the deduced flow will be limited. For example, computational unit 72 could limit the program flow to just the first several levels of the game.

If the request is proper, the page is extracted from ROM 32 (S4). To do this, the request is processed by bus unit 50 and sent to translator 52. Translator 52 is not necessary where the addresses used by the processor are the same the addresses used to access ROM 32. As Tables 1-2 indicate, the addresses do not always correspond. The addresses also will need translation if the encryption alters the addresses for the data. Once the address of ROM 32 at which the requested page is stored is determined, that address is output on bus 54 to either ROM 32 or cache 60. In either case, the requested data is input to decryptor 62. The returned data might be program instructions or data objects. If the data is program instructions, corresponding entries of the branch table are included with the data, along with the checksum and timing information, if used.

Decryptor 62 uses the key value from key register 64 to decrypt the data. Decryptor 62 is the inverse of encryptor 108, and the key value is either equal to, or the inverse of, the key value stored in key register 110, depending on the type of encryption used. The decrypted data is then decompressed by decompressor 68. The effect of these elements is to reproduce sections of the data in data blocks 114, 116, 118 and 120 shown in FIG. 3. This data is then separated into the secure program (dear ROM data) which is passed back to processor 20 via bus unit 50 and hidden data (branch table, checksums, timing data) which is passed to computational unit 72. Computational unit 72 stores this data in private tables 74 (S5). Bus unit 50 passes the secure program page in the clear to processor 20 (S6). As explained above, the secure program page alone would not allow the copyist to duplicate the operation of the game program.

Once processor 20 has a page of program data, it executes the next instruction in that page (S7). Before executing the instruction, processor 20 checks the instruction to see if it is a branch instruction (S8). If it is not a branch instruction, processor 20 executes the instruction (S9) and checks for further instructions in the page (S10). If more instructions are present, processor 20 gets the next instruction (looping back to step S7), otherwise processor 20 requests the next page from ROM 32 (looping back to step S1).

On the other hand, if the instruction is a branch instruction, which processor 20 does not process, a branch request is passed to security chip 30 (S11). If the branch request is not proper, as determined in step S12, computational unit 72 halts processor 20 (S13). For a request to be proper, it must be expected, must occur at the time expected, and the bus checksum must be correct. The response from security chip 30 to a proper branch request is the address to which processor 20 should branch. Of course, for conditional branches, processor 20 will need to pass one or more arguments to security chip 30, which will calculate which of a true address and a false address to return (S14). Security chip 30 then passes the address back to processor 20 (S15), the processor jumps to that address (S16) and gets the instruction at that address (looping back to step S7). In this way, an address is provided for a branch without processor 20 ever being told what kind of branch it is or what all the possible branch addresses are.

Computational unit 72 is used both to process branch requests and to evaluate whether a request for a branch is proper. To do this, it uses a private branch table, which is stored as part of private tables 74. This branch table need not store all the branches, but just those which are upcoming. For each branch entry in the branch table, the following fields are maintained:

TYPE - the type of branch, selected from:

1) unconditional jump

2) conditional jump

3) subroutine call

4) subroutine return.

CONDITION - Only used with conditional jumps; indicates the condition tested.

ADDRESS 1 - For unconditional jumps and conditional jumps with a true condition, this address is the address to jump to; for calls, it is the called address; and for returns, it is not used.

ADDRESS 2 - Not used for unconditional jumps. For a conditional jump with a false condition, this is the address to jump to; for calls this is the return address, which is saved on a stack. This is not used for returns.

In some embodiments, processor 20 does not specify, and is never told, the index into the branch table for an upcoming branch. In those embodiments, the branch table tracks which branch index should follow the current branch. Of course, the next branch depends on which branch is taken, so that information is stored in the following two fields in those embodiments:

NEXT BRANCH 1 - Indicates the index of the branch in the program code which is the first branch in the code after ADDRESS 1.

NEXT BRANCH 2 - Indicates the index of the branch in the program code which is the first branch in the code after ADDRESS 2.

CHECKSUM - The expected checksum for all the program code preceding the branch.

EXECUTION TIME - The expected execution time from the previous branch to the next branch.

PASSWORD - The password required to execute the current branch.

The TYPE field indicates the type of branch and, consequently, which other fields are used. If example, an entry for an unconditional branch (e.g., "goto 5") need not include a condition or a false condition address. Of course, in some systems other branches are possible, such as conditional calls and conditional returns. In some high-security systems, NOP branches might also be included in the secure program.

The CONDITION field might be expressed as an operand and a constant, for comparisons of a variable against the constant (e.g., "branch if (i>=10)") or just an operand for variable-to-variable comparisons (e.g., "branch if (x<y)"). Where variables are needed for the comparison, they are passed by processor 20 to security chip 30 as part of the branch request. Processor 20 need not be informed of which condition is being applied, just how many and which variables to pass as arguments. In one embodiment, the TYPE field indicates which type of condition field is used and a VALUE field indicates the constant value where one is used.

The ADDRESS 1 and ADDRESS 2 fields supply the next address for the currently requested branch. For conditional branches, ADDRESS 1 is supplied if the condition is true, otherwise ADDRESS 2 is supplied. For unconditional branches, ADDRESS 2 is not used. For calls, ADDRESS 1 is the called address and is supplied to processor 20, while ADDRESS 2 is the address of the instruction following the call (i.e., the return address). That ADDRESS 2 value is placed on a stack for later use with the corresponding return branch. For a return, neither address field is used; the return address comes from the stack.

Table 2 shows a secure program intended to be run by a processor such as processor 20. When the processor reaches a branch request (which replaces a branch in the clear program), the processor makes a branch request and passes to the security chip the index of the branch request with the arguments necessary for the evaluation of a condition. For example, at address 4 in Table 2, a branch request is made for a specific branch index. The instruction "br.sub.-- req 1" signals that entry 1 is the branch table is to be used. However, for some determined copyists, the index of the branch request might be used to extract branch information. For example, by tracing enough "br.sub.-- req 1" instructions, the copyist could determine that it is equivalent to a return instruction. In turn, each of the indexed branch requests can be analyzed to determine the type and condition for each branch.

To make this sort of analysis more difficult, the indices in instructions can be eliminated. Thus, instead of the instructions "br.sub.-- req 1" and "br.sub.-- req 2" being available to the processor, both of these are known only as "br.sub.-- req". The indexing information is stored in the fields NEXT BRANCH 1 and NEXT BRANCH 2. Since all branches are controlled by computational unit 72, the branch request following the address of the current branch is known and thus is easily stored. The NEXT BRANCH 1 field contains the index of the next branch when ADDRESS 1 is the branch taken and the NEXT BRANCH 2 field contains the index for the next branch when ADDRESS 2 is the branch taken. For a call, ADDRESS 1 is the start of the called subroutine and ADDRESS 2 is the address of the instruction following the call instruction. Thus, NEXT BRANCH 1 is the index of the first branch in the subroutine and NEXT BRANCH 2 is the index of the first branch following the ADDRESS 2 address. For calls, ADDRESS 2 and NEXT ADDRESS 2 are pushed onto a stack in computational unit 72.

Where used, the CHECKSUM, EXECUTION TIME and PASSWORD fields are used to determine whether the branch request is authorized. After a branch, bus information from bus taps is fed to computational unit 72, which checksums the bus data until a branch is found. The resulting checksum is compared to the stored CHECKSUM value. If these are different, computational unit 72 will take action to prevent the further progress of the game. The checksum can be applied to all traffic over the processor bus except, of course, variable data.

Similarly, real-time clock 76 is used to recorded the time between branches and that time is compared to the EXECUTION TIME value. The expected amount of time is easily determined if the processor clock rate is known, since there are no intervening branches and the known number of instructions between the branches. Alternatively, a separate real-time clock is not needed. If a PRNG is used as part of the decryption process, it could be set to clock each instruction cycle, whether or not it is being used. That way, if extra instructions are inserted, the PRNG would lose sync with the data and corrupt it.

For particularly sensitive branches, a PASSWORD value could be assigned, where the processor must supply the password for the branch to be taken. The PASSWORD value might be calculated from a known combination of the state of the processor or memory contents of the local memory.

Relying on the security chip for branch processing might take longer than if the processor was executing a clear program. Where the execution of code is time-critical, the protection of selected sections of the program code could be disabled so that the processor does its own branch processing. Alternatively, portions of the processing necessary for the time-critical program code could be executed by the security chip to save processing time.

FIG. 5 shows a branch unit 500 which is a part of computational unit 72 used to implement the above rules. Branch unit 500 receives an entry from branch table 502, data from a bus tap 504 and arguments from a DATA IN bus 506 and, based on those inputs, outputs either an error signal indicating an improper branch was requested or a properly requested branch address. In some embodiments, the branch address is passed to processor 20, while in other embodiments the branch address is used to control which instructions are provided to processor 20 without ever informing the processor of the address for those instructions.

Branch unit operates as follows. Once an entry in branch table 502 is selected, the fields VALUE, TYPE, CHECKSUM, PASSWORD, TIMING, ADDRESS 1, ADDRESS 2, NEXT 1 and NEXT 2 are output. The VALUE field is the constant associated with a conditional jump with a comparison to a constant, and forms one input to subtractor 508. The other input to subtractor 508 comes from a register 510 which holds the latest contents of the DATA IN bus. Subtractor 508 provides results for comparisons of a variable argument against a constant, and in some cases merely indicates whether the one input is greater than, equal to, or less than the other input. Subtractor 512 similarly compares the output of register 510 and the output of a second register 514 coupled to register 510. The outputs of both registers are provided to a control section 516.

Control section 516 determines whether an error signal is to be output and also controls two multiplexers (muxes) 518, 520. The output of mux 518 is the branch address, selected from one of ADDRESS 1, ADDRESS 2 and a stack top value from a stack 522. The output of mux 520 is one of NEXT 1, NEXT 2, an initial value, and the stack top value. The output of mux 520 indicates the index for the next branch and is fed back to an index input for branch table 502. The initial value is a pointer to the first branch in the chain of branches, so that the PENDING line is properly initialized.

Control section 516 determines which output of mux 518 is active based on its inputs, as indicated above: when the branch TYPE is an unconditional jump, a call, or a conditional jump with a true condition, ADDRESS 1 is selected. ADDRESS 2 is selected for a conditional jump with a false condition and the stack top is selected for a return branch. In the case of a call, ADDRESS 2 is pushed onto the stack, for use with the next return.

Control section 516 also determines which output of mux 520: when the branch TYPE is unconditional, a call, or a conditional jump with a true condition, NEXT 1 is selected and applied to the PENDING line. NEXT 2 is selected for a conditional jump with a false condition and the stack top is selected for a return branch.

Control section 516 outputs an error signal if the CHECKSUM value from branch table 502 does not match what checksum logic 524 calculates as the checksum from bus tap 504, if the execution time obtained by monitoring real-time clock 76 does not match the expected execution time indicated by the EXECUTION TIME (TIMING) field, or if the password provided by processor 20 does not match the PASSWORD field.

FIG. 6 shows scrambler 106 in more detail. Scambler 106 comprises a demultiplexer (demux) 602, a mux 604, a pseudo-random number generator (PRNG) 606 and a number of buffers 608. Three buffers 608A, 608B and 608C are shown, however the number of buffers is not limited to three. The effect of scrambler 106 on an input data stream is to rearrange the order of bits, bytes, words or blocks of the input data stream in a deterministic and reversible manner.

To do this, demux 602 parses the input data elements (bits, bytes, words or blocks) at its input to one of its outputs as determined by a current pseudorandom number. As the current pseudorandom number changes, the output to which the elements are directed changes. Mux 604 combines the separated streams of elements into one stream as they are output by the buffers. The elements are reordered because they require different amounts of time to travel between demux 602 and mux 604, due to the arrangement of buffers 608. Each buffer 608 is either a first-in, first-out (FIFO) which alternates its head and tail, or is a FIFO which alternates as a last-in first-out (LIFO) buffer. In the former case, each time an element is shifted into a buffer 608 from the left, an element is output to mux 604 from the right and each time an element is shifted into the buffer from the fight, an element is output from the left. In the latter case, elements are pushed into the buffer from either end, but they are output from the right end. The end from which the element is shifted into the buffer 608 is controlled by the values output by PRNG 606.

Thus, knowing the pseudorandom number sequence, one could discover the reordering pattern and reverse it. In order to discover the pseudorandom number sequence, the key value (stored in key register 64 of FIG. 2 or key register 110 of FIG. 3) must be known, since that key value acts as the seed for PRNG 606. Of course, where hardware is at a premium, scrambler 106 could use portions of the decompressor, or the key value could be used to scramble or modify internal decompression tables, such as probability estimation or R-code tables.

Where hardware logic is especially at a premium, the pseudorandom number generator (PRNG) 700 shown in FIG. 7 can be used. PRNG 700 requires only a key shift register 702, a maximal length sequence (MLS) shift register 704, two muxes 706, 708 and one XOR gate 710. Inputs to PRNG 700 are provided by a key clock 712, an MLS clock 714, a KEY IN serial input, a KEY LOAD signal and an INIT/RUN signal. Once loaded, key shift register 702 can be used as key register 64 or 110, with the application of an uninterruptible power source 716.

FIG. 7 shows the input to key shift register 702 being the output of mux 706, which is either the looped-back output of key shift register 702 or the KEY IN input depending on whether the KEY LOAD signal at the select input of mux 706 is asserted or not. FIG. 7 also shows the input to MLS shift register 704 being the output of mux 708 which is either the output of key shift register 702 or the output of XOR gate 710 depending on whether the INIT/RUN signal at the select input of mux 708 is set to INIT or RUN. The inputs to XOR gate 710 are the output of MLS shift register 704 and one tap from a nonfinal stage of MLS shift register. The particular tap used and the number of stages in MLS shift register determine the length of the pseudorandom number sequence which results. For examples of sequence lengths and tap points, see Knuth, D. E., The Art Of Computer Programming, 2d. Ed., 1981, pp. 27-29 and Table 1 therein. In one embodiment, the number of stages (flip-flops) for MLS shift register 704 is 98 and the number of bits in a key value is 98, however other lengths and taps work equally well. Of course, the number of bits in the key value should be large enough that a copyist cannot easily guess its value. A 98 stage MLS shift register will produce a sequence of bits which repeats only every 2.sup.98 -1 bits. With this many stages, the shift register need not be maximal length. One advantage to not having the shift register be maximal length is that the set of taps for maximal length shift registers are known in the art and therefore a non-maximal length shift register would be more difficult to reverse engineer.

The key value is initially loaded into key shift register 702 by asserting the KEY LOAD signal, applying the key to the KEY IN input and clocking key clock 712 until the key value is loaded. Once the key value is loaded, the KEY LOAD signal is unasserted, so that the clocking of key clock 712 merely circulates the key value within key shift register 702. The KEY LOAD signal should be unasserted permanently, which could be done by having the key preceded by a leading "1" bit. That bit is then used to set a flip-flop (not shown) when it reaches the output of key shift register 702. That flip-flop would control whether or not the KEY LOAD signal could be asserted and would also be powered by uninterruptible power source 716.

The key value is circulated in key shift register 702 to read it out. When the INIT/RUN signal is set to INIT, the key value will be clocked into MLS shift register 704 by MLS clock 714, which clocks along with key clock 712. Once loaded, MLS shift register 704 will run and circulate its contents altered, of course, by XOR gate 710 to form a maximal length sequence of pseudorandom numbers, as is known in the art. The pseudorandom numbers of the sequence can be read out in parallel from MLS shift register 704. With a low-cost PRNG such as the one just described, multiple keys become more feasible.

In summary, the above detailed description described a system for preventing the copying of program data by a copyist having access only to the end user portions of the hardware and/or software needed to run the program. While the examples referred to a specific application of protecting game programs which are provided on game cartridges and used with game consoles, other applications were described. Furthermore, the invention is usable even where the program is provided primarily as software, so long as a small hardware component containing the security chip is provided. But one improvement of the present invention over the prior art is that the program data is kept encrypted until decrypted by a security chip, and even then less than all of the program data is provided to a processor--only the program code for executing the instance of the program whose flow is determined for the specific set of inputs provided by the user is made available. The data not provided to the processor is either provided only at a time known to be the appropriate time for the processor to be requesting the program data, or is never provided to the processor. In the latter case, the security chip performs the operations which would have been performed by the processor had the security chip provided all the program data. In one embodiment, the information retained by the security chip is branching information. Thus, each time a processor encountered a branch instruction, that instruction could only be completed with the assistance of the security chip.

The above description also described the internal structure and operation of the security chip, a system for generating encrypted program data, the interaction of the security chip and the processor during normal operation and operation while under attack by a copyist, as well as a low-cost pseudorandom number generator based on a stored key value.

The above description is illustrative and not restrictive. Many variations of the invention will become apparent to those of skill in the art upon review of this disclosure. Merely by way of example, the above description described an embodiment of the invention which protected video game programs from unauthorized copying and use, however non-game applications of the invention follow from this disclosure. Other variations are discussed below.

In one particular embodiment of a video game according to the present invention, the security chip tracks the number of "lives" a player has left and the amount of time remaining until the player must move on to the next level. The security chip decrypts the program data one level at a time, and thus initially provides only the program data for the first level of the game. The program data contains initial values which are never shown in the clear outside the security chip and those values are used to set a timer for the level. As the player is playing the game, the program informs the security chip when certain events occur. If the information from the processor is as expected, the game is played normally. However, if the information is not as expected, time can be added to the timer or "lives" can be removed. If the rime on the timer is extended, the player has more time to wait to get to the next level. If the time is extended often enough due to the program running differently than intended, the timer will never run down and the player will remain on the first level. One advantage to this approach over the security chip simply shutting down the processor is that it is not apparent when in the program the security chip first detects a problem.

The former approach is not without its advantages. If the processor is part of a fault-tolerant system, which might or might not be subject to attack by copyists, the security chip can be used as a means for preventing an errant processor from continuing once it has failed. The same security chip can be used to halt the processor or set off an alarm when improper execution is detected, but the assumption there is that the unexpected operation is caused by hardware or software failure instead of deliberate acts of a copyist.

As an example of non-game use, the processor might perform image processing. In image processing, a convolution might be required. A convolution is performed as a series of many multiply operations and an add operation. Since the security chip can monitor the data bus of the processor, the security chip can perform the addition as the multiply results appear on the bus. When the sum is needed, the processor requests it from the security chip. If the processor is run without the security chip, the convolution will either be wrong or the processor will run slower since it will have to do the accumulation itself.

Where the program data is compressed, elements of the decompressor might be used to contribute to the decryption process. For example, FIG. 6 shows a data scrambler which could be formed from buffers of the decompressor. Also, where the decompressor is an entropy encoder, the security chip could use the key value for form the initial parameters for the decompression process, such as the initial probability values. This has the additional advantage of preventing the one-to-one mapping of bits that usually occurs at the start of the entropy coder before enough bits have been received to infer probabilities from the bits themselves.

When the security chip detects a security violation it need not stop the processor. Other options are to reset the processor after a random delay, output pseudorandom numbers as decoded data or adjust the PRNG by complement enabling or other means so that the PRNG slowly degrades the data being output.

The scope of the invention should, therefore, be determined not with reference to the above description, but instead should be determined with reference to the appended claims along with their full scope of equivalents. ##SPC1##