when i started study CPU exploitation --> such a dark powerful art but it was difficult to find such technical information --> everything was written in advanced writeups, research papers, github...
--> i am writing such a article so i can help myself from the past --> make everything easy for him --> so he will become such a god working inside CPU now)
if article is useful and entertaining for man --> i will continue the series
NOTE --> forgive for such bad formatting --> i donot have experience with writing articles like legendary yasha
there is no organizing structure for writing this series (non linear approach) --> but i will start from basics --> this article will start with optimization of a spectre attack
--> but man ask why start from optimization if you cannot understand a Spectre attack himself and write himself first?
nice question --> do not worry --> fucking kick your ass --> just start --> study + execute code
--> i am writing such a article so i can help myself from the past --> make everything easy for him --> so he will become such a god working inside CPU now)
if article is useful and entertaining for man --> i will continue the series
NOTE --> forgive for such bad formatting --> i donot have experience with writing articles like legendary yasha
there is no organizing structure for writing this series (non linear approach) --> but i will start from basics --> this article will start with optimization of a spectre attack
--> but man ask why start from optimization if you cannot understand a Spectre attack himself and write himself first?
nice question --> do not worry --> fucking kick your ass --> just start --> study + execute code
--> we use a x86 processor for this article
sorry apple M1/M2((( --> use qemu
**donot compile the code with optimizations flags
Speculative execution (can skip for now)
It is basic enhacement inside modern CPUs to improve performance by predicting future outcomes of branches inside your code --> execute them ahead of time --> faster computation
example
imagine such a simple scenario with code with a conditional branch such as if-else statement. normally CPU could follow a sequential approach --> first wait while evaluating the condition --> then follow the appropriate path
but with speculative execution --> both evaluation of condition + execution of path takes place simultaneously --> then he will continue if the predicted path is the correct path after evaluation finishes --> if not he will discard the results and computes other branches
the idea is to keep CPU himseslf busy if resources are available --> maximimum throughput + minimum idle time
well such idea was discuss for long time before it became popular --> he first became popular inside of the legendary processors like Intel Pentium Pro with aggresive speculative execution techniques where he gives signifcant performance improvements --> now the techniques inside speculative execution became more advanced complex like --> out of order, branch prediction, speculative memory access, value prediction, thread level speculation +++ (no understanding of this needed now --> continue)))
Spectre Attack (can skip for now)
such a cool breakthrough from the legendary Project Zero inside 2018.
Spectre takes advantage fundamental idea of speculative execution --> ability to predict branches accurately most of the time, but not always
this is called branch misprediction --> if the processor executes the path of a wrongly predicted branch --> he must discard the incorrect speculative results + revert system state to the point behind mispredicted branch
to understand the essence of Spectre --> first remember that speculative execution himself leaves light traces of its actions inside CPU cache hierarchy (multiple levels like L1, L2 sometimes L3 each with different capacties + different access speeds)--> while the processor attempts to roll back any speculative operations on discovering a misprediction --> it is not able to fully undo his effects inside the cache))
this remaining cache information might include information about data evictions, updates, accesses ++ that happen inside the speculative phase
so from attacker side--> this is good for us --> with a cunning Spectre attack exploit (+ nice observation + timing )--> this remaining cache information can be used to extract sensitive data inside a victim process))
how to do this exactly?
we measure the time to access specific memory location --> which varies depend on whether associated cache lines were manipulated during speculative execution
Optimization
Inside this article we will write the optimization part of the Spectre attack (no need to understand Spectre now --> continue)))
"but why study such garbage man? i am not a programmer, i am a pentester sitting inside XSS commercial forum for a locker payment of 5kk$ notes from the cans of white house?"
--> well fuck himself
there are two important features of optimization we discuss
--> reduce noise
noise reduction inside cache access time measurements is important for a Spectre exploit --> increase accuracy of timing side-channel used to extract sensitive information --> more chance of successful attack (if you do not understand how noise affects Spectre --> do not worry --> this is not important for now, not the scope inside article --> first you can learn why noise arises --> and how to reduce him?)
any interference + disturbance (example such bastards come from other processes, interrupts, context switches, even variations inside system performance himself) will fuck the result of accurate measurement of the timing window
--> balanced timing window
timing windows --> specific time period during which attacker can observe the side effects of speculative execution which includes obtaining information about CPU cache state + other microarchitectural components. small timing window --> increasing precision of attack which also reduce potential for more noise
with such small timing window --> we can accurately meaure the timing difference between cache hits and misses --> reduce noise
with big timing window --> more time for extracting info
so which one to decide?
this is controversy debate --> but there is not a single answer himself
--> you have to profle the target system to understand cache behavior + spec execution patterns + timing variatitons
--> experiment with different window sizes + optimize
--> adaptive timing window
.....
but we will not discuss such inside this article --> so we focus more on the noise himself (final important factor than timing window)
Cache Lines
modern processors normally use a cache based memory hierarchy for improve the memory access performance. the cache is divided into fixed-size units called cache lines --> each line contains multiple memory addresses
by access memory in a cache friendly manner --> where memory addresses are likely to be accessed together are stored inside same cache line --> the processor can minimize the number of cache misses + improve performance
img_source --> trishagee.com/2011/07/22/dissecting_the_disruptor_why_its_so_fast_part_two__magic_cache_line_padding/
Prime+Probe Technique
the technique is the most basic technique for noise reduction by carefully controlling cache state + minimizing interference from other bastards
the basic idea --> prime the cache by loading specific data including specific victim process to evict some of its own data--> after certain delay we can probe the cache to measure time takes to access certain memory locations --> we then analyze the timing for victim's memory access patterns and extract sensitive info
NOTE --> we use the x86intrin header to access Intel intrinsics for x86 processors to work with special CPU instructions
--> we define a function prime_probe which takes array pointer --> prime probing technique (flush cache lines + access them --> measure access time)
mm_clflush instruction to flush each cache line in given range --> this will ensure that cache lines are empty --> need to be fetch from inside main memory when accessed
we access cache inside a nice cache friendly manner with 64 byte cache lines
** use volatile variable for sum so the compiler does not fuck him inside the ass
C:
#define CACHE_LINE_SIZE 64
void prime_probe(uint8_t *ptr) {
volatile uint64_t sum = 0; // store sum of accessed cache lines
// flush cache lines
for (int i = 0; i < 256; i++) {
_mm_clflush(ptr + i * CACHE_LINE_SIZE);
}
// access flushed cache lines --> measure access time
for (int i = 0; i < 256; i++) {
sum += *(volatile uint64_t *)(ptr + i * CACHE_LINE_SIZE);
// ***access cache lines using a volatile pointer --> ensure actual memory accesses
}
}--> now the code is finish --> lets measure performance of access array with and without prime probing
but why such ARRAY_SIZE * CACHE_LINE_SIZE ? --> the goal of such allocation for such specific size to align with cache line size --> such alignment helps improve memory access performance due to cache behavior because it reduces cache misses and improves memory access patterns --> better utilization of CPU cache and even faster execution times
C:
#define ARRAY_SIZE (1 << 20)
#define ITERATIONS 1000
int main() {
uint8_t *array = (uint8_t *)malloc(ARRAY_SIZE * CACHE_LINE_SIZE);
uint64_t start, end;
// first measurement --> without prime probe
start = __rdtsc();
for (int i = 0; i < ITERATIONS; i++) {
volatile uint64_t sum = 0;
for (int j = 0; j < ARRAY_SIZE; j++) {
sum += array[j * CACHE_LINE_SIZE];
}
}
end = __rdtsc();
printf("without prime probe --> %lu cycles/iteration\n", (end - start) / ITERATIONS);
// second measurement --> with prime probe
start = __rdtsc();
for (int i = 0; i < ITERATIONS; i++) {
prime_probe(array);
volatile uint64_t sum = 0;
for (int j = 0; j < ARRAY_SIZE; j++) {
sum += array[j * CACHE_LINE_SIZE];
}
}
end = __rdtsc();
printf("with prime probe --> %lu cycles/iteration\n", (end - start) / ITERATIONS);
free(array);
return 0;
}Results
Код:
without prime probe --> 3812776 cycles/iteration
with prime probe --> 3518063 cycles/iteration
without prime probe --> 3742036 cycles/iteration
with prime probe --> 3662542 cycles/iteration"aah such garbage man results from bastard drpalpatine --> i will throw 2 dislikes if i can"
--> we analyze and try improve
Can we improve?
from simple static analysis of code --> we find some bastards
1. increase ITERATIONS + ARRAY_SIZE
--> we will now get more accuracy by reducing outliers inside measurement
--> large array size increases chance of interference between memory accesses --> which is exactly what we want to measure with Prime+Probe
--> avoid issue with cache thrashing --> also we learn a new concept --> cache thrashing (when cache is frequently filled with data that is quickly evicte/replace by new data --> results in high cache misses) such concept itself is because of many reasons and there are nice mitigations --> outside of scope of this article
but such only improvement will not solve our problems because the problem is not significant as such numbers are already big and no practical difference inside results
2. instead of flush all cache lines inside array --> why not target specific cache lines which will likely interfere with the subsequent memory accesses
3. instead of access array elements sequential order --> we use different patterns (such as random access or even strided access)
why? --> better simulate real world memory access patterns --> he will help increase relevance of measurements + reduce impact of any specific optimization/interference inside our system
4. we will use more powerful timing technique --> RDTSC is a simple function --> he does not take effects of CPU frequency scaling, cache effects other bastards who will eat our accuracy
--> we will use the rdtscp instruction instead of rdtsc --> he will return a CPU ID of executing core
--> especially inside multiple cores or other complex systems
now enough theory --> apply
--> first we will modify the prime_probe() --> we will only target specific cache lines instead of all cache lines inside our array
C:
void prime_probe(uint8_t *ptr, int start, int end) {
volatile uint64_t sum = 0; // store sum of accessed cache lines
// flush --> specific cache lines
for (int i = start; i < end; i++) {
_mm_clflush(ptr + i * CACHE_LINE_SIZE);
}
// access flushed cache lines --> measure access time
for (int i = start; i < end; i++) {
sum += *(volatile uint64_t *)(ptr + i * CACHE_LINE_SIZE);
// ***access cache lines using a volatile pointer --> ensure actual memory accesses
}
}--> now we add random selection of cache set to Prime+Probe in each iteration + random access pattern instead of sequential
C:
#define PRIME_PROBE_ROUNDS 256 // number of cache lines targeted
int main() {
uint8_t *array = (uint8_t *)malloc(ARRAY_SIZE * CACHE_LINE_SIZE);
uint64_t start, end;
unsigned int garbage; // he will be unused --> because the compiler will optimize away the rdtscp instruction
// first measurement --> without prime probe
start = __rdtscp(&garbage);
for (int i = 0; i < ITERATIONS; i++) {
volatile uint64_t sum = 0;
for (int j = 0; j < ARRAY_SIZE; j++) {
sum += array[j * CACHE_LINE_SIZE];
}
}
end = __rdtscp(&garbage);
printf("without Prime+Probe --> %lu cycles/iteration\n", (end - start) / ITERATIONS);
// second measurement --> with prime probe
srand(time(NULL));
start = __rdtscp(&garbage);
for (int i = 0; i < ITERATIONS; i++) {
// random select a cache set --> prime and probe
int set_index = rand() % (ARRAY_SIZE / PRIME_PROBE_ROUNDS);
int prime_start = set_index * PRIME_PROBE_ROUNDS;
int prime_end = prime_start + PRIME_PROBE_ROUNDS;
prime_probe(array, prime_start, prime_end);
// access all cache lines --> inside selected cache set
volatile uint64_t sum = 0;
for (int j = prime_start; j < prime_end; j++) {
sum += array[j * CACHE_LINE_SIZE];
}
}
end = __rdtscp(&garbage);
printf("with Prime+Probe --> %lu cycles/iteration\n", (end - start) / ITERATIONS);
free(array);
return 0;
}Results
Код:
without Prime+Probe --> 58635843 cycles/iteration
with Prime+Probe --> 47416 cycles/iteration
without Prime+Probe --> 15100261 cycles/iteration
with Prime+Probe --> 13211 cycles/iterationnice))) such a cool improvement
Conclusion for Prime+Probe
"again drpalpatine you said --> we will decrease noise so it will be useful inside Spectre attacks but why did bastard decrease time cycles?"
--> here CPU cycles is like a proxy for noise inside cache access time measurements --> because caches access times are affected by noise simply
"does that mean noise is reduced by 99%? cool"
--> not really --> but we can assume significant noise reduction happened --> but we know that time cycles proportional to noise roughly
to accurately quantify such noise reduction --> we need to use more advanced statistical analysis/simulation approach etc so we can isolate impact of prime+probe
again remember why such study is important -->
noise reduction inside cache access time measurements is important for a Spectre exploit --> increase accuracy of timing side-channel used to extract sensitive information --> more chance of successful attack."
however such 97% improvement should be taken with salt grains --> it depends on specific hardware etc
Problems with Prime+Probe
cache contention --> when multiple processes/threads access same cache lines --> he will implement accuracy
cache replacement policy --> Prime+Probe depends inside cache replacement policy to evict target data from cache --> but different cache replacement policies have different evict patterns --> prediction when target data will be evicted become difficult
limited cache sets --> Prime+Probe is most effective when target data is inside a big number of cache sets --> but inside some systems --> number of cache sets is limited --> it will become difficult to isolate target data
etc
Flush+Reload
it is technique to measure time take to access a memory address --> determine if its inside cache or not --> we can do this flushing cache line containing containing memory address --> measure time take to reload cache line --> if time taken to reload cache line is shorter than threshold --> memory inside cache else not))
--> we define flush_cache_line function to flush a cache line from the CPU cache hierarchy using __mm_clflush function --> he is an intrinsic function that invokes CLFLUSH instruction --> force the CPU to write back + invalidate specified cache line
C:
void flush_cache_line(volatile uint8_t* ptr) {
_mm_clflush((const void*)ptr);
}--> we define reload_cache_line function to measure access time to a cache line
C:
uint64_t reload_cache_line(volatile uint8_t* ptr) {
uint64_t start, end;
unsigned int aux;
start = __rdtscp(&aux);
volatile uint8_t value = *ptr;
end = __rdtscp(&aux);
return (end - start);
}--> we will perform Flush+Reload technique inside the flush_reload function on cache line of array
first calculate pointer to cache line by multiplying index by CACHE_LINE_SIZE --> call flush_cache_line to flush cache line from CPU cache hierarchy --> call reload_cache_line to measure access time to cache line --> if access time less than THRESHOLD value --> print a message indicating a cache hit
C:
void flush_reload(uint8_t* array, int index) {
volatile uint8_t* ptr = &array[index * CACHE_LINE_SIZE];
flush_cache_line(ptr);
uint64_t access_time = reload_cache_line(ptr);
if (access_time < THRESHOLD) {
printf("cache hit at index %d --> access time --> %lu\n", index, access_time);
}
}--> we modify previous main function for Flush+Reload
C:
#define CACHE_LINE_SIZE 64
#define ARRAY_SIZE (1 << 22)
#define ITERATIONS 100
#define THRESHOLD 200 // cache access threshold
int main() {
uint8_t *array = (uint8_t *)malloc(ARRAY_SIZE * CACHE_LINE_SIZE);
uint64_t start, end;
unsigned int garbage; // unused variable
// first measurement --> without Flush+Reload
start = __rdtscp(&garbage);
for (int i = 0; i < ITERATIONS; i++) {
volatile uint64_t sum = 0;
for (int j = 0; j < ARRAY_SIZE; j++) {
sum += array[j * CACHE_LINE_SIZE];
}
}
end = __rdtscp(&garbage);
printf("without Flush+Reload --> %lu cycles/iteration\n", (end - start) / ITERATIONS);
// second measurement --> with Flush+Reload
srand(time(NULL));
start = __rdtscp(&garbage);
for (int i = 0; i < ITERATIONS; i++) {
int index = rand() % ARRAY_SIZE;
flush_reload(array, index);
}
end = __rdtscp(&garbage);
printf("with Flush+Reload --> %lu cycles/iteration\n", (end - start) / ITERATIONS);
free(array);
return 0;
}Results
Код:
without Flush+Reload --> 28099291 cycles/iteration
cache hit at index 792050 --> access time --> 182
cache hit at index 313170 --> access time --> 199
cache hit at index 1445633 --> access time --> 186
with Flush+Reload --> 865 cycles/iteration
without Flush+Reload --> 28199962 cycles/iteration
cache hit at index 1636770 --> access time --> 198
with Flush+Reload --> 525 cycles/iterationcool with such significant results? what does such mean?
--> when processor access memory --> he store a copy of accessed data in a small, fast cache memory --> which is significantly faster than main memory --> when two or more processes accesss same memory location --> they interfere with each other caching behavior --> this can throw cache misses --> so processor will access main memory again to retrieve data --> increasing number of cycles
--> with Flush+Reload --> we take advantage of such behavior by flushing cache line corresponding to a memory location + Reload it 00> if memory location was access relcently --> data will be inside cache --> reload is very fast than if data was retrieve from main memory --> this reduce the noise caused by cache misses --> more accurate measurement
Exploit? how?
i demonstrated both such techniques as means of noise reduction for accuracy in measurements but they are cache attacks))) cool you learned two such attacks --> we will soon write a simple exploit in future articles inside series but now you have learn working with CPU --> like writing simple programs and optimize them (here we write a simple function for access array --> optimize him)
Flush+Reload > Prime+Probe?
--> we do not access memory address repeated times --> he is faster than Prime+Probe
--> more accuracy --> measuring time taking to reload cache line is nice indicator of memory access
--> when victim memory is frequently modified + small cache line size --> Flush+Reload is better here because he detect more fine access patterns in small time
etc
Prime+Probe > Flush+Reload?
--> multi core system --> different cores may have different copies of same cache line --> with Prime+Probe we can prime cache line on one core --> then probe it inside other core --> reveal information about victim memory access in other core
--> when victim memory is read only --> read only memory regions cannot be modified with Flush+Reload
etc
C:
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#include <x86intrin.h>
#define CACHE_LINE_SIZE 64
#define ARRAY_SIZE (1 << 22)
#define ITERATIONS 10000
#define PRIME_PROBE_ROUNDS 256 // number of cache lines targeted
void prime_probe(uint8_t *ptr, int start, int end) {
volatile uint64_t sum = 0; // store sum of accessed cache lines
// flush --> specific cache lines
for (int i = start; i < end; i++) {
_mm_clflush(ptr + i * CACHE_LINE_SIZE);
}
// access flushed cache lines --> measure access time
for (int i = start; i < end; i++) {
sum += *(volatile uint64_t *)(ptr + i * CACHE_LINE_SIZE);
// ***access cache lines using a volatile pointer --> ensure actual memory accesses
}
}
int main() {
uint8_t *array = (uint8_t *)malloc(ARRAY_SIZE * CACHE_LINE_SIZE);
uint64_t start, end;
unsigned int garbage; // he will be unused --> because the compiler will optimize away the rdtscp instruction
// first measurement --> without prime probe
start = __rdtscp(&garbage);
for (int i = 0; i < ITERATIONS; i++) {
volatile uint64_t sum = 0;
for (int j = 0; j < ARRAY_SIZE; j++) {
sum += array[j * CACHE_LINE_SIZE];
}
}
end = __rdtscp(&garbage);
printf("without Prime+Probe --> %lu cycles/iteration\n", (end - start) / ITERATIONS);
// second measurement --> with prime probe
srand(time(NULL));
start = __rdtscp(&garbage);
for (int i = 0; i < ITERATIONS; i++) {
// random select a cache set --> prime and probe
int set_index = rand() % (ARRAY_SIZE / PRIME_PROBE_ROUNDS);
int prime_start = set_index * PRIME_PROBE_ROUNDS;
int prime_end = prime_start + PRIME_PROBE_ROUNDS;
prime_probe(array, prime_start, prime_end);
// access all cache lines --> inside selected cache set
volatile uint64_t sum = 0;
for (int j = prime_start; j < prime_end; j++) {
sum += array[j * CACHE_LINE_SIZE];
}
}
end = __rdtscp(&garbage);
printf("with Prime+Probe --> %lu cycles/iteration\n", (end - start) / ITERATIONS);
free(array);
return 0;
}
C:
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#include <x86intrin.h>
#define CACHE_LINE_SIZE 64
#define ARRAY_SIZE (1 << 22)
#define ITERATIONS 100
#define THRESHOLD 200 // cache access threshold
void flush_cache_line(volatile uint8_t* ptr) {
_mm_clflush((const void*)ptr);
}
uint64_t reload_cache_line(volatile uint8_t* ptr) {
uint64_t start, end;
unsigned int aux;
start = __rdtscp(&aux);
volatile uint8_t value = *ptr;
end = __rdtscp(&aux);
return (end - start);
}
void flush_reload(uint8_t* array, int index) {
volatile uint8_t* ptr = &array[index * CACHE_LINE_SIZE];
flush_cache_line(ptr);
uint64_t access_time = reload_cache_line(ptr);
if (access_time < THRESHOLD) {
printf("cache hit at index %d --> access time --> %lu\n", index, access_time);
}
}
int main() {
uint8_t *array = (uint8_t *)malloc(ARRAY_SIZE * CACHE_LINE_SIZE);
uint64_t start, end;
unsigned int garbage; // unused variable
// first measurement --> without Flush+Reload
start = __rdtscp(&garbage);
for (int i = 0; i < ITERATIONS; i++) {
volatile uint64_t sum = 0;
for (int j = 0; j < ARRAY_SIZE; j++) {
sum += array[j * CACHE_LINE_SIZE];
}
}
end = __rdtscp(&garbage);
printf("without Flush+Reload --> %lu cycles/iteration\n", (end - start) / ITERATIONS);
// second measurement --> with Flush+Reload
srand(time(NULL));
start = __rdtscp(&garbage);
for (int i = 0; i < ITERATIONS; i++) {
int index = rand() % ARRAY_SIZE;
flush_reload(array, index);
}
end = __rdtscp(&garbage);
printf("with Flush+Reload --> %lu cycles/iteration\n", (end - start) / ITERATIONS);
free(array);
return 0;
}hope you enjoy such article --> crticism appreciates me --> write more soon)
Author: drpalpatine (c)
Written specifically for xss.pro
