Reverse Engineer THIS! Towards Provable Cryptographic Protection for Circuit IP

Look around you, and it is likely you’ll see at least a dozen things that include computing “chips”: laptops, monitors, smartphones, printers, TVs, and the cables that connect them; toys, washing machines, and “smart” devices of all varieties; not to mention cars, medical devices, and industrial systems. Behind each chip is a massive global supply chain that, roughly speaking, begins with an integrated-circuit (IC) design firm, and ends with the fabrication of the design into physical chips, which are then integrated into products and larger systems.

Because the cost of building a fabrication plant can run into the billions, most design firms operate in a so-called “fabless” model, in which they entrust their designs—think of these as complete descriptions of the gates and interconnecting wires that implement a given set of functionalities—to an external, and not necessarily trusted foundry. There isn’t a lot of choice when it comes to which foundry, either: In 2018, ten foundries accounted for more than 95% of all production. As you can imagine, design firms are not excited by the prospect of handing over their hard-earned intellectual property in plaintext form to a party they may not trust. And with good reason: IP theft is estimated to cost the IC-design industry more than $100B, annually. Theft not only undermines competitiveness, but also opens the door to the production of counterfeit or out-of-spec chips, or even maliciously altered chips carrying hidden hardware trojans.  

If delivering the circuit design in plaintext form is the root of the problem, then why not encrypt the design before sending it to the foundry? Modern encryption algorithms are meant to transform their plaintext input into ciphertext output that, to every plausible attacker, is indistinguishable from a sequence of random bytes. In this way, they hide everything about the content and structure of the plaintext input. But a sequence of random bytes is not something that a foundry can fabricate into a chip! The foundry could recover a fabricatable circuit—namely, the original design—if it held the encryption secret needed to decrypt the ciphertext, but that just returns us to the current state of affairs.

An alternative approach is “split-manufacturing,” that is: sending, say, just the layout of the gates to one foundry, without the number and positions of the wires that connect them. Then having a second, trusted foundry “insert” the wires into the partially fabricated chip. There are a number of real-world criticisms of this approach, the simplest being: if you have a trusted foundry at your disposal, why not just use them for the whole job? Note that the design firm cannot play the role of the second foundry, itself, because they lack the expensive infrastructure to do so. At best, circuit designers can perform simple operations upon the chips that are returned from the foundry, e.g., burning a (relatively) small amount of information into on-chip lookup tables, which are themselves subcircuits of the larger design.

The Design-Hiding Problem

So, assuming that a single foundry does the fabrication, how might a design house protect its IP? This is the design-hiding (DH) problem. At a high-level, a solution to the DH problem would cryptographically transform a description of an original circuit into another valid circuit—which we’ll call an opaque circuit—where seeing the latter circuit (only) does not make it easy to see what was the original circuit that produced it. Intuitively, despite having full view of the gates and wires of the opaque circuit, an untrusted foundry shouldn’t be able to reverse engineer a circuit that computes the original functionality. A bit more precisely, seeing the opaque circuit shouldn’t significantly increase the foundry’s ability to do this, over what it could have done before seeing the opaque circuit. On its own, this intuitive security goal isn’t too hard to achieve. But what happens when the foundry fabricates the opaque circuit into chips, and returns these to the design firm? By construction, these chips will not compute what the original chip was designed to compute. The designers must be able to restore the opaque chips to have the original functionality, and only by making simple modifications to the chip.  

In a sense: the opaque circuit needs to be “far enough” away from the original circuit in order to thwart reverse engineering of the original design and functionality, yet “close enough” to the original circuit so that it can be restored to the original functionality via simple operations on the chip.  

Note that only the design firm should be able to restore the opaque chips to the intended functionality. As such, there must be some secret quantity (i.e., a cryptographic key) that is associated with the transformation of the original circuit into an opaque circuit, and only known to the design firm. 

Building DH Schemes Requires Proper Foundations

Between 2008 and 2021, many potential solutions to the DH problem appeared in the hardware security literature. They were efficient in terms of power, performance, and area overhead… but all shown to be vulnerable to attacks. In large part, these attacks recovered the secret keys used to create the opaque circuit. With the secret key, the foundry can mimic what the design firm would do to restore the opaque chip; hence, perfectly “reverse engineer” the original circuit functionality.  

Why did things end up this way, particularly after 25+ years of cryptography research that successfully addressed a wide variety of problems that were no less challenging than the DH one? The simple answer is that the hardware security community had never taken the first, and most important step in the modern cryptographic approach: precisely define what a valid DH scheme is, and what a secure DH scheme must achieve. We call this “formalizing the problem.”

The syntax: what is a DH scheme? The first piece of the formalization lets you look at a candidate solution and decide whether or not it is worth further consideration. For example, an encryption scheme could be used to hide a circuit design, but we’ve already seen that it is a non-solution because it fails to check crucial operational boxes. So an encryption scheme, while it does give a way to hide a circuit design (by transforming its description into a cryptographically strong ciphertext), it does not give us a valid DH scheme. We call this first piece of formalization the syntax of a DH scheme. The syntax is spiritually akin to an API, in that it tells you (abstractly) what are the algorithms that must be realized, along with their input and output types, and how these algorithms should interact in order to operate correctly under honest use. Loosely speaking, a DH scheme consists of two named algorithms that correspond to the two actions that the design firm must take: Hide the circuit design, and Restore the chip returned from the foundry.¹ Intuitively, a correctly operating DH scheme is one for which the following abstract “workflow” always holds. If you hand the opaque circuit produced by Hide to the foundry, and it honestly fabricates a chip for this circuit, then executing Restore on the chip and the secret key (used in Hide) will always result in a chip whose input-output behavior is precisely that described by the original circuit.

The security notion: what protections do we want? The second piece of the formalization effort asks us to establish a security notion for (valid) DH schemes to target. A security notion captures two things: the security goal with respect to which we want to measure attacks (the “adversarial goal”), and a model of the environment(s) in which the DH scheme is deployed and attacks are mounted (the “attack model”). The lack of a proper security notion is what hamstrung all of those efficient-yet-insecure efforts from prior work. None had actually defined what sorts of reverse-engineering attacks were in-scope, nor even what it meant for a reverse-engineering attack to be successful. Because the published attacks on early schemes were able to extract the secret hiding-key, researchers de facto adopted “inability to efficiently recover the key” as the definition of successful reverse engineering.² But really what one wants is to be able to say “no efficient attack admitted by the attack model can reverse-engineer the original circuit’s functionality with probability much better than what you’d get by making an educated guess.” That statement still includes a lot of hand-waving that needs to be properly defined; most importantly, we still haven’t said what it means to reverse-engineer something.  

In 2022, Animesh Chhotaray and I (hereafter, CS’22) formalized a syntax and security notion that captured what hardware-security researchers had been trying to achieve: how to prevent a well-resourced adversary from producing a circuit whose input-output behavior is identical to the original circuit. Moreover, the focus of prior work had been narrowed to considering stateless circuits with a single bit of output. So we targeted this class of circuits, too. After all, if you can’t show that reverse-engineering attacks are preventable for these simple sorts of circuits, then you certainly can’t hope to show it for more sophisticated ones. 

With the formal foundations put in place, we gave a conceptually simple DH scheme, and mathematically proved that this “OneChaff” scheme can protect (stateless, single-bit output) circuits from having their (entire) functionality reverse-engineered.

So, is the DH Problem “Solved”? 

Not even close. The problem that Animesh and I solved, the one that the hardware security community had been chasing, is too narrowly scoped to be of much practical use. For one thing, most modern circuits have multiple bits of output, and include sequential logic (i.e., state). At the moment, no formal foundations have been set for these, and this prevents the development of provably secure schemes for such circuits. For another, the definition of successful reverse-engineering in our paper requires the attacker to recover a description of the full input-output behavior of the original circuit. 

Let’s say that you have a circuit with 80-bits of input. Would you be happy if the adversary could recover the input-output behavior on 2^{80}-1 of the possible inputs? Realistic notions of reverse-engineering need to be explored, and new DH schemes developed that can be proved to achieve them.  

Working with existing workflows

In a different direction, there are interesting and significant challenges posed when considering how to implement the “OneChaff” scheme from CS’22 in realistic workflows. We said that this scheme is conceptually simple, and that’s true. Imagine that you had the entire input-output table in front of you, and that you could ask a modern electronic design automation (EDA) tool to produce a circuit from this table. To implement OneChaff, you’d randomly pick, say, 1024 of the inputs listed in this table, and flip the corresponding output-bit value. At its core, that’s the Hide algorithm of OneChaff. But for interesting circuits, you’re likely to have more than 40-bits of input, meaning you’d have a table listing a trillion input-output pairs. But no one designs circuits that way; instead, they design them in high-level specification languages (e.g., VHDL) that, effectively, give a compact way to describe (implicitly) all of those pairs. 

The obvious way to affect the same flipping of 1024 output values would be to augment the high-level code for the original circuit C with a block of conditional logic that tests whether the input is in the identified set and, if so, flip the output of the circuit. Let’s call the corresponding new circuit C’. So far, so good. But if you were to put the code for C into the EDA tool, and separately put the code for C’ into the EDA tool, it is unclear how different would be the resulting gate-and-wire layouts for the two. In particular, the EDA tool is designed to produce circuits optimized for power consumption, silicon wafer area, and runtime performance. It seems reasonable that the optimized circuit for C’ will look very much like the optimized circuit for C, since the difference between the two is a simple block of conditional logic. If that’s the case, then the foundry may be able to identify the subcircuit corresponding to the conditional logic and strip it out, thereby obtaining the optimized circuit for C. Whether or not this is the case needs exploring; in general, how to implement something like OneChaff “pre-EDA” is an open question. Even less clear is how you would implement something like OneChaff “post-EDA,” that is, on circuits that design houses have already run through the standard design workflow.  The latter is likely what one would want for (more) rapid integration into current workflows; ultimately, we’d like to see DH functionalities be built into EDA tools.

A “unicorn” research opportunity

This post only scratches the surface of what we already know needs to be tackled. Generalizing the existing formal foundations to address circuits with many bits of output and sequential logic, developing secure DH schemes for these settings, assessing the circuit overhead they impose and updating schemes accordingly, shaping DH schemes to fit realistic workflows... Reaching the point of “problem solved” in any of these directions will require many person-years of sustained effort. The return on that investment is potentially huge: Practical, scalable DH solutions would plug a known security hole in a multi-hundred-billion dollar industry of critical importance to national defense, strategic innovation, and commercial product development..

The DH space is a unicorn opportunity for researchers: it is wide open, and full of low-hanging fruits that are opportunities for significant progress; it has interesting challenges to address, both in theory and in practice; it is driven by real and substantial concerns from an industry that is crucial to modern life; and very few researchers already occupy the space. What more could we want?!  It’s time to roll up our collective sleeves, and see where the work takes us.   

‍

Footnotes

1 Note that the Hide-algorithm operates on the description of a circuit, whereas the Restore-algorithm operates on a chip. These are the sorts of subtleties that are surfaced in the process of establishing good syntax.

2 In fact, because one particular attack —the so-called “SAT attack” [SRM’15]— managed to recover the keys used by all of the then-published schemes, some papers took SAT-attack-resistance as the definition of security.