title: CACHE SNIPER : Accurate timing control of cache evictions
authors: Samira Briongos Ida Bruhns Pedro Malagón Thomas Eisenbarth José M. Moya
text: 
  Uniformization of Riemann surfaces revisited
      Rareş Stan
      December 30, 2023
  ============================================
  
  
  
  
  
  
  Microarchitectural side channel attacks have been very prominent in security research over the last few years. Caches have been an outstanding covert channel, as they provide high resolution and generic cross-core leakage even with simple user-mode code execution privileges. To prevent these generic cross-core attacks, all major cryptographic libraries now provide countermeasures to hinder key extraction via cross-core cache attacks, for instance avoiding secret dependent access patterns and prefetching data.
  In this paper, we show that implementations protected by `good-enough' countermeasures aimed at preventing simple cache attacks are still vulnerable. 
  We present a novel attack that uses a special timing technique to determine when an encryption has started and then evict the data precisely at the desired instant. This new attack does not require special privileges nor explicit synchronization between the attacker and the victim. One key improvement of our attack is a method to evict data from the cache with a single memory access and in absence of shared memory by leveraging the transient capabilities of TSX and relying on the recently reverse-engineered L3 replacement policy. We demonstrate the efficiency by performing an asynchronous last level cache attack to extract an RSA key from the latest wolfSSL library, which has been especially adapted to avoid leaky access patterns, and by extracting an AES key from the  implementation included in OpenSSL bypassing the per round prefetch intended as a protection against cache attacks. 
  
  
  
  
  § INTRODUCTION
  
  
  Modern CPUs are highly optimized to achieve the maximum performance and efficiency for existing manufacturing technologies while ensuring logical correctness and isolation between processes. But since any running software interacts with the microarchitectural elements of the processor and  changes their state, shared hardware resources are influenced by all processes running on a machine. An attacker can leverage these shared resources to recover secret information from a victim software by exploiting the microarchitectural state <cit.>.
  
  Among the microarchitectural elements utilized in these attacks, the cache memory has probably been the most exploited hardware resource. Traditionally, cache side channel attacks have focused on cryptographic implementations. For instance, cache attacks have successfully retrieved ECDSA <cit.>, RSA <cit.> and AES <cit.> keys, even breaking the isolation between virtual machines (VMs) <cit.>. As these attacks do not require any special privileges to succeed, side channel attacks pose a great threat and keep gaining attention.
  
  As a direct response to the threat imposed by microarchitectural attacks, many different countermeasures were put in place. As described by Ge et al. <cit.>, preemptive countermeasures try to help in the hard task of designing leakage free code <cit.>, hardware countermeasures either design or take advantage of hardware features to avoid the leakage and detection based countermeasures try to determine whether there is an attack going on <cit.>. In this paper, we will focus on the preemptive countermeasures of side channel resistant code and prefetching. 
  
  Prefetching is used as a strategy to improve performance as well as preventing attackers from observing the cache state in cache attacks <cit.>. For example, a prefetching strategy was implemented in OpenSSL 1.0.0a and beyond: The  implementation prefetches the  before executing each round <cit.>. If the attacker flushes a line holding data from the  before or during the execution of any intermediate round, and waits till the encryption has been performed, she will only observe cache hits. Consequently, she would not be able to distinguish whether those access are due to the actual utilization of the line or to the prefetch stage <cit.>. 
  
  Several recent works have shown that in scenarios where the attacker controls the OS, even smallest leakages can be exploited. Many recent prominent works have either exploited the intra-core resource sharing of simultaneous multithreading (SMT) <cit.> or the ability of interrupted execution of SGX <cit.>. These attacks are so powerful that several cryptographic libraries, including OpenSSL, now ignore them: the cost of protecting against them is exuberant and arguably not justified in scenarios where attacker control of the OS is out of scope (or simply worse than the attacks). Thus, they make do with the imperfect but allegedly sufficient countermeasures of prefetching and leakage minimization described above.
  
  In this work, we show that even a classic user-lever cache adversary can overcome these countermeasures. At a very high level, the attacker has an offline stakeout phase where she determines the time elapsed between the start of the target algorithm and the use of the target function or data. In the online phase, she then detects the start of the target algorithm by the victim, waits for the time previously determined, and evicts the target data from the cache. The attacker can then collect valuable data to extract the key. Due to the high precision gained from the exact timing of the eviction, very small windows of opportunity can be leveraged. We demonstrate the attack on an OpenSSL AES implementation and a square and multiply implementation from wolfSSL. Both are considered protected from side channel attacks, but both have vulnerabilities that can be exploited by .  
  
  
  
    §.§.§ Contributions
  
  In summary, this paper presents the following contributions. 
  
  
    - We present , a methodology to evict data from the cache at the desired instant, even in the absence of shared memory, taking advantage of the replacement policy. 
  
    - We reduce the number of samples required to get a cryptographic key by precisely selecting the instant of time at which we desire to interrupt a victim process.
  
    - We demonstrate that prefetching data to the cache is not effective against cache attacks, if there is a window of time during the execution of a sensitive part of code, at which private data is not accessed uniformly.
  
    - We show in realistic experimental setups the feasibility of side channel last-level cache attacks against the AES  implementation that includes prefetching as countermeasure, and against an RSA implementation protected by a side channel resistant implementation.
  
  
  
  
    §.§.§ Disclosure and Code Publication
  
  We demonstrate our method by attacking two real world cryptographic implementations, an AES implementation by OpenSSL (version 1.0.2k) and an RSA square-and-multiply implementation by wolfSSL (version 4.4.0). We responsibly disclosed to both libraries on June 22nd and 23rd. The communication with the OpenSSL team is still ongoing. No CVE was issued since falls outside their threat model. Additionally, the implementation was removed entirely from the latest version of OpenSSL. wolfSSL immediately issued CVE-2020-15309 and proposed a fix for the vulnerability, which we checked and acknowledged. 
  
  
  
  
  § BACKGROUND
  
  This section introduces some basic concepts on cache memory, cache attacks and transactional execution that are of key importance in the efficiency of the proposed cache attack.
  
  
  
   §.§ Cache architecture
  
  
  Caches are small memories located between the processor and the main memory, specially designed to reduce the gap between processor and memory throughput. Modern processors include cache memories that are hierarchically organized; low level caches (L1 and L2) are core private, smaller and closer to the processor (with reduced latency), whereas the last level cache (LLC or L3) is bigger and shared among all the cores. Intel processors have traditionally included L3 inclusive caches, in order to simplify the implementation of cache coherence: all the data which is present in the private low-level caches has to be in the shared L3 cache.
  
  Most modern processors include w-way set-associative caches; a trade-off between directly mapped caches, usually with high cache miss rates, and fully associative caches, with a very complex logic. The cache is organized into multiple sets (s), each of them containing w lines of usually 64 bytes of data. The set in which each line is placed is derived from its address (directly mapped). The address bits are divided into offset (lowest-order bits used to locate data within a line), index (log_2(S) consecutive bits starting from the offset bits that address the set) and tag (remaining bits which identify if the data is cached). Many caches additionally contain slices. The entries are mapped to the slices by a function f, which usually depends on some fixed bits of the data. Slice selection mechanisms are usually not public, and effort has gone into reverse engineering them. The do however not have an impact on .
  
  
  
   §.§ Replacement policies
  
  
  At some point during the use of a set-associative cache, data will need to be loaded into the cache after a cache miss, but the corresponding cache set is full. At this point, an algorithm called the replacement policy decides which of the currently cached lines is evicted and replaced with the line accessed. As it is crucial for maximizing the hit ratio and achieving good performance, manufacturers do not publish the implementation details of the policy. Each cache level has it's own replacement policy. Based on the observations of the evictions in the LLC, most modern processors implement pseudo-LRU (Last Recently Used) policies.  Regarding Intel, the official name of the LLC replacement policy is “The Quad-Age LRU” <cit.>.
  
  There have been several efforts to reverse engineer the replacement policy of Intel processors in order to estimate/measure the number of misses, without explaining which concrete elements in the cache would be evicted in the event of a miss <cit.>. Later studies <cit.> have focused on eviction strategies related to maximize the number of evictions in order to improve memory attacks. Recently, the replacement policy of all the cache levels of modern Intel processors have been reverse engineered and published<cit.>.
  
  
  
   §.§ Transactional memory and Intel TSX
  
  
  Intel TSX is an instruction set extension for x86 that supports Transactional memory. Transactional memory enables optimistic execution of the transactional code regions specified by the programmer. The processor executes the specified sections assuming that there is no conflict with other threads or CPU cores, which might access or modify the same data. Transactional memory reduces the need of mutual exclusion mechanisms, using a local version of data and registering a hardware-based callback mechanism in case a conflict with other threads is detected. If the execution ends successfully, the processor commits all the changes as if they had occurred instantaneously, becoming visible to the remaining processes. Otherwise, the transaction is cancelled, all memory changes are discarded and a callback function is called. This process is known as an , and the callback is known as an . There are various reasons why a transaction may abort in Intel TSX, but we particularly focus on the cache related ones. Namely, a transaction aborts if data from its “write set” is evicted from the L1 cache or if data from its “read set” is evicted from the L3 cache  <cit.>. AMD provides similar transaction mechanisms and ARM is introducing it.
  
  
  
  
  
  
   §.§ Related work
  
  Cache memory was first mentioned as a covert channel in 1992 <cit.>. Since then, many different techniques have been developed: Kelsey entertained the idea of attacks based on cache hit ratios, Osvik et al. proposed the widely known  and  attacks, revealing the cache sets accessed by the victim, and Gullasch and Yarom and Falkner both developed a powerful attack that exploits shared memory, which they later named    <cit.>. From these attacks,  and  are widely used due to their high resolution. This work focuses on  and , a derivative of  that leverages transactional aborts to detect cache evictions caused by the victim process <cit.>.  
  
  
  The  technique requires shared memory, which means the victim and attacker use the same data during their respective execution. This can be met by them using the same library, which is often the case for libraries shipped with the operating system. In addition, a  instruction is needed on the target processor, which is not the case in many scenarios, e.g. when attacking from JavaScript <cit.>. The attacker uses this instruction to flush the desired lines from the cache, making sure the victim process needs to load them from memory to use them. She then reloads the data, measuring the time this takes. If the victim process used the data, the reload time observed by the attacker will be short. This attack is easy to implement and provides precise information about the data the victim process uses at cache-line granularity. 
  
  The  attack has been used in many ways since it was introduced. Gullasch et al. retrieved an AES key and Yarom et al.  demonstrated that one trace is enough to retrieve an RSA key, and attacked ECDSA  <cit.>.  is applicable to launch cross-VM-attacks, used for attacking AES, retrieve keystrokes or profile the victim <cit.>. 
  
  It is vital for  that the attacker and the victim share memory. The  attack still works in virtual environments <cit.>. An attacker can target the LLC cache, particularly one set of the LLC, and it will still able to extract sensitive information. Since  does not require special OS features, it can be applied on virtually any system. As a preparation step for a  attack, the attacker needs to construct an eviction set (a group of w different addresses that map to one specific set in w-way set-associative caches). Constructing eviction sets and dealing with missing address information as well as slice selection mechanisms has been discussed extensively in the literature <cit.>. 
  
  One of the drawbacks of both the  and  technique is the necessity for precise timers to detect whether the victim accessed the memory. The timer-less attack  exploits Intel's implementation of Hardware Transactional Memory TSX: it starts a transaction to fill the the targeted cache set (prime), then waits if it receives an abort because the victim has accessed this set <cit.>. However it does obviously require Intel TSX, which is not available on all machines. 
  
  The OpenSSL AES implementation protected by the prefetch was attacked by Ashokkumar et al. in 2018. They used a chosen plaintext approach targeting the first and second round of the AES in OpenSSL <cit.>. Cohney et al. attack the last round of the AES, but in a very different setting. They target a deeper layer implementation of T-Table AES used only to encrypt seeds for the pseudo random number generator in AES <cit.>. While failing to protect these inner implementations the same way as the public ones is a notable oversight, it is also one of the main difference to our target: We attack an implementation that is explicitly protected from cache side channel attacks. The second difference is that as many other side channel attacks, this one uses SGX enclaves in step mode to enhance their timing granularity. Moghimi et al. <cit.> also target SGX assuming a malicious or compromised operating system. The scenario allows them to use the L1 cache as source of information. This way they retrieve various samples per round and manage to distinguish the prefetching stages from the normal operations of the round for both  T-Table and an  implementations of AES.
  
   does not require SGX, nor the frequent interrupts of the victim given by the powerful adversarial scenario controlling the OS. It works across cores and does not need special privileges. It only requires either shared memory with the vicitim (e.g. vial libraries) or TSX. 
  Thus,  is a general attack technique that can be used in many settings. We chose to demonstrate it on an AES and and RSA implementation, but it can be applied in many scenarios to circumvent cache attack countermeasures. 
  
  
  
  § TARGET ALGORITHMS
  
  
  The different cryptographic algorithms that have been shown to be vulnerable to cache attacks have in common that they perform secret dependant accesses to memory. An attacker can observe these accesses through the cache and then retrieve the aforementioned secrets. 
  
  For this reason a common countermeasure with less impact on performance than flushing the data from the caches is to prefetch the data in the cache to prevent the attacker from distinguishing data that have been used for the cryptographic operation from data that have not.
  
  We focus on two common algorithms (AES and RSA) that have been targeted multiple times, in particular we focus on two implementations that have been theoretically protected against these attacks. In the following sections we describe their implementations and explain the countermeasures they implement.
  
  
  
   §.§ AES  implementation in OpenSSL
  
  
  
  AES <cit.> is a commonly used symmetric block cipher that operates with data in blocks of 16-bytes. It consists of different operations (AddRoundKey, SubBytes, ShiftRows and MixColumns) that are repeated each round. The  is the table that holds the data for the SubBytes operation, concretely it holds 256 byte values.
  
  The  software implementation of AES replaced the previously used T-Table implementation, which used four tables (T-Table) with pre-computed values of the SubBytes, ShiftRows and MixColumns operations. That is, it transformed the aforementioned operations into look up operations in order to improve the performance of the encryption and decryption processes. The accesses to the tables are key dependant and not all of them are used during the encryption process. This fact has been exploited multiple times to recover the secret keys <cit.>.
  
  As opposed to the T-Table implementation, the  implementation does not merge different operations into one. The table is used 16 times each round, once per round input byte, during the SubBytes operation. Considering a cache line size of 64 bytes, such table uses 4 cache lines (256 bytes). If we compute the probability of not accessing one of these cache lines and assume a key size of 128 bits, and as a result 10 rounds, such probability is equal to 0, as shown in equation <ref>. As a consequence, an attacker observing the cache before and after the encryption process will not gain any information from that observation.
  
      [no access  in encryption]= ( 1-64256)^10*16= 0
  
  
      [no access  in round]= ( 1-64256)^16= 0.01
  
  
  Equation <ref> shows that observing each round individually would give a 0.1 chance of not accessing one of the lines. Instead of relying on the challenging task to stop the process after each round, the countermeasure of prefetching was applied: The OpenSSL  implementation includes a prefetch stage before each of the rounds. Since the 256 bytes of the  table map to 4 different cache lines, the encryption process only has to read 4 values to ensure the whole  table is loaded into the cache memory. Even when the S-Box implementation performs key-dependant memory access, the data will always be in the cache. As a result, traditional side channel attacks cannot be used to extract information from this implementation. Irazoqui et al. analyzed the OpenSSL implementation in 2017 with a tool for leakage detection and came to the same conclusion, declaring it leakage free <cit.>. Indeed, if we compare the time it takes to perform an encryption with the time it takes to perform a single Probe <cit.> in one set, it is clear that the resolution of a  attack[The Probe includes sequential accesses to the elements of the eviction set and no cache misses that would increase the Probe times] is not high enough to retrieve fine-grained information from this implementation: As we can see in figure <ref>, a probe time without any cache misses takes almost as long as the entire encryption. Even if the attacker primes the cache before the encryption starts and is able to tell exactly when the encryption starts, a single cache miss will increase the time required for probing to be greater than the total encryption time. 
  
  The  implementation is not the default one in OpenSSL when an AES encryption operation is triggered from the command line. However, when using the C API of the library, a call to the function  will use the . A developer wishing to use the default AES-NI instructions (as in the command line) has to explicitly indicate it. While analyzing the shared library included in Ubuntu 16.04 or CentOS 7.6 (OpenSSL 1.0.2g), we observed an additional protection. The OpenSSL implementation of AES has four different S-Boxes. If there are, for example, two processes using the library at the same time, each of them will use a different table.
  
  
  
  We discovered this implementation is still vulnerable, since there are tiny time windows during the encryption process from which the attacker can gain valuable information. As we will show in section <ref>, our proposal allows an attacker to observe information referring to just the last round, even in the absence of shared memory. We show how to bypass the prefetch, and perform a cross-core cache attack that recovers the secret key of this theoretically protected implementation. 
  
  
  
   §.§ WolfSSL RSA exponentiation
  
  
  
  RSA is the most widely used public key cryptographic algorithm. It considers a public key (n,e) where n is the product of two prime numbers p and q that remain secret, and a private key (p,q,d) where d ≡ e^-1(p-1)(q-1). In order to understand the attacks only the encryption and decryption operations are relevant. For a message m,  the ciphertext c is obtained as c=m^e n and it is recovered with an analogous operation m=c^d n. In particular the decryption, which is the exponentiation operation using the secret key, is the target of the attack.
  
  There are multiple ways of implementing this exponentiation <cit.>. We will focus particularly on the square-and-multiply exponentiation, since the wolfSSL implementation is based on this. The square-and-multiply approach scans the bits of the secret exponent, performing a square operation independently of the value of the scanned bit, and a multiplication if such bit is equal to 1. Thus, an attacker monitoring the square and multiply operations can retrieve the sequence of bits of the exponent. 
  
  The countermeasures wolfSSL has deployed to protect this implementation are to always perform the square and the multiply operations and to load the two possible values of the bit to keep them in the cache so they prevent an attacker from distinguishing which one (0 or 1) was used. These are clearly put in place to prevent cache attacks, which can be seen in both the source code comments and the release notes <cit.>. The resulting procedure is summarized in algorithm <ref>. 
  
  
  
  end if
  [IF]IfEndIf[1] #1 
  end for
  [FOR]ForAllEndFor[1] #1 
  
  
  In order to analyze the wolfSSL implementation of the exponentiation, we compiled the latest version at the time of writing this paper (version 4.4.0) with the –enable-debug –enable-keygen flags in order to be able to keep the symbols after the installation and to generate RSA keys. Later, we ran the tests included in the library itself to analyze their RSA implementation and found that the exponentiation is still vulnerable despite the steps taken to remove side channel vulnerabilities. 
  
  As in the case of AES, this approach still leaves a window long enough for observations of the bit values. Indeed there are two possible windows to retrieve the secret information. Firstly, at the end of the multiplication operation in line <ref> only the result referring to the actually used bit is stored. In that copy process, one of the two possible values is loaded while the other one remains untouched. This leaks the key bit. The second window is even bigger, because the reduce operation in line <ref> only uses the information of the actual key bit value, not taking the precaution of loading both values. This means that this function could be even vulnerable to a traditional cache attack, although the synchronization between the attacker and the victim process would be a challenge.
  
  
  
  § ATTACK SCENARIO AND OVERVIEW
  
  
  One of the goals of this work is to demonstrate an attack mechanism that gives an attacker more insights about what the victim is doing and further control of the cache evictions so she can obtain the desired information. We first describe the considered scenario, in which the attacker does not interact with the victim directly. Next, we describe the steps of the  approach.
  
  
  
  In the considered scenario, which is depicted in Figure <ref>, we can find the following agents:
  
  
  	
    Server Encrypts/decrypts a block of data whenever it gets a request from any client. While this is a simplified version of a real server process, it is enough to create a realistic scenario for the attacks. 
  	
    Client Sends requests at random times, each around 500μs plus a random time. This process tries to emulate the normal behavior of a real network.
  	
    Attacker Monitors the cache to detect the exact times when the target process (an encryption process) is running so it can launch a precise attack.
  
  
  Our main assumption is that both the attacker and the victim are using the same machine. Since we assume no synchronization between the victim and the attacker, the attacker does not know when the victim is running an encryption. Thus, the first challenge for the attacker is to detect when the victim is performing an encryption, which she does by spying on the cache. 
  
  The second challenge for the attacker is to design a technique that allows her to evict the target data from the memory at the desired instant. Note that this eviction has to be accurate since the attacker has a very limited time window to observe the victim behavior. To retrieve necessary information up front, the attacker needs to perform an offline stakeout phase. Then,  is conducted in three steps:
  
  
      
    Aim Detect the execution of the victim process.
      
    Wait Wait for a pre-determined time 
      
    Shoot Cause an eviction of the desired data.
  
  
  We will explain the stakeout and the aim and shoot steps in the following sections. The wait step is straight forward after completing the stakeout. Note that although we use AES for exemplification, the presented approaches are general, and can be applied to virtually any other target. The pseudocode of the attack is displayed in listing <ref>, and all line numbers in the following refer to this code. 
  
  
  
   §.§ Stakeout: Preparing for attack
  
  The goals of the stakeout-phase are to find an appropriate cache region to monitor and determining the waiting time for the second attack step. This can be performed offline and is completely independent of any victim executions. 
  
  For AES, we would like to monitor the . As stated in section <ref>, we have to determine which of the four es is used by the server. In our case it is the third table, and it seems to stay the same through executions. To retrieve this information, an attacker can just perform an unmodified version of the  or even  attacks and profile the process. 
  
  The waiting time is the time between the start of the encryption and the relevant observation window. The constant WAIT_TIME represents that value in listing <ref>. One possible way to obtain it is to profile the victim application on a machine similar to the target machine. The attacker measures the time it takes the process to execute the code between the point that serves for detection and the point in which the attacker can gain information from the evicted data, for example, the last round of the AES encryption process in our scenario. Note that the time it takes to execute the clflush has to be considered but it is not significant if no fence instructions are used to measure its execution time. As a result, we can evict data that is accessed as soon as 60 cycles after the execution of the line used for detection. This time has to be considered when selecting the gadget function.
  
  A second approach assumes that an attacker does not know the waiting time in advance, but she knows some characteristics of the process as the probability of observing a cache hit or miss in the target. For example around 1% of cache misses will be ideally observed if we hit exactly the last round of the AES encryption or around 50% of the bits are expected to be 1 in an RSA secret key. In this case, the value for WAIT_TIME can be retrieved automatically by analyzing the number of hits and misses observed in the recovery step (lines <ref> - <ref>) and modifying its value accordingly. Even further, the attacker can define an initial value for WAIT_TIME and update or adapt it dynamically based on the comparison between the actual and the expected observations. 
  
  
  
   §.§ Aim: Detection of the victim's execution
  
  
  In order to spy on a reduced time window during the execution of the target algorithms we must be able to identify such window during the runtime. For this reason, we study different detection mechanisms to cover a variety of attack scenarios. In the most favorable scenario, the host machine has Intel TSX, which we aim to use for detection. In the second scenario, the attacker relies on the existence of shared memory and on the knowledge of some characteristics of the target algorithm. Indeed, as we will show in later sections, if the victim prefetches the target data, we can use that prefetch for detection. Finally, and although we do not explore further in that direction we briefly describe other approaches that could be used for detection.
  
  To evaluate which of the different approaches works better, we have modified the server, so it gives us information about the precise time instants at which the target process (an AES encryption) begins and ends. We then use this information to evaluate how many of the encryptions have been detected and if so, how many of them are detected before the encryption has ended to ensure we still have time for making an observation. 
  
  In particular, we monitor one of the lines of the . And since the prefetching stage of the targeted OpenSSL AES implementation involves the  being loaded into the cache at the beginning of the encryption process, this reliably informs the attacker when the encryption has started: whenever we detect the presence of the  data in the cache, we assume the encryption has started. 
  
  
  
    §.§.§ Leveraging TSX for detection
  
  
  As we have already stated, the process running inside a transaction can either be completed and commit the results or suffer an abort and rollback the computations. 
  
  The  attack <cit.> deliberately causes conflicts in the L3 cache with the victim process to determine whether it has or has not used certain data. We use such conflicts in the L3 cache to determine the exact instants when the process executes the target instructions or uses certain data we want to monitor. The specific targets here are the data in the  in the attack against AES and one instruction in the vulnerable exponentiation function in the case of the attack against RSA. 
  
  First of all we build eviction sets mapping to the same sets as our targets. We enabled hugepages to construct eviction sets as Liu et al. did in <cit.>, although it is possible to use the reverse-engineered mapping function <cit.> or a different approach that does not require the use of huge pages  <cit.>. We read the data in one eviction set inside the transaction and wait for the victim to execute. We observed some spontaneous aborts as also noticed in previous works <cit.>, but we were able to properly detect 97% out of 10000 encryption processes executed during this experiment. We believe that during the “undetected” executions we were loading the data into the transactional region concurrently or just after the execution of the victim process, or an unrelated process accidentally evicted our data.  
  
  Moreover, we have used the abort handler to read the system timestamp and compared this value with the timestamp we have collected in the server just before executing the encryption process. The difference between them is almost constant and the mean the value of this difference is 380 cycles in our system (Intel Core i5-7600K). Based on this measurements, we state that this technique accurately informs about the execution of the victim and that the attack gets the abort as soon as the conflict happens. Note that the measured times include the execution of some instruction before the prefetch of the   and the time it takes the CPU to retrieve the  data from the main memory. That is, the transaction aborts once the data has been effectively loaded into the cache and the attacker's data is removed. 
  While a heavy system load leads to additional aborts that are not related to the encryption, it does not influence the detection time. 
  
  
  
    §.§.§ Shared Memory and detection
  
  
  The   <cit.> technique has revealed itself as one of the most reliable sources of information in cache attacks, especially when compared to the  technique <cit.>. The main reason is that, in the former case, observations are made on a shared memory block, whereas in the latter case, any other process running in the machine could force an eviction and the attacker would not be able to distinguish the origin of the eviction. The  technique requires the victim and the attacker to share the library. This is often not a problem since, for example, we have observed that both Ubuntu 16.04 and CentOS 7.6 are shipped with a compiled version of libcrypto (OpenSSL 1.0.2g) and newer versions of Ubuntu  such as Ubuntu 20.04 also come with the latest version of the shared library (OpenSSL 1.1.1f). Similarly, wolfSSL, when compiled and installed, generates a shared library. 
  
  Back to the  example, the attacker flushes the data of the  line monitored in the previous scenario and then waits for an arbitrary time and reloads that data. We have observed that, if we do not include this waiting time, we are not able to observe any cache access. We have similarly considered two different ways of ensuring that the process waits for a fixed time: increasing the value of a variable up to a limit or actively polling the system counter through the  instruction and constantly checking if we have waited for the desired time. Each approach yields to different results, but they are similar in the sense that they lead to similar detection rates.
  
  Figure <ref> shows the results in terms of correctly detected encryptions and valid encryptions (the encryption was detected before the victim had actually finished it) as a function of the waiting time. The waiting time refers to the limit up to which a variable is increased: from 0 to the limit. As we did in the previous case, we collect information referring to 10000 encryptions per each considered limit. As it can be derived from the figure, limits around 20 obtain the best results in terms of valid encryptions. As a consequence, an attacker should select that limit to maximize the chances of success when trying to evict data later during execution of the target window. In any case, these results show that it is also possible to use the  technique for detection in case the processor does not include TSX, although the results will not be as accurate as the ones obtained using TSX. 
  
  
  
  
  
    §.§.§ Other scenarios
  
  
  Another option to detect the execution of the victim process are  based approaches. If we look back to figure <ref> and compare the Probe times with the execution of the whole encryption process it seems clear that performing a complete Probe of the data in the eviction set is not a real option to obtain valid information for the attack from a single round. However, considering the replacement policy of the L3 cache and that the attacker knows the insertion order of the elements in the eviction set, she can sequentially access such elements from the one that was first inserted to the one that was last inserted. This way, she can be reasonably sure that she is accessing the element that the target will replace in case of conflict.
  
  The main drawback of this approach is that even if the detection is successful, the attacker does not have any control of the state of the cache at the time the victim executes. As a result, she cannot accurately predict the number of accesses that will be required to evict the recently inserted data. Since the capability of the attacker to achieve this eviction during the execution of the victim process is determined by this state of the cache and the number of required accesses, the attacker capabilities are rather limited in this scenario.
  
  
  
   §.§ Shoot: Accurate eviction of the data
  
  
  Due to the prefetching or to the always execute and always load into the cache strategies, the ability of the attacker to retrieve the secret information is determined by his ability to evict the data from the cache during the vulnerable windows. Namely, when attacking the  implementation of AES our goal is to achieve evictions during the last round and after the last prefetch, when attacking the RSA exponentiation, our target are certain windows during the execution of some operations in the multiply or the reduce functions.
  
  
  
  As we did when explaining the detection scenarios, we also consider different possibilities in this case. The considered scenarios are depicted in figure <ref>. Note that since we obtained the best detection results for the machines with TSX, this is the feature we first look for, although it will not be used during the eviction process. In figure <ref> we have highlighted the scenarios we are going to describe more deeply in this section for the shake of simplicity and brevity. In all cases the idea is the same, once we know the victim is running we wait for the exact time determined in stakeout, which will allow us to force the eviction at the desired instant.
  
  In the following, we refer to the technique that allows us to evict data from the cache once the execution of the victim has been detected using the TSX capabilities as method 1 when there is shared memory between the victim and the attacker, and as method 2 when there is not. Although not explicitly mentioned in the figure, the attacker has to recover the information leaked thanks to the accurate eviction of the data. For method 1, reloading the shared data is enough, in the second case, another access is required.
  
  In order to help us with the explanation of both methods, we include the pseudocode of the  attack process (Aim, wait, shoot, then recover information) particularized to the  attack that we have been using as example in this section. Note that the procedure procedure summarized in the algorithm <ref> is general, the attacker just has to change the  by her target, for example the RSA multiply function in our other example, and adapt the waiting times and the eviction function correspondingly. 
  
  As we will show, method 1 differs from method 2 in the way the cache set is filled during the transaction, in the value of the WAIT_TIME even if the target is the same, in the way this target is evicted from the cache and finally in the way the information about the actual access to the data is inferred. Next, we explain the particularities of each approach.
  
  
  
  
  [IF]IfEndIf[1] #1 
  [FOR]ForAllEndFor[1] #1 
  
  
  
  
    §.§.§ Method 1
  
  
  As we have already stated, this method relies on the existence of shared memory. That allows the attacker to flush from the cache the desired data when the desired instant comes. Once the transaction is started, the attacker has to fill the cache set (line <ref> in the algorithm <ref>). It is not required for the attacker to place the data in any specific order but she must fill the whole set to get the abort signal that will inform her that the victim is accessing the target. One can see this detection mechanism as a “break point” the attacker places into the code without notifying it to the victim.
  
  Once the abort is triggered by the victim's access, we use the handler to carry the attack. This process includes mainly the definition of the time the attacker has to wait (line <ref>), the procedure to evict the data (line <ref>) and finally a way to retrieve and store the desired information (lines <ref> - <ref>). Since there is shared memory data is evicted using the clflush instruction and retrieved measuring the time it takes to read such data (reload). This is a traditional  attack carried by an abort handler, which allows for very precise timing of the flush instruction. 
  
  
  
    §.§.§ Method 2
  
  
  If there is no shared memory or the data is going to be retrieved from a non shared variable (e.g. in the attack against RSA), it is still possible to achieve the desired eviction accurately by just accessing one memory location. In order to be able to do this, we have to manipulate the cache state prior to the detection of the encryption process. Indeed, the required state of the cache, depends on the replacement policy of the last level cache and it can be changed by accessing data located in the cache. Note that accesses to data located in lower caches do not change the state of the last level cache. Interestingly, the state of the cache remains unchanged when the transaction aborts. In other words, the abort does not revert the microarchitectural state of the cache. 
  
  One of the simplest ways to check this assumption, is flushing some data out of the cache before executing the transactional code. Then, in the transactional region, reload that data back into the cache. Next, we wait in an endless loop doing nothing within the transaction, until an abort happens. The abort handler checks if the data is in the cache or not. We have repeated this test 10000 times, and the conclusion is that the data that has been loaded into the cache during a transactional operation, remains in the cache after such operation has finished, in the sense that even if the process never gets to see the result of the code executed inside the transaction, the microarchitectural state of the processor retains some information. 
  
  This is similar to transient execution attacks  <cit.>, which exploit the fact that microarchitectural changes of transient executions that have never been committed are still observable from the architectural state. 
  
  Although the manipulation of the data in the cache is performed during the preparation of the code for the detection, in the fill_cache_set() function of the algorithm <ref> (line <ref>), it is directly related with the eviction, and this is the reason why we are giving more details in this section. This initial setup is also one of the differences between method 1 and method 2. Also, since this approach evicts the target by accessing another block instead of using the clflush instruction (line <ref>) this has an effect on the WAIT_TIME value. Namely, the target data is not evicted from the cache until the replacement block has been retrieved from the main memory, and this introduces a delay of around 200 cycles since detection. This means that around 250 cycles must elapse after detection, otherwise it is not possible to evict the data. The profiling of the victim for the selection of the WAIT_TIME or the automation of the process to obtain it is still necessary. The last difference to method 1 is how data is retrieved, in this case another access is required (line <ref> )
  
  In the following, we give more information about why it is possible to use TSX to support our attack, how this approach works and some considerations related with the L1 cache replacement policy.
  
  
  
    
  Replacement policy and accurate eviction of data 
  
  
  The replacement policy described in <cit.> agrees with the ones described in <cit.> in the selection of the eviction candidate most of the times. Indeed, our attack can be explained considering any of them as the correct one. Mainly, once the data is inserted into the cache set, all of them distinguish two different ages above the age 0, and they all consider that the data is evicted from the cache with age 3. They differ in the way the ages are updated. Since our attack was originally designed using the approach described in <cit.>, we will use that policy for the explanation.
  
  Besides the replacement policy, there are two things we need to bear in mind to understand this approach. The first one is that only access to the last level cache update the values of the ages of the elements in the LLC. The second one is that the LLC in our machine is inclusive. This means that if the victim loads the  into the cache after a cache miss, it will be loaded in all the cache levels, and in case this data is used multiple times during the encryption, it will be retrieved from the low level caches leaving the age of the cache line holding the  unchanged. As a result, if it is the oldest element in the set when inserted, it will be evicted in case of conflict.
  
  
  
  The general idea of the attack is depicted in Figure <ref> particularized for the  attack. As a difference with the previous approach the attacker needs to set the ages of the elements that have just been inserted into the set (stage 1) to the ones shown in the second stage of the figure. This means that the  function in the algorithm  <ref> involves two steps. Note that all the elements in the eviction set are accessed, so the transaction still aborts when the victim accesses the monitored data. 
  
  Once the encryption begins, the  data will be placed into the cache. In that moment, the oldest element (A) that we have not accessed to ensure it is older than the rest of elements, will be evicted. At the moment the  data is inserted, and considering all the updates in the ages of the blocks, all the blocks (the ones originally placed in the cache by the attacker and the  block) will have the same age. Since we perform the accesses in such a way that the oldest element before inserting the  data (A) is located in the first position in the set, the  automatically becomes the eviction candidate just after being inserted. 
  
  Then the procedure is similar as it was in the previous case. We wait for the desired time and then by accessing A (which is out of the cache because it was replaced with the  data) we ensure that the data of the  is removed from the cache. We wait until the encryption ends, and finally retrieve the information about the actual access to the  by accessing B. Since B is the first element with age 3, in case of conflict it will be replaced with the  data. Note that after the recovery step we need to change the ages again in a similar way they did in the Reload+Refresh attack <cit.>.
  
  
  
    
  Influence of the replacement policy of the L1 caches 
  
  
  When trying to force all the elements in the set to get the ages depicted in the stage 2 of Figure <ref>, we accessed the corresponding blocks B to H as a linked list (to avoid pipeline effects as much as possible). We thought that this way all the data would be retrieved from the LLC and as a result, the ages of all the elements would be updated. To test our hypothesis that the data was retrieved from the LLC, we measured the times it took us to read each of the blocks. Surprisingly, we found out that some of them were retrieved from the L1 cache. The replacement policy of L1 and L2 caches was responsible for this effect, so we performed some experiments to understand how it works.
  
  In fact, we only observed this behaviour in our processor LLC whose LLC is 12-way associative, whereas the L1 and the L2 caches are 8-way and 4-way associative respectively. However, we performed the same test in a different processor (Intel i7-6700K) with a 16-way associative cache, and all the data was retrieved from the LLC. In the first case, just after the 12 elements of the set have been placed in the cache, 4 of them are only present in the LLC, and the L1 cache will have suffered 4 misses but still keep 4 of these blocks. The replacement policy defines which elements are replaced and which are replaced. On the contrary, if the number of ways of the LLC is 16, the L1 cache will have suffered 8 misses. This means it is likely that the 8 elements that were first accessed only reside in the LLC. We observed that in the first case the block we call B is in the L1 cache whereas it is not in the second case. For these reasons we conducted some experiments to determine the replacement policy in the low level caches. 
  
  Low level caches are assumed to implement a Pseudo-LRU replacement policy, simpler than the policy implemented in the LLC. We conducted some experiments aimed to retrieved that policy. Based on our observations and some intuition we already had, we were similarly able to explain our results assuming a replacement policy and checking times. It turns out that Intel implements a tree based Pseudo-LRU replacement policy in the low level caches. Independently and concurrently with the design of this attack, some other researchers arrived to the same conclusion <cit.>.
  
  
  
  To sum up, the tree-based replacement policy is represented in Figure <ref>. Starting from the root node it selects each of the branches depending on the intermediate values of the nodes. In the example the eviction candidate is marked in red. Since the root node contains a 1, it selects the right branch. The value of the pointed node is a 0, so it selects the left branch. Finally, the last node has a 1, so it points to the element at the right, F in the example. Note that the blocks of memory in the cache set (A to H) are ordered. According to our experiments when the cache set is completely empty, the elements are inserted linearly in the first free block they find regardless of the actual values of the nodes. Once the set gets completely filled with data, the apparent value of all the nodes seems to be 0. If an element in the cache is either accessed or replaced, the values of the nodes that pointed to it are switched.
  
  This replacement policy explains why B is in the L1 cache after reading the whole LLC eviction set (12 elements). For this reason, B cannot be the first element to be accessed because its age would not change. Based on this replacement policy, we have prepared a linked list of addresses to access 11 elements of the eviction set out of 12 possible in our 12-way cache, that ensures all of them are in the LLC. This way we are able to reduce their age and indeed, we have checked that the designed access pattern retrieves all the elements in that list are retrieved from the LLC.
  
  
  
  § RESULTS
  
  
  
  In this section we explain how we recover the AES and RSA secret keys, demonstrating that the countermeasures to prevent cross-core last level cache attacks can be circumvented. In the cases where some adaptations of the proposed approach are possible, we mention it. All the experiments were performed in the machine described in table <ref>. The version of OpenSSL used is the one included in our CentOS system (OpenSSL 1.0.2k). Note that the replacement policy on which this attack relies is implemented in the Intel Core processors starting from the 6th generation.
  
  
  
  
  
  
   §.§ Attack against the AES
  
  
  This targeted  implementation was also attacked in <cit.>, albeit for a much more powerful adversary with full OS control targeting SGX. That work monitored the entire L1 data cache, observing various samples per round, allowing them to distinguish the prefetching stages from the normal operations of the round. Our approach on the contrary does not need to frequently interrupt the victim, works across cores and does not have any special requirement, just user-level privileges as commonly assumed for cache attacks.
  
  As we have already stated in the previous sections of this work, the target of our attack against the  is the last round of the encryption. In this round, the contents of the  is xored with the corresponding round key to get the ciphertext. In order to retrieve the secret key in all scenarios (method 1 and 2) we use the information referring to the accesses to the  retrieved during the attack phase (Algorithm <ref>) and assume the ciphertext to be known by the attacker. 
  
  We use the non-access approach described in <cit.>. In a nutshell, they used information from cache misses, that is whenever the victim did not load the data into the cache. Note that in this particular implementation, the  is accessed 16 times during the last round, and even if we are able to accurately get the information referring to the last round exclusively, we would not know which of the 16 accesses was responsible for this access. On the contrary, if we determine that an element has not been accessed it means none of the operations in the last round has used it. As a consequence, we xor each byte of the ciphertext with the 64 values of the  held in the cache line (k_i= C_i⊕  [0 to 63]). None of these values could be the secret key.
  
  In our test system the last round takes around 50-60 cycles to execute. However the encryption time is not constant, and has a variance of around 15 cycles. Thus, even if we interrupt the victim at the exactly chosen time, which is the estimated time when the last round starts to perform its operations, we may not hit our target. Even slight variation in the interruption instantly lead to a different number of observed accesses. If we interrupt before the last prefetch, we will only observe cache hits. In contrast, if we evict the   data after the encryption has ended, we will only see cache misses. Indeed, assuming that the 16 operations that use the  in the last round of the encryption are executed sequentially from 0 to 15, the expected cache miss probability depends on the exact operation at which is evicted from the cache. This probability is depicted in Figure <ref>. 
  
  
  
  To deal with the variation 
  in the execution time of the algorithm and to maximize our success chances, when estimating the WAIT_TIME in the Algorithm <ref> instead of using the probability of 1% as the expected one, we allow up to 7% of cache misses. This way we try to ensure that the observed cache misses actually happen in the round. This value was determined empirically in our machine, by selecting a different probability values and carrying multiple experiments with the value of WAIT_TIME adapted dynamically according to that probability and window sizes of 10 000 observations.
  
  Both approaches, the one that assumes shared memory (method 1) and the one that does not (method 2), are able to successfully retrieve the secret AES key. Even with the false positives (cache misses that do not refer to the key byte) introduced by all the variances, we get enough information from all the rounds. Indeed, as our results show, it is more likely to evict the data in the middle of the execution of the last round than just at the beginning. As a result some bytes are recovered faster than others as it can be observed in Figure <ref>. The number of samples required to retrieve the secret key slightly varies between executions and depends on the threshold selected, even if we use the adaptive approach. In both cases, the minimum number of samples required to retrieve the whole key is about 500000.  
  
  
  
  As can be observed in Figure <ref>, half of the key has been completely leaked after 100000 samples (the initial four bytes are obtained with 10000  samples, although it cannot be clearly observed in the figure). Around 12 of the 16 bytes are already known with 200000 samples. Retrieving the last 4 bytes of the key is the hardest part, it takes 300000 more samples, which gives an idea about the difficulty of evicting the data in between the execution of the prefetch and the subsequent access in the last round. 
  
  Figure <ref> is complementary to Figure <ref>. It represents the number of guesses that an attacker would require to retrieve the key using brute force and the information about the actual access of the victim. Note that both plots represent the same experiment. Different experiments have yielded to similar results but, as we have stated before depend on the actual threshold defined by WAIT_TIME. Besides, we have noticed that the location of the  in the cache is also important, because there are some sets that are noisier than others. 
  
  
  
  
  
  
   §.§ Attack against RSA
  
  
  The modular exponentiation executed for the RSA decryption operations in the wolfSSL implementation is a variation of the well-known square-and-multiply algorithm. Indeed, it is a cache attack protected version of the square-and-multiply implementation that we have described in section <ref>. 
  
  Based on the code they provide for the tests, we generated different secret keys of 2048 bits, and embedded them in our server application in such a way that it decrypts the received data by calling to the wolfSSL RSA decrypt operation. Note that in this case we can observe the leakage by monitoring accesses to one of the two arrays R[0] or R[1], cause the accesses to each of them depend on the key bit value (0 or 1). During the execution of the multiply function, they are both loaded into the memory, but at the end of the function they perform a copy operation wich only accesses 
  the required value. That is, an attacker can for example remove R[0] from the cache before the execution of the copy operation and check it afterwards. This operation takes around 70-80 cycles in our system, which should be enough for the observation.
  
  However, attacking this implementation is eased by the reduce operation executed after the multiply operation. Such function only loads the correct value of R[y] where y is the secret key value. The execution of the reduce operation lasts about 2300 cycles in our test system. Note that this time even allows the execution of a complete probe cycle so we do not to be so precise evicting the data when targeting this function.
  
  As a difference with the attack against AES where we targeted the  for both detection and eviction it is not possible to use the same content for detection and eviction in this case. Namely, we have used both the multiply and the reduce operations for the detection and later evict R[0]. Note that while the functions are shared, R[0] and R[1] are not, so the approach explained in method 1 is not possible. Also, the attacker will have to profile the application for determining the WAIT_TIME and to determine the cache set in which R[0] is loaded. The task of profiling is eased with the help of the detection of the multiply function. In our posterior experiments we assume that the attacker already knows the set where R[0] maps.
  
  There are also some other differences with method 2, since we do not require such an accurate eviction and loading the data of a whole eviction set conflicting with R[0] in the transactional region leads to false positives in detection so it is not required. However, some of them can be loaded to reduce the time it takes to evict R[0] considering that all of them can be accessed when retrieving the actual information about the access equivalent to the inference step in algorithm <ref>, line <ref>.
  
  In this case, the key bits correctly guessed depend on both the accuracy of the detection and on the ability of the attacker to remove the data from the cache during the execution of the leaky parts of the code. The mean time between the execution of two multiply operations is about 24000 cycles. That time seems to be “constant” and it is enough for carrying the detection, eviction and retrieving the data. We collected information for the execution of 100 RSA decryptions. Our attack correctly detected 96.8% of the multiply operations introducing 1.3% of false positives. From those correctly detected operations, the information referring to the access to R[0] featured 91% of true positives rate and 87.2% of false negative rate, namely a precision of 87,6%. 
  
  Note that no further processing of the results was done. If so, it is possible to determine which of the executions of the multiply operation were not detected. Note that since we get quite exact timestamps from the aborts, trace alignment becomes easier. The decision about the correct value of the secret bits of the exponent can be made based on the information retrieved from various traces.
  
  
  
  § COUNTERMEASURES
  
  
  The presented attack is feasible due to the fact that the interval between an access to a piece of data or a function that could leak data, and the following access gives the attacker the possibility to observe such accesses and, as a consequence, retrieve the secret information. In order to prevent this leakage, these susceptible windows must be removed from the source code, and as a consequence the code should be redesigned. In order to help developers to find leakages in their code, there are tools that detect these leakages <cit.>.
  
  In particular, the AES  implementation for x86, could make this attack harder just by including one last prefetch after the encryption ends. Alternatively, each  lookup could access all four cache lines, eliminating cache line leakage.
  Considering the wolfSSL RSA implementation, it should at least load into the cache the leaky data in the two vulnerable functions. Note however, that the proposed countermeasures are intended to prevent the exploitation through the LLC, however the powerful SGX scenario may still be able to retrieve some information.
  
  Regarding the countermeasures that prevent cache attacks by means of new cache designs <cit.> or applying hardware modifications <cit.>, they can be effective for the presented attack. However, they are not available yet. Similarly, techniques that allocate the victim and the attacker data in different and mutually exclusive cache sets <cit.> would prevent this attack.
  
  Finally, detection based countermeasures that monitor the execution of the algorithms they aim to protect and collect information about execution times or from performance counters (i.e. cache misses or accesses) to detect changes in the execution trace could detect the attack <cit.>. Note that  was not designed to be stealthy and generates cache misses on the victim algorithm. However  can also improve the efficiency of existing attacks. Indeed, we tested it against the T-table implementation, retrieving the secret key in about 4-5 ms from just 300 encryptions. These short times seriously limit the capability of the aforementioned countermeasures to trigger the alarm on time. 
  
  
  
  § CONCLUSIONS
  
  We present , a new side channel attack consisting of the steps aim, wait, and shoot. The aim step detects the exact start of the victim operation. The attacker then waits for a predetermined time. Last, in the shoot step, the target element is evicted from the cache at precisely the right moment. We show that  can be used to launch last level cache side channel attacks on implementations that are generally regarded as protected by leveraging tiny windows of secret dependent accesses in the implementation. 
  
  Achieving such accurate evictions is possible thanks to the ability of TSX to synchronize with the execution of the target algorithms, the knowledge of the replacement policies implemented in Intel processors and to the fact that the modification of the state of the cache inside the transactional region remains even if the transaction aborts and never commits.
  
  We demonstrate this by retrieving the secret key from the OpenSSL AES  implementation and the secret bits of the modular exponentiation implemented as part of the the wolfSSL RSA decryption algorithm, both of which were regarded as secure against cache side channel attacks since traditional cache attacks would not be able to retrieve such information.  can however be applied to a much wider range of targets. 
  
  
  plain
  
  
  