A Survey of Techniques for Improving Security of GPUs <s> Timing side-channel attack <s> Graphics Processing Units (GPUs) have become mainstream parallel computing devices. They are deployed on diverse platforms, and an increasing number of applications have been moved to GPUs to exploit their massive parallel computational resources. GPUs are starting to be used for security services, where high-volume data is encrypted to ensure integrity and confidentiality. However, the security of GPUs has only begun to receive attention. Issues such as side-channel vulnerability have not been addressed. The goal of this paper is to evaluate the side-channel security of GPUs and demonstrate a complete AES (Advanced Encryption Standard) key recovery using known ciphertext through a timing channel. To the best of our knowledge, this is the first work that clearly demonstrates the vulnerability of a commercial GPU architecture to side-channel timing attacks. Specifically, for AES-128, we have been able to recover all key bytes utilizing a timing side channel in under 30 minutes. <s> BIB001 </s> A Survey of Techniques for Improving Security of GPUs <s> Timing side-channel attack <s> To avoid information leakage during program execution, modern software implementations of cryptographic algorithms target constant timing complexity, i.e., the number of instructions executed does not vary with different inputs. However, many times the underlying microarchitecture behaves differently when processing varying data inputs, which covertly leaks confidential information through the timing channel. In this paper, we exploit a novel fine-grained microarchitectural timing channel, stalls that occur due to bank conflicts in a GPU's shared memory. Using this attack surface, we develop a differential timing attack that can compromise table-based cryptographic algorithms. We implement our timing attack on an Nvidia Kepler K40 GPU, and successfully recover the complete 128-bit AES encryption key using 10 million samples. We also evaluate the scalability of our attack method by attacking a 8192-thread implementation of the AES encryption algorithm, recovering some key bytes using 1 million samples. <s> BIB002 </s> A Survey of Techniques for Improving Security of GPUs <s> Timing side-channel attack <s> Graphics processing units (GPUs) are becoming default accelerators in many domains such as high-performance computing (HPC), deep learning, and virtual/augmented reality. Recently, GPUs have also shown significant speedups for a variety of security-sensitive applications such as encryptions. These speedups have largely benefited from the high memory bandwidth and compute throughput of GPUs. One of the key features to optimize the memory bandwidth consumption in GPUs is intra-warp memory access coalescing, which merges memory requests originating from different threads of a single warp into as few cache lines as possible. However, this coalescing feature is also shown to make the GPUs prone to the correlation timing attacks as it exposes the relationship between the execution time and the number of coalesced accesses. Consequently, an attacker is able to correctly reveal an AES private key via repeatedly gathering encrypted data and execution time on a GPU. In this work, we propose a series of defense mechanisms to alleviate such timing attacks by carefully trading off performance for improved security. Specifically, we propose to randomize the coalescing logic such that the attacker finds it hard to guess the correct number of coalesced accesses generated. To this end, we propose to randomize: a) the granularity (called as subwarp) at which warp threads are grouped together for coalescing, and b) the threads selected by each subwarp for coalescing. Such randomization techniques result in three mechanisms: fixed-sized subwarp (FSS), random-sized subwarp (RSS), and random-threaded subwarp (RTS). We find that the combination of these security mechanisms offers 24- to 961-times improvement in the security against the correlation timing attacks with 5 to 28% performance degradation. <s> BIB003
In this section, we discuss works that demonstrate timing side-channel attacks along with their countermeasures. Table 5 highlights their similarities and differences. Jiang et al. BIB002 present a differential timing attack which leverages timing variability due to ShM bank conflicts to recover AES encryption key. The AES-128 algorithm includes ten rounds of operations and in each round, a 16B key is used, which is termed as the 'round-key'. From any round key, an adversary can obtain the original 16B key. Their attack focuses on leaking the last-round key. Figure 4 shows the address division for mapping to ShM. Accesses going to the same bank cause conflict and due to the SIMT execution model, the bank seeing the highest number of conflicts determines the execution time of the memory instruction. Hence, the execution time of an ShM instruction depends on the memory addresses and consequent bank-conflicts. They use a kernel which loads data from ShM using a thread-warp. The kernel is written in a manner to create conflicts among the threads. The address accessed by each thread decides the number of conflicts and hence, the completion time of the load operation. In the AES algorithm, memory access for reading the lookup table depends on the value of the key. Since the table is word-aligned, the completion time of a table access for a warp is expected to vary linearly with the number of conflicts generated by the threads. The overall encryption time also depends on the conflicts caused by table accesses. Due to the relation between table-index and round-key, the number of conflicts in one round of AES operation for a warp can be predicted by guessing the round-key. If an adversary uses many plaintexts and correlates the encryption latency with the number of conflicts, then, this correlation should be high for a correct key guess and low for wrong key guesses. This is the basis of launching differential timing attack. Since each table access uses one state byte, each round key byte can be separately attacked. For each guess of the byte value (between 0 to 255), they compute the correlation between average timing and number of bank conflicts. Based on this, a correct key byte is distinguished from incorrect ones. In practice, they compute average timing for data samples leading to two and four conflicts. Then, the "difference of means" between them is expected to be twice the penalty for one conflict, which is 19 (∼2*9.8) cycles, where 9.8 cycles is average penalty for one conflict. Proceeding in this way, they recover all the 16 bytes of the key. Their attack is also applicable to other table-based cryptographic algorithms. To mitigate their attack, use of ShM can be completely avoided, or the use of ShM data can be reduced to avoid all bank conflicts. They also note that encryption time measurements obtained on GPU are more accurate than that on CPU due to the data-transfer and initialization operations. Further, they test the scalability of their attack by attacking an 8192-thread AES implementation. In such a real scenario, the timing has to be measured on CPU since the kernel code running on GPU cannot be modified to insert timing routines. Also, since the scheduling of blocks/warps on GPU SMs is not known, launching an attack to recover accurate key becomes challenging. Jiang et al. BIB001 show a correlation timing attack on GPU to completely recover the AES key. They use 128-bit "electronic codebook" (ECB) mode AES encryption with T-tables, which uses 16B key to encrypt a 16B block. Each thread performs one block-encryption. They store the keys in the constant cache. All threads of a warp simultaneously read the same round-key. T-tables are stored in GlM since access to them leads to different memory requests which are serialized and hence, storing them in the constant cache would lead to resource wastage. They record time in two ways: clean measurement, where the warp execution time inside a kernel can be measured, and noisy measurement, where the latency of incoming/outgoing messages can be measured. They note that the AES algorithm issues memory requests for loading its T-table entries, whose addresses depend on the plaintext and encryption key. Under SIMT paradigm, a load instruction of a warp generates one memory request from each of its 32 threads. These requests are coalesced and merged with the requests queued in miss status holding register (MSHR). The time incurred in serving the 32 memory address requests of a warp scales linearly with the number of unique cache line requests. Given this high correlation, memory addresses (and hence, the key) can be inferred from the timing measurements. Specifically, in the last round of AES, each table index can be obtained from one byte of the key and corresponding byte of ciphertext, irrespective of other bytes of ciphertext. Using this, each byte can be individually guessed. For each key guess, they compute number of coalesced accesses (NCAs) for every 32-block message, and then, find the correlation of timing with the NCAs. For a correct key-byte guess, the NCA is correct and hence, the correlation is highest, otherwise it is low. From this, the correct key can be estimated. They note that with an unoptimized binary, the correlation is even higher. With no optimizations, the CUDA instructions are not reordered. Hence, a table access gets stalled due to data dependency, which makes timing measurements more predictable. Their attack can recover all key bytes of AES-128 in 30 minutes. Under noisy measurements, only 10 out of 16 key bytes are recovered. However, by increasing the number of measurements and using noise-reduction strategies, all the 16 key bytes are recovered and thus, the addition of noise does not fully mitigate the attack. To mitigate these attacks, more noise/randomness can be added to timing measurements and the key can be frequently changed. Also, the mapping of the table-lookup index to cache line can be randomized, which prohibits the attacker from deducing the number of unique cache line requests generated. Kadam et al. BIB003 note that the determinism in coalescing mechanism leads to a security vulnerability. They assume the same attack model as Jiang et al. BIB001 . They note that the execution time of last-round and overall execution time have a high correlation with last round coalesced accesses. Based on this, the correct key can be found as one showing the highest correlation. They assume that the attacker can observe last-round execution time and thus, launch a stronger attack. Also, use of last round execution time allows them to evaluate their technique on the simulator and experiment with different coalescing policies. Correlation timing attack exploits the deterministic nature of memory access coalescing, from which the number of coalesced accesses (NCA) can be accurately inferred. Disabling coalescing thwarts this attack, but exacerbates data-migration and energy overheads. GPU AES implementation leaks information due to two reasons. Firstly, coalescing groups all threads of a warp in a single subwarp which makes it easy to infer NCA by (1) finding the table indices and (2) finding the number of memory blocks (i.e., NCA), based on the sequential mapping of table entries to memory blocks of known size. Secondly, the grouping-order of the thread does not influence coalescing since all threads of a warp are considered together for coalescing. On performing coalescing at the subwarp level, the thread-grouping order affects NCA, depending on the threads falling into the same subwarp. Figures 5(a)-(b) illustrate the impact of subwarps on memory coalescing. For simplicity, assume that a warp has four threads, which may be grouped in a single subwarp ( Figure 5(a) ) or two subwarps ( Figure 5(b) ). Each thread generates one memory access request. With a single subwarp, the requests from the second and third thread are coalesced and thus, a total of three coalesced accesses are generated. On using two subwarps, coalescing is performed separately for each subwarp. Each subwarp generates two accesses, for a total of four accesses. Their techniques tackle these limitations to reduce the correlation and make it difficult to infer the last round key bytes. The first technique, termed "fixed-size subwarps" (FSS) changes the number of subwarps since without knowing this, an adversary may not accurately estimate NCA. With increasing number of subwarps, the variance in NCA reduces, which also weakens the correlation. The limitation of this technique is that, since different values of subwarp-count lead to significantly different execution time, an adversary can guess the subwarp-count by repeatedly measuring the execution times. The second technique, termed "random-sized subwarp" (RSS), randomizes the number of threads per subwarp while keeping the total number of threads per warp still constant, i.e., 32. This makes it difficult for an adversary to guess NCA even if he knows the number of subwarps. The third technique, named "randomthreaded subwarp" (RTS) randomizes the threads which form a subwarp and thus, brings further randomness in NCA. The third technique can be combined with previous two techniques. Figures 5(c) and 5(d) show examples of FSS+RTS and RSS+RTS, respectively. With FSS+RTS, both subwarps have 2 threads, but they are not mapped in order, e.g., subwarp 1 has threads 1 and 3, and not threads 2 and 3. Hence, four coalesced accesses are produced. With RSS+RTS, first and second subwarps have 1 and 3 threads, respectively. This changes the mapping of one thread, viz., thread 0 is now mapped to subwarp 1. Hence, three coalesced accesses are generated. Clearly, RSS+RTS provides randomness for stronger security. For the example shown in Figure 5(d) , RSS+RTS also provides the benefit of reducing NCA, however, in general, it may not always reduce NCA. Their techniques improve GPU security significantly and allow achieving a tradeoff between security and performance loss.