Transcription
CaSA: End-to-end Quantitative Security Analysis ofRandomly Mapped CachesThomas Bourgeat , Jules Drean , Yuheng Yang† , Lillian Tsai, Joel Emer‡ , Mengjia YanMIT CSAIL, † MIT/University of Chinese Academy of Sciences, ‡ gjiay}@mit.edu Authors contributed equally to this work.Abstract—It is well known that there are micro-architecturalvulnerabilities that enable an attacker to use caches to exfiltratesecrets from a victim. These vulnerabilities exploit the fact thatthe attacker can detect cache lines that were accessed by thevictim. Therefore, architects have looked at different forms ofrandomization to thwart the attacker’s ability to communicateusing the cache. The security analysis of those randomly mappedcaches is based upon the increased difficulty for the attacker todetermine the addresses that touch the same cache line that thevictim has accessed.In this paper, we show that the analyses used to evaluate thoseschemes were incomplete in various ways. For example, they wereincomplete because they only focused on one of the steps used inthe exfiltration of secrets. Specifically, the step that the attackeruses to determine the set of addresses that can monitor thecache lines used by the transmitter address. Instead, we broadenthe analysis of micro-architecture side channels by providing anoverall view of the communication process. This allows us toidentify the existence of other communication steps that can alsoaffect the security of randomly mapped caches, but have beenignored by prior work.We design an analysis framework, CaSA, to comprehensivelyand quantitatively analyze the security of these randomly mappedcaches. We comprehensively consider the end-to-end communication steps and study the statistical relationship betweendifferent steps. In addition, to perform quantitative analysis, weleverage the concepts from the field of telecommunications toformulate the security analysis into a statistical problem. Weuse CaSA to evaluate a wide range of attack strategies andcache configurations. Our result shows that the randomizationmechanisms used in the state-of-the-art randomly mapped cachesare insecure.Index Terms—Micro-architecture side channel, randomlymapped cache, security analysis.I. I NTRODUCTIONThe class of attacks that exploit micro-architectural vulnerabilities to breach processor security, generally referredto as side-channel attacks, have become a serious securitythreat. Using these attacks, an attacker can steal secrets from avictim application running on the same machine by monitoringthe side effects of the victim’s actions on various microarchitectural states. Such attacks are effective and have beenused to leak encryption keys [1], [2]. Many of these attacksemploy speculative execution to modify cache states [3]–[5] tocompletely bypass memory isolation and leak arbitrary data.As described in [6], there is a series of elements commonto most attacks that exploit micro-architectural vulnerabilities.These include either pre-existing or attacker-generated code runin the victim’s security domain that 1) accesses secret information and 2) transmits that information over a communicationchannel that 3) is received by an attacker. The signal receivedby the receiver leaks a secret that was supposed to stay withinthe victim’s security domain.Focusing just on the communication phase of an attack,the transmitter is in the victim’s code, and the receiver isin the attacker’s code. The medium of the communicationchannel is the micro-architectural state that can be modified, i.e.,modulated, by the activity of the transmitter. A communicationchannel may actually be composed of multiple subchannels,just as a radio transmission may use multiple frequencies.For numerous contemporary attacks, the communicationmedium is the last-level cache, and each cache line can beconsidered a communication subchannel. In the simple case ofa directly mapped cache, modulating a subchannel involves thetransmitter accessing a specific address, since that will changethe state of exactly one well-defined cache line. A receivercan monitor the state of the same cache line (subchannel) forchanges (modulation) by accessing an address to occupy thatcache line (subchannel) and, at a later time, measure the latencyof a re-access to the same address to determine whether it is ahit or miss.For a more complex cache, such as a set-associative cache,the receiver needs to use multiple addresses to monitor thecache set that will be used by the transmitter, i.e, multiplesubchannels. In other cases, the transmitter might also usemultiple addresses, i.e., modulating multiple subchannels. Thesesets of addresses accessed by the transmitter and receiverare referred to as the transmitter set and the receiver setrespectively. The attacker generates a receiver set by using aso-called eviction set construction algorithm [7], [8]. Later wegeneralize this operation as the process of receiver calibration.Randomly Mapped Caches. Among various architecturalsolutions that address security vulnerabilities by disruptingcommunication via cache-based channels, randomly mappedcaches [9]–[12] are considered highly effective with plausiblesecurity properties and low performance overhead. Randomlymapped caches aim to significantly increase an attacker’s effortsto find a receiver set that monitors all the possible subchannelsthat might be modulated by the transmitter. They leverage oneof the two ideas: make cache behavior non-deterministic byintroducing some randomness into the functions used to mapmemory addresses to cache lines (subchannels) [10], [11], and
dynamically change these functions [9], [10], [12].In such complex caches, the subchannels that the transmitterwill modulate are not publicly known to attackers. Moreover,with non-deterministic caches, the attacker can only guess theprobability of an address to be mapped to a given cache line,and modulation can only be observed probabilistically. Thisuncertainty requires the attacker to use complex methods togenerate receiver addresses that have a high probability tomonitor the cache lines modulated by the transmitter.Unfortunately, the security claims of randomly mappedcaches are quite fragile. For example, a recent secure cachedesign, CEASER [9], which claimed to be able to tolerateyears of attack, has been broken by more advanced eviction setconstruction algorithms [7], [10]. Similarly, ScatterCache [11],another recently proposed randomly mapped cache design, canbe broken by a new eviction set construction algorithm [13]within a few seconds.The reason behind the failures of those designs lies in theirlimited security analyses. In fact, those defense mechanismswere designed to block very specific eviction set constructiontechniques. For instance, some weak security analyses [9]–[11], [13] only consider the case where the attacker tries toobtain a receiver set that monitor the subchannels used bythe transmitter with high probability. Such an analysis ignoresthe existence of alternative strategies where the attacker couldspend a modest amount of resources on constructing a receiverset that has a lower probability to monitor these subchannels.With such a weak receiver set, she would rely on repeatedlymonitoring the modulations from the transmitter to ultimatelyleak the secret.Communication Paradigm. In this paper, we introduce ageneralized communication paradigm for micro-architectureside channels. The paradigm serves two purposes. First, itprovides the overall view of the communication processand identifies the end-to-end communication steps that acomprehensive security analysis has to consider. Second, itenables us to think of micro-architecture side-channel attacksusing concepts from telecommunications, so we can formulatethe security analysis into a statistical problem and performquantitative ctedsignalsFig. 1: Communication paradigm.DecodeTo obtain the signal, the receiver needs to detect the statechanges of the channel caused by the transmitter. In cachebased side channels, the receiver can obtain the signal usingvarious approaches, such as Prime Probe [2]. The signal—made of cache hit and miss events—can then be formalizedmathematically and studied with statistics and probabilities.Finally, the receiver needs to perform a decode step tointerpret the detected signals. The decode step can be straightforward if the detected signal directly corresponds to thesecret value. In cache-based channels, this decode step canbe complicated if it needs to cope with noise, and nondeterministic behaviors of the cache.This Paper. We propose Cache Security Analyzer (CaSA) toquantitatively analyze the security of randomly mapped caches.We aim to use CaSA to comprehensively evaluate a wide rangeof communication strategies and cache configurations.The design of CaSA is built from three insights. First, insteadof solely focusing on the calibration step, CaSA performs anend-to-end analysis on the three communication steps in Fig. 1.Second, it leverages telecommunication concepts to formulatethe security analysis into a statistical problem and quantifythe security by measuring the end-to-end communication cost.Third, CaSA identifies the existence of a trade-off in distributingresources between the calibration step and the signaling step.It explores that trade-off to find the communication strategythat minimizes the overall communication cost.We use CaSA to evaluate randomly mapped caches ofdifferent configurations and discover the quantitative impacts ofdifferent parameters on the communication cost (Findings 1-4in Section VII). Furthermore, we have made new observationsto better understand the limitations and benefits of randomlymapped caches that refute several common beliefs. We highlighttwo takeaways here:1) When communicating on randomly mapped caches, spending the maximum amount of resources on calibration isneither the only nor always the best strategy. This refutes thecommon belief [11], [13] that an effective receiver set mustbe able to achieve a high eviction rate, i.e., that monitorsmost subchannels that the transmitter could modulate.2) In the case where dynamic changes in mapping functionsare used, information can be leaked and accumulated acrossmapping function changes. This refutes the common beliefthat attacks must be completed during the life of a singlemapping function [9], [10].The communication paradigm, shown in Fig. 1, consists ofWith those insights and quantitative results, we show thatthree steps: calibration, signaling and decode.the randomization mechanisms used in the state-of-the-artFirst, the receiver often needs to perform a calibration step.randomly mapped caches [9]–[11] (except for NewCache [12])Calibration is like a tuning process in a radio-based system,are insecure.and aims to determine which subchannels will be modulatedThe contributions of this paper are:by the transmitter, and where to tune the receiver to monitorthose subchannels. For a cache-based channel, the calibration A three-step, end-to-end communication paradigm expandingstep involves running an eviction set construction algorithm [7].the security analysis of cache-based side channels beyondPrior analyses [9]–[11], [13] have only focused on this step.just the calibration of the receiver.The second step is a signal transfer step (signaling for short) Formulating the security analysis into a statistical problemwhere the receiver obtains the signal from the transmitter.to enable quantitative analysis.
CaSA, a comprehensive and quantitative security analysisframework of side-channel communication via randomlymapped caches.A thorough security evaluation and new observations tounderstand the limitations and benefits of randomly mappedcaches.II. BACKGROUNDA. Cache-based Side Channel Attacksit harder for a receiver to know which subchannels willbe modulated by a transmitter, and which subchannels arepreconditioned or monitored by the receiver. It aims to mitigatecache attacks by significantly increasing the difficulty of thereceiver’s calibration step.There are various flavors of randomly mapped cache designs [9]–[12], each with different performance and securitycharacteristics. To better understand their differences, wedistinguish these designs based on three characteristics of themapping function, namely whether:In a cache-based side channel attack, the transmitter and thereceiver use the cache as the communication channel, and each 1) It uses public or secret hash functions;cache line as a subchannel. Various such attacks exist [1], [8], 2) It is static or can be dynamically changed over time;[14]–[25], and follow the procedure described in Fig. 1.3) It uses a single or multiple hash functions at a point inIn each attack, the receiver first performs a calibration steptime.by finding a group of addresses called receiver addresses.Table I categorizes each design by mapping strategy.The receiver uses the receiver addresses to monitor a set ofStaticDynamicsubchannels, usually a cache set. Next, the receiver performs the SingleSet-associativecacheCEASER[9]signaling step, which consists of two substeps: precondition andHash GroupIntel sliced LLC [26]NewCache [12]detection. The receiver preconditions a group of subchannelsMultipleScatterCache [11]Skewed-CEASER [10]into a known state in order to optimize its chances of monitoringHash Groupsstate changes in these subchannels. The precondition generally TABLE I: Classification of cache mapping strategies. Usesinvolves accessing the receiver addresses to fill a cache set. It public hash functions.waits for the transmitter to modulate some of the monitoredsubchannels by accessing some cache lines. It then detects the 1) Public vs. Secret hash functions. Traditional set-associativemodulation of those subchannels by either measuring the time caches use a public hash function, which simply extractsof re-accessing the receiver addresses (Prime Probe [1], [8]), bits from the physical address and uses them as the setor measuring the time of accessing the transmitter addresses index. The other caches in Table I use secret hash functions.(Evict Reload [15]), or measuring the execution time of the For example, the last-level caches in Intel processors aretransmitter (Evict Time). Finally, it performs the decode step organized into multiple slices. The mapping function includesan undocumented slice hash function to decide which slice anbased on the measurement result.address should map to. NewCache [12] uses a table-based hashtimefunction. CEASER [9] and ScatterCache [11] use encryptionbased hash functions.set0 abax evictaxinsertEven though using a secret mapping function could beset1bthought to make calibration more difficult, it alone cannotbthwart cache attacks. It has been demonstrated that theret1: Primet2: Waitt3: Probeexist efficient algorithms for attackers to reverse engineer theFig. 2: An example of Prime Probe attacks. Line a and b are hash function [27], [28] or even to directly construct effectivereceiver addresses; line x is the transmitter address.receiver sets [7], [10] without needing to know anything aboutFig. 2 visualizes an example of using Prime Probe as the the mapping function.signaling strategy on a two-way cache, which contains three 2) Static v.s. Dynamic hash functions. To further secure thesteps: Prime, Wait, and Probe. The receiver preconditions two cache, researchers proposed to periodically change the hashsubchannels in set0 by accessing lines a and b (Prime). It then function instead of using a static hash function. A cache withwaits for the transmitter to modulate a subchannel in set0 by a dynamic mapping function uses one hash function in eachaccessing line x, which evicts line b from that subchannel epoch, and switches to a different hash function at the end of(Wait). At a later time, the receiver checks the state of the an epoch.The length of an epoch has a significant impact on thesubchannels in set0 by re-accessing lines a and b, and measuringthe access latency (Probe). Based on the long access latency, performance and security of the design. To be secure, the epochthe receiver knows that line b missed in the cache and the state should be short enough so that the receiver cannot both calibrateof a subchannel in set0 has been modified (modulated) by the and detect signals within one epoch. However, upon epochswitching, every line in the cache has to be remapped, andtransmitter.using small epochs thus incurs serious performance overhead.B. Randomly Mapped Cache DesignsNewCache [12] uses extremely small epochs—changing theThe mapping function in a cache decides how memory hash function every time a cache conflict occurs. CEASER [9]addresses are mapped to cache sets. Randomly mapped caches and Skewed-CEASER [10] change the hash function when theintroduce randomness into the mapping functions to make number of cache accesses reaches a threshold. The threshold is
configured to be smaller than the number of accesses required Scope. Our analysis focuses on investigating the fundamentalby the state-of-the-art eviction set construction algorithm [7]. problems in the randomization schemes used by randomlySkewed-CEASER [10] claims years of security when setting mapped caches. Prior work [30] has shown that the mappingthe threshold as 100 L, where L is the total number of lines function used in CEASER [9] and Skewed-CEASER [10] onlyin the cache.consists of linear functions and has a key invariant vulnerability,3) Single vs. Multiple hash functions. Researchers have pro- that is, changing the key used in the mapping function cannotposed more advanced secure cache designs, namely multi-hash change the collisions between addresses. This vulnerabilitycaches such as ScatterCache [11] and Skewed-CEASER [10], can be fixed using non-linear hash functions. Note that, ourwhich use multiple hash functions at any point in time. These analysis is independent of which hash function is used anddesigns contrast with single-hash caches, which only ever use studies new vulnerabilities that have not been explored in priorwork [30]. Indeed, we focus on analyzing the fundamentala single hash function.problem that is intrinsic to randomly mapped caches.addrBesides, we consider the analysis of the following two types fg-1f0f1of attacks orthogonal to the analysis of randomly mappedcaches: flush-based attacks [14], [18] and occupancy-basedattacks [31]. The reason is that randomly mapped caches arenot designed to and thus are unable to mitigate these attacks. Hence,we do not analyze such attacks in this paper.hashhashgroup 0hashgroup 1group g-1Fig. 3: A cache with multiple hash groups.IV. M OTIVATIONCorrectly reasoning about the security of randomly mappedAs shown in Fig. 3, a multi-hash cache is organized ascachesis challenging. Prior security analyses have mademultiple hash groups. Each hash group is organized as a normalincorrectsecurity claims by narrowly considering two communiset-associative cache, and uses a distinct hash function. To docationstrategiesby the attacker. We claim that a comprehensivea lookup in the cache, all the hash-groups are looked up, withsecurityanalysisshould provide an end-to-end quantitativeat most one of them being a cache hit. On a cache miss, theanalysisofabroadrange of communication strategies.cache first picks one of the hash groups using a uniformlyrandom policy and then uses the corresponding hash functionA. Limitations of Prior Workto generate the set index for that hash-group.Prior security analyses [10], [11], [13] only targeted specificAs a result, the mapping function becomes non-deterministic.An address can end up in different hash groups, i.e., modulating calibration strategies that require a huge amount of resourcesdifferent subchannels, even within one epoch. It significantly and are unlikely to be completed within one epoch. We use theincreases the attacker’s difficulty in obtaining a receiver set to following simple example in Fig. 4 to illustrate the limitationsmonitor all the subchannels that will be used by the transmitter. of their analyses. Fig. 4 compares the results of three differentScatterCache [11] uses a single-way per hash group design. calibration strategies on a cache with 2 hash groups and 1Skewed-CEASER [10] makes the number of ways per hash way in each group. Each figure shows hash group 0 on top,hash group 1 at the bottom, and how the transmitter andgroup a configurable parameter.receiver addresses are mapped to corresponding subchannels.Thesubchannels that can be used by the transmitter addressIII. T HREAT M ODEL AND S COPEare marked in grey.We follow the standard threat model of cross-core cachereceiver addresstransmitter addressbased side channel attacks. We assume the attacker and thehashhashhashvictim are co-located on the same processor chip, but residegroup 0group 0group 0set 0on different cores. A transmitter embedded in the victim and aset 1receiver controlled by the attacker communicate via channelsset 2in a shared last-level cache. Even though we focus on theset 3last-level cache, our analysis and our tool, CaSA, can be easilyhashhashhashgroup 1group 1group 1extended to other levels of the cache hierarchy.The attacker can reside in a user-level process or in amalicious operating system in a secure enclave context, such asSGX [29]. Like previous work [20], we assume the receiver canuse a single thread or multiple threads to control multiple cores(a)(b)(c)on the chip. The transmitter may be latent in the code of thevictim and execute as part of the victim’s normal processing, or Fig. 4: An illustrative example of different calibration strategies:the attacker can leverage speculative execution [3] to provoke (a) hard-conflict receiver addresses; (b) many soft-conflictreceiver addresses; (c) one soft-conflict receiver address.the execution of the transmitter.
The security analysis in Skewed-CEASER [10] only con- by accumulating 16 samples, the receiver can know if thesidered using “hard-conflict” receiver addresses for signaling. transmitter was accessed or not with 99% confidence, based onA “hard-conflict” receiver address maps to the same cache whether it detects modulations in at least one of the signalingset as the transmitter address in every hash group, shown in samples or it detects no modulations across all samples.Fig. 4(a). Their analysis only consider such addresses becauseAlternatively, the receiver could spend more resources ononce the attacker has enough hard-conflict addresses (2 in this calibration to obtain two receiver addresses instead of one. Inexample), she can perform the rest of the communication (e.g., this situation, she would only need to accumulate 7 samplesPrime Probe) in the same way as on a conventional cache. to decode the secret with the same level of confidence. TheRandomly mapped caches are designed to make it extremely examples above clearly demonstrate the existence of a trade-offdifficult to obtain hard-conflict addresses. In fact, for a given in distributing resources between calibration and signaling.transmitter address, when there are 8 or 16 hash groups, theremay not exist enough hard-conflict addresses given the limited B. The Need for Comprehensive and Quantitative Analysissize of the address space in the state-of-the-art systems [11].In addition to the trade-off between calibration and signalEven though a receiver set with hard-conflict addresses istransfer, we find it is necessary to perform a comprehensiveguaranteed to be functional, i.e., guarantee to monitor all theand quantitative analysis of randomly mapped caches, sincesubchannels that will be used by the transmitter, it is not thethere exist multiple other factors that can affect the security ofonly way to communicate on randomly mapped caches.these designs. We provide the intuitions of how these factorsThe security analysis in ScatterCache [11] considered usingcan affect communication on randomly mapped caches below.a large number of “soft-conflict” receiver addresses. A “softFirst, we need to consider the effects of having multipleconflict” receiver address maps to the same set as the transmittertransmitter addresses. Intuitively, having more transmitteraddress in at least one hash group, as shown in Fig. 4(b). Softaddresses can make communication easier, because the numconflict addresses are much easier to find than hard-conflictber of subchannels associated with the transmitter increasesaddresses but can only be used to monitor the transmitter withand the communication can work as long as the receiversome probability. The assumption behind their analysis is thatcan successfully monitor at least one modulation from thethe attacker needs to get a large receiver set (e.g., 256 addressestransmitter. Note that, in practice, multi-address transmitterson an 8MB LLC) in order to monitor the transmitter with 99%do occur in many security-sensitive applications. For example,probability. Crafting such a large receiver set is expensivethe square-and-multiply exponentiation algorithm used in RSAand unlikely to be completed within one epoch. Consequently,encryption [32] acts as a multi-address transmitter: both thestrong security claims were made under such assumptions.square and multiply functions are composed of instructionsThere exists a key problem with these analyses: theyresiding in multiple cache lines.overlooked a broad range of communication strategies thatSecond, we need to consider the effects of noise. Intuitively,are available to the attacker. In addition to the prior analysisthepresence of noise can make communication more difficult,where the receiver spends a huge amount of resources onbecausethe receiver often cannot distinguish the modulationscalibration to achieve a high monitoring probability, othergeneratedby the transmitter or by the noise. CaSA quantitaeffective communication strategies are also possible, such as,tivelymeasuresthe impacts of noise and we discovered a newusing a small amount of resources on calibration to obtainfindingthatnoisecan have a positive impact on communication.a receiver set with low monitoring probability, and relyingFinally,forcachesthat periodically change the mappingon repeating the signaling step to decode secrets with a highfunctions,weinvestigatethe feasibility of performing thesuccess rate. A comprehensive analysis should explore thecommunicationacrossepochs.Prior work assumed that commutrade-off in distributing resources between calibration andnicationmustcompletewithinone epoch and no is paper, we challenge thisFig. 4(c) shows an example of using 1 receiver addressassumption.Itistruethat,areceiverset constructed in anthat soft-conflicts with the transmitter on a single subchannel.epochcanonlybeusedforthesignalingsteps in the sameSuch a receiver set is fairly cheap to construct. In ts fromexample, the receiver has a probability of 0.5 to monitor tand misssubchannel and the transmitter also has a probability of 0.5 lsaremodulate that subchannel. As a result, when the inthereceiveraddress is accessed, the probability of the receiver observinga modulation is 0.5 0.5 0.25. When the transmitter is not sets. Intuitively, if the same secret bit is transmitted, the samplesaccessed, this probability is 0. Even though the probability obtained from different epochs can be combined to increaseto observe a modulation is low, the receiver can repeat the decoding accuracy.CaSA is designed to quantitatively analyze the impacts ofsignal transfer step to accumulate samples. Those samples aretheabove factors on the security of randomly mapped caches.then used to infer if the transmitter was accessed (observingSpecifically,CaSA can answer the following questions.some modulation) or not (observing no modulation). Thislast phase is the decoding step and increasing the number of Given a cache configuration, such as the one in Fig. 4, andsamples will increase the decode success rate. In our example,the number of transmitter addresses, how should a receiver
distribute resources between calibration and signal transferto exfiltrate the maximum amount of information?Considering background noise, how much more difficult isit for an attacker to mount a successful attack?Among different cache configurations (e.g., 1-way per hashgroup and 2-way per hash group), which one is moredifficult to attack, measured by the number of attacker’scache accesses to leak one secret bit?V. C A SA OVERVIEWThe goal of CaSA is to measure the security of different configurations of randomly mapped caches. We striveto comprehensively evaluate how various communicationparameters quantitatively affect the amount of informationleakage on a given cache configuration. To enable quantitativeanalysis, we innovatively leverage concepts from the fieldof telecommunications (Section I) and formulate the signalsin cache-based side channels into a statistical representation.In this section, we first describe the full security analysisspace, and then describe the statistical representation of signals,followed by the security metric used in CaSA.A. The Security Analysis SpaceThe paper strives to comprehensively evaluate the choicesavailable with respect to the three components used in cachebased side channel communication, i.e., transmitter, receiverand channel (i.e., cache), as well as parameters related to noise.Transmitter. An important parameter related to the transmitteris the number of transmitter addresses. We expect programdevelopers to set that sole transmitter parameter based ontheir knowledge of the applications or using program analysistools [33]–[35].Receiver. The receiver can c
Fig. 1: Communication paradigm. The communication paradigm, shown in Fig. 1, consists of three steps: calibration, signaling and decode. First, the receiver often needs to perform a calibration step. Calibration is like a tuning process in a radio-based system,
