Side-channel attacks gained widespread notoriety in early 2018. A side-channel attack includes any attack based on information gained from the implementation of a computer system, rather than weaknesses in the implemented algorithm itself. Such side-channel attacks may use timing information, power consumption, electromagnetic leaks or even sound as an extra source of information, that is exploited to obtain information and/or data from the system. Side-channel attacks include Spectre and Meltdown, both of which rely on deducing whether data originates in a cached or un-cached location. To a significant degree, the determination of where data originates relies upon the precise timing of events such as loads from memory space.
Modern operating systems map the kernel into the address space of every process executed by the processor. Access to the kernel space is restricted using a supervisor bit of the processor that is set to permit kernel access to the kernel space and is reset to block or prohibit user access to the kernel space. Meltdown overcomes this memory isolation, thereby permitting the user process to read the entire kernel memory of the machine executing the user process. Meltdown relies upon out-of-order execution to obtain data from the kernel space. CPUs supporting out-of-order execution support running operations speculatively to the extent that processor's out-of-order logic processes instructions before the CPU is certain whether the instruction is valid and committed. Meltdown reads information from the protected kernel space by causing the processor to execute multiple instructions such as:
data=getByte(kernelAddress)variable=probeArray(data)The “getByte” instruction will ultimately fail because of the prohibited read of kernel memory. However, the simultaneous access of an element in “probeArray” will pull the data from “probeArray” into cache. By timing reads at addresses from 0 to 255 in cache, the attacker is able to deduce the content of “kernelAddress.”
For example, after flushing the cache, the Meltdown attacker retrieves a value “01000000” (binary “64”) from a first address in the kernel memory. Prior to the processor generating an exception to the unauthorized read from kernel memory, the attacker uses retrieved kernel data as an index to access element “64” in a known array located in user space. The processor retrieves the value of array element 64 and loads the value into cache. The attacker then attempts to read every element from the array—access times for elements 0-63 and 65-255 will be relatively long as the data is retrieved from main memory. However the access time for element 64 will be considerably shorter as the data need only be retrieved from the cache. From this the attacker can deduce the data the first address in kernel memory is “0100000”. By performing the action for every location in kernel memory, the attacker is able to read the contents of the kernel memory.
A first class of Spectre attacks takes advantage of branch target misprediction by a CPU to read data from memory into cache. Upon detecting the misprediction, the CPU clears the data from the pipeline, but the data read into cache remains. A covert side-channel may then be used to obtain the residual data from the cache. In this class of attack, the attacker trains the branch predictor in a system to take a particular branch. For example, using the following instructions, an attacker may train the system by providing values for “x” that are consistently smaller than the size of “array1.” The attacker thus trains the system to speculatively execute the subsequent instruction based on the assumption that the branch has been historically true:
if ( x < array1.size( )) {int value = array2[array1[x] * 256] // branch 1}After training the system, the attacker sets the cache to a known state and provides a value of “x” that exceeds the size of “array1.” Having been previously trained that “x” is typically less than the size of “array1,” the processor executes the branch instruction (prior to the processor throwing the exception due to “x” being greater than the size of “array1”) and uses the value found at address “x” as an index to look up the value at address “x” in array2. The processor loads the value at address “x” in array2 into cache. The attacker then reads all of the values of array2 and is able to determine the value of “x” as the address in array2 having the shortest access time.
For example, assume array1 has 256 elements addressed “0” to “255.” The attacker provides values of “x” between 0 and 255 to train the system that the branch instruction is routinely executed. The attacker then sets the cache to a known state and provides a value of 512 for “x” (i.e., a value greater than 255). The value “01000000” (i.e., “64”) at memory location 512 is read. The processor then looks up the value of array2 at address 64*256 and loads the value into cache. The attacker then examines the read time for each element in array2, the read time for element at address 64*256 will be less than the read time for the other array2 addresses, providing the attacker the information that the address at memory location 512 is “01000000” or “64.” By performing the action for every memory location, the attacker is able to read the contents of the memory byte-by-byte.
A second class of Spectre attacks exploits indirect branching by poisoning the Branch Target Buffer (BTB) such that a CPU speculatively executes a gadget that causes the CPU to read data from memory into cache. Upon detecting the incorrect branching, the CPU clears the data from the pipeline but, once again, the data read into cache remains. A covert side-channel may then be used to obtain the residual data from the cache. In this class of attack, the attacker poisons the BTB of the victim system by repeatedly performing indirect branches to a virtual address in the victim's system that contains the gadget. For example, an attacker may control the content of two registers (R1, R2) in the victim's system at the time an indirect branch occurs. The attacker must find a gadget in the victim's system that, upon speculative execution by the victim's CPU, leaks data from selected memory locations in the victim's system. The gadget may be formed by two instructions, the first of which contains an instruction that mathematically and/or logically (add, subtract, XOR, etc.) combines the contents of register R1 with another register in the victim's system and stores the result in R2. The second instruction reads the contents of register R2, storing the value in R2 in cache.
For example, the attacker may control two registers in the victim system, ebx (R1) and edi (R2). The attacker then finds two instructions on the victim's system, such as:
adcedi,dword ptr [ebx+edx+13BE13BDh]adcdl,byte ptr [edi]By selecting ebx=m−0x13BE13BD−edx the attacker is able to read the victim's memory at address “m.” The result is then added to the value in edi (R2). The second instruction in the gadget causes a read of R2 which contains the sum of “m” plus the attacker's value initially loaded into edi, transferring the value into the cache. By detecting the location of R2 within the cache using a side-channel timing attack, the attacker is able to determine the value of “in.”
Although the following Detailed Description will proceed with reference being made to illustrative embodiments, many alternatives, modifications and variations thereof will be apparent to those skilled in the art.
USPTO Backgrounds
USPTO Backgrounds