A security model for randomization-based protected caches

Cache side-channel attacks allow adversaries to learn sensitive information about co-running processes by using only access latency measures and cache contention. This vulnerability has been shown to lead to several microarchitectural attacks. As a promising solution, recent work proposes Randomization-based Protected Caches (RPCs). RPCs randomize cache addresses, changing keys periodically so as to avoid long-term leakage. Unfortunately, recent attacks have called the security of state-of-the-art RPCs into question. In this work, we tackle the problem of formally defining and analyzing the security properties of RPCs. We first give security definitions against access-based cache sidechannel attacks that capture security against known attacks such as Prime+Probe and Evict+Probe. Then, using these definitions, we obtain results that allow to guarantee security by adequately choosing the rekeying period, the key generation algorithm and the cache randomizer, thus providing security proofs for RPCs under certain assumptions.This research was supported by the European Union Regional Development Fund withinthe framework of the ERDF Operational Program of Catalonia 2014-2020 with a grant of50% of the total cost eligible, under the DRAC project [001-P-001723], and by the SpanishGovernment, under the CONSENT project [RTI2018-095094-B-C21]. Carles Hernándezis partially supported by Spanish Ministry of Science, Innovation and Universities under“Ramón y Cajal”, fellowship No. RYC2020-030685-I. Vatistas Kostalabros is partiallysupported by the Agency for Management of University and Research Grants (AGAUR) ofthe Government of Catalonia, under “Ajuts per a la contractació de personal investigadornovell”, fellowship No. 2019FI B01274. Miquel Moretó is partially supported by theSpanish Ministry of Economy, Industry and Competitiveness under “Ramón y Cajal”,fellowship No. RYC-2016-21104.Peer ReviewedPostprint (published version