Pwnable.kr [memcpy]

// 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();
		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 : ----- erased in this source code -----\n");
	return 0;
}

 

readme 파일을 읽어보면, nc 0 9022를 통해서 해당코드로 컴파일된 실행파일에 접근할 수 있다.

 

그냥 입력값을 넣고 진행을 하면 segment fault가 뜨는 것을 확인할 수 있는데, 

fast_memcpy()를 진행할 때 오류가 나는 것을 확인할 수 있고 

해당 asm 코드가 문제가 있지 않을까 예상 가능하다.

(참고: 코드를 보면 해당 asm코드는 len>=64일 때만 실행된다.)

 

movdqa와 movntps라는 어셈코드를 사용하는데, 

두 명령어 다 aligned double qword만큼을 옮기는 역할을 수행한다.

그래서 코드에서도 16byte(double qword) 단위로 증가시키는 것을 볼 수 있다.

 

단, 저기서 aligned라는 의미가 알아서 정렬을 시켜주는 게 아니라 정렬이 '되어있는 상태여야만 한다'는 의미라서,

dest의 주소가 double qword 단위로 (0x10단위로)정렬이 되어 있지 않다면, 오류가 발생하는 것이다.

 

해당 소스코드를 개인 linux에서 컴파일 후 dest의 주소를 확인하게 되면, 

항상 입력값 + 8 만큼의 공간 할당 이후 다음 공간을 할당하는 것을 볼 수 있다. 

 

최초 0x10으로 aligned 되어있는 상태에서 시작하는 것으로 보이고,

입력 범위 중에 최솟값으로만 입력한다고 가정하였을 때

 

0x08+8 => aligned

0x10+8 => not aligned

0x20+8 => aligned again

0x40+8 => not aligned, always len>=64 from here

 

이렇게 진행되므로, 4번째 입력값부터 항상 최솟값 + 8을 입력해주면

aligned된 상태로 dest의 시작주소가 설정된다. 

(최솟값은 항상 0x10의 배수이고, n * 0x10 + 8만큼 할당되는 상황이니 +8 더해주면 (n+1) * 0x10만큼 할당된다.)

 

이렇게 10번 다 진행되면, flag가 나온다.

참고로 10번째에는 +8을 해주지 않아도 시작주소는 9번째 입력값에 의해 aligned된 상태이므로 상관없다.