[Toddler's Bottle] memcpy writeup

문제

Are you tired of hacking?, take some rest here.
Just help me out with my small experiment regarding memcpy performance.
after that, flag is yours.

http://pwnable.kr/bin/memcpy.c

ssh memcpy@pwnable.kr -p2222 (pw:guest)

---

분석

memcpy.c의 내용

// compiled with : gcc -o memcpy memcpy.c -m32 -lm
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <signal.h>
#include <unistd.h>
#include <sys/mman.h>
#include <math.h>

unsigned long long rdtsc(){
        asm("rdtsc");
}

char* slow_memcpy(char* dest, const char* src, size_t len){
    int i;
    for (i=0; i<len; i++) {
        dest[i] = src[i];
    }
    return dest;
}

char* fast_memcpy(char* dest, const char* src, size_t len){
    size_t i;
    // 64-byte block fast copy
    if(len >= 64){
        i = len / 64;
        len &= (64-1);
        while(i-- > 0){
            __asm__ __volatile__ (
            "movdqa (%0), %%xmm0\n"
            "movdqa 16(%0), %%xmm1\n"
            "movdqa 32(%0), %%xmm2\n"
            "movdqa 48(%0), %%xmm3\n"
            "movntps %%xmm0, (%1)\n"
            "movntps %%xmm1, 16(%1)\n"
            "movntps %%xmm2, 32(%1)\n"
            "movntps %%xmm3, 48(%1)\n"
            ::"r"(src),"r"(dest):"memory");
            dest += 64;
            src += 64;
        }
    }

    // byte-to-byte slow copy
    if(len) slow_memcpy(dest, src, len);
    return dest;
}

int main(void){

    setvbuf(stdout, 0, _IONBF, 0);
    setvbuf(stdin, 0, _IOLBF, 0);

    printf("Hey, I have a boring assignment for CS class.. :(\n");
    printf("The assignment is simple.\n");

    printf("-----------------------------------------------------\n");
    printf("- What is the best implementation of memcpy?        -\n");
    printf("- 1. implement your own slow/fast version of memcpy -\n");
    printf("- 2. compare them with various size of data         -\n");
    printf("- 3. conclude your experiment and submit report     -\n");
    printf("-----------------------------------------------------\n");

    printf("This time, just help me out with my experiment and get flag\n");
    printf("No fancy hacking, I promise :D\n");

    unsigned long long t1, t2;
    int e;
    char* src;
    char* dest;
    unsigned int low, high;
    unsigned int size;
    // allocate memory
    char* cache1 = mmap(0, 0x4000, 7, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
    char* cache2 = mmap(0, 0x4000, 7, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
    src = mmap(0, 0x2000, 7, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);

    size_t sizes[10];
    int i=0;

    // setup experiment parameters
    for(e=4; e<14; e++){    // 2^13 = 8K
        low = pow(2,e-1);
        high = pow(2,e);
        printf("specify the memcpy amount between %d ~ %d : ", low, high);
        scanf("%d", &size);
        if( size < low || size > high ){
            printf("don't mess with the experiment.\n");
            exit(0);
        }
        sizes[i++] = size;
    }

    sleep(1);
    printf("ok, lets run the experiment with your configuration\n");
    sleep(1);

    // run experiment
    for(i=0; i<10; i++){
        size = sizes[i];
        printf("experiment %d : memcpy with buffer size %d\n", i+1, size);
        dest = malloc( size );

        memcpy(cache1, cache2, 0x4000);        // to eliminate cache effect
        t1 = rdtsc();
        slow_memcpy(dest, src, size);        // byte-to-byte memcpy
        t2 = rdtsc();
        printf("ellapsed CPU cycles for slow_memcpy : %llu\n", t2-t1);

        memcpy(cache1, cache2, 0x4000);        // to eliminate cache effect
        t1 = rdtsc();
        printf("src : %p\ndest: %p\n", src, dest);
        fast_memcpy(dest, src, size);        // block-to-block memcpy
        t2 = rdtsc();
        printf("ellapsed CPU cycles for fast_memcpy : %llu\n", t2-t1);
        printf("\n");
    }

    printf("thanks for helping my experiment!\n");
    printf("flag : FL4G{##########yongy0ng2##########}\n");
    return 0;
}

코드에 적힌 방식으로 compile한 뒤 실행한 모습

10회 반복하며 memcpy를 시도해볼 메모리 크기를 입력받고 어떤 실험을 모두 통과하면 flag를 주는 방식!

그렇다면 그 실험이 무엇인지 면밀히 분석하자!

rdtsc : 단순히 실행시간을 체크하기 위한 용도

movntps : src TO dest, 단순 mov로 보인다.

참고 : MOVNTPS--Move Aligned Four Packed Single-FP Non Temporal

movdqa : double quadword 값을 mov 해주는 instruction. 만약 source나 destination 중 memory operand가 있다면 16byte-boundary에서 aligned 되어 있어야 한다. 즉 메모리 주소값이 0x10의 배수이어야 한다는 뜻!

참고 : MOVDQA - Move Aligned Double Quadword

그렇다면 위의 실행결과에서 Segmentation fault가 발생한 이유는 다음과 같이 설명할 수 있다.

experiment3까지는 fast_memcpy함수에 전해지는 len 값이 64보다 작아서 movdqa가 실행되지 않았다! 따라서 dest가 0x10으로 정렬되어 있지 않아도 프로그램이 정상작동했지만 experiment4부터는 그렇지 않았던 것이다.

dest는 이런식으로 증가한다.

i번째 dest = (i-1)번째 dest + [(i-1)번째 size로 malloc할때 할당되는 memory 용량]

(단, 1번째 dest = 0x8bfb410)

---

FL4G

그렇다면 0x8bfb438 에서 32 ~ 64사이의 값을 입력해서 0x....0을 만드는 방법은?

0x8bfb438 + 40 = 0x8bfb460

malloc(size) 결과로 40(=0x28)byte의 memory를 할당받기 위한 적절한 size 값은?

35.

위와 같이 모든 experiment에 대한 적절한 값을 구해서 실행해준 결과는 다음과 같다.

...