Main

main 함수 분석

폭탄을 해체하기에 앞서, main 함수를 디스어셈블하여 프로그램의 전체적인 구조를 파악하자.

(현재 BOMB과는 다른 BOMB의 사진이지만, 설명에는 문제 없기에 해당 이미지를 사용하였습니다.)

main 함수의 흐름은 각 페이즈마다 read_line 함수로 입력을 받은 뒤, 해당 단계의 함수(phase_1, phase_2, ...)를 호출하는 구조로 이루어져 있다. read_line 함수의 반환 값, 즉 사용자 입력 문자열의 주소는 첫 번째 인자를 전달하는 레지스터인 %rdi에 저장되어 각 phase 함수로 전달된다. 그리고 phase_defused함수를 실행하는 구조로 이루어져있다.

우선은 이정도까지만 알고, phase1을 보도록 하자.

Phase 1

phase_1 함수를 디스어셈블하면 다음과 같다.

<+11>에서 strings_not_equal 함수를 호출하는 것이 핵심이다. 함수명으로 보아 두 문자열이 다른지 판별하는 역할을 추측할 수 있다. 함수의 인자는 리눅스 x86-64 호출 규약에 따라 %rdi, %rsi, %rdx, %rcx 순서로 전달된다.

• %rdi: main 함수에서 전달된 사용자 입력의 주소이다.
• %rsi: <+4>에서 0x18a1(%rip)에 위치한 값을 로드한다. 이는 정답 문자열의 주소일 확률이 높다.

GDB를 통해 %rsi에 로드될 메모리 주소에 저장된 문자열을 확인해보자.

정답으로 추정되는 문자열을 찾았다. strings_not_equal 함수는 두 문자열이 다르면 0이 아닌 값을 반환하고, 같으면 0을 반환할 것이다. <+16>, <+18>의 jne (Jump if Not Equal) 명령어는 함수의 반환 값(%eax)이 0일 때 분기하여 폭탄을 맞게 되므로, 두 문자열이 같아야 함을 알 수 있다.

따라서 Phase 1의 정답은 GDB로 확인한 문자열이다.

답: When I get angry, Mr. Bigglesworth gets upset.

Phase 2

phase_2는 phase_1보다 길지만, 순차적으로 분석하면 복잡하지 않다.

함수의 초반부(_start ~ <+22>)는 스택 공간을 설정하는 전처리 과정이다. fs:0x28의 주소는 스택 가드 검사를 위한 것이라고 한다. - https://stackoverflow.com/questions/10325713/why-does-this-memory-address-fs0x28-fs0x28-have-a-random-value)

1. 입력 형식 확인

<+25>에서 read_six_numbers 함수를 호출하는 것으로 보아, 6개의 정수를 입력받는 것을 추측할 수 있다. GDB를 사용하여 이 추측을 확인한다.

1. *phase_2 + 25에 breakpoint를 설정한다.
2. 임의의 6개 정수(3 2 1 0 1 2)를 입력하고 프로그램을 실행한다.
3. ni 명령어로 read_six_numbers 함수를 실행시킨 후, 스택 포인터($rsp)가 가리키는 메모리 영역을 16진수, Word단위로 확인한다.

스택을 확인하면 입력한 3 2 1 0 1 2가 순서대로 저장된 것을 볼 수 있으며, 이를 통해 6개의 정수를 입력받는다는 추측이 옳았음을 알 수 있다.

2. 첫 번째 숫자의 조건

다음 명령어는 스택의 가장 위에 있는 값, 즉 첫 번째 입력값과 0x1을 비교한다.

*(%rsp)는 스택의 최상단 값을 의미하며, 이는 첫 번째로 입력한 정수이다. jne(Jump if Not Equal) 명령어를 통해 이 값이 1이 아니면 폭탄이 터지는 것을 알 수 있다. 따라서 첫 번째 숫자는 반드시 1이어야 한다.

현재까지의 답: 1 ? ? ? ? ?

3. 나머지 숫자의 규칙

첫 번째 숫자가 1이라는 사실을 바탕으로, 나머지 다섯 개 숫자의 규칙을 파악하기 위해 프로그램의 핵심 로직인 반복문을 분석해보자. 이를 위해 첫 번째 폭탄을 피할 수 있는 1로 시작하는 임의의 입력값인 1 2 1 0 1 2을 사용한다.

반복문 진입 전 레지스터 및 메모리 설정

반복문에 진입하기 전, 프로그램은 다음과 같이 레지스터와 메모리를 설정한다.

• <+36> mov %rsp, %rbx: %rbx 레지스터가 %rsp가 가리키는 스택에 저장된 6개의 숫자 배열의 시작 주소를 가리키도록 한다.
• <+39> lea 0x14(%rbx), %rbp: %rbp 레지스터에 *(%rbx+20)의 값을 저장한다. (0x14 = 20) 앞서 봤듯, 입력된 6개의 정수는 워드(4바이트) 단위로 *(%rbx),*(%rsp)가 가리키는 주소에 연속적으로 저장된다. %rbx를 기준으로 각 숫자의 위치는 다음과 같다.

  • (%rbx): 첫 번째 숫자

  • (%rbx + 4): 두 번째 숫자

  • (%rbx + 8): 세 번째 숫자

  • ...

  • (%rbx + 20): 여섯 번째 숫자

    따라서 마지막에 입력한 값인 2가 %rbp에 저장된다.

반복문 로직 분석

1. 값 로드

   <+61> mov (%rbx),%eax 명령어를 통해 포인터 %rbx가 가리키는 현재 값을 %eax 레지스터에 로드한다. 예를 들어, 루프의 첫 진입 시 %rbx는 첫 번째 숫자인 1을 가리키므로 %eax에는 1이 저장된다.

2. 2배 연산

   <+63> add %eax,%eax를 실행하여 %eax의 값을 2배로 만든다. (%eax는 1 * 2 = 2가 된다).

3. 값 비교

   <+65> cmp %eax,0x4(%rbx)는 2배가 된 %eax의 값과 다음 숫자를 비교한다. 0x4(%rbx)는 현재 위치에서 4바이트 떨어진 주소, 즉 배열의 다음 원소를 의미한다.

4. 조건부 분기

   <+68>의 je 명령어는 비교 결과 두 값이 같을 경우에만 분기하여 폭탄을 피하게 한다.

5. 포인터 값 이동
   <+52> add $0X4, %rbx를 취해 %rbx의 값을 4씩 증가시키며(다음 숫자로 이동) 입력된 6개의 숫자를 모두 순회할 때까지 계속된다. (종료기준: <+56>, <+59>)

이 로직을 통해 N번째 숫자는 N-1번째 숫자의 2배여야 한다는 핵심 규칙($N_i =2 \times N_{i-1}$)을 도출할 수 있다.

앞서 첫 번째 숫자는 1이어야 함을 확인했고, 나머지 숫자들은 이전 숫자의 2배라는 규칙을 따르므로 전체 수열을 완성할 수 있다.

답: 1 2 4 8 16 32