Private Circuits: Securing Hardwareagainst Probing AttacksYuval Ishai1, Amit Sahai2, and David Wagner31Technion — Israel Institute of Technology,[email protected] University, [email protected] of California, Berkeley, [email protected]. Can you guarantee secrecy even if an adversary can eavesdrop on yourbrain? We consider the problem of protecting privacy in circuits, when facedwith an adversary that can access a bounded number of wires in the circuit. Thisquestion is motivated by side channel attacks, which allow an adversary to gainpartial access to the inner workings of hardware. Recent work has shown that sidechannel attacks pose a serious threat to cryptosystems implemented in embeddeddevices. In this paper, we develop theoretical foundations for security againstside channels. In particular, we propose several efficient techniques for buildingprivate circuits resisting this type of attacks. We initiate a systematic study of thecomplexity of such private circuits, and in contrast to most prior work in this areaprovide a formal threat model and give proofs of security for our constructions.Keywords: cryptanalysis, side channel attacks, provable security, secure multi-partycomputation, circuit complexity.1 IntroductionThis paper concerns the following fascinating question: Is it possible to maintain se-crecy even if an adversary can eavesdrop on your brain? A bit more precisely, can weguarantee privacy when one of the basic assumptions of cryptography breaks down,namely, when the adversary can gain access to the insides of the hardware that is mak-ing use of our secrets? We formalize this question in terms of protecting privacy incircuits, where an adversary can access a bounded number of wires in the circuit. Weinitiate the study of this problem and present several efficient techniques for achiev-ing this new type of privacy. Before describing the model and our contribution in moredetail, we motivate the problem by providing some necessary background.1.1 BackgroundOur understanding of cryptography has made tremendous strides in the past three de-cades, fueled in large part by the success of analysis- and proof-driven design. Mostsuch work has analyzed algorithms, not implementations: typically one thinks of acryptosystem as a black box implementing some mathematical function and implicitlyassumes the implementation faithfully outputs what the function would (and nothingelse). However, in practice implementations are not always a true black box: partialinformation about internal computations can be leaked (either directly or through side-channels), and this may put security at risk.?Work done in part while at Princeton University.This difference between implementations and algorithms has led to successful at-tacks on many cryptographic implementations, even where the underlying algorithmwas quite sound. For instance, the power consumed during an encryption operation orthe time it takes for the operation to complete can leak information about intermediatevalues during the computation [26, 27], and this has led to practical attacks on smart-cards. Electromagnetic radiation [34, 17, 35], compromising emanations [37], crosstalkonto the power line [38, 36], return signals obtained by illuminating electronic equip-ment [3, 36], magnetic fields [33], cache hit ratios [25, 31], and even sounds given offby rotor machines [24] can similarly give the attacker a window of visibility on internalvalues calculated during the computation. Also of interest is the probing attack, wherethe attacker places a metal needle on a wire of interest and reads off the value carriedalong that wire during the smartcard’s computation [2]. In general, side channel attackshave proven to be a significant threat to the security of embedded devices.The failure of proof-driven cryptography to anticipate these risks comes from an im-plicit assumption in many4currently accepted definitions in theoretical cryptography,namely, the secrecy assumption. The secrecy assumption states that legitimate partic-ipants in a cryptographic computation can keep intermediate values and key materialsecret during a local computation. For instance, by modeling a chosen-plaintext attackon the encryption scheme E as an algorithm AEkwith oracle access to Ek, we implic-itly assume that the device implementing Ekoutputs only Ek(x) on input x, and doesnot leak anything else about the computation of Ek(x). Thus the ‘Standard Model’ intheoretical cryptography often takes the secrecy assumption for granted, but as we haveseen, there are a bevy of ways that the secrecy assumption can fail in real systems.One possible reaction is to study implementation techniques that ensure the secrecyassumption will always hold. For instance, we can consider adding large capacitorsto hide the power consumption, switch to dual-rail logic so that power consumptionwill be independent of the data, shield the device in a tamper-resistant Faraday cage toprevent information leakage through RF emanations, and so on. Many such hardwarecountermeasures have been proposed in the literature. However, a limitation of suchapproaches is that, generally speaking, each such countermeasure must be speciallytailored for the set of side channels it is intended to defeat, and one can only plan adefense if one knows in advance what side channels an attacker might try to exploit.Consequently, if the designer cannot predict all possible ways in which informationmight leak, hardware countermeasures cannot be counted on to defend reliably againstside channel attacks.This leaves reason to be concerned that hardware countermeasures may not beenough on their own to guarantee security. If the attacker discovers a new class ofside channel attacks not anticipated by the system designer, all bets are off. Given thewide variety of side channel attacks that have been discovered up till now, this seemslike a significant risk: As a general rule of thumb, wherever three or four such vulner-abilities are known, it would be prudent to assume that there may be another, similarbut unknown vulnerability lurking in the wings waiting to be discovered. In particular,it is hard to predict what other types of side channel pitfalls might be discovered in the4This implicit assumption is definitely not universal. For instance, the field of secure multi-partycomputation asks for security even when some parties can be corrupted or observed.future, and as a