[CSAPP] 2. Bomb lab (Assembly Reversing & GDB Tool) - Phase 5

다른 phase와 다르게, phase 5는 조금 특별하다. 왜 그런지는 문제와 함께 살펴보자.

 

하던대로, phase_5의 함수부터 분해하여보자!

 

0000000000401062 <phase_5>:
  401062:	53                   	push   %rbx
  401063:	48 83 ec 20          	sub    $0x20,%rsp
  401067:	48 89 fb             	mov    %rdi,%rbx
  40106a:	64 48 8b 04 25 28 00 	mov    %fs:0x28,%rax
  401071:	00 00 
  401073:	48 89 44 24 18       	mov    %rax,0x18(%rsp)
  401078:	31 c0                	xor    %eax,%eax
  40107a:	e8 9c 02 00 00       	callq  40131b <string_length>
  40107f:	83 f8 06             	cmp    $0x6,%eax
  401082:	74 4e                	je     4010d2 <phase_5+0x70>
  401084:	e8 b1 03 00 00       	callq  40143a <explode_bomb>
  401089:	eb 47                	jmp    4010d2 <phase_5+0x70>
  40108b:	0f b6 0c 03          	movzbl (%rbx,%rax,1),%ecx
  40108f:	88 0c 24             	mov    %cl,(%rsp)
  401092:	48 8b 14 24          	mov    (%rsp),%rdx
  401096:	83 e2 0f             	and    $0xf,%edx
  401099:	0f b6 92 b0 24 40 00 	movzbl 0x4024b0(%rdx),%edx
  4010a0:	88 54 04 10          	mov    %dl,0x10(%rsp,%rax,1)
  4010a4:	48 83 c0 01          	add    $0x1,%rax
  4010a8:	48 83 f8 06          	cmp    $0x6,%rax
  4010ac:	75 dd                	jne    40108b <phase_5+0x29>
  4010ae:	c6 44 24 16 00       	movb   $0x0,0x16(%rsp)
  4010b3:	be 5e 24 40 00       	mov    $0x40245e,%esi
  4010b8:	48 8d 7c 24 10       	lea    0x10(%rsp),%rdi
  4010bd:	e8 76 02 00 00       	callq  401338 <strings_not_equal>
  4010c2:	85 c0                	test   %eax,%eax
  4010c4:	74 13                	je     4010d9 <phase_5+0x77>
  4010c6:	e8 6f 03 00 00       	callq  40143a <explode_bomb>
  4010cb:	0f 1f 44 00 00       	nopl   0x0(%rax,%rax,1)
  4010d0:	eb 07                	jmp    4010d9 <phase_5+0x77>
  4010d2:	b8 00 00 00 00       	mov    $0x0,%eax
  4010d7:	eb b2                	jmp    40108b <phase_5+0x29>
  4010d9:	48 8b 44 24 18       	mov    0x18(%rsp),%rax
  4010de:	64 48 33 04 25 28 00 	xor    %fs:0x28,%rax
  4010e5:	00 00 
  4010e7:	74 05                	je     4010ee <phase_5+0x8c>
  4010e9:	e8 42 fa ff ff       	callq  400b30 <__stack_chk_fail@plt>
  4010ee:	48 83 c4 20          	add    $0x20,%rsp
  4010f2:	5b                   	pop    %rbx
  4010f3:	c3                   	retq

모든 함수가 그러하듯, 스택 공간 확보하고, old stack pointer 저장하고... 하는 과정을 거친 다음, 401078 줄을 수행하여 %eax를 0으로 초기화한다.

 

이후, 다른 함수처럼 "sscanf" 대신 "string_length"라는 함수를 호출하여, 일단 문자열의 길이를 확인하는듯 하였다. 이 함수를 호출하기 전, %rdi에 담긴 정보를 %rbx에 옮기는 듯 하여, 옮기기 전 %rdi에 어떤 것이 담기는지 확인하여보자. 문자열 "testin"이라는 문자열을 넣고, 401063을 실행하기 전에 %rdi에 어떤 것이 담기는 지 확인하여보자.

(gdb) x/s $rdi
0x6038c0 <input_strings+320>:   "testin"

 

아하! %rdi에는 처음에 넣은 문자열이 들어있는 것을 확인할 수 있다. 이제, 다른 퍼즐을 맞추러 가자. 문자열 "string_length" 이후에는 %rax의 값과 상수 0x6을 비교하는데, 만약 같지 않을 경우 폭탄이 터진다. 즉, %rax = 6이 담겨있어야 한다는 이야기다. 그럼, string_length 함수를 분해하여보자.

000000000040131b <string_length>:
  40131b:	80 3f 00             	cmpb   $0x0,(%rdi)
  40131e:	74 12                	je     401332 <string_length+0x17>
  401320:	48 89 fa             	mov    %rdi,%rdx
  401323:	48 83 c2 01          	add    $0x1,%rdx
  401327:	89 d0                	mov    %edx,%eax
  401329:	29 f8                	sub    %edi,%eax
  40132b:	80 3a 00             	cmpb   $0x0,(%rdx)
  40132e:	75 f3                	jne    401323 <string_length+0x8>
  401330:	f3 c3                	repz retq 
  401332:	b8 00 00 00 00       	mov    $0x0,%eax
  401337:	c3                   	retq

먼저, %rdi에 접근하여 0과 비교한다. 만약 0일 경우 401332로 건너뛰어, %rax에 0을 담고 return을 하게 된다. 만약 0이 아닐경우, %rdi의 주소값을 %rdx으로 옮긴 후, %rdx의 값을 1만큼 증가시킨다. 이후에 %rax에 %rdx를 옮긴 후, %rax에 %rdi를 빼준다. 그리고 나서 %rdx로 접근하였을 때 값이 0인지 체크한다. 만약 0이 아니라면 401323의 과정을 반복한다. 

 

repz retq는 branch prediction관련 instruction으로, 이 경우 40132b가 false일 때동안은 계속 반복된다고 할 수 있다. 

 

먼저, 40131b에서 %rdi에 담긴 값을 살펴보자.

(gdb) x/x $rdi
0x6038c0 <input_strings+320>:   0x74

0x74라는 hex 값을 추출하였다. 문자열 관련 함수이므로 이를 ascii로 변환하면, 소문자 "t"이다. 즉, 0x0임을 확인하는 것은 input이 0x0(null)인 경우를 확인한다고 할 수 있다. 이후 한 문자씩 돌면서, null char가 나올때까지 반복문이 순회되는 것을 알 수 있다. (C에서는 모든 문자열의 끝은 NULL(\0)이다.)

 

이번 input으로 "testin"이라는 문자열을 넣었으므로, 정말로 %rdi 근처에 이러한 값이 있는지 확인하자.

(gdb) x/6x $rdi
0x6038c0 <input_strings+320>:   0x74    0x65    0x73    0x74    0x69    0x6e

(gdb) x/6s $rdi
0x6038c0 <input_strings+320>:   "testin"

 

아하! 정말로 문자열이 담겨있는 것을 확인할 수 있고, %rax에는 문자열의 길이가 담긴다는 것을 암시한다.

---

다시 본론으로 돌아와, "string_length" 함수를 호출한 다음, %rax와 상수 0x6을 비교한다. 만약 같을 경우 점프하고, 같지 않으면 폭탄이 터진다. 따라서, 입력 문자열의 길이는 6이라고 추측할 수 있다.

 

6개 문자열이 들어온다면, 4010d2로 점프하여 %rax = 0을 한 다음, 40108b로 점프하고, %rcx = %rbx + %rax를 한다. 현재 %rax = 0이므로, %rcx = %rbx이라 할 수 있다. 이후 %rdx에 %cl을 넣은 뒤, %rdx = %rdx & 0xf 연산을 한다.

 

즉, %rdx의 값의 마지막 4비트를 추출하였고, 그 다음 instruction에서 %rdx += 0x4024b0을 한다. 이후 *(%rsp + %rax + 0x10) = %dl을 한 다음, %rax에 1을 더한 뒤 이 과정을 %rax = 6이 될때까지 한다. (6번의 loop을 암시한다.)

 

무슨 말인지 모르겠다고? 정상이다. 천천히 해보자.

 

일단, %rdx += 0x4024b0을 하고 있다. 일단, 0x4024b0의 값을 살펴보자!

(gdb) x/16c 0x4024b0
0x4024b0 <array.3449>:  "maduiersnfotvbyl"

무언가 나왔고, 문자열은 "maduiersnfotvbyl"이다. 이걸 기억하고 가자.

 

위의 과정을 다시 천천히 정리하여보자.

 

1. 401067에서 %rdi("testin"의 시작 주소)를 %rbx로 옮긴다.

2. %rbx("testin"의 시작 주소) + %rax를 %rcx에 옮긴다.

3. %rcx의 가장 오른쪽 8비트(%cl)를 %rdx로 옮긴다.

4. 이 중 하위 4비트만큼 뽑아낸다. (AND 연산의 의미이다. Data lab에서 많이 했지않나!)

5. %rdx에 0x4024b0을 더한다.

6. %rdx의 가장 오른쪽 8비트(%dl)을 (%rsp+%rax+10)의 주소에 저장한다.

7. 루프를 %rax = 6이될때까지 반복한다.

 

무슨 말인지 아직도 모르겠는가? %rdx는 하나의 offset 역할을 하는 것을 알 수 있다. 즉, %rdx = 0이면 m, %rdx = 1이면 a, %rdx = 2이면 d... 즉, %rdx는 위의 문자열의 index 역할을 하는 것이다. 이를 차곡차곡 쌓아 stack 안에 쌓는 것이라고 추측할 수 있다.

 

그럼 무슨 문자열과 같아야 하는가? 일단 루프를 모두 돌았다는 가정 하에 나아가보자. 4010b3에서 %rsi 안에 0x40245e의 값이 들어가는 것을 확인할 수 있다. 이후 %rdi 안에는 (%rsp+10) (쌓은 문자열의 시작 메모리 주소, 왜인지는 위의 6번을 보면 이해가 갈것이다.)를 담고, strings_not_equal을 호출한다. 즉, %rsi 안에 넣는 0x40245e에 어떤 값이 들어가 있는 지 확인하여야 한다.

 

4010b3까지 실행한 후, x 명령어를 사용하여 확인하면 다음과 같다.

(gdb) x/s 0x40245e
0x40245e:       "flyers"

우리의 목표는 어떤 문자열을 처리한 결과 문자열 "flyers"를 만드는 것이다. 해쉬 테이블과 같이 만들면 다음과 같이 해석할 수 있다.

 

hex index : 0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
hash str  : m	a	d	u	i	e	r	s	n	f	o	t	v	b	y	l

 

"flyers" 문자열은 idx 기준 9, F, E, 4, 5, 6이 나와야 한다. 따라서, input_string[i] & 0xf는 9, F, E, 4, 5, 6이 나와야 한다.

 

ASCII 테이블을 바탕으로 다음과 같이 만들 수 있다.

0x69	0x6F	0x6E	0x64	0x65	0x66
i	o	n	d	e	f

입력 문자열은 "iondef"가 가능하고, ASCII 기준 끝의 4비트만 맞추어 준다면 어떤 답이든 가능하다. 예를 들면, '9?>456"도 가능한 정답이다.

 

마지막으로, phase_5를 우리에게 익숙한 코드로 변환하여보자.

void phase_5(const char* input) {

    if (string_length(input) != 6) {
        explode_bomb();
    }

    const char* hashmap = "maduiersnfotvbyl";
    char arr[7];
    for (int i = 0; i < 6; i++) {
        arr[i] = hashmap[input[i] & 0xf];
    }
    
    if (string_not_equal(arr, "flyers")) {
        explode_bomb();
    }
}

실제로 푸는데 진땀 좀 뺐던 문제이다.

 

답 : "iondef"