BACKGROUND OF THE INVENTION

1. Field of The Invention

[0001] The present invention relates generally to circuit design, and more particularly, to providing tamper detection and tamper resistance capability to integrated circuits.

[0002] A security system is implemented at multiple levels. At the very bottom level of a security system is hardware that provides the root of security and thrust. Due to weaknesses of software-based security solutions, the recent years see a growing trend of migrating software -based security solutions to hardware-based security solutions. However, a hardware -based security solution still faces a number of security threats. An adversary may resort to a number of techniques to extract confidential data, cryptographic keys or intellectual properties from a hardware system, for example, by testing, side channel analysis, or reverse engineering. An adversary involved in the supply chain may also install a Trojan horse component in a hardware system that may tamper hardware computation integrity or provide a back door for information leak.

2. Description of the Relevant Art

[0003] A number of techniques are available to ensure data and design confidentiality. (1) Testing is protected by encoding, lock and key, or checking the signature of test vectors to guarantee the test vectors are authentic. (2) Including additional circuitry prevents power analysis attacks (by inducing noises or hiding supply variation), timing analysis attacks (by reducing performance difference or increasing performance uncertainty), and fault injection attacks (by concurrent checking).

[0004] Other than data and design confidentiality, security-providing hardware further needs to provide computation integrity. Many of the existing hardware integrity-ensuring techniques are based on ensuring data integrity. For example, a FPGA design can be protected by encrypting and hashing its configuration bit stream. In computer architecture, static code integrity verification protects instructions and data in memory, e.g., by encrypting and hashing in writing, and decrypting and hash matching in reading.

Dynamic code integrity verification detects tamper of runtime instruction sequences, e.g., insertion of malicious instruction sequences by tampering a procedure return address stack through an overflown buffer. Techniques include the traditional control flow checking techniques such as basic and generalized path signature analysis or memory access pattern check. Encrypting and hashing register file contents further prevents leak of decrypted instructions and data at system interrupts.

[0005] Watermarking, tamper proofing, and obfuscation are the typical techniques for software IP protection. Watermarking is the technique which embeds a secret message into the IP to discourage IP theft by enabling the establishment of IP ownership. Tamper proofing technique protects the IP from being tampered by making the IP with any unauthorized modification non-functional. Obfuscating method makes the IP "unintelligible," e.g., difficult to reverse engineer while preserving its correct functionality.

[0006] The dominant hardware IP protection techniques are watermarking. IP watermarking is to secretly convey the information on content ownership and IP rights. Compared with steganography, IP watermarking further requires the property of robustness, i.e., being infeasible to remove or make useless without destroying the object at the same time. Watermarking has been applied to protect soft IPs including combinational logic, sequential circuits, finite state machines and FPGA designs, physical design, and CAD tools. Similar techniques include physical tagging and fingerprinting. These hardware IP watermarking techniques can be categorized as static and dynamic ones. In static hardware IP watermarking, the watermark is detected without running the IP. The dominant technique is constraint- based, i.e., to include extra constraints which indicate ownership information in solving an optimization problem, such as logic optimization, place and route. In dynamic hardware IP watermarking, the watermark can only be detected by running the IP. For example, watermarks can be embedded in logic don't care conditions, a watermarked FSM gives the encrypted ownership information for a given input vector sequence, or, exhibits a unique property for the input vector sequence which is the encrypted ownership information.

[0007] These hardware IP watermarking techniques do not lead to hardware IP tamper -proofing.

Compared with watermarking, tamper-proofing further requires the watermarks to be verified effectively in the runtime. Static hardware IP watermarks are difficult to verify, e.g., they require reverse engineering to retrieve logic or physical design properties. Dynamic hardware IP watermarks can only be verified by applying special input vectors. They do not monitor system runtime behavior, while a Trojan may only start tamper the authentic logic after it is activated. To the best of this inventor's knowledge, no tamper- proofing technique has been developed for hardware IP protection. For example, deploying on-chip monitors to check inconsistency of control signals and data in a microprocessor is a concurrent checking technique and does not achieve tamper-proofing as a supply chain adversary may tamper the monitors.

[0008] A system of concurrent checking capability generates information bits and check bits, for example, in an error-detecting code. The simplest check bits can be parity bits, or, duplicate of the information bits in a dual-module redundancy (DMR) scheme. Checking the consistency between the information bits and the check bits can detect runtime errors such as soft errors or adversary tampers (e.g., triggered by a timer) which cannot be detected by testing.

[0009] A similar category of techniques are built-in self-test (BIST). A typical BIST scheme includes a pattern generator, a response compactor, and a comparator. BIST leads to significant test cost reduction. However, it may not be effective in detecting adversary tamper. For example, a Trojan may not alter the computation result, or, a Trojan may only be triggered by some input patterns that are not included in the BIST scheme.

[0010] A supply chain adversary's capability originates from his knowledge on the hardware design. Hardware design obfuscation reduces a supply chain adversary's capability by limiting his knowledge on the design. The state-of-the-art hardware IP obfuscation techniques introduce a password for a combinational logic block or a FSM to function correctly. Software and hardware design obfuscation has long been studied as a potentially powerful tool against design tamper. Recent theoretical studies show that, (1) there exist functions that cannot be obfuscated, and (2) there exist functions that can be obfuscated. Barak et al. showed the existence of (contrived) classes of functions which are not obfuscatable, or, a general purpose obfuscator does not exist. Goldwasser and Kalai showed that there exist many natural classes of functions that cannot be obfuscated with respect to auxiliary input

(intuitively, one may think auxiliary input as the history or previous executions of the circuit). In contrast, Hohenberger et al. showed a scheme to obfuscate a public key-based re-encryption program by designing a probabilistic function of the keys, and re -randomizing its inputs and outputs. Besides, the only positive obfuscation result is of point functions, which are Boolean functions that return 1 on exactly one input, for example, a password check program. Canetti and Wee separately showed how to obfuscate a point function based on a random oracle, e.g., a hash function that hides all details. An obfuscated point function queries the random oracle on an input, and compares the answer with a stored value. For example, a password check program encrypts an input, and compares the encryption result with a stored value, which is an encrypted password. As a result, it achieves the virtual black box property of obfuscation. This scheme is based on a weaker definition of obfuscation, which says that there is a negligible probability to distinguish an adversary circuit based on the obfuscated scheme and a simulator based on a black box of the function. As a result, this obfuscation scheme of point functions cannot be extended to obfuscate arbitrary Boolean functions.

SUMMARY OF THE INVENTION

[0011] Disclosed herein are methods and circuits which provide a level of security for integrated circuits against supply chain attacks.

[0012] A supply chain adversary may install a hardware Trojan that is triggered at system runtime. A hardware Trojan can be a logic bomb that compromises hardware computation integrity by altering the authentic computation result, or a back door that compromises hardware data confidentiality by leaking out secrets or confidential information. A back door may launch an attack by performing more (e.g., in leaking out information) or less (e.g., in bypassing existing security checks) than expected, while keeping the authentic computation results intact. Since a logic bomb can be detected by online testing or concurrent checking, we focus on detecting back doors.

[0013] In some embodiments, provided is a tamper-evident architecture that generates a fingerprint for the internal states of a hardware system during the performance of a computation. A fingerprint is a short bit string that uniquely identifies a large original data item for all practical purposes, just as human fingerprints uniquely identify people for practical purposes. Fingerprints are typically used to avoid data duplication. For example, a web browser or proxy server can efficiently check if a remote file has been modified, by only fetching its fingerprint and comparing it with that of a previously fetched copy. In the proposed tamper-evident architecture, a fingerprint uniquely identifies the internal states of a hardware system during the performance of a computation. A supply chain adversary cannot tamper any signal that contributes to the fingerprints, otherwise he will leave tamper evidence such as a missing or incorrect fingerprint. He may insert new circuits and generate new signals but he cannot tamper the existing circuits and the existing signals.

[0014] The fingerprints are verified offline by re-computation based on a different implementation, for example, on a FPGA chip to detect any Trojan installed by an ASIC foundry, or, based on netlists synthesized by a different CAD vendor to detect any Trojan installed by a CAD vendor, or, based on a design with a different IP to detect any Trojan installed by an IP provider, or, based on a design from a different designer to detect any Trojan installed by a designer. A supply chain adversary does not have access to the verification scheme, such that he cannot alter the verification scheme to his advantage.

[0015] In particular, to detect an attack that achieves an intact fingerprint by freezing fingerprint generation during the attack, and restoring the system run as well as fingerprint generation after the attack, system time stamps are included in the sampled signals, and a computation start time is stored along with the fingerprint for each computation. Fingerprints are verified offline based on their computation start times. The system clock is further verified against the real clock to detect any attack that achieves an intact fingerprint by compromising the system clock.

[0016] In some other embodiments, provided are methods and circuits for VLSI tamper resistance by design obfuscation.

[0017] A supply chain adversary is an insider who is involved in the design and the manufacturing of a hardware device. His tamper capability is based on his role in the supply chain, specifically, his read and write permission in the design and the manufacturing process of a specific device. An IP provider or a designer for a specific module may have limited access to the design, while a foundry or a chip-level integration designer has access to the whole device design. The general lack of access control in today's supply chain further facilitates an adversary to gain knowledge of a design and launch attacks. Besides based on his role in the supply chain, a supply chain adversary may gain further knowledge of a design by probing, testing, side -channel analysis, or reverse engineering. As a result, a supply chain adversary may have read and write permission to the whole design of a particular device.

[0018] Obfuscation is a long-standing problem in computer security and cryptography. To obfuscate a function /is to create an implementation of / that reveals nothing about / except its input-output behavior. Intuitively, a circuit obfuscator O is an efficient algorithm that, given a circuit C implementing some function outputs another circuit 0(C) such that (i) (preserving functionality) it computes (perhaps approximately) the same function as (ii) (polynomial slowdown) its size is within a polynomial factor of c, and, (iii) ("virtual black box" property) for any efficient adversary that computes some predicate on 0(C), there exists an efficient simulator that computes the same predicate with black-box access to an oracle that evaluates /.

[0019] The present invention achieves hardware design obfuscation based on reconfiguration. For example, the dominant technology such as FPGA achieves reconfigurable logic based on lookup tables. A lookup table includes a 2n-to-l multiplexer and 2n configuration memory cells. One constructs an «-input gate of specific logic by loading configuration data bits to the configuration memory cells. A multiplexer also provides reconfigurable interconnect. Such a reconfiguration technology is fully compatible with the ASIC technology, i.e., reconfigurable logic modules can be embedded on an ASIC chip without any change in the manufacturing process.

[0020] In this technology, the end user determines the reconfigurable modules in the hardware system after the design and the manufacturing process, such that nobody in the design and manufacturing process has any knowledge on the logic implementation in a reconfigurable module. A supply chain adversary has only "black box" access to a reconfigurable module. He may know the logic function of a reconfigurable module based on his role in the design and manufacturing process, but he does not know the exact implementation of the logic function in the reconfigurable module. He cannot perform reverse engineering, run testing or probe internal signals of a reconfigurable module because the reconfigurable logic module has not been constructed. Only a field engineer or a Trojan device may have access to a reconfigurable logic module. A Trojan device has limited intelligence. A field engineer may gain no knowledge on the reconfigurable logic if reconfiguration is applied right after the field engineer's visit, effectively achieving the "virtual black-box" property of the reconfigurable logic module. As a result, a reconfigurable implementation of a logic function /is an obfuscated implementation because it possesses the three properties of obfuscation: (i) preserving functionality, (ii) polynomial slowdown, and (iii) "virtual black-box."

BRIEF DESCRIPTION OF THE DRAWINGS

[0021] Advantages of the present invention will become apparent to those skilled in the art with the benefit of the following detailed description of embodiments and upon reference to the accompanying drawings in which:

[0022] Figure 1 is an illustration of an instruction insertion Trojan including a Trojan ROM, multiplexers, and trigger logic (colored), and a tamper-evident architecture including multiplexers that sample runtime signals including the system time in a round-robin scheme, and a fingerprint generator based on a secure hash function (below the pipeline) in a processor.

[0023] Figure 2 is an illustration of an obfuscated implementation of a point function, which outputs logic one if for a given input x, the output of an one-way function h (such as SHA) equals to a stored value y.

[0024] Figure 3 is an illustration of part of an instruction decoder that is reconfigurable to accept different instruction opcode encodings. The instruction opcodes are stored in a PROM such as a flash memory, and are sent to a group of sequential elements through a scan chain when the system is powered on.

[0025] Figure 4 is an illustration of an obfuscated implementation of an instruction decoder that is based on embedded reconfigurable logic in ASIC technology.

[0026] Figure 5 is an illustration of an exemplary Ethernet IP core, which checks transmit descriptors at given memory locations, and transfers data from the memory to an internal FIFO and to the network. The dashed rectangle marks possible reconfigurable logic modules.

[0027] While the invention may be susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. The drawings may not be to scale. It should be understood, however, that the drawings and detailed description thereto are not intended to limit the invention to the particular form disclosed, but to the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the present invention as defined by the appended claims.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

[0028] It is to be understood that the present invention is not limited to particular devices or systems, which may, of course, vary. It is also to be understood that the terminology used herein is for the purpose of describing particular embodiments only, and is not intended to be limiting. Furthermore, note that the word "may" is used throughout this application in a permissive sense (i.e., having the potential to, being able to), not a mandatory sense (i.e., must). The term "include," and derivations thereof, mean "including, but not limited to." As used in this specification and the claims, the singular forms "a," "an" and "the" include plural referents unless the content clearly indicates otherwise. Thus, for example, reference to "a circuit" includes a combination of two or more circuits.

[0029] A supply chain adversary such as a foundry may insert a Trojan in a processor that inserts Trojan instructions at runtime. The purpose of the inserted Trojan instructions may be to perform additional tasks, for example, leaking confidential or secret information to the network, while keeping the authentic on-the-fly computation intact.

[0030] Such a Trojan can be very small. For example, it may only need to include a Trojan ROM containing the Trojan instructions, a few multiplexers at the instruction fetch unit inputs, and a trigger logic module (shown as colored modules in Figure 1). The Trojan trigger logic module monitors the next program count (npc) in the instruction fetch unit. When the trigger condition is met, for example, the lower n bits of the next program count are all zero's, the Trojan multiplexers direct the instruction fetch unit to fetch instructions from the Trojan ROM other than from the instruction cache. Since the Trojan ROM is very small, it can be addressed by the lower n bits of the program count. The Trojan instruction sequence starts by saving the program count and the other processor internal states, and ends by restoring the processor internal states including the program count. When the low n bits of the program count equal to the address of the last Trojan instruction (that restores the program count), the Trojan multiplexers direct the instruction fetch unit to fetch instructions from the instruction cache. This resumes the authentic operation.

[0031] Such a Trojan cannot be detected by static code integrity check, because the Trojan instructions are not in the memory. It cannot be detected by testing or non-lock-stepping concurrent checking because the authentic computation results are intact. Lock-stepping concurrent checking may detect such a Trojan. However, if a lock-stepping concurrent checking module resides on the same chip as the function system, a supply chain adversary such as a foundry or a chip-integration designer can easily tamper the checking mechanism. If a lock-stepping concurrent checking mechanism resides on a different chip, it would be difficult to achieve synchronization, and only a limited number of signals can be monitored. As a result, a supply chain adversary may tamper the system while keeping the sampled signals intact.

[0032] In some embodiments of the present invention, provided is a fingerprint-based tamper detection method based on a tamper-evident architecture (TEA) that generates fingerprints for sampled signals (shown below the instruction pipeline in Figure 1). By sampling the instruction fetch unit inputs, one can detect Trojans that send Trojan instructions to the instruction fetch unit. While at a higher cost, a supply chain adversary may create his own Trojan instruction fetch unit that inserts Trojan instructions to the instruction decoder unit. By sampling the instruction decoder unit inputs, one can detect Trojans that send Trojan instructions to the decoder unit. While at a higher cost, a supply chain adversary may create his own Trojan instruction decoder unit that sends control signals and data to the function units in the execute stage. To defeat such an attack, one needs to further sample the execute stage inputs. While at an even higher cost, a supply chain adversary may create his own Trojan function units. To defeat such an attack, one needs to further sample the register files and the memory inputs. [0033] A round-robin scheduling algorithm samples the signals for a fingerprint generator based on a hash function that accepts fixed-length messages. One can sample any specific signal once in every k clock cycles, which guarantees to detect any inserted Trojan instruction sequence that takes more than k clock cycles.

[0034] A secure hash function such as Matyas-Meyer-Oseas, Davies-Meyer or Miyaguchi-Preneel can be implemented for fingerprint generation (Figure 1).

[0035] One of the strongest attack schemes against this fingerprint-based tamper detection scheme is to freeze the fingerprint generator based on clock gating during an attack. To thwart such an attack, the system time is included in the sampled signals (Figure 1). To enable verification, the start time is also included along with the fingerprint for each process. Given this scheme, to achieve the same fingerprint, a Trojan needs to freeze the system clock during Trojan instruction execution, and resume the system clock after Trojan instruction execution. A Trojan can achieve this by clock gating. However, this would lead to a discrepancy between the system time and the real time. Checking the system time against the real time will detect such an attack. If the Trojan restores the system time to be consistent with the real time before starting the next process, the next process will have a later start time, which will be detected in verification.

[0036] In some other embodiments of the present invention, provided are VLSI design obfuscation techniques based on reconfiguration.

[0037] In some embodiments, provided is obfuscated VLSI implementation of a point function. An obfuscated point function is achieved by encrypting the primary input and comparing with the encrypted configuration memory content. For example, for a one-way function h and an input x, the return value of the one-way function h(x) is compared with the configuration memory content (Figure 2). Implementing the one-way function at least partially in reconfigurable logic increases the adversary attack complexity, such that a lower cost function h can be chosen for a given adversary complexity to achieve the reverse function hT ¹ .

[0038] In some other embodiments, provided is obfuscated VLSI implementation of a re-encryption scheme. Obfuscation of a re-encryption scheme is based on obfuscation of an module that outputs (y ^A (ci2/ai), y ^A (b2/bi), y) where y is a random number, (ai, bi, g) and f<% fe, h) are Alice and Bob's secret keys, respectively (See, for example, S. Hohenberger, G. N. Rothblum, A. Shelat, and V. Vaikuntanathan. Securely Obfuscating Re-Encryption. In Theory of Cryptography Conf, pages 233-252, 2007). A reconfigurable logic implementation of the module is an obfuscated implementation that provides the root of design confidentiality and leads to obfuscation of the re -encryption scheme.

[0039] To prevent an adversary from inserting plaintext Trojan instructions to a computer system, an instruction decoder needs to take as input encrypted instructions, e.g., instructions of a different opcode encoding. Such an instruction decoder needs to be further obfuscated to gain the virtual black box property such that an adversary cannot gain sufficient knowledge on the decoder, the instruction set and the machine code format.

[0040] In some embodiments of the present invention, provided is an instruction decoder that is reconfigurable to accept different instruction opcode encodings. An exemplary implementation is based on a comparator and a group of sequential elements which store the instruction opcodes. The instruction opcodes are stored in a PROM such as a flash memory. When the system is powered on, a "program opcodes" signal sends the instruction opcodes from the PROM to the sequential elements through a scan chain (Figure 3). [0041] In some embodiments, provided is an obfuscated instruction decoder that is based on obfuscated VLSI implementation of point functions that output logic one for specific opcodes, respectively.

[0042] In some other embodiments, provided is obfuscated VLSI implementation that is based on concealing logic functions in reconfigurable logic. For an instruction decoder, without knowing the input encrypted instruction format, and the complete decoder logic, a Trojan cannot (1) insert Trojan instructions in the same encrypted format, or (2) insert input to the ASIC decoder logic. If the reconfigurable logic module is only at the input of the decoder logic, a supply chain adversary may understand the decoder logic which is implemented in the ASIC technology, and insert input signals to the ASIC decoder logic. To thwart this attack, one needs to embed reconfigurable logic in ASIC logic. For maximum attack complexity or reverse engineering complexity at minimum area, power consumption and performance overhead, it is preferred that reconfigurable logic gates cut the decoder logic into separate logic networks (Figure 4).

[0043] Besides instruction insertion attacks, other supply chain attacks may have a limited capability, but still be effective. For example, in a computing system where the data in memory storage is encrypted, a Trojan may read the decrypted data in the caches and send them to the network.

[0044] To prevent a Trojan from accessing confidential data and sending packets to the network, in some embodiments of the present invention, each network transmit packet originating from a mission-critical computer includes a signature, while a network router checks the signature and drops any packet with an incorrect signature. An exemplary Ethernet IP core drops any packet which has an incorrect signature. And such checking is tamper-proof, e.g., a supply chain adversary cannot bypass such checking. In some embodiments, this is based on a tamper-proof signature verification scheme, which requires a message be encrypted based on its signature, such that a receiver must complete the signature verification scheme to achieve the correct message. Specifically, an Ethernet IP core MAC control module which decrypts a transmit message based on its signature, and sends the decrypted message to the internal FIFO. The internal FIFO is implemented in reconfigurable logic, such that a supply chain adversary cannot insert Trojan messages directly to the FIFO (Figure 5). One also needs to prevent a supply chain adversary from constructing an alternative FIFO. This is achieved by obfuscating the interconnects. In some embodiments, a module encrypts a message based on its signature. To prevent a supply chain adversary from invoking this module and encrypting a Trojan message to transmit, this signature generation and encryption module and the caller of this module need to be implemented at least partially in

reconfigurable logic.

[0045] In some other embodiments, every network transmit packet originating from a mission-critical computer is re-encrypted to prevent a network back door Trojan from leaking confidential information. Every network transmit is a DMA (direct memory access). All the data in memory are encrypted. All the data are re-encrypted during transmission. The receiver decrypts the data based on his private key. This is based on a re-encryption obfuscation scheme, such that a supply chain adversary has no knowledge on the sender's key and the receiver's key. A network back door Trojan without the sender's key and the receiver's key cannot send messages through the re-encryption module. If a Trojan sends a plaintext message to the network, the re-encryption module outputs corrupted data. To prevent a Trojan from inserting a Trojan message at the re-encryption module output, one needs to include the logic networks around the re-encryption module output in an embedded reconfigurable logic module.

[0046] While the present invention is effective in detecting or resisting supply chain attacks, it is further applicable to detect or resist other security attacks. Examples of such application include attestation of trusted computing and resistance to malware and spyware intrusion. [0047] Further modifications and alternative embodiments of various aspects of the invention will be apparent to those skilled in the art in view of this description. Accordingly, this description is to be construed as illustrative only and is for the purpose of teaching those skilled in the art the general manner of carrying out the invention. It is to be understood that the forms of the invention shown and described herein are to be taken as examples of embodiments. Elements and materials may be substituted for those illustrated and described herein, parts and processes may be reversed, and certain features of the invention may be utilized independently, all as would be apparent to one skilled in the art after having the benefit of this description of the invention. Changes may be made in the elements described herein without departing from the spirit and scope of the invention as described in the following claims.

[0048] In this patent, certain U.S. patents, U.S. patent applications, and/or other materials (e.g., articles) have been incorporated by reference. The text of such U.S. patents, U.S. patent applications, and other materials is, however, only incorporated by reference to the extent that no conflict exists between such text and the other statements and drawings set forth herein. In the event of such conflict, then any such conflicting text in such incorporated by reference U.S. patents, U.S. patent applications, and other materials is specifically not incorporated by reference in this patent.