Private Circuits II:Keeping Secrets in Tamperable CircuitsYuval Ishai?, Manoj Prabhakaran??, Amit Sahai? ? ?, and David Wagner†Abstract. Motivated by the problem of protecting cryptographic hard-ware, we continue the investigation of private circuits initiated in [16]. Inthis work, our aim is to construct circuits that should protect the secrecyof their internal state against an adversary who may mo dify the valuesof an unbounded number of wires, anywhere in the circuit. In contrast,all previous works on protecting cryptographic hardware relied on anassumption that some portion of the circuit must remain completely freefrom tampering.We obtain the first feasibility results for such private circuits. Our mainresult is an efficient transformation of a circuit C, realizing an arbi-trary (reactive) functionality, into a private circuit C0realizing the samefunctionality. The transformed circuit can successfully detect any serioustamp ering and erase all data in the memory. In terms of the informationavailable to the adversary, even in the presence of an unbounded numberof adaptive wire faults, the circuit C0emulates a black-box access to C.1 IntroductionCan you keep a secret when your brain is being tampered with? In this paper westudy the seemingly paradoxical problem of constructing a circuit such that allparts of the circuit are open to tampering at the level of logic gates and wires,and yet the circuit can maintain the secrec y of contents of memory. We constructprivate circuits which, even as they are being tampered with, can detect suchtampering and, if necessary, “self-destruct” to prevent leaking their secrets. Weconsider security against a powerful inquisitor who may adaptively query thecircuit while tampering with an arbitrary subset of wires within the circuit,including the part of the circuit that is designed to detect tampering.The above question is motivated by the goal of designing secure cryptographichardware. While the traditional focus of cryptography is on analyzing algorithms,in recent years there have been growing concerns about physical attacks thatexploit the implementations (rather than the functionality) of cryptographic?Technion. This research was supported by grant 2004361 from the United States-Israel Binational Science Foundation (BSF) and grant 36/03 from the Israel ScienceFoundation.??U.I.U.C.? ? ?U.C.L.A. This research was supported by grants from the NSF ITR and Cybertrustprograms, a grant from BSF, an Alfred P. Sloan Foundation Fellowship, and a gen-erous equipment grant from Intel.†U.C. Berkeley.2 Yuval Ishai, Manoj Prabhakaran, Amit Sahai, and David Wagnerprimitives. For instance, it is in some cases possible to learn the secret key ofan encryption scheme by measuring the power consumed during an encryptionoperation or the time it takes for the operation to complete [19, 20]. Other typesof physical attacks rely on inducing faults [6, 5, 20], electromagnetic radiation[28, 11, 29], magnetic fields [27], cache hit ratios [18, 24], probing wires using ametal needle [1], and others [17, 31, 32, 30, 2, 30]. In general, attacks of this typehave proven to be a significant threat to the practical security of embeddedcryptographic devices.One possible approach for defeating the above type of attacks is by design-ing specific hardware countermeasures, such as adding large capacitors to hidethe power consumption. Many such countermeasures have been prop os ed in theliterature. An inherent limitation of these approaches is that each such counter-measure must be specially tailored for the set of specific p hysical attacks it isintended to defeat. For example, one might design physical protection againstattacks based on e lec tro-magnetic radiation, but still be vulnerable to attacksbased on physical probes.A different approach is to tackle the problem at the logical level, namely bydesigning algorithms that, when implemented, will be robust against a wide classof physical attacks. Here, we would want to classify attacks not based on thephysical mechanism of the attack, but rather on the logical effect of the attack –for instance, can we defend against all physical attacks that toggle the value ona wire? Several ad-hoc approaches have b ee n suggested (e.g., [10, 21, 15]) withsome subsequently broken [7, 9]. Recently, a more general and theoretically soundstudy of physical security has been initiated in [16, 22, 12] (see Section 1.4 for anaccount of this related work).The current paper continues this line of work, but departs from all previouswork in the following fundamental way. All types of attacks that were previouslyconsidered from a theoretical perspective are either (1) in some sense spatiallylimited, and in particular cannot be applied to the entire circuitry on whichthey are mounted [12]; or (2) deal with observation rather than faults [16, 22].The question that motivates our work is the intriguing possibility of offeringprotection even against adversaries that can tamper with the entire circuit. Thisgoal might sound too ambitious. For instance, the adversary can easily modifythe functionality of the circuit by simply destroying it completely. However, thisdoes not rule out the possibility of preventing the adversary from learning thesecret information, say a cryptographic key, stored in the circuit. Once the deviceis already in the hands of the adversary, secrecy is the primary relevant concern.The above question is captured by our notion of a private circuit, which wealso call a self-destructing circuit. Informally, such a circuit should carry outsome specified functionality (say, encryption) while protecting the secrecy of itsinternal state (a key) even against an unbounded number of adversarial faults.A natural way for achieving this goal is to build a tamper detection mechanismwhich can detect faults and trigger a “self-destruction” mechanism to erase allinternal state. (This is akin to a prisoner of war taking a suicide pill.) Thecentral problem with implementing this approach in our setting is that such atamper detection circuitry as well as the self-destruction mechanism itself can bePrivate Circuits II: Keeping Secrets in Tamperable Circuits 3attacked and disabled by the adversary. Thus, it is tempting to conjecture thatsuch self-destructing circuits simply cannot exist.In this paper, we obtain the first positive results establishing the feasibilityof private circuits in the prese nce of adversarial faults that can affect any