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

이제까진 그래도 괜찮았다. 근데, phase 4부터는 난이도가 조금 어려워진다. 사실 꼼수는 많이 있지만, 정확히 알고가기에는어려운 부분이 많이 있었다.

 

각설은 여기까지만 하고, 일단 하던대로 함수 phase_4부터 분해하여보자.

000000000040100c <phase_4>:
  40100c:	48 83 ec 18          	sub    $0x18,%rsp
  401010:	48 8d 4c 24 0c       	lea    0xc(%rsp),%rcx
  401015:	48 8d 54 24 08       	lea    0x8(%rsp),%rdx
  40101a:	be cf 25 40 00       	mov    $0x4025cf,%esi
  40101f:	b8 00 00 00 00       	mov    $0x0,%eax
  401024:	e8 c7 fb ff ff       	callq  400bf0 <__isoc99_sscanf@plt>
  401029:	83 f8 02             	cmp    $0x2,%eax
  40102c:	75 07                	jne    401035 <phase_4+0x29>
  40102e:	83 7c 24 08 0e       	cmpl   $0xe,0x8(%rsp)
  401033:	76 05                	jbe    40103a <phase_4+0x2e>
  401035:	e8 00 04 00 00       	callq  40143a <explode_bomb>
  40103a:	ba 0e 00 00 00       	mov    $0xe,%edx
  40103f:	be 00 00 00 00       	mov    $0x0,%esi
  401044:	8b 7c 24 08          	mov    0x8(%rsp),%edi
  401048:	e8 81 ff ff ff       	callq  400fce <func4>
  40104d:	85 c0                	test   %eax,%eax
  40104f:	75 07                	jne    401058 <phase_4+0x4c>
  401051:	83 7c 24 0c 00       	cmpl   $0x0,0xc(%rsp)
  401056:	74 05                	je     40105d <phase_4+0x51>
  401058:	e8 dd 03 00 00       	callq  40143a <explode_bomb>
  40105d:	48 83 c4 18          	add    $0x18,%rsp
  401061:	c3                   	retq

매번 분석의 시작은 sscanf이고, 인수의 개수부터 파악을 하고 시작하였다. 함수 sscanf를 호출한 결과는 %rax이므로, 이 값과 상수 0x2를 비교하여 같지 않으면 폭탄이 터진다는 것을 파악하였다. 따라서, input 2개를 받는다는 것을 확인할 수 있다.

 

그럼, 이게 정수인지 아닌지 확인하기 위하여 phase_2때 사용한 방법을 다시 활용하여보자. Instruction 40101a까지 실행한 이후, %rsi에 담긴 문자열을 확인하여보자.

(gdb) x/s $rsi
0x4025cf:       "%d %d"

정수 input 2개를 받는 것을 확인할 수 있다. 테스트를 위하여 "100 200"을 입력하여보자. 이후 instruction 0x40102e에서, 상수 0xe와 *(%rsp+0x8)을 비교하는 것을 볼 수 있다. 이때 jbe를 통해 비교하므로 x명령어로 *(%rsp+0x8)에 어떤 값이 들어있는지 먼저 확인하자.

(gdb) x/d $rsp+8
0x7fffffffdf28: 100

첫 번째 input이 들어와 있음을 확인할 수 있다. 현재 폭탄이 터지지 않으려면 jbe가 true가 되어야 하므로, 첫 번째 input은 0xe = 14보다 작아야 함을 알 수 있다. 

 

따라서, 새로운 테스트로 "1 345"를 넣어보도록 하자. 무사히 통과가 되는 것을 확인할 수 있다.

 

이후에 %edx 레지스터에 14, %esi 레지스터에 0, %edi 레지스터에 첫 번째 input을 넣고 func4 함수를 호출하는 모습을 볼 수 있다. 함수 호출 이후 %eax를 검사하여, jne (ZF = 0)일 경우 폭탄이 터지게 된다. (이는 phase_1에서 설명하였다.) 즉, func4 함수의 결과값으로 0이 나오지 않아야지 통과가 가능하다는 것을 유추할 수 있다.

 

그럼, 함수 func4를 분석하여보자.

0000000000400fce <func4>:
  400fce:	48 83 ec 08          	sub    $0x8,%rsp
  400fd2:	89 d0                	mov    %edx,%eax
  400fd4:	29 f0                	sub    %esi,%eax
  400fd6:	89 c1                	mov    %eax,%ecx
  400fd8:	c1 e9 1f             	shr    $0x1f,%ecx
  400fdb:	01 c8                	add    %ecx,%eax
  400fdd:	d1 f8                	sar    %eax
  400fdf:	8d 0c 30             	lea    (%rax,%rsi,1),%ecx
  400fe2:	39 f9                	cmp    %edi,%ecx
  400fe4:	7e 0c                	jle    400ff2 <func4+0x24>
  400fe6:	8d 51 ff             	lea    -0x1(%rcx),%edx
  400fe9:	e8 e0 ff ff ff       	callq  400fce <func4>
  400fee:	01 c0                	add    %eax,%eax
  400ff0:	eb 15                	jmp    401007 <func4+0x39>
  400ff2:	b8 00 00 00 00       	mov    $0x0,%eax
  400ff7:	39 f9                	cmp    %edi,%ecx
  400ff9:	7d 0c                	jge    401007 <func4+0x39>
  400ffb:	8d 71 01             	lea    0x1(%rcx),%esi
  400ffe:	e8 cb ff ff ff       	callq  400fce <func4>
  401003:	8d 44 00 01          	lea    0x1(%rax,%rax,1),%eax
  401007:	48 83 c4 08          	add    $0x8,%rsp
  40100b:	c3                   	retq

연산을 하나씩 따라가보자.

 

400fd2: %rax = %rdx

400fd4: %rax = %rax - %rsi

400df6: %rcx = %rax

400fd8: %rcx >>= 31 (%rax /= 2^31)

400fdb: %rax += %rcx

400fdd: %rax >>= 1 ( %rax /= 2)

400fdf: %rcx = %rax + %rsi ( * 1)

 

이 이후부터는 test를 통해 분기점을 가른다. %rcx가 %rdi보다 크다면 400ff2로 점프하고, 아니라면 %rdx에 *(%rdx - 1)

가 담기고 func4를 재호출한다. 즉, 재귀함수 꼴이라는 이야기이다.

 

함수 func4를 우리가 보기에 친숙한 형태로 C코드로 변환하면 다음과 같이 바꿀 수 있다. 위의 논리적인 구조를 천천히 따라와보자. 추가적인 정보로, shr라는 instruction을 쓴다는것 자체가 unsigned라는 것을 암시하고 있다.

unsigned int func4(unsigned int input, unsigned int* rdx, unsigned int* rsi) {
    unsigned int rax = ((*rdx - *rsi) + ((*rdx - *rsi) >> 31)) / 2;
    unsigned int rcx = rax + *rsi;
    
    if (rcx < input) {
    	*rsi = ++rcx;
        func4(input, rdx, rsi);
        return 2*rax + 1;
    } else if (rcx > input) {
        *rdx = --rcx;
        func4(input, rdx, rsi);
        return 2*rax + 1;
    } else {
        return 0;
    }
}

func4를 최초로 호출할 때 %rdx 레지스터에 14, %rsi 레지스터에 0, %rdi 레지스터에 첫 번째 input을 넣고 시작한다. 따라서, 위의 경우 최대한 재귀함수를 피하기 위해서는 rcx와 input값이 같아야 한다. 즉, rsi = 0이므로 rax와 input값이 같아야 하고, rdx에 14, rsi에 0을 대입하고 rax를 계산하여보면 rax = 0이어야 한다.

 

즉, 첫 번째 input이 0이면 모든 문제가 아주 쉬워진다는 것이다. 재귀함수를 호출하지 않는 유일한 경우는, 첫 번째 input으로 0을 넣는 경우이다.

 

아하! 이제 첫 번째 input에 0을 넣어다고 치면 func4를 통해 %rax 레지스터 안에 7이 담기므로, 폭탄을 피할 수 있다. 이후, 401051에서 [cmpl 0x0 0xc(%rsp)]를 하므로, *(%rsp + 0xc)를 살펴보아야 한다. phase_3때의 기억을 떠올려 보면 두 번째 input이 있을 가능성이 아주 높고, 실제로 phase_3때 썼던 방법을 사용하면 두 번째 input이 저장되어 있는 것을 알 수 있다. cmpl이 true여야지 폭탄을 피할 수 있으므로, 두 번째 input은 0이어야 하는 것을 추측할 수 있다. 

 

따라서, 첫 번째 input과 두 번째 input 모두 0이라 할 수 있다.

 

답 : 0 0

---

그럼, "첫 번째 input 0이 아닐 경우 재귀함수를 풀어서 그 값을 구해야하냐!"라는 질문이 나올 수 있는데, 사실 func4를 복구하였으면, 다음과 같은 방법으로 답의 후보를 뽑을 수 있다.

int solution() {
    for (int temp = 0; temp <= 15; temp++) {
        int res = func4(0xe, 0, temp);
        if (res == 0) {
            printf("%d ", res);
        }
    }
}

실제로 코드를 실행시켜보면, temp = 0, 1, 3, 7이 가능하다. 즉, 첫 번째 input으로는 0, 1, 3, 7이 가능하다는 의미이다.

 

답 : 0 0 / 1 0 / 3 0 / 7 0