Universal secure token for obfuscation and tamper resistance

• US 8,171,306 B2
• Filed: 11/05/2008
• Issued: 05/01/2012
• Est. Priority Date: 11/05/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Venkatesan, Ramarathnam, Goyal, Vipul
• Primary Examiner(s): Colin, Carl
• Assistant Examiner(s): Lesniewski, Victor
• Application Number:
  US12/265,197
• Publication Number:
  US 20100115260A1
• Time in Patent Office: 1,273 Days
• Field of Search: 713/159, 713/172, 713/185, 713/187, 713/189, 713/193, 713/194, 726/9, 726/20, 726/22, 726/26, 726/30
• US Class Current: 713/187
• CPC Class Codes: G06F 21/14 against software analysis or reverse engineering, e.g. by obfuscation
• CPC Class Codes: H04L 2209/16 Obfuscation or hiding, e.g. involving white box
• CPC Class Codes: H04L 9/3234 involving additional secure or trusted devices, e.g. TPM, smartcard, USB or software token network architectures or network communication protocols for supporting authentication of entities using an additional device in a packet data network H04L63/0853
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC

Abstract

Program obfuscation is accomplished with tamper proof token including an embedded oracle. A public obfuscation function can be applied to any program/circuit to produce a new obfuscated program/circuit that makes calls to the corresponding oracle to facilitate program execution. A universal circuit representation can be employ with respect to obfuscation to hide circuit wiring and allow the whole circuit to be public. Furthermore, the token or embedded oracle can be universal and stateless to enable a single token to be employed with respect to many programs.

Claims

1. A program obfuscation system, comprising:

a hardware token including a secret oracle component, the hardware token and the secret oracle component having a stateless operation to enable interacting concurrently with multiple obfuscated program components, the secret oracle component enabling use of an execution identity for an entire execution to facilitate security when interacting concurrently with the multiple obfuscated program components;

an obfuscated program component of the multiple obfuscated program components, produced by a public obfuscation function corresponding to the secret oracle component, that includes queries to the secret oracle component included in the hardware token to facilitate evaluation of the obfuscated program component, the secret oracle component to assign a secret obfuscation identity to each of the queries, the obfuscated program component obfuscated as a universal circuit; and

an evaluation component that detects unauthorized modification with respect to the obfuscated program component or input based in part on message authentication codes in conjunction with input encryption, program evaluation, and output decryption.

2. The system of claim 1, wherein the hardware token and secret oracle component restrict queries to a fixed size.

3. The system of claim 1, wherein the secret oracle component includes an encryption component that encrypts program input in response to one or more queries.

4. The system of claim 3, further comprising an injection component that injects a message authentication code within the input to facilitate tamper detection.

5. The system of claim 1, wherein the secret oracle component includes an input component that receives encrypted input, evaluates a portion of the program, and returns encrypted results.

6. The system of claim 5, further comprising a tamper component that generates the message authentication code associated with the encrypted results to facilitate tamper detection.

7. The system of claim 5, further comprising a decryption component that decrypts the results.

8. A method of program obfuscation, comprising:

receiving queries including encrypted information from a plurality of obfuscated universal circuit representations of programs, by a computer including a memory and a processor, the plurality of obfuscated universal circuit representations of programs comprising one or more input wires;

assigning a secret obfuscation identity to each of the queries;

processing the queries in parallel at a secret oracle component having a stateless operation, the secret oracle component enabling use of an execution identity for an entire execution to facilitate security when processing the queries in parallel, the secret oracle component included in a hardware token;

returning encrypted results to at least one of the plurality of obfuscated universal circuit representations;

receiving message authentication codes associated with one or more input wires to detect unauthorized modification; and

verifying input authentication utilizing the message authentication codes prior to evaluation in conjunction with the encrypted information, evaluation of the querying program, and output decryption.

9. The method of claim 8, further comprising receiving at least one input encryption query and returning an encrypted version of each input wire in the universal circuit.

10. The method of claim 9, further comprising outputting a message authentication code for each input wire of the universal circuit to facilitate identification of input alteration subsequent to encryption.

11. The method of claim 8, further comprising receiving a gate evaluation query including encrypted versions of the input wires and the gate and returning an encrypted version of the gate evaluation result.

12. The method of claim 8, further comprising receiving a query for decrypted output for a gate wire, decrypting the output, and returning the value.

13. The method of claim 12, further comprising authenticating encrypted data received with the query, and verifying that the wire is an output wire prior to returning the value.

14. A method of program obfuscation comprising:

acquiring, by a computer including a memory and a processor, a public obfuscation function;

applying the function to a circuit representation of a program to generate an obfuscated universal circuit that includes queries to an oracle that is tamper resistant and stateless, the oracle to process multiple queries from multiple programs in parallel, to assign a secret obfuscation identity to each of the multiple queries, the oracle enabling use of an execution identity for an entire execution to facilitate security when processing the multiple queries from the multiple programs in parallel, and to facilitate evaluation of the obfuscated universal circuit, wherein the oracle is included in a hardware token; and

detecting unauthorized modification of the obfuscated universal circuit or input based in part on message authentication codes, input encryption, program evaluation and output decryption.

15. The method of claim 14, further comprising acquiring the public obfuscation function from a particular user possessing the corresponding oracle.

16. The method of claim 14, further comprising acquiring the public obfuscation function from a token creation authority that creates the public obfuscation function and provides the corresponding oracle to a user.