[Pwnable.kr] memcpy 풀이 (10pt)

 

 

풀이

다음은 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();
		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;
}

해당 소스코드를 나의 로컬 서버에서 컴파일하고 그냥 잘 실행되길래 pwnable.kr 서버에서 해봤는데 안되더라..

소스 코드를 간단히 해석해보자면, 다음과 같다.

 

1. pow(2, e-1) ~ pow(2, e)만큼의 size를 할당한다.

2. size 만큼 dest에 동적 할당을 해준다.

3. slow_memcpy와 fast_memcpy를 한번씩 총 10번을 수행한다.

4, 무사히 10번 다 돌았으면 flag를 출력한다.

 

그래서 그냥 입력값을 모두 low 값으로 설정하고 돌려봤다.

추가로, dest의 주소 값을 출력해주는 구문을 추가해줬다.

ok, lets run the experiment with your configuration
experiment 1 : memcpy with buffer size 8
Address1 -> 0x94b7410
ellapsed CPU cycles for slow_memcpy : 3518
ellapsed CPU cycles for fast_memcpy : 200

experiment 2 : memcpy with buffer size 16
Address1 -> 0x94b7420
ellapsed CPU cycles for slow_memcpy : 326
ellapsed CPU cycles for fast_memcpy : 444

experiment 3 : memcpy with buffer size 32
Address1 -> 0x94b7438
ellapsed CPU cycles for slow_memcpy : 406
ellapsed CPU cycles for fast_memcpy : 496

experiment 4 : memcpy with buffer size 64
Address1 -> 0x94b7460
ellapsed CPU cycles for slow_memcpy : 848
ellapsed CPU cycles for fast_memcpy : 208

experiment 5 : memcpy with buffer size 128
Address1 -> 0x94b74a8
ellapsed CPU cycles for slow_memcpy : 1424
Segmentation fault (core dumped)

프로그램이 5번째에서 죽어버린다. 후에 모두 high 값으로 설정하고 돌려봤으나 역시 마찬가지로 프로그램이 죽는다.

---

+ ㅡㅡ.. movdqa와 movntps 명령어를 구글링하던 도중에 풀이와 관련된 힌트를 강제로 스포당했다..

 

먼저 movdqa를 찾아봤는데, 128byte의 정렬된 데이터를 다룬다고 적혀있었다.

저 실행 화면을 보면 알 수 있듯이, 3번째 실험에서 주소의 끝이 38이므로, 정렬되지 않은 형식이기에 프로그램이 죽는 것 이었다. 그렇다면 모든 주소를 128byte의 정렬된 형식으로 바꾸면 되지 않을까?

 

계속되는 시도 끝에 3번 실험 결과를 정렬된 주소 값으로 바꾸는데 성공했다. (걍 때려 맞춰서..)

ok, lets run the experiment with your configuration
experiment 1 : memcpy with buffer size 8
Address1 -> 0x833b410
ellapsed CPU cycles for slow_memcpy : 3458
Address2 -> 0x833b410
ellapsed CPU cycles for fast_memcpy : 252

experiment 2 : memcpy with buffer size 24
Address1 -> 0x833b420
ellapsed CPU cycles for slow_memcpy : 718
Address2 -> 0x833b420
ellapsed CPU cycles for fast_memcpy : 584

experiment 3 : memcpy with buffer size 48
Address1 -> 0x833b440
ellapsed CPU cycles for slow_memcpy : 758
Address2 -> 0x833b440
ellapsed CPU cycles for fast_memcpy : 980

experiment 4 : memcpy with buffer size 64
Address1 -> 0x833b478
ellapsed CPU cycles for slow_memcpy : 1012
Segmentation fault (core dumped)

그러나 4번 실험에서 오류가 발생한다.

아까 명령어를 찾다가 스포당한게 있어서.. 왜인지 알아버렸다.

 

16배수로 해야 한다는 것은, 128byte 형식일 때 이미 예상은 했으나, 여기서 8칸 만큼을 추가로 줘야 한다는 것이었다.

동적 할당을 할 때, heap에서 뒤에 추가로 붙는 데이터들이 8byte가 붙는다고 적혀있는 글을 봤다.

그렇다면 low + 8한 값을 넣어주면 문제가 해결되지 않을까?

페이로드는 다음과 같다. 이번 문제는 좀 찝찝하게 풀었다..

from pwn import *

p = remote('localhost', '9022')

for i in range(4,14):
        low = 2 ** (i -1)
        high = 2 ** i

        p.recvuntil(str(high) + ' : ')
        if i != 4:
                p.sendline(str(low+8))
        else:
                p.sendline(str(low))

for w in range(0, 65):
        print p.recvline()