Method for encrypting a program for subsequent execution by a microprocessor configured to decrypt and execute the encrypted program

• US 9,461,818 B2
• Filed: 10/29/2013
• Issued: 10/04/2016
• Est. Priority Date: 05/25/2010
• Status: Active Grant

• Current Assignee: VIA Technologies Incorporated (VIA Technologies)
• Original Assignee: VIA Technologies Incorporated (VIA Technologies)
• Inventors: Henry, G. Glenn, Parks, Terry, Bean, Brent, Crispin, Thomas A.
• Primary Examiner(s): Joo, Joshua
• Assistant Examiner(s): Naji, Younes
• Application Number:
  US14/066,350
• Publication Number:
  US 20140195821A1
• Time in Patent Office: 1,071 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 21/52 during program execution, e.g. stack integrity ; Preventing unwanted data erasure; Buffer overflow
• CPC Class Codes: G06F 21/54 by adding security routines or objects to programs
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/71 to assure secure computing or processing of information
• CPC Class Codes: G06F 21/72 in cryptographic circuits
• CPC Class Codes: G06F 2212/402 Encrypted data
• CPC Class Codes: G06F 2212/452 Instruction code
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: G06F 9/30003 Arrangements for executing specific machine instructions
• CPC Class Codes: G06F 9/30058 Conditional branch instructions
• CPC Class Codes: G06F 9/30079 Pipeline control instructions, e.g. multicycle NOP
• CPC Class Codes: G06F 9/30178 of compressed or encrypted instructions
• CPC Class Codes: G06F 9/30189 according to execution mode, e.g. mode flag
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 2209/20 Manipulating the length of blocks of bits, e.g. padding or block truncation
• CPC Class Codes: H04L 9/0618 Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation
• CPC Class Codes: H04L 9/0827 involving distinctive intermediate devices or communication paths network architectures or network communication protocols using different networks H04L63/18
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04L 9/0894 : Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

A method for encrypting a program for subsequent execution by a microprocessor configured to decrypt and execute the encrypted program includes receiving an object file specifying an unencrypted program that includes conventional branch instructions whose target address may be determined pre-run time. The method also includes analyzing the program to obtain chunk information that divides the program into a sequence of chunks each comprising a sequence of instructions and that includes encryption key data associated with each of the chunks. The encryption key data associated with each of the chunks is distinct. The method also includes replacing each of the conventional branch instructions that specifies a target address that is within a different chunk than the chunk in which the conventional branch instruction resides with a branch and switch key instruction. The method also includes encrypting the program based on the chunk information.

Claims

1. A method for encrypting an unencrypted program for subsequent execution by a microprocessor configured to decrypt and execute the encrypted program, the method comprising:

receiving an object file specifying the unencrypted program that includes conventional branch instructions whose target address is determinable prior to a time in which the microprocessor runs the unencrypted program;

obtaining chunk information;

dividing the unencrypted program into a sequence of chunks, wherein each of the chunks comprises a sequence of instructions, wherein the chunk information further comprises encryption key data associated with each of the chunks, wherein the encryption key data associated with each of the chunks is distinct;

replacing each of the conventional branch instructions that specifies a target address that is within a different chunk than a chunk in which a conventional branch instruction resides with a branch and switch key instruction that includes distinct key reference and branch information fields, the key reference field referencing a set of encryption keys for encrypting a targeted chunk, and the branch information field including information for computing a target address; and

encrypting the unencrypted program based on the chunk information and the branch and switch key instruction.

2. The method of claim 1, wherein each of the branch and switch key instructions specifies a storage location within the microprocessor storing the encryption key data associated with the chunk that includes the target address specified by the branch and switch key instruction.

3. The method of claim 1, wherein said encrypting the unencrypted program based on the chunk information about the chunks comprises:

for each block of instruction data of each of the chunks, generating an encryption key based on the encryption key data associated with the chunk and a portion of a memory address of a block, so that the unencrypted program is uniquely encrypted as a function of a location of the unencrypted program in memory.

4. A method, for encrypting an unencrypted program for subsequent execution by a microprocessor configured to decrypt and execute the encrypted program, the method comprising:

receiving an object file specifying the unencrypted program that includes conventional branch instructions whose target address is determinable prior to a time in which the microprocessor runs the unencrypted program;

obtaining chunk information;

dividing the unencrypted program into a sequence of chunks, wherein each of the chunks comprises a sequence of instructions, wherein the chunk information further comprises encryption key data associated with each of the chunks, wherein the encryption key data associated with each of the chunks is distinct;

replacing each of the conventional branch instructions that specifies a target address that is within a different chunk than a chunk in which a conventional branch instruction resides with a branch and switch key instruction;

for each block of instruction data of each of the chunks, generating an encryption key based on the encryption key data associated with the chunk and a portion of a memory address of a block by;

selecting first and second key values from the encryption key data based on a first portion of the memory address;

rotating the first key value based on a second portion of the memory address;

adding or subtracting the rotated first key value to or from the second key value based on a third portion of the memory address to generate the encryption keys;

for each block, performing a Boolean exclusive-OR (XOR) operation of the block with the generated encryption key.

5. The method of claim 4, wherein the encryption key data includes K key values, P is a percentage of possible key combinations used, and a width of the encryption key and each of the K key values is W bytes, wherein said selecting, rotating, and adding or subtracting yields P×

W²×

(K!/(2×

(K−

2)!)) different combination of bytes of the K key values over a sequence of memory addresses.

6. A method, for encrypting an unencrypted program for subsequent execution by a microprocessor configured to decrypt and execute the encrypted program, the method comprising:

receiving an object file specifying the unencrypted program that includes conventional branch instructions whose target address is determinable prior to a time in which the microprocessor runs the unencrypted program;

obtaining chunk information;

dividing the unencrypted program into a sequence of chunks, wherein each of the chunks comprises a sequence of instructions, wherein the chunk information further comprises encryption key data associated with each of the chunks, wherein the encryption key data associated with each of the chunks is distinct;

replacing each of the conventional branch instructions that specifies a target address that is within a different chunk than a chunk in which a conventional branch instruction resides with a branch and switch key instruction; and

encrypting the unencrypted program based on the chunk information and the branch and switch key instruction through a process that comprises;

for each block of instruction data of each of the chunks, generating an encryption key based on the encryption key data associated with the chunk and a portion of a memory address of a block; and

performing a Boolean exclusive-OR (XOR) operation of the block with the generated encryption key;

wherein the encryption key data includes K key values, a width of the encryption key and each of the K key values is W bytes, and P is a percentage of possible key combinations of the K key values used, wherein said generating the encryption key based on the encryption key data associated with the chunk and a portion of a memory address of the block yields an effective encryption key length of P×

W²×

(K!/(2×

(K−

2)!)) bytes.

7. A method for encrypting an unencrypted program for subsequent execution by a microprocessor configured to decrypt and execute the encrypted program, the method comprising:

receiving an object file specifying the unencrypted program that includes conventional branch instructions whose target address is determinable only at a time in which the microprocessor runs the unencrypted program;

obtaining chunk information;

dividing the unencrypted program into a sequence of chunks, wherein each of the chunks comprises a sequence of instructions, wherein the chunk information further comprises encryption key data associated with each of the chunks, wherein the encryption key data associated with each of the chunks is distinct;

replacing each of the conventional branch instructions with a branch and switch key instruction that includes distinct key reference and branch information fields, the key reference field referencing a set of encryption keys for encrypting a targeted chunk, and the branch information field including information for computing a target address; and

encrypting the unencrypted program based on the chunk information and the branch and switch key instruction.

8. The method of claim 7, further comprising:

including the chunk information within the object file for loading into the microprocessor prior to execution of the unencrypted program by the microprocessor.

9. The method of claim 8, wherein the chunk information within the object file for loading into the microprocessor prior to execution of the unencrypted program specifies for each of the chunks a storage location within the microprocessor storing the encryption key data associated with the chunk.

10. The method of claim 7, wherein said encrypting the unencrypted program based on the chunk information comprises:

for each block of instruction data of each of the chunks, generating an encryption key based on the encryption key data associated with the chunk and a portion of a memory address of a block;

performing a Boolean exclusive-OR (XOR) operation of the block with the generated encryption key.

11. A method, for encrypting an unencrypted program for subsequent execution by a microprocessor configured to decrypt and execute the encrypted program, the method comprising:

receiving an object file specifying the unencrypted program that includes conventional branch instructions whose target address is determinable only at a time in which the microprocessor runs the unencrypted program;

obtaining chunk information;

dividing the unencrypted program into a sequence of chunks, wherein each of the chunks comprises a sequence of instructions, wherein the chunk information further comprises encryption key data associated with each of the chunks, wherein the encryption key data associated with each of the chunks is distinct;

replacing each of the conventional branch instructions with a branch and switch key instruction; and

for each block of instruction data of each of the chunks, generating an encryption key based on the encryption key data associated with a chunk and a portion of a memory address of a block by;

selecting first and second key values from the encryption key data based on a first portion of the memory address;

rotating the first key value based on a second portion of the memory address;

adding or subtracting the rotated first key value to or from the second key value based on a third portion of the memory address to generate the encryption keys;

for each block, performing a Boolean exclusive-OR (XOR) operation of the block with the generated encryption key.

12. The method of claim 11, wherein the encryption key data includes K key values, P is a percentage of possible key combinations used, and a width of the encryption key and each of the K key values is W bytes, wherein said selecting, rotating, and adding or subtracting yields P×

W²×

(K!/(2×

(K−

2)!)) different combination of bytes of the K key values over a sequence of memory addresses.

13. A method, for encrypting an unencrypted program for subsequent execution by a microprocessor configured to decrypt and execute the encrypted program, the method comprising:

receiving an object file specifying the unencrypted program that includes conventional branch instructions whose target address is determinable only at a time in which the microprocessor runs the unencrypted program;

obtaining chunk information;

dividing the unencrypted program into a sequence of chunks, wherein each of the chunks comprises a sequence of instructions, wherein the chunk information further comprises encryption key data associated with each of the chunks, wherein the encryption key data associated with each of the chunks is distinct;

replacing each of the conventional branch instructions with a branch and switch key instruction; and

encrypting the unencrypted program based on the chunk information and the branch and switch key instruction through a process that comprises;

for each block of instruction data of each of the chunks, generating an encryption key based on the encryption key data associated with the chunk and a portion of a memory address of a block; and

performing a Boolean exclusive-OR (XOR) operation of the block with the generated encryption key;

wherein the encryption key data includes K key values, a width of the encryption key and each of the K key values is W bytes, and P is a percentage of possible key combinations of the K key values used, wherein said generating the encryption key based on the encryption key data associated with the chunk and a portion of a memory address of the block yields an effective encryption key length of P×

W²×

(K!/(2×

(K−

2)!)) bytes.

14. A computer program product encoded in at least one non-transitory computer usable medium for use with a computing device, the computer program product comprising:

computer usable program code embodied in said medium, for specifying a method for encrypting an unencrypted program for subsequent execution by a microprocessor configured to decrypt and execute the encrypted program, the computer usable program code comprising;

first program code for receiving an object file specifying the unencrypted program that includes conventional branch instructions whose target address may be determined is determinable prior to the time in which the microprocessor runs the unencrypted program;

second program code for obtaining chunk information, dividing the unencrypted program into a sequence of chunks, wherein each of the chunks comprises a sequence of instructions, wherein the chunk information further comprises encryption key data associated with each of the chunks, wherein the encryption key data associated with each of the chunks is distinct;

third program code for replacing each of the conventional branch instructions that specifies a target address that is within a different chunk than a chunk in which a conventional branch instruction resides with a branch and switch key instruction; and

fourth program code for generating an encryption key based on the encryption key data, for each block of instruction data for each of the chunks, by;

selecting first and second key values from the encryption key data based on a first portion of the memory address;

rotating the first key value based on a second portion of the memory address; and

adding or subtracting the rotated first key value to or from the second key value based on a third portion of the memory address to generate the encryption key;

performing a Boolean exclusive-OR (XOR) operation of a block with the generated encryption key.

15. The computer program product of claim 14, wherein each of the branch and switch key instructions specifies a storage location within the microprocessor storing the encryption key data associated with the chunk that includes the target address specified by the branch and switch key instruction.

16. The computer program product of claim 14, wherein the encryption key data includes K key values, P is a percentage of possible key combinations used, and a width of the encryption key and each of the K key values is W bytes, wherein said selecting, rotating, and adding or subtracting yields P×

W²×

(K!/(2×

(K−

2)!)) different combination of bytes of the K key values over a sequence of memory addresses.

17. The computer program product of claim 14, wherein the encryption key data includes K key values, P is a percentage of possible key combinations of the K key values used, and a width of the encryption key and each of the K key values is W bytes, wherein said generating the encryption key based on the encryption key data associated with the chunk and a portion of a memory address of the block yields an effective encryption key length of P×

W²×

(K!/(2×

(K−

2)!)) bytes.

18. The computer program product of claim 14, wherein the at least one non-transitory computer usable medium is selected from a set of a disk, tape, or other magnetic, optical, or electronic storage medium.