Method and System for Using a Non-Inversible Transform and Dynamic Keys to Protect Firmware

The present invention relates generally to cryptography, and more particular to encrypting and decrypting object codes in firmware.

Cryptography has became increasingly important in protecting firmware, program, and data with the rapid development of the information superhighway, the Internet, and the World Wide Web. Many of the well known cryptographic methods have been based on mathematical-intensive calculations, such as the RSA and Deffie-Hellman approaches, and not based on the design of digital electronics. The digital electronics approach seeks to protect firmware, program, and data with similar qualities and desirable characteristics as the RSA and Deffie-Hellman approaches. A desirable cryptographic approach encrypts and decrypts information quickly to minimize delays that occurs during the computation process while providing a high degree of security, such using multiple decryption keys, to withstand cryptoanalytic attacks.

FIGS. 1A-1B show a bit reverse ciphering technique for encrypting object codes and decrypting encrypted codes. The bit reverse ciphering technique uses an exclusive-OR operator for both the encrypting and decrypting processes. The exclusive-OR operator produces the same Boolean equation for taking an exclusive-OR operation of a first variable and a second variable to produce a result Y, and for taking the result Y and the second variable to obtain back the value of the first variable. In FIG. 1A, the object code X.sub.n is encrypted to an encrypted code Y.sub.n by an encrypted key k.sub.o by the Boolean equation: Y.sub.n =X.sub.n .sym.k.sub.0, where n=1, . . . , N. In FIG. 1B, the object code X.sub.n is retrieved by taking an exclusive-OR of Y.sub.n and k.sub.0 as denoted by the Boolean equation: X.sub.n =Y.sub.n .sym.k.sub.o, where n=1, . . . , N. The selection of the common Boolean operator for both the encryption process and decryption process reduces the complexity of the implementation while minimizes the delay in decoding the encrypted codes. However, the bit reverse ciphering technique is quite susceptible upon cryptoanalytic attack. A short key k.sub.0 can be easily decrypted by trying different possible permutations. Even if a key is constructed using a long string of object codes, the key is still not difficult to decrypt by using a probability density function to decrypt the encrypted code. Thus, the bit reverse ciphering technique is not desirable to protect object codes from intruders.

FIGS. 2A-2B show an inversible transform technique that is more difficult to decrypt than the bit reverse ciphering technique. The object code X.sub.n is encrypted to an encrypted code Y.sub.n by taking the transform of X.sub.n, represented by the equation Y.sub.n =T(X.sub.n). The transform T is selected as having a corresponding inverse transform as denoted by T.sup.-1. Correspondingly, the object code X.sub.n can be decrypted from the encrypted code Y.sub.n from the equation X.sub.n =T.sup.-1 (Y.sub.n). In the inversible transform ciphering technique, the process of encrypting an object code X.sub.n is different from the process of decrypting an encrypted code Y.sub.n. The following example illustrates this difference. For a first sequence of codes X.sub.n, where n=0, 1, 2, . . . , 7, that transforms to a second sequence of codes Y.sub.n, where n=0, 1, 2, . . . , 7, the transform T is characterized as follows:

000 to 001

001 to 101

010 to 111

011 to 011

100 to 110

101 to 000

110 to 100

111 to 010

The inversible transform ciphering technique has the characteristics of one-to-one mapping, which makes it vulnerable upon cryptoanalytic attach. The inversible transform may be decrypted by monitoring the statistic occurrence of codes to find the inverse transform by comparing the frequency of occurrence of the encrypted code Y.sub.n to the object code X.sub.n. For example, in a 3-bit binary string, the binary code "111" has the highest probability of occurrence relative to the other 3-bit binary codes. If the binary code "111" is mapped to the binary code "010", the binary code "010" in the encrypted domain retains the characteristics of the highest probability of occurrence as derived from the binary code "111". By observing the occurrence of codes, an intruder may be able to decrypt the mapping relationship between the object code X.sub.n and the encrypted code Y.sub.n. Therefore, the inversible transform ciphering technique is also vulnerable upon cryptoanalytic attach.

As shown in FIGS. 3A-3B, a non-inversible ciphering technique provides another alternative to protect an object code X.sub.n without subjecting the object code X.sub.n to be decrypted by statistical occurrence. The non-inversible ciphering technique provides high security to object codes X.sub.n because it does not have an one-to-one mapping relationship between the object code X.sub.n and the encrypted code Y.sub.n. Although the non-inversible ciphering technique provides high security to protect the object code X.sub.n, this technique does not have a corresponding inverse transform to decrypt the encrypted code Y.sub.n back to the object code X.sub.n. Without a corresponding inverse transform, the object code X.sub.n cannot be recovered on the basis of knowing the encrypted code Y.sub.n, and therefore, the non-inversible ciphering technique is not suitable to protect object codes in firmware, program, or data.

Accordingly, it is desirable to have a method and system for encrypting object codes and decrypting encrypted codes using a non-inversible transform.

The present invention discloses a method and system to encrypt an object code using a non-inversible transform and dynamic keys in an encryption circuit and an decryption circuit. The encryption circuit operates to encrypt an object code to an encrypted code using a sequence of dynamic keys which possess non-inversible transform characteristics. Similarly, the decryption circuit operates to decrypt the encrypt code using a sequence of dynamic keys which possess non-inversible transform characteristics.

Two types of keys are used to encrypt object codes and to decrypt encrypted codes. The first one is the single key X.sub.0, and the second one is a sequence of dynamic keys k.sub.n which possesses non-inversible transform characteristics. The single key X.sub.0 is known by both the encryption circuit and the decryption circuit. In addition, the decryption circuit must contain the same type of transform used by the encryption circuit to transform the object code. The sequence of dynamic keys k.sub.n changes in accordance to a timing index in which a different key is computed for a different timing cycle. The dynamic key is generated by a non-inversible transform T on an object code X.sub.n.

The encryption circuit contains a transform circuit U to transform an object code to an encrypted code and the decryption circuit also contains a transform circuit U to transform the encrypted code back to the object code. The transform circuit U can be implemented in various computer hardware, including ROMs, PLAs, and combinatorial logic. The transform circuit U is partitioned into two sections, with the first section called a mobile device U.sub.m and the second section called a resident device U.sub.r. The mobile device U.sub.m typically holds a smaller portion of the transform circuit U so that it can be manufactured within a compact dimension. The mobile U.sub.m unit is designed to be a removable unit, but it can also be a stationary unit. The resident device U.sub.r holds the majority of the logic circuits in the transform circuit U.

One advantage of the present invention is that the present method and system increases the complexity of the permutations and thus increase the protection to withstand upon cryptoanalytic attach. If an object code X.sub.n contains b bits, then the bit reverse method provides 2.sup.b possible combinations of keys. The inversible transform method offers greater resistance from its one-to-one mapping scheme with 2.sup.b !, or 2.sup.b .times.(2.sup.b -1).times.(2.sup.b -2) . . . 2.times.1 permutations of keys. Although the non-inversible transform method offers even greater resistance with the 2.sup.b2.spsp.b -2.sup.b ! permutations, the non-inversible transform method cannot be used to encrypt an object code since no inverse transform exists to decrypt the encrypted code back the object code. The present invention offers greater resistance to withstand upon cryptoanalytic attach having permutations of 2.sup.b {2.sup.b2.spsp.b -2.sup.b !}, which represents the bit reverse method combinations of 2.sup.b, combine the non-inverse transform combinations of (2.sup.b2.spsp.b), minus the inversible transform combinations of 2.sup.b !.

The foregoing aspects and many of the attendant advantages of this invention will become more readily appreciated as the same becomes better understood by reference to the following detailed description, when taken in conjunction with the accompanying drawings, wherein:

FIGS. 1A-1B are schematic diagrams for encrypting object codes to encrypted codes and decrypting encrypted codes back to object codes using a bit reverse ciphering technique.

FIGS. 2A-2B are schematic diagrams for encrypting object codes to encrypted codes and decrypting encrypted codes back to object codes using an inversible transform ciphering technique.

FIGS. 3A-3B are schematic diagrams for encrypting object codes to encrypted codes and decrypting encrypted codes back to object codes using a non-inversible transform technique.

FIG. 4 is a schematic diagram for encrypting object codes and decrypting encrypted codes using a non-inversible transform and dynamic keys in the present invention.

FIG. 5 is a schematic diagram of the encryption circuit to encrypt an object code to an encrypted code.

FIG. 6 is a schematic diagram of one embodiment of the decryption circuit to decrypt the encrypted code back to an object code.

FIG. 7 is a schematic diagram of the second embodiment of the decryption circuit with a mobile transformer device and a resident transform device.

FIG. 8 is a schematic diagram of a set of registers for delaying data.

FIG. 9 is an illustrative schematic diagram of the permutator to convert the encrypted code with q bit-width back to the object code with b bit-width.

FIG. 10 is a schematic diagram of a plurality of exclusive-OR gates showing the composition for each exclusive-OR gate having a pair of inputs to generate a single output signal.

FIGS. 11A-11B show an example of a simple transform circuit and the routing connections in a permutator.

FIG. 12 is a flowgraph of the process to encrypt an object code to an encrypted code.

FIG. 13 is a table showing the permutations from one-bit to eight-bit for a bit reverse technique, an inversible transform technique, a non-inversible transform, and the present method and system.

Referring now to FIG. 4, there is shown a schematic diagram for encrypting an decryption an object code using the non-inversible transform and dynamic keys of the present invention. A processing unit 1 couples to a read only memory 2 through a ciphering circuit 3. The ciphering circuit 3 operates as a security link to safeguard the accessing of the object code from the processing unit 1. The processing unit 1 further couples to other electrical devices, such as input devices 4a-4c, output devices 5a-5c, and random access memories 6a-6c.

In FIG. 5, there is shown a schematic diagram of an encryption device. The encryption circuit 7 includes an exclusive-OR logic gate 8 and a transform circuit 9 containing a transform U device 10, a set of registers 11, and a permutator 12. Object code X.sub.n feeds through a first path 13 through the transform U device 10, the set of registers 11, and the permutator 12 to the exclusive-OR gate 8. The transform U device 10 transforms a first set of binary numbers X.sub.n to a second set of binary numbers Z.sub.m, where X.sub.n ={X.sub.0, X.sub.1, . . . , X.sub.n } and Z.sub.m ={Z.sub.0, Z.sub.1, . . . , Z.sub.m }. The transform U device 10 possesses a non-inversible transform characteristics such that the numerical value of m is less than the numerical value of n, and the mapping of X.sub.n to Z.sub.m constitutes a multiple-to-one mapping, i.e. not one-to-one mapping. For example, if {X.sub.0, X.sub.1, X.sub.2, X.sub.3, X.sub.4, X.sub.5, and X.sub.6 } maps to {Z.sub.1 }, there exists no inverse transform mapping from Z.sub.1 back to X.sub.n domain. Therefore, the transform U device 10 produces a non-inversible transform for encrypting an object code X.sub.n to an encrypted code Z.sub.m.

The set of registers 11 contains X.sub.n-1 registers and provides one-clock-cycle timing delays to the permutator 12. The permutator 12 converts the encrypted code with q bit-width to a permutated code with b bit-width. Object code X.sub.n feeds through a second path 14 directly to the exclusive-OR gate 8. The exclusive-OR gate 8 computes the Boolean logical operation of these two inputs with the equation Y.sub.n =X.sub.n .sym.U(X.sub.n-1) to generate an encrypted code of Y.sub.n, where Y.sub.n contained a series of binary numbers as represented by Y.sub.m ={Y.sub.0, Y.sub.1, . . . , Y.sub.n).

FIG. 6 is a schematic diagram of a decryption circuit. Similar to the encryption circuit 7, the decryption circuit 15 includes an exclusive-OR logic gate 16 and a transform circuit 17 containing a transform U device 18, a set of registers 19, and a permutator 20. Object code X.sub.n feeds through a first path 21 through the transform U device 18, the registers 19, and the permutator 20 to the exclusive-OR gate 16. The transform U device 18 transforms a first set of binary numbers X.sub.n to a second set of binary numbers Y.sub.m, where X.sub.n ={X.sub.0, X.sub.1, . . . , X.sub.n } and Y.sub.m ={Y.sub.0, Y.sub.1, . . . , Y.sub.m }. The transform U device 18 possesses a non-inversible transform characteristics such that the numerical value of m is less than the numerical value of n and the mapping of X.sub.n to Y.sub.m constitutes a multiple-to-one mapping, i.e. not one-to-one mapping. For example, if {X.sub.0, X.sub.1, X.sub.2, X.sub.3, X.sub.4, X.sub.5, and X.sub.6 } maps to {Y.sub.1 }, there exits no inverse transform mapping from Y.sub.1 back to X.sub.n domain. Therefore, the transform U device 18 produces a non-inversible transform of decrypting the encrypted code Y.sub.n back to the object code X.sub.n.

The set of registers 19 contains X.sub.n-1 registers and provide one-clock-cycle timing delays to the permutator 20. The permutator 20 converts the code with q bit-width to a permutated code with b bit-width. The encrypted code Y.sub.m feeds through a second path 22 directly to the exclusive-OR gate 16. The exclusive-OR gate 16 computes the Boolean logical operation of these two inputs with the equation X.sub.n =Y.sub.m .sym.U(X.sub.n-1) to obtain the object code X.sub.n, where X.sub.n contained a series of binary numbers as represented by X.sub.m ={X.sub.0, X.sub.1, . . . , X.sub.m } and where U(X.sub.n-1) is also denoted by the symbol Z.sub.m. Therefore, the encrypted code Y.sub.m has been decrypted to obtain back the object code X.sub.n for retrieving the object code X.sub.n to the processing unit 1.

FIG. 7 is a schematic circuit of the second embodiment of the transform U circuit 17 with a mobile transform device U.sub.m 23 and a resident transform device Ur24. The transform U circuit 17 is partitioned into two parts, namely the mobile transform device U.sub.m 23 and the resident transform device U.sub.r 24. To phrase it in another way, the combination of the mobile transform device U.sub.m 23 and the resident transform device U.sub.r 24 combines in parts to represent the whole circuitry of the transform U circuit 17. The transform U circuit 17 can be designed using a set of combinatorial logic devices, a ROM, or a PLA. Therefore, in a set of combinatorial logic devices, the mobile transform device U.sub.m 23 and the resident transform device U.sub.r 24 consists of two sub-set of the combinatorial logic device in the transform U circuit 17. In a ROM or PLA, the mobile transform device U.sub.m 23 and the resident transform device U.sub.r 24 will be two selected portions of the ROM or PLA, as determined by a designer.

These three implementation approaches, ROm, PLA, or combinatorial logic, can be constructed from a combination of basic logic gates, such as AND gates, OR gates, NOR gates, NAND gates, and XOR gates. A person who possesses ordinary skill in the art would appreciate the many different combinations of the logic devices that can be chosen to implement the design of the mobile transform device U.sub.m 23 and the resident transform device U.sub.r 24.

Turning now to FIG. 8, there is shown a schematic diagram of a set of registers for delaying the data. The length of the registers is determined by the bit-width of q. If q bit is three bits wide, for example, the set of registers would contain R1, R2, and R3 registers to hold the data. These registers are driven by a common clock and provide on-clock-cycle delay before the data is transferred from the transform devices 10 or 18 to the permutators 12 or 20. In FIG. 9, there is shown an illustrative schematic diagram of the permutators 12 or 20 to convert the encrypted code with q bits-width to a permutated codes with p bit-width. The routing connections of the permutators 12 or 20 depend on a preferred design choice. If the bit width of b is larger than the bit width of q, some bit positions of b-bit will be assigned with a logic value of "0" or "1" as fixed values at those bit positions. FIG. 10 is a schematic diagram of a plurality of exclusive-OR gates showing the composition for each exclusive-OR gate having a pair of inputs to generate a single output signal. An exclusive-OR gate ("XOR") having inputs a0 and a1 is represented by a0 XOR a1={NOT a0) (AND a1)} OR {a0 AND (NOT a1)}.

FIGS. 11A-11B show a basic example of the transform devices 10 or 18 and the routing connections of the permutators 12 or 20. In this example, the bit width of the object code is three, with b=3, and the transformed encrypted code is one bit wide, with q=1. The length of the software program is five, with N=5. The sequence of object codes X.sub.n contain values of X.sub.1 =101, X.sub.2 =110, X.sub.3 =111, X.sub.4 =000, and X.sub.5 =011, while setting X.sub.0 =011. The decryption circuit decrypts the encrypted codes and the above parameters as follows:

For n=1,

k.sub.1 =U(011)=010

Y.sub.1 =X1.sym.k.sub.1 =101.sym.010=111

For n=2,

k.sub.2 =U(101)=010

Y.sub.2 =X.sub.2 .sym.k.sub.2 =110.sym.010=100

For n=3,

k.sub.3 =U(110)=010

Y.sub.3 =X.sub.3 .sym.k.sub.3 =111.sym.010=101

For n=4,

k.sub.4 =U(111)=010

Y.sub.4 =X.sub.4 .sym.k.sub.4 =000.sym.010=010

For n=5,

k.sub.5 =U(000)=000

Y.sub.5 =X.sub.5 .sym.k.sub.5 =011.sym.000=011

Referring now to FIG. 12, there is shown a flowgraph of the process to encrypt an object code to an encrypted code. At step 25, the first value of a sequence of object codes X.sub.n is initialized. The value of n is set to the numerical value of one in step 26. At step 27, the decryption circuit 15 computes the dynamic keys, with k.sub.n =U(X.sub.n-1). At step 28, the decoder 15 computes a sequence of encrypted codes Y.sub.n =X.sub.n XOR K.sub.n such that a value of m in Y.sub.n is selected which is less is less than a value of n in X.sub.n. At step 29, the value of n is incremented by one. At step 30, let N denotes the length of the program, if n does not greater than N, then the program returns to step 27, but if the n equals to N, then at step 31, the sequence of object codes X.sub.n has been encrypted to the sequence of encrypted codes Y.sub.m.

FIG. 13 is a table showing the permutations from one-bit to eight-bit for a bit reverse technique, an inversible transform technique, a non-inversible transform, and the present method and system. If an object code X.sub.n contains b bits, then the bit reverse method provides 2.sup.b possible combinations of keys from its one-to-one mapping scheme. The inversible transform method offers greater resistance from its multiple-to-one mapping scheme with 2.sup.b ! or mathematically equivalent to 2.sup.b .times.(2.sup.b -1).times.(2.sup.b -2) . . . 2.times.1 permutations of keys. Although the non-inversible transform method offer even greater than resistance with the 2.sup.b2.spsp.b -2.sup.b ! permutations, it cannot be used to encrypt an object code since no inverse transform exists to decrypt back the original data. This invention offers greater resistance to withstand cryptoanalytic attack with permutations of 2.sup.b {2.sup.b2.spsp.b -2.sup.b !}, which represents the bit reverse method combinations of 2.sup.b, combine the non-inverse transform combinations of (2.sup.b2.spsp.b), minus the inversible transform combinations of 2.sup.b !.

While the preferred embodiment of the invention has been illustrated and described, it will be appreciated that various changes can be made therein without departing from the spirit and scope of the invention.