Cache-based side channel attack on AES in Cloud
January - May 2014 | RV College of Engineering | Team size : 3
Introduction: With the increase in usage of cloud, new vulnerabilities have been uncovered which are unique to such systems. The key to a cloud computing environment is hardware virtualization. This consists of multiple instances of virtual machines which utilize the resources on a physical machine. Overlapping usage of physical machine resources such as memory cache by the virtual machines leads to improvement in the use of computing resources in terms of energy consumption and cost effectiveness. This sharing of resources can be used to create cache based side channels which promotes the risk of leakage of information across virtual machines.
Set up a private cloud environment using open source software OpenStack.
Demonstrate a cache based side channel attack between virtual machines where a malicious virtual machine owned by the attacker extracts 128-bit AES encryption key from a victim virtual machine which has been spawned on the same physical machine by performing cache pattern analysis.
Two techniques for mitigating this attack by disrupting the cache access patterns during the encryption of the algorithm.
The plaintext that has been encrypted using AES algorithm is known to the attacker.
The attacker knows where the victim’s lookup tables reside in memory.
From the reduced group of affected cache sets, the attacker knows exact 16 cache sets affected by AES after permutation.
Setting up OpenStack : OpenStack is an open source software that is used for setting up Private cloud. This module forms the basis of the entire paper. The side channel attack is shown among the virtual machines created in this private cloud. The shared cache theory is based on the OpenStack architectural design. The services for the compute and controller nodes are enabled which are required for creating and running instances. The Compute and Controller nodes are configured and many services are enabled for the proper functioning of the cloud. The Virtual machines are created in the compute nodes based on the image available.
AES Encryption Algorithm : AES (Advanced Encryption Standard) is a symmetric key algorithm. The algorithm supports a key size of 128,192 or 256 bits. In the paper we use keys of size 128 bits. The round function is repeated fixed number of times usually 10 for key size of 128 bits. This is required to encrypt a plaintext of 128 bits to a cipher text of 128 bits. The 16 byte plaintext is represented as 4x4 array. Each round has four steps- Byte substitution, Row Shift, Column Mixing and a Round key operation. These operations are very expensive hence these are replaced by inexpensive lookup tables which increases the speed of encryption and decryption. There are four lookup tables say t0, t1, t2 and t3. In the function the initial 4 indices obtained by XORing the plaintext and the key is 4 bytes each. These are used in the first round of AES where 16 values of the lookup table corresponding to the 16 indices are accessed. From each lookup table maximum of 4 memory accesses are possible in the first round. These 16 memory accesses affect a maximum of 16 cache sets.
Cache Access Pattern Analysis : The attacker clears the cache and fills the whole cache by reading from contiguous array of size equal or more than the size of the cache. The number of clock cycles required to read the array is measured before and after filling the cache. The shared cache is affected when the victim runs the AES algorithm. Again when the array is re-read the clock cycle is measured which is now altered. Depending upon the variation in the clock cycles the cache access is analyzed. The initial number of 4096 cache sets is reduced based on the known lookup table addresses. The cache sets that are affected by running the AES algorithm is required for extraction of the key. All the cache sets which had a negative drop or which remained constant even after the victim runs the AES algorithm are rejected. Further, those which had a very small positive change in the clock cycles are rejected as the difference is less than what is responsible for cache miss. This is done multiple times to get accurate result.
Extraction of AES key : There is a very close relationship among the Lookup table indices and the AES encryption key. The non-accessed indices can be found from the non-accessed cache sets and this can be obtained by the cache pattern analysis. The key is of 16 bytes and each byte can take 256 values. In the method used, for each byte all those not possible values are rejected. This is done repeatedly using different plaintext and more values for each byte are rejected. The key can be then extracted by applying brute force to the remaining possible values. The cache is cleared and a contiguous array of size equal or greater than that of the cache is read by the attacker in the Prime stage. The attacker then waits in a busy loop for the victim to run its AES. Once the AES is executed there is a sudden increase in the clock cycle values for all the selected cache sets which shows the occurrence of the attack. Then using the indices values the key is extracted.
Mitigation : The cache based side channel attack helps the attacker to extract private information about the victim lying in the same physical machine. This reduces the security of the virtual machines created in the cloud environment. A mitigation measure can be taken to ensure security of the cloud environment. Clearing of the cache before running the AES by victim can ensure that no cache based side channel can be created. This can be further improved by randomly accessing the lookup tables which causes a confusion for the attacker to analyse the cache access pattern. The cache is cleared by doing mathematical operations which do not involve any memory accesses. Also in the AES algorithm the lookup tables are randomly accessed to ensure there is no side channel created.
Experimental Results and Analysis :
For the attacker to extract the AES key from the victim, the cache sets affected by running AES should be known. Each lookup table has 256 elements which correspond to particular cache sets in the cache memory. From the initial group of all cache sets, the possible affected cache sets are determined based on mapping of the lookup table addresses as shown in fig 1. More than one element in the lookup table can map to the same cache set.
Figure 1 : Mapping of lookup table addresses
The possible group of cache sets can be further reduced by analyzing the cache based on any constant or negative drop in the number of clock cycles as shown in fig 2. After the victim runs AES, the number of clock cycles taken by the attacker to access the cache sets affected by the AES is expected to increase. All those cache sets with the same or lesser number of clock cycles before and after running AES are the ones which have not been utilized by AES algorithm.
Figure 2 : Constant or negative drop in clock cycles
When the victim runs AES algorithm, some cache sets are affected. Hence, when the attacker tries to access these cache sets, there is a cache miss. This will result in a difference of at least 250 clock cycles. All those cache sets which had difference less than 250 clock cycles were rejected as shown in fig 3
Figure 3 : Small Positive Change in clock cycles
Once the group of non-accessed cache sets are known by the attacker, the corresponding non-accessed indices are found, these possible set of non-accessed indices are XORed with the plaintext to obtain the reduced possible set of values for each byte of the key. This is repeated for different plaintexts and the possible key set becomes smaller as shown in fig 4.
Figure 4 Reduction in possible key set
Unique security aspects of the Cloud have motivated this paper. Primary among them is that the Cloud’s architecture is particularly vulnerable to cache driven side channel attack. This paper is an earnest attempt to develop and implement novel techniques to prevent cache based side channel attack. In order to design a solution for counterattack, the details on how the attack is conducted to extract private information was required.
OpenStack, a private cloud operating system, is set up to host the system and its requirements. A robust access driven side channel attack on AES implementation is demonstrated. The approach in carrying out cache pattern analysis is unique and it aims to reduce the possible key byte set to the maximum extent before carrying out brute force. The possible key sets are reduced from 2128 to 233 effectively using few samples for analysing cache patterns followed by a brute force technique to fully recover 128 bit AES key.Cache flushing and randomized lookup tables access avoids the creation of cache based channel thus providing a more secure cloud environment.
Future Work :
The attacker VM should locate the physical host of the victim VM and place a new VM co-resident to the victim. The key extraction should be possible when the base address of the lookup tables is not known. The possible key set may be reduced further, before applying brute force method.