{'fraction_non_alphanumeric': 0.02660092398848122, 'fraction_numerical': 0.014315606289751186, 'mean_word_length': 4.8837152608483665, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
MemJam: A False Dependency Attack against Constant-Time Crypto Implementations

Cache attacks exploit memory access patterns of cryptographic implementations. Constant-Time implementation techniques have become an indispensable tool in fighting cache timing attacks. These techniques engineer the memory accesses of cryptographic operations to follow a uniform key independent pattern. However, the constant-time behavior is dependent on the underlying architecture, which can be highly complex and often incorporates unpublished features. CacheBleed attack targets cache bank conflicts and thereby invalidates the assumption that microarchitectural side-channel adversaries can only observe memory with cache line granularity. In this work, we propose MemJam, a side-channel attack that exploits false dependency of memory read-after-write and provides a high quality intra cache level timing channel. As a proof of concept, we demonstrate the first key recovery attacks on a constant-time implementation of AES, and a SM4 implementation with cache protection in the current Intel Integrated Performance Primitives (Intel IPP) cryptographic library. Further, we demonstrate the first intra cache level timing attack on SGX by reproducing the AES key recovery results on an enclave that performs encryption using the aforementioned constant-time implementation of AES. Our results show that we can not only use this side channel to efficiently attack memory dependent cryptographic operations but also to bypass proposed protections. Compared to CacheBleed, which is limited to older processor generations, MemJam is the first intra cache level attack applicable to all major Intel processors including the latest generations that support the SGX extension.

Abstract-Cache attacks exploit memory access patterns of cryptographic implementations. Constant-Time implementation techniques have become an indispensable tool in fighting cache timing attacks. These techniques engineer the memory accesses of cryptographic operations to follow a uniform key independent pattern. However, the constant-time behavior is dependent on the underlying architecture, which can be highly complex and often incorporates unpublished features. CacheBleed attack targets cache bank conflicts and thereby invalidates the assumption that microarchitectural side-channel adversaries can only observe memory with cache line granularity. In this work, we propose MemJam, a side-channel attack that exploits false dependency of memory read-after-write and provides a high quality intra cache level timing channel. As a proof of concept, we demonstrate the first key recovery attacks on a constant-time implementation of AES, and a SM4 implementation with cache protection in the current Intel Integrated Performance Primitives (Intel IPP) cryptographic library. Further, we demonstrate the first intra cache level timing attack on SGX by reproducing the AES key recovery results on an enclave that performs encryption using the aforementioned constant-time implementation of AES. Our results show that we can not only use this side channel to efficiently attack memory dependent cryptographic operations but also to bypass proposed protections. Compared to CacheBleed, which is limited to older processor generations, MemJam is the first intra cache level attack applicable to all major Intel processors including the latest generations that support the SGX extension.

I. INTRODUCTION
In cryptographic implementations, timing channels can be introduced by key dependent operations, which can be exploited by local or remote adversaries [1,2]. Modern microarchitectures are complex and support various shared resources, and the operating system (OS) maximizes the resource sharing among concurrent tasks [3,4]. From a security standpoint, concurrent tasks with different permissions share the same hardware resources, and these resources can expose exploitable timing channels. A typical model for exploiting microarchitectural timing channels is for a spy process to cause resource contention with a victim process and to measure the timing of its own or of the victim operations [5,6,7,8]. The observed timing behavior give adversaries strong evidence on the victim's resource usage pattern, thus they leak critical runtime data. Among the shared resources, attacks on cache have received significant attention, and their practicality have been demonstrated in scenarios such as cloud computing [5,8,9,10,11,12]. A distinguishable feature of cache attacks is the ability to track memory accesses with high temporal and spatial resolution. Thus, they excel at exploiting cryptographic implementations with secret dependent memory accesses [2,13,14,15]. Examples of such vulnerable implementations include using S-Box tables [16], and efficient implementations of modular exponentiation [17].
The weakness of key dependent cache activities has motivated researchers and practitioners to protect cryptographic implementations against cache attacks [7,18]. The simplest approach is to minimize the memory footprint of lookup tables. Using a single 8-Bit S-Box in Advanced Encryption Standard (AES) rather than T-Tables makes cache attacks on AES inefficient in a noisy environment, since the adversary can only distinguish accesses between 4 different cache lines. Combining small tables with cache state normalization, i.e., loading all table entries into cache before each operation, defeats cache attacks in asynchronous mode, where the adversary is only able to perform one observation per operation. More advanced side channels such as exploitation of the thread scheduler [19], cache attack on interrupted execution of Intel Software Guard eXtension (SGX) [20], performance degradation [21] and leakage of other microarchitectural resources [22,23] remind us the importance of constant-time software implementations. One way to achieve constant-time memory behavior, is the adoption of small tables in combination with accessing all cache lines on each lookup [7]. The overhead would be limited and is minimized by the parallelism we can achieve in modern processors. Another constant-time approach adopted by some public cryptographic schemes is interleaving the multipliers in memory known as scatter-gather technique [24].
Constant-time implementations have effectively eliminated the first generation of timing attacks that exploit obvious key dependent leakages. The common view is that performance penalty is the only downside which, once paid, there is no need to be further worried. However, this is far from the reality and constant-time implementations may actually give a false sense of security. A commonly overlooked fact is that constant-time implementations and related protections are relative to the underlying hardware [25]. In fact, there are major obstacles preventing us from obtaining true constanttime behavior. Processors constantly evolve with new microarchitectural features rolled quietly with each new release and the variety of such subtle features makes comprehensive evaluation impossible. A great example is the cache bank conflicts attack on OpenSSL RSA scatter-gather implementation: it shows that adversaries with intra cache level resolution can successfully bypass constant-time techniques relied on cacheline granularity [26]. As a consequence, what might appear as a perfect constant-time implementation becomes insecure in the next processor release-or worse-an unrecognized behavior might be discovered, invalidating the earlier assumption.

A. Our Contribution
We propose an attack named MemJam by exploiting false dependency of memory read-after-write, and demonstrate key recovery against two different cryptographic implementations which are secure against cache attacks with experimental results on both regular and SGX environments. In summary:  [7,24], static and runtime analysis [27,28] and cache architecture [29,30,31,32].

B. Experimental Setup and Generic Assumptions
Our experimental setup is a Dell XPS 8920 desktop machine with Intel(R) Core i7-7700 processor running Ubuntu 16.04. The Core i7-7700 has 4 hyper-threaded physical cores. Our only assumptions are that the attacker is able to co-locate on one of the logical processor pairs within the same physical core as the victim. In the cryptographic attacks, the attacker can measure the time of victim encryption. The attacker further knows which cryptographic implementation is used by the victim, but she does not need to have any knowledge of the victim's binary or the offset of the S-Box tables. We will discuss assumptions that are specific to the attack on SGX at Section VI.

II. RELATED WORK
Side channels including power, electromagnetic and timing channels have been studied for a few decades [1,33,34]. Timing side channels can be constructed through the processor cache to perform key recovery attacks against cryptographic operations such as RSA [15], ECDSA [14], ElGamal [9], DES [13] and AES [2,8]. On multiprocessor systems, attacks on the shared LLC-a shared resource among all the coresperform well even when attacker and victim reside in different cores [8]. Flush+Reload, Prime+Probe, Evict+Reload, and Flush+Flush are some of the proposed attack methodologies with different adversarial scenarios [2,11,12]. Performance degradation attacks can improve the channel resolution [19,21]. LLC attacks are highly practical in cloud, where an attacker can identify where a particular victim is located [5,9]. Despite the applicability of LLC attacks, attacks on coreprivate resources such as L1 cache are as important [23,35]. Attacks on SGX in a system level adversarial scenario are notable examples [20,36]. There are other shared resources, which can be utilized to construct timing channels [37]. Exploitation of Branch Target Buffer (BTB) leaks if a branch has been taken by a victim process [22,23,36]. Logical units within the processor can leak information about the arithmetic operations [38,39]. CacheBleed proposes cache bank conflicts and false dependency of memory write-after-read as side channels with intra-cache granularity [26]. However, cache bank conflicts leakage does not exist on current Intel processors, and we verify the authors' claim that the proposed write-after-read false dependency side channel does not allow efficient attacks.
Defense: software and hardware strategies have been proposed such as alternative lookup tables, data-independent memory access pattern, static or disabled cache, and cache state normalization to defend against cache attacks [7]. Scatter-Gather techniques have been adopted by RSA and ECC implementations [24]. In particular, introducing redundancy and randomness to the S-Box tables for AES has been proposed [18]. A custom memory manager [40], relaxed inclusion caches [31] and solutions based on cache allocation technology (CAT) such as Catalyst [29] and vCat [32] are proposed to defend against LLC contention. Sanctum [30] and Ozone [41] are new processor designs with respect to cache attacks. Detectionbased countermeasures have also been proposed using performance counters, which can be used to detect cache attacks in cloud environments [27,42]. MASCAT [28] is proposed to block cache attacks with code analysis techniques. CachD [43] detects potential cache leakage in the production software. Nonetheless, these proposals assume that the adversary cannot distinguish accesses within a cache line. That is, attacks with intra cache-line granularity are considered out-of-scope. Doychev et al. proposed the only software leakage detector that consider full address bits as its leakage model [44].

A. Multitasking
The memory management subsystem shares the dynamic random-access memory (DRAM) among all concurrent tasks, in which a virtual memory region is allocated for each task transparent to the physical memory. Each task is able to use its entire virtual address space without meddling of memory accesses from others. Memory allocations are performed in pages, which each virtual memory page can be stored in a DRAM page with a virtual-to-physical page mapping. The logical processors are also shared among these tasks and each logical processor executes instructions from one task at a time, and switches to another task. Memory write and read instructions work with virtual addresses, and the virtual address is translated to the corresponding physical address to perform the memory operation. The OS is responsible for page directory management and virtual page allocation. The OS assists the processor to perform virtual-to-physical address translation by performing an expensive page walk. The processor saves the address translation results in a memory known as Translation Look-aside Buffer (TLB) to avoid the software overhead introduced by the OS. Intel microarchitecture follows a multistage pipeline and adopts different optimization techniques to maximize the parallelism and multitasking during the pipeline stages [45]. Among these techniques, hyper-threading allows each core to run multiple concurrent threads, and each thread shares all the core-private resources. As a result, if one resource is busy by a thread, other threads can consume the remaining available resources. Hyper-threading is abstracted to the software stack: OS and applications interact with the logical processors.

B. Cache Memory
DRAM memory is slow compared to the internal CPU components. Modern microarchitectures take advantage of a hierarchy of cache memories to fill the speed gap. Intel processors have two levels of core-private cache (L1, L2), and a Last Level Cache (LLC) shared among all cores. The closer the cache memory is to the processor, the faster, but also smaller it is compared to the next level cache. Cache memory is organized into different sets, and each set can store some number of cache lines. The cache line size, which is 64 byte, is the block size for all memory operations outside of the CPU. The higher bits of the physical address of each cache line is used to determine which set to store/load the cache line. When the processor tries to access a cache line, a cache hit or miss occurs respective of its existence in the relevant cache set. If a cache miss occurs, the memory line will be stored to all 3 levels of cache and to the determined sets. Reloads from the same address would be much faster when the memory line exists in cache. In a multicore system, the processor has to keep cache consistent among all levels. In Intel architecture, cache lines follow a write-back policy, i.e, if the data in L1 cache is overwritten, all other levels will be updated. The LLC is inclusive of L2 and L1 caches, which means that if a cache line in LLC is evicted, the corresponding L1 and L2 cache lines will also be evicted [45]. These policies help to avoid stale cached data where one processor reads invalid data mutated by another processor.

C. L1 Cache Bottlenecks
L1 cache port has a limited bandwidth and simultaneous accesses will be block each other. This bottleneck is critical in super-scalar multiprocessor systems. Older processors' generation adopted multiple banks as a workaround to this problem [46], in which each bank can operate independently and serve one request at a time. While this partially solved the bandwidth limit, it creates the cache bank conflicts phenomena which simultaneous accesses to the same bank will be blocked. Intel resolved the cache bank conflicts issue with the Haswell generation [45]. Another bottleneck mentioned in various resources is due to the false dependency of memory addresses with the same cache set and offset [45,46]. Simultaneous read and write with addresses that are multiples of 4 kB is not possible, and they halt each other. The processor cannot determine the dependency from the virtual address, and addresses with the same last 12 bits have the chance to map to the same physical address. Such simultaneous access can happen between two logical processors and/or during the outof-order execution, where there is a chance that a memory write/read might be dependent on a memory read/write with the same last 12 bits of address. Such dependencies cannot be determined on the fly, thus they cause latency.

D. Cache Attacks
Cache attacks can be exploited by adversaries where they share system cache memory with benign users. In scenarios where the adversary can colocate with a victim on the same core, she can attack core-private resources such as L1 cache, e.g., OS adversaries [20,36]. In cloud environment, virtualization platforms allow sharing of logical processors to different VMs; however, attacks on the shared LLC have a higher impact, since LLC is shared across all the cores. In cache timing attacks, the attacker either measure the timing of the victim operations, e.g, Evict+Time [2] or the timing of his own memory accesses, e.g, Prime+Probe [8]. The attacker needs to have access to an accurate time resource such as the RDTSC instruction. In the basic form, attacks are performed by one observation per entire operation. In certain scenarios, these attacks can be improved by interrupting the victim and collecting information about the intermediate memory states. Side channel attacks exploiting cache bank conflicts rely on synchronous resource contention. CacheBleed methodology is somewhat similar to Prime+Probe, where the attacker performs repeated operations, and measures it's own access time [26]. In a cache bank conflicts attack, the adversary repeatedly performs simultaneous reads to the same cache bank and measures their completion time. A victim on a colocated logical processor who access the same cache bank would cause latency to the attacker's memory reads.
In this work, we focus on a critical false dependency mentioned as 4K Aliasing where data that is multiples of 4k apart in the address space is seen as dependent. 4k Aliasing happens due to virtual addressing of L1 cache, where data is accessed using virtual addresses, but tagged and stored using physical addresses. More than one virtual addresses can refer to the same data with the same physical address and the determination of dependency for concurrent memory accesses, requires virtual address translation. Physical and virtual address share the last 12 bits, and any data accesses whose addresses differ in the last 12 bits (i.e. the distance is not 4k) cannot have a dependency. For the fairly rare remaining cases, address translation needs to be done before resolving the dependency, which causes latency. Note that the granularity of the potential dependency, i.e. whether two addresses are considered "same", depends also on the microarchitecture, as dependencies can occur at the word or cache line granularity (i.e. ignoring the last 2 or last 6 bits of the address, respectively). These rare false dependencies due to 4K aliasing can be exploited to attack memory, since the attacker can deliberately process falsely dependent data by matching the last 12 bits of his own address with a security critical data inside a victim process.
4K Aliasing has been mentioned in various places as an optimization problem existing on all major Intel processors [45,46]. We verify the results of Yarom et al. [26], the only security related work regarding false dependencies, which exploited write-after-read dependencies. The resulting timing leakage by write stall after read is not sufficient to be used in any cryptographic attack. MemJam exploits a different channel due to the false dependency of read-afterwrite, which causes a higher latency and is thus simply observable. Intel Optimization Manual highlights the readafter-write performance overhead in various sections [45]. As described in Section 11.8, this hazard occurs when a memory write is closely followed by a read, and it causes the read to be reissued with a potential 5 cycles penalty 1 . In Section B.1.4 on memory bounds, write operations are treated under the store bound category. In contrast to load bounds, Top-down Microarchitecture Analysis Method (TMAM) 2 reports store bounds as fraction of cycles with low execution port utilization and small performance impact. These descriptions in various sections highlight that read-after-write stall is considered more critical than write-after-read stall.

A. Memory Dependency Fuzz Testing
We performed a set of experiments to evaluate the memory dependency behavior between two logical processors. In these experiments, we have thread A and B running on the same physical core, but on different logical processors, as shown in Figure 1. Both threads perform memory operations; only thread B measures its timing and hence the timing impact of introduced false dependencies.
Read-after-read (RaR): In the first experiment, the two logical threads A and B read from the same shared cache and can potentially block each other. This experiment can reveal cache bank conflicts, as used by CacheBleed [26]. B uses Listing 1 to perform read measurements and A constantly reads from different memory offsets and tries to introduce conflicts. A reads from three different type of offsets: (1) Different cache line than B, (2) same cache line, but different offset than B, and (3) same cache line and same offset as B. As depicted, there is no obvious difference between the histograms for three cases in Figure 2a verifying the lack of cache bank conflicts on 7th generation CPUs.
Write-after-read (WaR): The histogram results for the second experiment on false dependency of write-after-read is 1 LD_BLOCKS_PARTIAL.ADDRESS_ALIAS Performance Monitoring Unit (PMU) event counts the number of times reads were blocked. 2   shown in Figure 2b, in which the cache line granularity is obvious. Thread A constantly reads from different type of memory offsets, while thread B uses Listing 2 to perform write measurements. The standard deviation for conflicted cache line (blue) and conflicted offset (red) between thread A and B is distinguishable from the green bar where there is no cache line conflict. This shows a high capacity cache granular behavior, but the slight difference between conflicted line and offset verifies the previous results stating a weak offset dependency [26].
Read-after-write (RaW): Figure 2c shows an experiment on measuring false dependency of read-after-write, in which, thread A constantly writes to different memory offsets. Thread B uses Listing 1 to perform read measurements. Accesses to three different types of offsets are clearly distinguishable. The conflicted cache line accesses (blue) are distinguishable from non-conflicted accesses (green). More importantly, conflicted accesses to the same offset (red) are also distinguishable from conflicted cache line accesses, resulting in a side channel with intra cache-line granularity. There is an average of 2 cycle penalty if the same cache line has been accessed, and a 10 cycle penalty if the same offset has been accessed. Note that the word offsets in our platform have 4 byte granularity. From an adversarial standpoint, this means that an adversary learns about bits 2-11 of the victim memory access, in which 4 bits (bits 2-5) are related to intra cache-line resolution, and thus goes beyond any other microarchitectural side channels known to exist on 6th and 7th generation Intel processors ( Figure 5).
Read-after-weak-Write (RawW): In this experiment on the read-after-write conflicts, we followed a less greedy strategy on the conflicting thread. Rather than constantly writing to the same offset, A executes write instructions to the same offset with some gaps filled with other memory accesses and instructions. As shown in Figure 3, the channel dramatically became less effective. This tells us that causing read access penalty will be more effective with constant writes to the same offset without additional instruction. In this regard, we will use Listing 3 in our attack to achieve the maximum conflicts.  Read-after-Write Latency: In the last experiment, we tested the delay of execution over a varying number of conflicting reads. We created a code stub that includes 64 memory read instructions and a random combination of instructions between memory reads to create a more realistic computation. The combination is chosen in a way to avoid unexpected halts and to maintain the parallelism of all read operations. We measure the execution time of this computation on B, while A is writing to a conflicting offset. First, we measured the computation with 64 memory reads to addresses without conflicts. Our randomly generated code stub takes an average of 210 cycles to execute. On each step of the experiments, as shown in Figure 4, we change some of the memory offsets to have the same last 12 bits of address as of Aś conflicting write offset. We observe a growth on read accesses' latency by increasing the number of conflicting reads. Figure 4 shows the results for a number of experiments. In all of them, the overall execution time of B is strongly dependent on the number of conflicting reads. Hence, we can use the RaW dependency to introduce strong timing behavior using bits 2-11 of a chosen target memory address.

V. MemJam CORRELATION ATTACK
MemJam uses read-after-write false dependencies to introduce timing behavior to otherwise constant-time implementations. The resulting latency is then exploited using a correlation attack. MemJam proceeds with the following steps: 1) Attacker launches a process constantly writing to an address using Listing 3 where the last 12 bits match the virtual memory offset of a critical data that is read in the victim's process. 2) While the attacker's conflicting process is running, attacker queries the victim for encryption and records a ciphertext and execution time pair of the victim. Higher time infers more accesses to the critical offset. 3) Attacker repeats the previous step collecting ciphertext and time pairs. The attack methodology resembles the Evict+Time strategy originally proposed by Tromer et al. [7], except that the attacker uses false dependencies rather than evictions to slow down the target and that the slowdown only applies to an 4-byte block of a cache line. Furthermore, all of the victim's accesses addresses with the same last 12 bits are slowed down while an eviction only slows the first memory access(es). Based on the intra cache level leakage in Figure 5, we divide a 64 byte cache line into 4-byte blocks and hypothesize that the access counts to a block are correlated with the running time of victim, while the attacker jams memory reads to that block, i.e, the attacker expects to observe a higher time when there are more accesses by the victim to the targeted 4-byte block and lower time when there are lower number of accesses. Based on this hypothesis, we apply a classical correlation based side-channel approach [33] to attack implementations of two different block ciphers, namely AES and SM4, a standard cipher. SM4 among AES, Triple DES, and RC4 are the only available symmetric ciphers as part of Intel's IPP crypto library [49] 3 . Both implementations have optimizations to hinder cache attacks. In fact, the AES implementation features a constant cache profile and can thus be considered resistant to most microarchitectural attacks including cache attacks and high-resolution attacks as described in [20]. MemJam can still extract the keys from both implementations due to the intra cache-line spatial resolution as depicted in Figure 5. We describe the targeted implementations next, as well as the correlation models we use to attack them.

A. Attack 1: IPP Constant-Time AES
AES is a cipher based on substitution permutation network (SPN) with 10 rounds supporting 128-bit blocks and 128/192/256-bit keys [53]. The SubBytes is a security-critical operation and the straightforward way to implement AES SubBytes operation efficiently in software is to use lookup tables. SubBytes operates on each byte of cipher state, and it maps an 8-bit input to an 8-bit output using a non-linear function. A precomputed 256 byte lookup table known as S-Box can be used to avoid recomputation. There are efficient implementations using T-Tables that output 32-bit states and combine SubBytes and MixColumns operations. T-Table implementations are highly vulnerable to cache attacks. During AES rounds, a state table is initiated with the plaintext, and it holds the intermediate state of the cipher. Round keys are mixed with states, which are critical S-Box inputs and the main source of leakage. Hence, even an adversary who can partially determine which entry of the S-Box has been accessed is able to learn some information about the key.
Among the efforts to make AES implementations more secure against cache attacks, Safe2Encrypt_RIJ128 function from Intel IPP cryptographic library is noteworthy. This implementation is the only production-level AES software implementation that features true cache constant-time behavior and does not utilize hardware extensions such as AES-NI or SSSE3 instruction sets. This implementation is also part of the Linux SGX SDK [54] and can be used for production code if the SDK is compiled from the scratch, i.e., it does not use prebuilt binaries. We verified the match between the implementation in Intel IPP binary and SGX SDK source code  Figure 6. This implementation protects AES against any kind of cache attacks, as the attacker sees a constant cache access pattern: The S-Box table only occupies 4 cache lines, and on each SubBytes operation, all of them will sequentially be accessed. This implementation can be executed in less than 2000 cycles on a recent laptop processor. This is fast enough for many cryptographic applications, and it provides full protection against cache attacks, even if the attacker can interrupt the execution pipeline.
Based on MemJam 4-byte granular leakage channel, and the design of AES, we can create a simple correlation model to attack this implementation. The accessed table index of the last round for a given ciphertext byte c and key byte k is given as index = S −1 (c ⊕ k). We define matrix A for the access profile where each row corresponds to a known ciphertext, and each column indicates the number of accesses when index < 4. While we assume that the attacker causes slowdowns to the first 4-byte block of S-Box, we define matrix L for leakage where each row corresponds to a known ciphertext and each column indicates the victim's encryption time. Then our correlation attack is defined as the correlation between A and L, in which the higher the number of accesses, the higher the running time. Our results will verify that correlation is high, even though the implementation has dummy accesses to the monitored block. These can be ignored as noise, slightly reducing our maximum achievable correlation. AES Key Recovery Results on Synthetic Data: We first verified the correctness of our correlation model on synthetic data using a noise free leakage (generated by PIN [55]). For each of the 16 key bytes using a vector that matches exactly to the number of accesses to the targeted block of S-Box for different ciphertexts, all the correct key bytes will have the highest correlation after 32,000 observations with the best and worst correlations of 0.046 and 0.029 respectively. AES Key Recovery Results using MemJam: Relying on the verification of Synthetic Data, we plugged in the real attack data vector, which consists of pairs of ciphertext and time measured through repeated encryption of unknown data blocks. Results on AES show that we can effectively exploit the timing information, and break the so-called constanttime implementation. The victim execution of AES encryption function takes about 1700 and 2000 cycles without and with an active thread on the logical processor pair, respectively. The target AES implementation performs 640 memory accesses to the S-Box, including dummy accesses. If the spy thread constantly writes to any address that collides with a S-Box block offset, the time will increase to a range between 2000 and 2300 cycles. The observed variation in this range has a correlation with the number of accesses to that block. Figure 7 shows the linear relationship between the correlation of synthetic data and real attack data for one key byte after 2 million observations. Most of the possible key candidates for a target key byte have a matching peak and hill between the two observations. The highest correlation points in both cases declare the correct key byte (0.038 red, 0.014 blue). The quantitative difference is due to the expected noise in the real measurements. Figure 8 shows the correlation of 4 different key bytes after 2 million observations with the correct key bytes having the highest correlations. Our repeated experiments with different keys and ciphertexts show that 15 correct key bytes have the highest correlation ranks, and there is only the key byte at index 15 that has a high rank but not necessarily the highest. Figure 9 shows the key ranks over the number of observations. Key byte ranks take values between 1 and 256, where 1 means that the correct key byte is the most likely one. As it is shown, after only 200,000 observations, the key space is reduced to a computationally insecure space and a key can be found with an efficient key enumeration method [56]. After 2 million observations, all key bytes except one of them are recovered. The non-optimized implementation of this attack processes this amount of information in 5 minutes.

B. Attack 2: IPP Cache Protected SM4
SM4 is a block cipher 4 that features an unbalanced Feistel structure and supports 128-bit blocks and keys [57]. SM4 design is known to be secure and no relevant cryptanalytic attacks exist for the cipher. Figure 10 shows a schematic of one round of SM4. T1-T4 are 4 × 32-bit state variables of SM4. Within each round, the last three state variables and a 32-bit round key are mixed, and each byte of the output will be replaced by a non-linear S-Box value. After the non-linear layer, the combined 32-bit output of S-Boxes x are diffused using the linear function L. The output of L is then mixed with the first 32-bit state variable to generate a new random 32-bit state value. The same operation is repeated for 32 rounds, and each time a new 32-bit state is generated as the next round T4 state. The current T2, T3, T4 are treated as T1, T2, and T3 for the next round. The final 16 bytes of the entire state after the last round produce the ciphertext. SM4 Key schedule produces 32 × 32-bit round keys from a 128-bit key. Since the key schedule is reversible, recovering 4 repeated round keys provides enough entropy to reproduce the cipher key.
All the SM4 operations except the S-Box lookup are performed in 32-bit word sizes. Hence, SM4 implementation is both simple and efficient on modern architectures. We chose the function cpSMS4_Cipher from Intel IPP Cryptography library. Our target is based on the straightforward cipher algorithm with addition of S-Box cache state normalization. We recovered this implementation through reverse engineering of Intel IPP binaries. The implementation preloads four values from different cache lines of S-Box before the first round, and it mixes them with some dummy variables, forcing the processor to fill the relevant cache lines with S-Box table. This cache prefetching mechanism protects SM4 against asynchronous cache attacks. On our experimental setup, the implementation runs in about 700 cycles, which informs us that this implementation maintain a high speed while secure against asynchronous attacks. Interrupted attacks that leak intermediate states would not be as simple, since the interruption need to happen faster than 700 cycles. We will further discuss the difficulty of correlating any cache-granular information, even if we assume the adversary can interrupt the encryption and perform some intermediate observations.
Single-round attack on SM4: We define c 1 , c 2 , c 3 , c 4 as the four 32-bit words of a ciphertext and k r as the secret round key for round r. We recursively follow the cipher structure Fig. 10: SM4 Feistel Structure: In each round, the last three words from the state buffer and the round key will be added. Each byte of the output will be replaced by S-Box lookup. The function L performs a linear bit permutation. from the last round with our ciphertext words as inputs, and write the last 5 rounds' relations as Equation 1. In each round, x i r is the S-Box index, and i is the byte offset of the 32bit word x r . With a similar approach to the attack on AES, we define matrix A for the access profile, where each row corresponds to a known ciphertext, and each column indicates the number of accesses when x i r < 4. Then we define the matrix L for the observed timing leakage and the correlation between A and L similar to the AES attack. In contrast, S-Box indices in the AES attack are defined based on a nonlinear inverse S-Box operation of key and ciphertext, which eventually maps to all possible key candidates. In SM4, the index x i r is defined before any non-linear operation. As a result, an attack capable of distinguishing accesses of 4 out of 256 S-Box entries reveals only 6 bits per key byte. In the mentioned relations, performing the attack using this model on x i 32 , recovers the 6 most significant bits of each key byte i for the last round key (Total of 24 out of the 32 bits).
Multi-round attack on SM4: The relationship for round 31 can be used not only to recover 6-bit key candidates of round 31, but also the remaining unknown 8 bits of entropy for round 32. This is due to the linear property of function L and the recursive nature of newly created state variables. After the attack on round 32, similar to the round key, we only have certainty about 24 bits of the new state variable d 1 , but this information will be propagated as the input to round 31. The next round of attack for key byte of round 31 needs more computation to process an 8 bit of unknown key and 8 bit of unknown state (total of 16 bit), but this is computationally feasible, and the 8-bit key from round 32 with highest correlation can be recovered by attacking the S-Box indices in round 31. We recursively applied this model to each round resulting a correlation attack with the following steps, which gives us enough entropy to recover the key: 1) x32 → 24 bits of k32.
2) x31 → 24 bits of k31 + 8 bits of k32 3) x30 → 24 bits of k30 + 8 bits of k31 4) x29 → 24 bits of k29 + 8 bits of k30 5) x28 → 24 bits of k28 + 8 bits of k29 6) Recover the key from k32, k31, k30, k29 SM4 Key Recovery Results on Synthetic Data: Our noisefree synthetic data shows that 3000 observations are enough to find all correct 6-bit and 8-bit round key candidates with the highest correlations. Even in an interrupted cache attack or without cache protection, targeting this implementation using a cache-granular information would be much harder and inefficient due to the lack of intra cache-line resolution. If we only distinguish the 64-byte cache lines out of a 256-byte S-Box, we only learn 4 × 2-bit (total of 8 bits) out of 32-bit round keys, and on each round, we need to solve 8 bits + 24 bits of uncertainty. Although solving 32-bit of uncertainty sounds possible for a noise-free data, it is computationally much harder in a practical noisy setting. Our intra cache line leakage can exploit SM4 efficiently in a known-ciphertext scenario, while the best efficient cache attack on SM4 requires chosen plaintexts [58].
SM4 Key Recovery Results using MemJam: The results on SM4 show even more effective key recovery against this implementation compared to AES. Figure 11 shows the correlation for 6-bit round keys after 5 rounds of repeated attack, and the correlation for 12-bit key candidates can be seen in Figure 12. The attack expects assurance on the correct key candidates for each round of attack before proceeding to the next round due to the recursive structure of SM4. In our experiment using real measurement data, we have noticed that 40,000 observations are sufficient to have assurance of correct key candidates with the highest correlations. Our implementation of the attack can recover the correct 6-bit and 8-bit keys, and it takes about 5 minutes to recover the cipher key. In Figure 12,  Fig. 12: The accumulated correlations for SM4 8-bit keys after 5 rounds using 40,000 observations. Each correct candidate has the highest correlation.
have a very high aggregated correlation compared to the 6-bit candidates.

VI. MemJamING SGX ENCLAVE
Intel SGX is a trusted execution environment (TEE) extension released as part of Skylake processor generation [54]. The main goal of SGX is to protect runtime data and computation from system and physical adversaries. Having said that, SGX must remain secure in the presence of malicious OS, thus modification of OS resources for facilitation of side-channel attacks is relevant and within the considered threat model. Previous works demonstrate high resolution attacks with 4 kB page [59,60] and 64 B cache line granularity [20,61]. Intel declared microarchitectural leakages out of scope for SGX, thus pushing the burden of writing leakage free constant-time code onto enclave developers. Indeed, Intel follows this design paradigm and ensures constant cache-line accesses for its AES implementation, making it resistant to all previously known microarchitectural attacks in SGX.
In this section, we verify that MemJam is also applicable to SGX enclaves, as there is no fundamental microarchitectural changes to resist against memory false dependencies. We repeat the key recovery results against Intel's constant-time AES implementation after moving it into an SGX enclave. The results verify the exploitability of intra cache level channel against SGX secure enclaves. In fact, the attack can be reproduced in a straightforward manner. The only difference is a slower key recovery due to the increased measurement noise resulting from the enclave context switch.

A. SGX Enclave Experimental Setup and Assumptions
Following the threat model of CacheZoom [20,36], we assume that the system adversary has control over various OS resources. Please note that SGX was exactly designed to thwart the threat of such adversaries. The adversary uses its OS-level privileges to decrease the setup noise: We isolate one of the physical cores from the rest of the running tasks, and dedicate its logical processors to MemJam write conflict thread and the victim enclave. We further disable all the non-maskable interrupts on the target physical core and configure the CPU power and frequency scaling to maintain a constant frequency. We assume that the adversary can measure the execution time of an enclave interface that performs encryption, and the enclave interface only returns the ciphertext to the insecure environment. Both plaintexts and the secret encryption key are generated at runtime using RDRAND instruction, and they never leave the secure runtime environment of SGX enclave. The RDTSC instruction cannot be used inside an enclave. The attacker uses it right before the call to the enclave interface and again right after the enclave exit. As a result, the entire execution of the enclave interface, including the AES encryption, is measured. As before, an active thread causing read-after-write conflicts to the first 4-byte of AES S-Box is executed on the neighboring virtual processor of the SGX thread.

VII. DISCUSSION
The Safe2Encrypt_RIJ128 AES implementation has been designed to achieve a constant cache access profile by ensuring that the same cache lines are accessed every time regardless of the processed data. The 4-byte spatial resolution of MemJam, however, thwarts this countermeasure by providing intra cache-line resolution. One approach to restore security and protect against MemJamis to apply constant memory accesses with a 4-byte granularity. That would require accessing every fourth byte of the table for each memory lookup for the purpose of maintaining a uniform memory footprint. At that point, it might be easier to just do a true constant time implementation and access all entries each time, resting assured that there is no other effect somewhere hidden in the microarchitecture resulting in a leak with byte granularity. As we discussed in the related work, system-wide defense proposals that apply to cache attacks are not relevant and cannot detect or prevent MemJam. Also, an adversary performing the MemJam attack does not need to know about the offset of S-Box in the binary, since she can simply scan the 10-bits address entropy through introducing conflicts to different offsets and measuring the timing of victim. This is important when it comes to obfuscated binaries or scenarios, where the offset of S-Box is unknown.
Hardware based, e.g, AES-NI or hardware assisted, e.g, SIMD-based bit-sliced implementations of AES or SM4 should exclusively be used to protect the targeted implementation in an efficient manner. Intel IPP has different variants optimized for various generations of Intel instruction sets [62]. Intel IPP features different implementations of AES as well as SM4 in these variants. A list of these variants and implementations are given in Table I. All of them have at least one vulnerable implementation. In cases where there is an implementation based on the AES-NI instruction set (or SSSE3 respectively), the library falls back to the basic version at runtime if the instruction set extensions are not available. The usability of this depends on the compilation and runtime configuration. Developers are allowed to statically link to a more risky variants [63], and they need to assure not to use the vulnerable versions during linking. These ciphers should be avoided in cases where the hardware does not provide support, e.g, Core and Nehalem does not support AES-NI, e.g, AES-NI can be disabled in some BIOS. After all, the current hardware support for cryptographic primitives are restricted and if any other cipher is demanded, this limitation and vulnerability endangers the security of cryptographic systems. A temporary workaround to defend against the source of leakage on current Intel microarchitectures is to disable hyper-threading.
Prior to MemJam it might have seemed reasonable to design SGX enclaves under the paradigm that constant cache line accesses result in leakage-free code. However, the increased 4-byte intra cache-line granularity of MemJam shows that only code with true constant-time properties, i.e. constant execution flow and constant memory accesses can be expected to have no remaining leakage on modern microarchitectures. Responsible Disclosure We have informed the Intel Product Security Incident Response Team of our findings on August 2nd, 2017. They have acknowledged the receipt and are currently reviewing our findings.

VIII. CONCLUSION
This work proposes MemJam, a new side-channel attack based on false dependencies. For the first time, we discovered new aspects of this side channel and its capabilities, and show how to extract secrets from modern cryptographic implementations. MemJam uses false read-after-write dependencies to slow down accesses of the victim to a particular 4-byte memory blocks within a cache line. The resulting latency of otherwise constant-time implementations was exploited with state-of-the art timing side-channel analysis techniques. We  showed how to apply the attack to two recent implementations of AES and SM4. According to the available resources, the source of leakage forMemJam attack is present in all Intel CPU families released in the last 10 years [45,46]. Our results also verified that MemJam is the first intra cache level attack applicable to SGX enclaves. Table II highlights the availability of the cache bank conflicts and 4k aliasing leakage source. MemJam is another piece of evidence that modern microarchitectures are too complex and constanttime implementations cannot simply be trusted with wrong assumptions about the underlying system. The remaining datadependent addressing within a cache line is exploitable.