[pwnable.kr] memcpy

1. 문제 확인

memcpy@pwnable:~$ ls
memcpy.c  readme
memcpy@pwnable:~$ cat readme
the compiled binary of "memcpy.c" source code (with real flag) will be executed under memcpy_pwn privilege if you connect to port 9022.
execute the binary by connecting to daemon(nc 0 9022).

9022포트로 접속할 수 있는 듯하다.

 

 

10번의 size범위 안에 입력 값을 받고 실행되다가 멈춘다.

 

[ 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;
}

오우오우 좀 많아 보이지만 아까 코드 돌다가 끊긴 부분이 저 마지막 for문에서 끊긴 것 같다. 그리고 for문이 완전히 다 돌고 나면 플래그 값을 던져줄 것 같다.

 

 

마지막 for문안의 살펴보면

slow_memcpy()와 fast_memcpy()를 실행하고 각 실행한 것의 시간을 측정한다.

 

 

여기서 slow_memcpy()는

src배열의 값을 dest배열에 1byte씩 복사한다.

 

 

그리고 fast_memcpy()는

len이 64보다 크거나 같을 때 while문이 len/64만큼 돌고 while문안의 어셈코드가 동작하는 것 같다.

 

gdb로 확인

 

---

2. 접근 방법

fast_memcpy의 어셈코드에서 movdqa와 movntps가 사용되었다.

여기서 사용된 movdqa와 movntps는 SIMD(Single Instruction Multiple Data)연산자로 하나의 명령어로 다중 데이터를 처리하는 연산이다. 여기서 말하는 다중 데이터는 일반적인 크기의 데이터가 아니라 64, 128, 256비트 크기를 가진 자료를 말한다.

(예전에도 이런 비슷한 문제 푼 것 같은데 기억이 안나네..)

어쨌든 위와 같은 SIMD연산을 사용할 때 크게 중요한 부분이 있는데 바로 Alignment(정렬)이다.

정렬을 맞추지 않고 복사하면 뻑날 수 있다.

 

1) MOVDQA - Move Aligned Double Quadword

• movdqa xmm1(dest), xmm2/m128(src) : Aligned double quadword를 src에서 dest로 이동
• 16Byte(128bit) 기준으로 정렬

2) MOVNTPS - Move Aligned Four Packed Single-FP Non Temporal

• movntps m128(dest), xmm(src) : 패킹된 단일 정밀도 부동 소수점 값을 src에서 dest로 이동
• 16byte(128bit) 기준으로 정렬

 

 

 

 

따라서, 중간에 프로그램이 멈춘 이유는 16byte로 정렬되지 않은 dest값이 존재하기 때문인 것 같다.

src값은 이미 정해져 있고

 

dest값은 우리가 입력한 값들이 들어 있는 size배열을 malloc의 인자로 받고 힙 영역을 할당받아 주소 값을 dest에 넣는 것 같다.

 

Alignment를 맞추기 위해 16byte배수를 입력하면 될 줄 알았지만

또 멈춘다... 근데 로컬에서는 겁나 잘된다.(?????)

 

저 주소가 heap영역에 할당된 주소인데

음... 디버깅하면은 금방 풀 수 있을 것같은데 서버에는 바이너리파일도 없고 컴파일도 할 수 없다. 젠장...

 

---

3. 문제 풀이

 

결국 다른 사람들이 쓴 롸업을 봤는데 음... 왜 다른 사람은 뻑나고 나는 뻑 안나고 잘 되지..??ㅋㅋㅋㅋㅋ그냥 넘어가자

 

 

---

4. 몰랐던 개념

 

참고 자료)

SIMD 로 배열 copy 작성__declspec(align(16)) 과 movdqu, movdqa

MOVNTPS--Move Aligned Four Packed Single-FP Non Temporal

MOVDQA--Move Aligned Double Quadword