-
[CS:APP/시스템 프로그래밍] Bomb Lab 풀이Programming/CS:APP 2024. 4. 1. 20:58
CMU CSAPP (Computer Systems: A Programmers Perspective, 컴퓨터 시스템) Bomb Lab 과제 Solution 및 해설입니다.
objdump를 활용한 리버스 엔지니어링을 통해 각 페이즈 해체 과정과 숨겨진 페이즈를 찾는 방법, 그리고 어셈블리 코드 분석 전략을 단계별로 설명합니다.Bomb Lab 시작하기
CMU CSAPP 홈페이지 에서 과제 다운로드가 가능하다.
wget http://csapp.cs.cmu.edu/3e/bomb.tar과제 파일 압축을 풀어준다. 안에는 실행 가능한 bomb 파일이 있다.
파일은 총 6번에 걸쳐 문자열 입력을 받는다. 잘못된 문자열을 입력시 폭탄이 폭발한다.폭탄이 폭발할 때마다 점수가 깎인다.
리버스 엔지니어링 스킬을 총동원해 올바른 문자열을 알아내고 폭탄을 해체해야 한다.(나처럼) 혼자서 진행할 경우 점수 시스템은 이용할 수 없다.
그래도 사명감을 갖고 폭탄이 터지지 않도록 주의해서 풀어보도록 한다.폭탄 해체는 실행 파일을 어셈블리어로 변환해서 진행한다.
어셈블리어 해석 시 각 레지스터 별 이름/역할이 헷갈려서 찾아 볼 일이 많다.
레퍼런스를 하나 띄워 놓고 작업하기를 추천한다.
여러 자료를 찾아봤는데, 스탠포드 대학교의 x86-64-reference cheat sheet 이 가장 미니멀하고 깔끔하게 정리를 잘 해놓았다.Objdump 사용하기
주어진 바이너리 실행 파일을 어셈블리어로 변환한다.
역어셈블러는 objdump를 사용하기로 했다.
gdb를 사용해도 좋지만 텍스트 파일로 왕창 변환해서 옆에 주석 달며 해석하는 게 더 취향에 맞았다.
터미널에서
objdump -d <file_name>를 실행하면 해당 파일의 어셈블리어 코드가 출력된다.objdump -d bomb분석의 편의를 위해 별도 텍스트 파일로 저장해주었다.
objdump -d --visualize-jumps bomb > bomb_disassembled.txt-visualize-jumps옵션은 man 페이지 읽다가 발견한 옵션인데, 화살표를 사용해 점프 인스트럭션을 시각화 해주는 옵션이다.
코드 구조 파악, 특히 반복문 해석할 때 엄청 유용하다.0000000000400da0 <main>: 400da0: 53 push %rbx 400da1: 83 ff 01 cmp $0x1,%edi 400da4: /-- 75 10 jne 400db6 <main+0x16> 400da6: | 48 8b 05 9b 29 20 00 mov 0x20299b(%rip),%rax # 603748 <stdin@GLIBC_2.2.5> 400dad: | 48 89 05 b4 29 20 00 mov %rax,0x2029b4(%rip) # 603768 <infile> 400db4: /--|-- eb 63 jmp 400e19 <main+0x79> 400db6: | \-> 48 89 f3 mov %rsi,%rbx 400db9: | 83 ff 02 cmp $0x2,%edibomb_disassembled.txt에는 bomb 파일의 실행 가능한 부분만 들어있다.
파일 내에서 사용되는 각종 변수에 관한 정보는 담겨있지 않다.프로그램의 메모리 세그먼트에서 읽기 전용
.rodata(초기화된) 전역 변수.data를 찾아와 따로 저장해준다.objdump -s -j .rodata bomb > bomb_rodata.txtContents of section .rodata: 4022b0 01000200 72002573 3a204572 726f723a ....r.%s: Error: 4022c0 20436f75 6c646e27 74206f70 656e2025 Couldn't open % 4022d0 730a0055 73616765 3a202573 205b3c69 s..Usage: %s [<i 4022e0 6e707574 5f66696c 653e5d0a 00546861 nput_file>]..Tha 4022f0 74277320 6e756d62 65722032 2e20204b t's number 2. K 402300 65657020 676f696e 67210048 616c6677 eep going!.Halfw%s와 같은scanf용 포매팅 문자열이 눈에 띈다.
각 페이즈 안내문으로 추정되는 문장도 발견할 수 있다.402400 426f7264 65722072 656c6174 696f6e73 Border relations 402410 20776974 68204361 6e616461 20686176 with Canada hav 402420 65206e65 76657220 6265656e 20626574 e never been bet 402430 7465722e 00000000 576f7721 20596f75 ter.....Wow! You 402440 27766520 64656675 73656420 74686520 've defused the 402450 73656372 65742073 74616765 2100666c secret stage!.fl 402460 79657273 00000000 00000000 00000000 yers............정답과 관련 있어 보이는 수상한 문장도 보이고, 숨겨진 스테이지에 관한 언급도 있다.
숨겨진 스테이지를 찾아보는 것도 재미있겠다..data섹션도 저장해놓자.objdump -s -j .data bomb > bomb_data.txtContents of section .data: 6030e0 00000000 00000000 00000000 00000000 ................ 6030f0 24000000 00000000 10316000 00000000 $........1`..... 603100 30316000 00000000 00000000 00000000 01`............. 603110 08000000 00000000 90316000 00000000 .........1`..... 603120 50316000 00000000 00000000 00000000 P1`............. 603130 32000000 00000000 70316000 00000000 2.......p1`..... 603140 b0316000 00000000 00000000 00000000 .1`............. 603150 16000000 00000000 70326000 00000000 ........p2`......data파트에는 의미 불명 데이터가 들어가 있다. 일단 넘어가자.준비가 끝났으니 폭탄 해체를 시작해본다.
Defusing Bomb
bomb_disassembled.txt파일을 열어보자.가장 먼저
main함수를 확인해본다.main의 초기 부분은 command line argument를 처리하고 폭탄을 세팅하고 있는 듯 하다.0000000000400da0 <main>: 400da0: 53 push %rbx 400da1: 83 ff 01 cmp $0x1,%edi 400da4: /-- 75 10 jne 400db6 <main+0x16> 400da6: | 48 8b 05 9b 29 20 00 mov 0x20299b(%rip),%rax # 603748 <stdin@GLIBC_2.2.5> 400dad: | 48 89 05 b4 29 20 00 mov %rax,0x2029b4(%rip) # 603768 <infile> 400db4: /--|-- eb 63 jmp 400e19 <main+0x79> 400db6: | \-> 48 89 f3 mov %rsi,%rbx 400db9: | 83 ff 02 cmp $0x2,%edi 400dbc: | /-- 75 3a jne 400df8 <main+0x58> 400dbe: | | 48 8b 7e 08 mov 0x8(%rsi),%rdi 400dc2: | | be b4 22 40 00 mov $0x4022b4,%esi 400dc7: | | e8 44 fe ff ff call 400c10 <fopen@plt> 400dcc: | | 48 89 05 95 29 20 00 mov %rax,0x202995(%rip) # 603768 <infile> 400dd3: | | 48 85 c0 test %rax,%rax 400dd6: +--|-- 75 41 jne 400e19 <main+0x79> 400dd8: | | 48 8b 4b 08 mov 0x8(%rbx),%rcx 400ddc: | | 48 8b 13 mov (%rbx),%rdx 400ddf: | | be b6 22 40 00 mov $0x4022b6,%esi 400de4: | | bf 01 00 00 00 mov $0x1,%edi 400de9: | | e8 12 fe ff ff call 400c00 <__printf_chk@plt> 400dee: | | bf 08 00 00 00 mov $0x8,%edi 400df3: | | e8 28 fe ff ff call 400c20 <exit@plt> 400df8: | \-> 48 8b 16 mov (%rsi),%rdx 400dfb: | be d3 22 40 00 mov $0x4022d3,%esi 400e00: | bf 01 00 00 00 mov $0x1,%edi 400e05: | b8 00 00 00 00 mov $0x0,%eax 400e0a: | e8 f1 fd ff ff call 400c00 <__printf_chk@plt> 400e0f: | bf 08 00 00 00 mov $0x8,%edi 400e14: | e8 07 fe ff ff call 400c20 <exit@plt> 400e19: \----> e8 84 05 00 00 call 4013a2 <initialize_bomb>일단 넘어가기로 하자.
이후 각 페이즈마다
<read_line>함수를 사용해 문자열 입력을 받고있다.
문자열은 각 페이즈를 담당하는 함수에 넘겨주고 있다.400e1e: bf 38 23 40 00 mov $0x402338,%edi 400e23: e8 e8 fc ff ff call 400b10 <puts@plt> 400e28: bf 78 23 40 00 mov $0x402378,%edi 400e2d: e8 de fc ff ff call 400b10 <puts@plt> 400e32: e8 67 06 00 00 call 40149e <read_line> 400e37: 48 89 c7 mov %rax,%rdi 400e3a: e8 a1 00 00 00 call 400ee0 <phase_1> 400e3f: e8 80 07 00 00 call 4015c4 <phase_defused> 400e44: bf a8 23 40 00 mov $0x4023a8,%edi 400e49: e8 c2 fc ff ff call 400b10 <puts@plt> 400e4e: e8 4b 06 00 00 call 40149e <read_line> 400e53: 48 89 c7 mov %rax,%rdi 400e56: e8 a1 00 00 00 call 400efc <phase_2> 400e5b: e8 64 07 00 00 call 4015c4 <phase_defused>1페이즈부터 확인해보자.
<phase_1>함수가 잇는0x400ee0주소로 이동한다.Phase 1
phase_1 함수는 다음과 같다.
0000000000400ee0 <phase_1>: 400ee0: 48 83 ec 08 sub $0x8,%rsp 400ee4: be 00 24 40 00 mov $0x402400,%esi 400ee9: e8 4a 04 00 00 call 401338 <strings_not_equal> 400eee: 85 c0 test %eax,%eax 400ef0: /-- 74 05 je 400ef7 <phase_1+0x17> 400ef2: | e8 43 05 00 00 call 40143a <explode_bomb> 400ef7: \-> 48 83 c4 08 add $0x8,%rsp 400efb: c3 retstrings_not_equal함수를 통해 두 문자열을 비교하고 두 문자열이 다르면 폭탄이 터지는 구조이다.strings_not_equal함수의 첫 번째 인자는%rdi이다. main 함수에서 넘겨준 인자이고, 우리가 입력한 문자열이다.함수의 두 번째 인자
%rsi(%esi)는$0x402400이다. 입력과 비교하는 정답 문자열이다.문자열은 포인터(
char *)로 전달된다. 주소0x402400에 있는 문자를 확인해보자.읽기 전용 데이터,
.rodata에서 주소0x402400부분을 확인하자.<주소> <16진수 값> <문자열>형식으로 표현되어있다.402400 426f7264 65722072 656c6174 696f6e73 Border relations 402410 20776974 68204361 6e616461 20686176 with Canada hav 402420 65206e65 76657220 6265656e 20626574 e never been bet 402430 7465722e 00000000 576f7721 20596f75 ter.....Wow! You"Border relations with Canada have never been better." 가 바로 정답이다.
objdump에서 NUL character
\0을.으로 표현하고 있음에 주의하자.
마침표.(ASCII:2e) 와 NUL character\0(ASCII:00)는 실제 16진수 값을 보고 구분 해야한다.꼼꼼하게 보면 알겠지만, 정답이 마침표를 포함한다.
1페이즈를 C언어로 표현하면 이런 느낌이겠다.
char *phase_1_ans = "Border relations with Canada have never been better."; void phase_1(char *input) { if (strings_not_equal(input, phase_1_ans)) { explode_bomb(); } }정답을 확인해보자. 폭탄 파일을 실행하고 정답을 입력해보면 된다.
입력간에 오타를 낸다면 폭탄이 터져버린다. (가상의) 점수가 깎여버린다.
아예 폭탄이 터지지 않도록 막아버리자.gdb를 통해 폭탄을 터트리는
explode_bomb함수에다가 breakpoint를 걸어준다.gdb ./bomb (gdb) b explode_bomb (gdb) run Welcome to my fiendish little bomb. You have 6 phases with which to blow yourself up. Have a nice day! > Border relations with Canada have never been better. Phase 1 defused. How about the next one?정답. 1페이즈를 성공적으로 해치웠다.
Phase 2
phase_2 함수는 다음과 같다.
0000000000400efc <phase_2>: 400efc: 55 push %rbp 400efd: 53 push %rbx 400efe: 48 83 ec 28 sub $0x28,%rsp 400f02: 48 89 e6 mov %rsp,%rsi 400f05: e8 52 05 00 00 call 40145c <read_six_numbers> 400f0a: 83 3c 24 01 cmpl $0x1,(%rsp) 400f0e: /----- 74 20 je 400f30 <phase_2+0x34> 400f10: | e8 25 05 00 00 call 40143a <explode_bomb> 400f15: +----- eb 19 jmp 400f30 <phase_2+0x34> 400f17: /--|----> 8b 43 fc mov -0x4(%rbx),%eax 400f1a: | | 01 c0 add %eax,%eax 400f1c: | | 39 03 cmp %eax,(%rbx) 400f1e: | | /-- 74 05 je 400f25 <phase_2+0x29> 400f20: | | | e8 15 05 00 00 call 40143a <explode_bomb> 400f25: | | \-> 48 83 c3 04 add $0x4,%rbx 400f29: | | 48 39 eb cmp %rbp,%rbx 400f2c: +--|----- 75 e9 jne 400f17 <phase_2+0x1b> 400f2e: | | /-- eb 0c jmp 400f3c <phase_2+0x40> 400f30: | \--|-> 48 8d 5c 24 04 lea 0x4(%rsp),%rbx 400f35: | | 48 8d 6c 24 18 lea 0x18(%rsp),%rbp 400f3a: \-----|-- eb db jmp 400f17 <phase_2+0x1b> 400f3c: \-> 48 83 c4 28 add $0x28,%rsp 400f40: 5b pop %rbx 400f41: 5d pop %rbp 400f42: c3 ret점프에 따른 분기 생성 이전부터 확인해보자.
0000000000400efc <phase_2>: 400efc: 55 push %rbp 400efd: 53 push %rbx 400efe: 48 83 ec 28 sub $0x28,%rsp 400f02: 48 89 e6 mov %rsp,%rsi 400f05: e8 52 05 00 00 call 40145c <read_six_numbers>스택에
0x28만큼 공간을 할당했다.
이후 포인터를(%rsp)read_six_numbers의 두 번째 인자(%rsi)로 전달한다.함수명으로 짐작하건데, 유저가 입력한 문자열(
%rdi)에서 정수 여섯 개를 읽어%rsi가 있는 위치에 전달하는 듯 하다.read_six_numbers함수를 한번 확인해본다.000000000040145c <read_six_numbers>: 40145c: 48 83 ec 18 sub $0x18,%rsp 401460: 48 89 f2 mov %rsi,%rdx 401463: 48 8d 4e 04 lea 0x4(%rsi),%rcx 401467: 48 8d 46 14 lea 0x14(%rsi),%rax 40146b: 48 89 44 24 08 mov %rax,0x8(%rsp) 401470: 48 8d 46 10 lea 0x10(%rsi),%rax 401474: 48 89 04 24 mov %rax,(%rsp) 401478: 4c 8d 4e 0c lea 0xc(%rsi),%r9 40147c: 4c 8d 46 08 lea 0x8(%rsi),%r8 401480: be c3 25 40 00 mov $0x4025c3,%esi 401485: b8 00 00 00 00 mov $0x0,%eax 40148a: e8 61 f7 ff ff call 400bf0 <__isoc99_sscanf@plt> 40148f: 83 f8 05 cmp $0x5,%eax 401492: /-- 7f 05 jg 401499 <read_six_numbers+0x3d> 401494: | e8 a1 ff ff ff call 40143a <explode_bomb> 401499: \-> 48 83 c4 18 add $0x18,%rsp 40149d: c3 ret주소 복사가 잔뜩 있다. sscanf 함수에 전달하기 위한 인자를 준비하는 듯 하다.
각각 살펴보면 다음과 같다.
- 첫 번째 인자(
%rdi): 입력 문자열 - 두 번째 인자(
%rsi):$0x4025c3,.rodata확인 결과"%d %d %d %d %d %d"(int 6개) - 세 번째 인자(
%rdx): phase_2가 전달한%rsi, 포인터int *arr(혹은&arr[0]) - 네 번째 인자(
%rcx): phase_2가 전달한%rsi+ 4인 주소, 포인터arr + 1(혹은&arr[1]) - 다섯 번째 인자(
%r8): phase_2가 전달한%rsi+ 8인 주소, 포인터arr + 2(혹은&arr[2]) - 여섯 번째 인자(
%r9): phase_2가 전달한%rsi+ 12인 주소, 포인터arr + 3(혹은&arr[3]) - 일곱 번째 인자(
(%rsp)): phase_2가 전달한%rsi+ 16인 주소, 포인터arr + 4(혹은&arr[4]) - 여덟 번째 인자(
0x8(%rsp)): phase_2가 전달한%rsi+ 20인 주소, 포인터arr + 5(혹은&arr[5])
sscanf함수의 리턴 값%eax가 5보다 작거나 같으면 폭탄이 폭발한다.sscanf함수는 읽기에 성공한 토큰 개수를 반환한다. 즉, 두 번째 문자열은 정수 6개로 이루어져야 한다.C로는 이런 느낌일테다.
void read_six_numbers(char *input, int *arr) { int num_scanned; num_scanned = sscanf(input, "%d %d %d %d %d %d", arr, arr + 1, arr + 2, arr + 3, arr + 4, arr + 5); if (num_scanned <= 5) { explode_bomb(); } }이제 다시 phase_2 함수로 돌아가자.
0000000000400efc <phase_2>: /* ... */ 400f05: e8 52 05 00 00 call 40145c <read_six_numbers> 400f0a: 83 3c 24 01 cmpl $0x1,(%rsp) 400f0e: /----- 74 20 je 400f30 <phase_2+0x34> 400f10: | e8 25 05 00 00 call 40143a <explode_bomb> 400f15: +----- eb 19 jmp 400f30 <phase_2+0x34>(%rsp)가 1이 아니면 폭발한다.
현재%rsp에는 배열(포인터)arr이 들어있다. 따라서(%rsp)는arr[0]이다.즉, 입력한 문자열은 숫자 1로 시작해야 된다는 말이다.
입력한 문자열이 1로 시작한다면,
0x400f30으로 점프한다.
주변 부분을 자세히 살펴보자.0000000000400efc <phase_2>: /* ... */ 400f17: /--|----> 8b 43 fc mov -0x4(%rbx),%eax 400f1a: | | 01 c0 add %eax,%eax 400f1c: | | 39 03 cmp %eax,(%rbx) 400f1e: | | /-- 74 05 je 400f25 <phase_2+0x29> 400f20: | | | e8 15 05 00 00 call 40143a <explode_bomb> 400f25: | | \-> 48 83 c3 04 add $0x4,%rbx 400f29: | | 48 39 eb cmp %rbp,%rbx 400f2c: +--|----- 75 e9 jne 400f17 <phase_2+0x1b> 400f2e: | | /-- eb 0c jmp 400f3c <phase_2+0x40> 400f30: | \--|-> 48 8d 5c 24 04 lea 0x4(%rsp),%rbx 400f35: | | 48 8d 6c 24 18 lea 0x18(%rsp),%rbp 400f3a: \-----|-- eb db jmp 400f17 <phase_2+0x1b> 400f3c: \-> 48 83 c4 28 add $0x28,%rsp 400f40: 5b pop %rbx 400f41: 5d pop %rbp 400f42: c3 ret루프 구조가 눈에 띈다.
화살표를 따라 구조를 관찰해보자.
400f30~400f3a부분은 루프 시작 전 초기화 단계 (이하LOOP_INIT)400f17~400f2c부분은 루프를 통해 반복되는 내용 (이하LOOP_BODY)
임을 알 수 있다.LOOP_INIT에서는%rbx와%rbp를 초기화하고 있다./* LOOP_INIT */ 400f30: 48 8d 5c 24 04 lea 0x4(%rsp),%rbx 400f35: 48 8d 6c 24 18 lea 0x18(%rsp),%rbp 400f3a: eb db jmp 400f17 <phase_2+0x1b>%rbx에는0x4(%rsp), 즉&arr[1]값이%rbp에는0x18(%rsp), 즉&arr[6]값이 들어간다.코딩 눈치를 약간 발휘해보면
%rbx를 iteration의 현재 포인터,%rbp는 종료 조건(Sentinel)으로arr배열을 순회 할 준비를 하는 것 같다.LOOP_BODY를 살펴보자./* LOOP BODY */ 400f17: /-------> 8b 43 fc mov -0x4(%rbx),%eax 400f1a: | 01 c0 add %eax,%eax 400f1c: | 39 03 cmp %eax,(%rbx) 400f1e: | /-- 74 05 je 400f25 <phase_2+0x29> 400f20: | | e8 15 05 00 00 call 40143a <explode_bomb> 400f25: | \-> 48 83 c3 04 add $0x4,%rbx 400f29: | 48 39 eb cmp %rbp,%rbx 400f2c: +-------- 75 e9 jne 400f17 <phase_2+0x1b>%rbx가 배열에서 현재 순회 중인 원소를 나타낸다면,-0x4(%rbx)는 그 이전 값이다. (4 forintsize)이를테면
%rbx가&arr[2]일때-0x4(%rbx)는&arr[1]이다.
따라서%eax는arr[1] + arr[1]가 들어간다.이때
%eax값과(%rbx)값이 다르다면 폭탄이 터진다. 두 값은 같아야한다.
즉 arr의 이전값을 두 번 더한 값은 현재값과 같아야 한다.이후
%rbx값을 증가시키고 (다음 원소)%rbp와 비교해 루프 종료를 확인한다.C로 번역해보면 이런 모습일테다.
void phase_2(char *input) { int *curp; int *endp; int *arr; read_six_numbers(input, arr); if (*arr != 1) { explode_bomb(); } curp = arr + 1; enp = arr + 6; do { if (*curp != *(curp - 1) + *(curp - 1)) { explode_bomb(); } curp++; } while (curp != endp); }혹은 이렇게 더 직관적으로 의역 해 볼 수 있다.
void phase_2(char *input) { int arr[6]; read_six_numbers(input, arr); if (arr[0] != 1) { explode_bomb(); } for (int i = 1; i < 6; i++) { if (arr[i] != 2 * arr[i - 1]) { explode_bomb(); } } }결국 정답은 1부터 시작해서 2배 씩 커지는 6자리 수열임을 알 수 있다.
1 2 4 8 16 32를 입력해본다.> 1 2 4 8 16 32 That's number 2. Keep going!Phase 3
점점 함수 길이가 길어진다.
앞 부분부터 먼저 살펴보자.0000000000400f43 <phase_3>: 400f43: 48 83 ec 18 sub $0x18,%rsp 400f47: 48 8d 4c 24 0c lea 0xc(%rsp),%rcx 400f4c: 48 8d 54 24 08 lea 0x8(%rsp),%rdx 400f51: be cf 25 40 00 mov $0x4025cf,%esi 400f56: b8 00 00 00 00 mov $0x0,%eax 400f5b: e8 90 fc ff ff call 400bf0 <__isoc99_sscanf@plt> 400f60: 83 f8 01 cmp $0x1,%eax 400f63: /-- 7f 05 jg 400f6a <phase_3+0x27> 400f65: | e8 d0 04 00 00 call 40143a <explode_bomb> 400f6a: \-> 83 7c 24 08 07 cmpl $0x7,0x8(%rsp) 400f6f: /----- 77 3c ja 400fad <phase_3+0x6a> /* ...................... */ 400fad: \--|-> e8 88 04 00 00 call 40143a <explode_bomb>read_six_integer에서 한 번 본 구조다.sscanf함수를 통해 문자열에서 정수 두 개를 읽고 있다.그 다음, 정확히 2개를 읽었는지 확인하고 첫 번째 정수
0x8(%rsp)(%rdx) 값이 7보다 크면 폭발한다.참고로
cmpl을 통해 비교하므로 -1(0xFFFFFFFF)역시 7보다 큰 값으로 처리된다.void phase_3(char *input) { int first, second; int num_scanned; num_scanned = sscanf(input, "%d %d", &first, &second); if (num_scanned <= 1) { explode_bomb(); } if (first > 7 || first < 0) { explode_bomb(); } /* ... */ }다음 부분을 보자
0000000000400f43 <phase_3>: /* ... */ 400f71: 8b 44 24 08 mov 0x8(%rsp),%eax 400f75: ff 24 c5 70 24 40 00 jmp *0x402470(,%rax,8) 400f7c: b8 cf 00 00 00 mov $0xcf,%eax 400f81: /-- eb 3b jmp 400fbe <phase_3+0x7b> 400f83: | b8 c3 02 00 00 mov $0x2c3,%eax 400f88: +-- eb 34 jmp 400fbe <phase_3+0x7b> 400f8a: | b8 00 01 00 00 mov $0x100,%eax 400f8f: +-- eb 2d jmp 400fbe <phase_3+0x7b> 400f91: | b8 85 01 00 00 mov $0x185,%eax 400f96: +-- eb 26 jmp 400fbe <phase_3+0x7b> 400f98: | b8 ce 00 00 00 mov $0xce,%eax 400f9d: +-- eb 1f jmp 400fbe <phase_3+0x7b> 400f9f: | b8 aa 02 00 00 mov $0x2aa,%eax 400fa4: +-- eb 18 jmp 400fbe <phase_3+0x7b> 400fa6: | b8 47 01 00 00 mov $0x147,%eax 400fab: +-- eb 11 jmp 400fbe <phase_3+0x7b> 400fad: | e8 88 04 00 00 call 40143a <explode_bomb> 400fb2: | b8 00 00 00 00 mov $0x0,%eax 400fb7: +-- eb 05 jmp 400fbe <phase_3+0x7b> 400fb9: | b8 37 01 00 00 mov $0x137,%eax 400fbe: \-> 3b 44 24 0c cmp 0xc(%rsp),%eax%eax에 첫 번째 정수를 넣고,0x402470에 있는 값에(%rax * 8)을 더한 주소로 이동하고 있다.점프 테이블 구조인 것 같다.
.rodata에서0x402470값을 확인해보자402470 7c0f4000 00000000 b90f4000 00000000 |.@.......@..... 402480 830f4000 00000000 8a0f4000 00000000 ..@.......@..... 402490 910f4000 00000000 980f4000 00000000 ..@.......@..... 4024a0 9f0f4000 00000000 a60f4000 00000000 ..@.......@.....7c0f400 00000000, 리틀 엔디안으로 변환하면0x400f7c가 된다.즉 이런 구조이다.
0000000000400f43 <phase_3>: /* ... */ 400f75: ff 24 c5 70 24 40 00 jmp *0x402470(,%rax,8) /* first == 0 */ 400f7c: b8 cf 00 00 00 mov $0xcf,%eax 400f81: /-- eb 3b jmp 400fbe <phase_3+0x7b> /* first == 1 */ 400f83: | b8 c3 02 00 00 mov $0x2c3,%eax 400f88: +-- eb 34 jmp 400fbe <phase_3+0x7b> /* first == 2 */ 400f8a: | b8 00 01 00 00 mov $0x100,%eax 400f8f: +-- eb 2d jmp 400fbe <phase_3+0x7b> /* first == 3 */ 400f91: | b8 85 01 00 00 mov $0x185,%eax 400f96: +-- eb 26 jmp 400fbe <phase_3+0x7b> /* first == 4 */ 400f98: | b8 ce 00 00 00 mov $0xce,%eax 400f9d: +-- eb 1f jmp 400fbe <phase_3+0x7b> /* first == 5 */ 400f9f: | b8 aa 02 00 00 mov $0x2aa,%eax 400fa4: +-- eb 18 jmp 400fbe <phase_3+0x7b> /* first == 6 */ 400fa6: | b8 47 01 00 00 mov $0x147,%eax 400fab: +-- eb 11 jmp 400fbe <phase_3+0x7b> /* first value out of range */ 400fad: | e8 88 04 00 00 call 40143a <explode_bomb> 400fb2: | b8 00 00 00 00 mov $0x0,%eax 400fb7: +-- eb 05 jmp 400fbe <phase_3+0x7b> 400fb9: | b8 37 01 00 00 mov $0x137,%eax /* After Jump Table */ 400fbe: \-> 3b 44 24 0c cmp 0xc(%rsp),%eax 400fc2: /-- 74 05 je 400fc9 <phase_3+0x86> 400fc4: | e8 71 04 00 00 call 40143a <explode_bomb> 400fc9: \-> 48 83 c4 18 add $0x18,%rsp 400fcd: c3 ret0~6의 정수 값에 대응되는 정해진 정답
%eax값이 존재하고, 입력한 두 번째 정수가 정답값과 일치해야 폭탄이 해제되는 구조이다.마치 로그인할 때 아이디랑 비밀번호를 입력하는 느낌과 비슷하다.
C 코드로 변환하면 다음과 같다.
void phase_3(char *input) { int user_id, input_pw; int valid_pw; int num_scanned; num_scanned = sscanf(input, "%d %d", &user_id, &input_pw); if (num_scanned <= 1) { explode_bomb(); } switch (user_id) { case 0: valid_pw = 207; break; case 1: valid_pw = 311; break; case 2: valid_pw = 707; break; case 3: valid_pw = 256; break; case 4: valid_pw = 389; break; case 5: valid_pw = 206; break; case 6: valid_pw = 682; break; case 7; valid_pw = 327; break; default: explode_bomb(); valid_pw = 0; break; } if (input_pw != valid_pw) { explode_bomb(); } }16진법 변환은 Windows Powertoys Run 을 사용했다.
암산을 해도 되고, 터미널에서 처리해도 되고 방법은 많다.
개인적으로 대충 후딱 보기엔 이게 제일 편하다.정답쌍이 7가지나 있으니 아무거나 선택해준다.
> 0 207 Halfway there!Phase 4
처음 부분을 살펴보자.
이젠 너무 익숙한sscanf진행이다.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 call 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 call 40143a <explode_bomb>C 코드로 해석하면 아래와 같다.
void phase_4(char *input) { int first, second; int num_scanned; num_scanned = sscanf(input, "%d %d", &first, &second); if (num_scanned != 2) { explode_bomb(); } if (first > 14 || first < 0) { explode_bomb(); } }first값의 범위 조건을 기억해두고 다음 파트를 보자000000000040100c <phase_4>: /* ... */ 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 call 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 call 40143a <explode_bomb> 40105d: \-> 48 83 c4 18 add $0x18,%rsp 401061: c3 retfunc4함수에 인수로 first값, 0, 14를 전달하고 있다.func4함수의 return 값이 0이 아닐 경우, 두 번째 입력 값이 0이 아닐경우 폭탄이 폭발한다.void phase_4(int *input) { /* ... */ int func4_res; func4_res = func4(first, 0, 14); if (func4_ret != 0 || second != 0) { explode_bomb(); } }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 call 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 call 400fce <func4> 401003: | 8d 44 00 01 lea 0x1(%rax,%rax,1),%eax 401007: \----> 48 83 c4 08 add $0x8,%rsp 40100b: c3 ret재귀적으로 구성이 되어있다.
먼저 처음 파트
%ecx와%eax값 변화에 집중을 해보자func4(arg1, arg2, arg3)라 할 때,%eax = arg3 - arg2가 된다.0000000000400fce <func4>: 400fce: 48 83 ec 08 sub $0x8,%rsp 400fd2: 89 d0 mov %edx,%eax 400fd4: 29 f0 sub %esi,%eax%ecx = (arg3 - arg2) >> 31 (logical)이다.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종합해보면
%eax = arg3 - arg2 + (arg3 - arg2) >> 31 (logical),%eax = %eax >> 1%ecx = %rax + arg2
이렇게 식을 정리해볼 수 있겠다.(arg3 - arg2) >> 31이 파트는 음수의 나눗셈에서 0 방향으로 rounding 하기 위한 bias이다.
식이 다소 복잡하지만 정리하면 결국%ecx = (arg3 - arg2) / 2 + arg2라는 의미이다.이제 남은 부분은 생각보다 간단하다.
0000000000400fce <func4>: /* ... */ 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 call 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 call 400fce <func4> 401003: | 8d 44 00 01 lea 0x1(%rax,%rax,1),%eax 401007: \----> 48 83 c4 08 add $0x8,%rsp 40100b: c3 ret%ecx를int val이라고 정의하고 흐름을 따라가면 된다.
C로 번역해보면 이렇게 된다.int func4(int first, int arg2, int arg3) { int val = arg2 + (arg3 - arg2) / 2; int res; if (val > first) { res = func4(first, arg2, val - 1); res += res; } else { res = 0; if (val < first) { res = func4(first, val + 1, arg3); res += res + 1; } } return res; }이제야 이 함수의 정체가 보이기 시작한다.
혹시 아직 잘 모르겠다면 아래 버전을 참조해보시라int func4(int target, int low, int high) { int mid = low + (high - low) / 2; int res; if (target < mid) { res = func4(target, low, mid - 1); res += res; } else { res = 0; if (target > mid) { res = func4(target, mid + 1, high); res += res + 1; } else { /* target == mid */ return res; } } return res; }func4는 재귀로 구현된 이분 탐색 함수였다.그러면 이제
func4의 반환 값이 0이 되는 target 값을 찾아야 한다.
이분 탐색 시 target 값이 중간 값의 오른쪽에 오는 것만(res += res + 1) 조심하면 된다.가장 간단한 값은 7이다. 한 큐에 탐색이 완료되고 0을 반환한다.
두 번째 정수는 0이여야 했었다.
7 0을 시도해보자> 7 0 So you got that one. Try this one.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 call 40131b <string_length> 40107f: 83 f8 06 cmp $0x6,%eax 401082: /-------- 74 4e je 4010d2 <phase_5+0x70> 401084: | e8 b1 03 00 00 call 40143a <explode_bomb>스택에 공간을 할당하고
%rbx에 input 문자열을 넣고있다.
이후 스택 보호 카나리 값을 세팅하고 문자열 길이를 측정하는 모습이다.
문자열의 길이는 정확히 6 글자가 되어야 한다.6글자 조건을 충족하면
0x4010d2로 점프한다.4010d2: \--|--|-> b8 00 00 00 00 mov $0x0,%eax 4010d7: \--|-- eb b2 jmp 40108b <phase_5+0x29>이후
%eax를 0으로 세팅하고40108b로 점프한다.0000000000401062 <phase_5>: /* ... */ 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>보인다. 루프가
%rax는 일전에 0으로 초기화 했었다. 매 iteration 마다 1씩 늘어나며 6일 때 종료된다.
익숙한 for loop 구조인 듯 하다.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%rbx에는 input 문자열이 들어있었다.
문자열의i번째 글자를 가져와, 뒤 4바이트 (0xf와 and)만 취해%edx에 저장하고 있다.i번째 글자가a(0x61)이라면%edx는0x1이,j(0x6a)면%edx는0xa가 되는 식이다.
이후 모종의 포인터0x4024b0+%rdx(%edx)에 있는 값을 어떤char배열의(0x10(%rsp))i번째 원소로 저장하고 있다.401099: 0f b6 92 b0 24 40 00 movzbl 0x4024b0(%rdx),%edx 4010a0: 88 54 04 10 mov %dl,0x10(%rsp,%rax,1).rodata확인 결과0x4024b0에는 문자열"maduiersnfotvbyl"가 있었다.
입력 문자열 문자"pabcdefghijklmno"는 각각"maduiersnfotvbyl"에 대응된다.다음 부분을 확인한다.
0000000000401062 <phase_5>: 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 call 401338 <strings_not_equal> 4010c2: 85 c0 test %eax,%eax 4010c4: /-- 74 13 je 4010d9 <phase_5+0x77> 4010c6: | e8 6f 03 00 00 call 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 call 400b30 <__stack_chk_fail@plt> 4010ee: \-> 48 83 c4 20 add $0x20,%rsp 4010f2: 5b pop %rbx 4010f3: c3 ret마지막에는 NUL char
\0를 추가해주고 변환된 문자열이0x40245e("flyers") 와 같은지 확인한다.
이후로는 스택 체크 관련 로직이다."pabcdefghijklmno"->"maduiersnfotvbyl"
이렇게 대응되는 하나의 변환 규칙이 존재한다.flyers에 대응되는 글자를 찾아본다.ionefg를 입력한다.> ionefg Good work! On to the next...Phase 6
phase_6 함수의 앞부분을 살펴보자. 정수 6개를 읽고 있다.
00000000004010f4 <phase_6>: 4010f4: 41 56 push %r14 4010f6: 41 55 push %r13 4010f8: 41 54 push %r12 4010fa: 55 push %rbp 4010fb: 53 push %rbx 4010fc: 48 83 ec 50 sub $0x50,%rsp 401100: 49 89 e5 mov %rsp,%r13 401103: 48 89 e6 mov %rsp,%rsi 401106: e8 51 03 00 00 call 40145c <read_six_numbers> 40110b: 49 89 e6 mov %rsp,%r14%r13,%r14에%rsp값이 들어간 것만 집고 넘어가자.다음 부분을 살펴보자.
두 개의 루프가 보인다.00000000004010f4 <phase_6>: /* ... */ 40110e: 41 bc 00 00 00 00 mov $0x0,%r12d 401114: /----------> 4c 89 ed mov %r13,%rbp 401117: | 41 8b 45 00 mov 0x0(%r13),%eax 40111b: | 83 e8 01 sub $0x1,%eax 40111e: | 83 f8 05 cmp $0x5,%eax 401121: | /-- 76 05 jbe 401128 <phase_6+0x34> 401123: | | e8 12 03 00 00 call 40143a <explode_bomb> 401128: | \-> 41 83 c4 01 add $0x1,%r12d 40112c: | 41 83 fc 06 cmp $0x6,%r12d 401130: | /-------- 74 21 je 401153 <phase_6+0x5f> 401132: | | 44 89 e3 mov %r12d,%ebx 401135: | | /----> 48 63 c3 movslq %ebx,%rax 401138: | | | 8b 04 84 mov (%rsp,%rax,4),%eax 40113b: | | | 39 45 00 cmp %eax,0x0(%rbp) 40113e: | | | /-- 75 05 jne 401145 <phase_6+0x51> 401140: | | | | e8 f5 02 00 00 call 40143a <explode_bomb> 401145: | | | \-> 83 c3 01 add $0x1,%ebx 401148: | | | 83 fb 05 cmp $0x5,%ebx 40114b: | | \----- 7e e8 jle 401135 <phase_6+0x41> 40114d: | | 49 83 c5 04 add $0x4,%r13 401151: \--|-------- eb c1 jmp 401114 <phase_6+0x20>먼저 바깥 루프는
%r12d가 6일 때 종료된다.
정수 배열을 순회하기 위한 카운터로 보인다.안쪽 루프
0x401135~는%ebx가 5일 때 종료된다.%ebx는 루프 시작 이전에%r12d로 초기화되어 1씩 늘어나는 카운터다.
(더해진 다음에 초기화 됨에 주의)바깥 루프 내용을 보자.
%r13포인터가 가르키는 값에 1을 빼고, 5보다 크다면 폭발한다.
6과 직접 비교하지 않는 이유는 0을 제외하기 위함이다.jle대신jbe를 썼기 때문에 unsigned 비교가 수행된다.이후
0x40114d:에서 매 iteration 마다%r13이 4씩 늘어난다.%r13은 현재 순회 중인 원소의 포인터인 듯 하다.종합하면, 입력한 6개 숫자 값이 1~6의 범위 안에 있는 지를 확인하고 있다.
안쪽 루프의 내용을 보면
%ebx값이 j라고 할 때,%eax = arr[j]와 바깥 루프의 현재 값0x0(%rbp) == 0x0(%r13)을 비교한다.C언어로 나타내면 다음과 같다.
void phase_6(char *input) { int arr[6]; read_six_numbers(input, arr); int *p = arr; for (int i = 0; i != 6; p++) { if (5 < (unsigned) *p - 1) { explode_bomb(); } i++; for (int j = i; j != 5; j++) { if (arr[j] == *p) { explode_bomb(); } } } }의역본
void phase_6(char *input) { int arr[6]; read_six_numbers(input, arr); for (int i = 0; i < 6; i++) { if (arr[i] > 6 || arr[i] <= 0) { explode_bomb(); } for (int j = i + 1; j < 6; j++) { if (arr[j] == arr[i]) { explode_bomb(); } } } }안 쪽 루프는 중복되는 원소가 있는지 체크하고있다.
즉 중복 없이 1~6 중 6개 정수를 나열해야한다. 정답은 1 2 3 4 5 6 의 순열인가 보다.다음도 루프 구조이다.
00000000004010f4 <phase_6>: /* ... */ 401153: \-------> 48 8d 74 24 18 lea 0x18(%rsp),%rsi 401158: 4c 89 f0 mov %r14,%rax 40115b: b9 07 00 00 00 mov $0x7,%ecx 401160: /-> 89 ca mov %ecx,%edx 401162: | 2b 10 sub (%rax),%edx 401164: | 89 10 mov %edx,(%rax) 401166: | 48 83 c0 04 add $0x4,%rax 40116a: | 48 39 f0 cmp %rsi,%rax 40116d: \-- 75 f1 jne 401160 <phase_6+0x6c>배열을 순회하며 각 원소를 (7 - 값)으로 바꿔주고 있다.
for (int i = 0; i < 6; i++) { arr[i] = 7 - arr[i]; }이후에도 중첩된 루프가 보인다.
00000000004010f4 <phase_6>: /* ... */ 40116f: be 00 00 00 00 mov $0x0,%esi 401174: /-------- eb 21 jmp 401197 <phase_6+0xa3> 401176: /--|-------> 48 8b 52 08 mov 0x8(%rdx),%rdx 40117a: | | 83 c0 01 add $0x1,%eax 40117d: | | 39 c8 cmp %ecx,%eax 40117f: +--|-------- 75 f5 jne 401176 <phase_6+0x82> 401181: | | /-- eb 05 jmp 401188 <phase_6+0x94> 401183: | | /--|-> ba d0 32 60 00 mov $0x6032d0,%edx 401188: | | | \-> 48 89 54 74 20 mov %rdx,0x20(%rsp,%rsi,2) 40118d: | | | 48 83 c6 04 add $0x4,%rsi 401191: | | | 48 83 fe 18 cmp $0x18,%rsi 401195: | | | /-- 74 14 je 4011ab <phase_6+0xb7> 401197: | \--|--|-> 8b 0c 34 mov (%rsp,%rsi,1),%ecx 40119a: | | | 83 f9 01 cmp $0x1,%ecx 40119d: | \--|-- 7e e4 jle 401183 <phase_6+0x8f> 40119f: | | b8 01 00 00 00 mov $0x1,%eax 4011a4: | | ba d0 32 60 00 mov $0x6032d0,%edx 4011a9: \--------|-- eb cb jmp 401176 <phase_6+0x82>가장 큰 루프
0x401176~0x4011a9은%rsi가 24일 때 종료된다.
0부터 시작해 매 iteration 마다 4씩 늘어나며 배열을 순회하는 모양이다.안쪽 구조는 복잡하다.
0x40119d:의 조건에 따라 크게 분기가 나뉘는 구조이다.
다음과 같이 정리해준다./* INNER LOOP */ 401176: /----------> 48 8b 52 08 mov 0x8(%rdx),%rdx 40117a: | 83 c0 01 add $0x1,%eax 40117d: | 39 c8 cmp %ecx,%eax 40117f: +----------- 75 f5 jne 401176 <phase_6+0x82> /* AFTER INNER LOOP */ 401181: eb 05 jmp 401188 <phase_6+0x94> /* JUMP TO MAIN LOOP BODY */ /* jle */ 401183: ba d0 32 60 00 mov $0x6032d0,%edx /* MAIN LOOP BODY */ 401188: 48 89 54 74 20 mov %rdx,0x20(%rsp,%rsi,2) 40118d: 48 83 c6 04 add $0x4,%rsi 401191: 48 83 fe 18 cmp $0x18,%rsi 401195: 74 14 je 4011ab <phase_6+0xb7> /* EXIT */ /* LOOP START */ 401197: 8b 0c 34 mov (%rsp,%rsi,1),%ecx 40119a: 83 f9 01 cmp $0x1,%ecx 40119d: 7e e4 jle 401183 <phase_6+0x8f> /* NO jle */ 40119f: b8 01 00 00 00 mov $0x1,%eax 4011a4: ba d0 32 60 00 mov $0x6032d0,%edx 4011a9: eb cb jmp 401176 <phase_6+0x82> /* JUMP TO INNER LOOP */C로 구조를 시각화하면 이런 느낌이겠다.
for (int i = 0; i < 6; i++) { /* LOOP START */ if (arr[i] > 1) { /* NO jle */ /* INNER LOOP */ } else { /* jle */ } /* MAIN LOOP BODY */ }LOOP START부분을 보자./* LOOP START */ 401197: 8b 0c 34 mov (%rsp,%rsi,1),%ecx 40119a: 83 f9 01 cmp $0x1,%ecx 40119d: 7e e4 jle 401183 <phase_6+0x8f>이 부분은 별게 없다.
%rsi는 4씩 늘어나는 카운터니(%rsp, %rsi, 1)은arr[i]이 된다.
이를 1과 비교하고 있다.arr[i]가 1보다 큰 케이스를 먼저 보자./* NO jle */ 40119f: b8 01 00 00 00 mov $0x1,%eax 4011a4: ba d0 32 60 00 mov $0x6032d0,%edx 4011a9: eb cb jmp 401176 <phase_6+0x82> /* JUMP TO INNER LOOP */ /* INNER LOOP */ 401176: /----------> 48 8b 52 08 mov 0x8(%rdx),%rdx 40117a: | 83 c0 01 add $0x1,%eax 40117d: | 39 c8 cmp %ecx,%eax 40117f: +----------- 75 f5 jne 401176 <phase_6+0x82> /* AFTER INNER LOOP */ 401181: eb 05 jmp 401188 <phase_6+0x94> /* JUMP TO MAIN LOOP BODY */안쪽 루프에서
%eax는 1부터 시작해 1씩 증가한다.%eax가arr[i]일 경우 종료된다.%rdx에는 모종의 주소0x6032d0가 들어간다.arr[i]와 1이 차이가 나는 만큼mov 0x8(%rdx), %rdx이 실행된다.%rdx를 포인터unsigned long *p라 할 때 C로는 아래와 같은 모습이겠다.unsigned long *p; for (int i = 0; i < 6; i++) { if (arr[i] > 1) { p = INIT_ADDR; /* 0x6032d0 */ for (int j = 1; j != arr[i]; j++) { p = *(++p); } } else { /* jle */ } /* MAIN LOOP BODY */ }아직 잘 감이 오지 않는다.
arr[i]가 1보다 작거나 같은 케이스를 보자. (입력 조건 상 1일 경우밖에 없지만)/* jle */ 401183: ba d0 32 60 00 mov $0x6032d0,%edx /* MAIN LOOP BODY */ 401188: 48 89 54 74 20 mov %rdx,0x20(%rsp,%rsi,2) 40118d: 48 83 c6 04 add $0x4,%rsi 401191: 48 83 fe 18 cmp $0x18,%rsi 401195: 74 14 je 4011ab <phase_6+0xb7> /* EXIT */%rdx를INIT_ADDR(0x6032d0) 로 두고 딱히 조작을 하지 않는다.그리고 그 값을
0x20(%rsp,%rsi,2)에 넣고 있다.
int보다 사이즈가 큰, 아마 포인터가 들어가는 배열인 듯 하다.종합/정리하면 다음과 같다.
unsigned long *p; unsigned long *p_arr[6]; for (int i = 0; i < 6; i++) { p = INIT_ADDR; /* 0x6032d0 */ for (int j = 1; j != arr[i]; j++) { p = *(++p); } p_arr[i] = p; }아직도 잘 모르겠다.
0x6032d0를 확인해보자..data섹션에서 확인가능하다.6032d0 4c010000 01000000 e0326000 00000000 L........2`..... 6032e0 a8000000 02000000 f0326000 00000000 .........2`..... 6032f0 9c030000 03000000 00336000 00000000 .........3`..... 603300 b3020000 04000000 10336000 00000000 .........3`..... 603310 dd010000 05000000 20336000 00000000 ........ 3`..... 603320 bb010000 06000000 00000000 00000000 ................ 603330 00000000 00000000 00000000 00000000 ................1~6 까지
arr값에 따른p_arr값을 정리해보자1(from input 6): 0x6032d0 (points to integer 332) 2(from input 5): 0x6032e0 (points to integer 138) 3(from input 4): 0x6032f0 (points to integer 924) 4(from input 3): 0x603300 (points to integer 691) 5(from input 2): 0x603310 (points to integer 447) 6(from input 1): 0x603320 (points to integer 443)뭔가 포인터가 꼬리에 꼬리를 무는 게 연결 리스트가 의심된다.
이런 식으로 구조체가 들어있는 게 아닐까?| mem |int val | int id |struct node *next| 6032d0 4c010000 01000000 e0326000 00000000 L........2`..... 6032e0 a8000000 02000000 f0326000 00000000 .........2`..... 6032f0 9c030000 03000000 00336000 00000000 .........3`..... 603300 b3020000 04000000 10336000 00000000 .........3`..... 603310 dd010000 05000000 20336000 00000000 ........ 3`..... 603320 bb010000 06000000 00000000 00000000 ................ 603330 00000000 00000000 00000000 00000000 ................이러면 코드의 의미가 명확해진다.
struct node { int val; int id; struct node *next; }; struct node *curr; struct node *nodes[6]; for (int i = 0; i < 6; i++) { curr = head; for (int j = 1; j != arr[i]; j++) { curr = curr->next; } nodes[i] = curr; }이제 다음 파트를 본다.
00000000004010f4 <phase_6>: /* ... */ 4011ab: 48 8b 5c 24 20 mov 0x20(%rsp),%rbx 4011b0: 48 8d 44 24 28 lea 0x28(%rsp),%rax 4011b5: 48 8d 74 24 50 lea 0x50(%rsp),%rsi 4011ba: 48 89 d9 mov %rbx,%rcx 4011bd: /----> 48 8b 10 mov (%rax),%rdx 4011c0: | 48 89 51 08 mov %rdx,0x8(%rcx) 4011c4: | 48 83 c0 08 add $0x8,%rax 4011c8: | 48 39 f0 cmp %rsi,%rax 4011cb: | /-- 74 05 je 4011d2 <phase_6+0xde> 4011cd: | | 48 89 d1 mov %rdx,%rcx 4011d0: \--|-- eb eb jmp 4011bd <phase_6+0xc9> 4011d2: \-> 48 c7 42 08 00 00 00 movq $0x0,0x8(%rdx) 4011d9: 000x28(%rsp)(&nodes[1]) 부터 시작해0x50(%rsp)(배열 끝) 까지 순회하는 루프이다.
눈치로 보아하니%rax가 현재 원소라면%rcx는 이전 원소를 가리키는 듯 하다.C로 번역하면 다음과 같다.
struct node *prev = nodes[0]; struct node *curr = nodes[1]; for (int i = 1; i < 6; i++) { prev->next = curr; curr = nodes[i]; prev = curr; }입력 순서대로 linked list를 재연결하는 모양이다.
마지막 파트를 보자
00000000004010f4 <phase_6>: /* ... */ 4011da: bd 05 00 00 00 mov $0x5,%ebp 4011df: /----> 48 8b 43 08 mov 0x8(%rbx),%rax 4011e3: | 8b 00 mov (%rax),%eax 4011e5: | 39 03 cmp %eax,(%rbx) 4011e7: | /-- 7d 05 jge 4011ee <phase_6+0xfa> 4011e9: | | e8 4c 02 00 00 call 40143a <explode_bomb> 4011ee: | \-> 48 8b 5b 08 mov 0x8(%rbx),%rbx 4011f2: | 83 ed 01 sub $0x1,%ebp 4011f5: \----- 75 e8 jne 4011df <phase_6+0xeb> 4011f7: 48 83 c4 50 add $0x50,%rsp 4011fb: 5b pop %rbx 4011fc: 5d pop %rbp 4011fd: 41 5c pop %r12 4011ff: 41 5d pop %r13 401201: 41 5e pop %r14 401203: c3 ret%ebp를 카운터로 총 다섯번 실행되는 루프이다.%rbx에는&nodes[0]가 들어있었음을 기억하자.struct node *curr = nodes[0]; struct node *next; for (int i = 0; i < 5; i++) { next = curr->next; if (curr.val > next.val) { explode_bomb(); } curr = curr->next; }정답이 되기 위해선 연결 리스트의 value가 내림차순으로 이루어져야 한다.
다시 id 별 value값을 살펴보자.
1(from input 6): 0x6032d0 (points to integer 332) 2(from input 5): 0x6032e0 (points to integer 138) 3(from input 4): 0x6032f0 (points to integer 924) 4(from input 3): 0x603300 (points to integer 691) 5(from input 2): 0x603310 (points to integer 447) 6(from input 1): 0x603320 (points to integer 443)value가 내림차순이 되려면 id의 순서는 다음과 같아야 한다.
3 - 4 - 5 - 6 - 1 - 2input(7로 뒤집은 값)의 순서는 아래와 같아야 한다.
4 - 3 - 2 - 1 - 6 - 5정답을 입력해본다.
> 4 3 2 1 6 5 Congratulations! You've defused the bomb!Secret phase
이제 숨겨진 페이즈만 남았다.
숨겨진 페이즈 진입 방법
디스어셈블 된 파일에서
secret_phase가 언제 호출 되는지를 찾아본다. 일반적인 문자열 검색으로 찾아볼 수 있다.phase_defused함수에 숨어 있었다.00000000004015c4 <phase_defused>: 4015c4: 48 83 ec 78 sub $0x78,%rsp 4015c8: 64 48 8b 04 25 28 00 mov %fs:0x28,%rax 4015cf: 00 00 4015d1: 48 89 44 24 68 mov %rax,0x68(%rsp) 4015d6: 31 c0 xor %eax,%eax 4015d8: 83 3d 81 21 20 00 06 cmpl $0x6,0x202181(%rip) # 603760 <num_input_strings> 4015df: /----- 75 5e jne 40163f <phase_defused+0x7b> 4015e1: | 4c 8d 44 24 10 lea 0x10(%rsp),%r8 4015e6: | 48 8d 4c 24 0c lea 0xc(%rsp),%rcx 4015eb: | 48 8d 54 24 08 lea 0x8(%rsp),%rdx 4015f0: | be 19 26 40 00 mov $0x402619,%esi 4015f5: | bf 70 38 60 00 mov $0x603870,%edi 4015fa: | e8 f1 f5 ff ff call 400bf0 <__isoc99_sscanf@plt> 4015ff: | 83 f8 03 cmp $0x3,%eax 401602: | /-- 75 31 jne 401635 <phase_defused+0x71> 401604: | | be 22 26 40 00 mov $0x402622,%esi 401609: | | 48 8d 7c 24 10 lea 0x10(%rsp),%rdi 40160e: | | e8 25 fd ff ff call 401338 <strings_not_equal> 401613: | | 85 c0 test %eax,%eax 401615: | +-- 75 1e jne 401635 <phase_defused+0x71> 401617: | | bf f8 24 40 00 mov $0x4024f8,%edi 40161c: | | e8 ef f4 ff ff call 400b10 <puts@plt> 401621: | | bf 20 25 40 00 mov $0x402520,%edi 401626: | | e8 e5 f4 ff ff call 400b10 <puts@plt> 40162b: | | b8 00 00 00 00 mov $0x0,%eax 401630: | | e8 0d fc ff ff call 401242 <secret_phase> 401635: | \-> bf 58 25 40 00 mov $0x402558,%edi 40163a: | e8 d1 f4 ff ff call 400b10 <puts@plt> 40163f: \----> 48 8b 44 24 68 mov 0x68(%rsp),%rax6개 페이즈를 전부 완료 했다면 (
num_input_strings == 6)0x603870에서 정수 두 개와 문자열 (0x402619("%d %d %s")) 을 읽어낸다.
형식만 맞으면 정수 값은 상관 없는 듯 하다. 문자열은0x402622("DrEvil")과 일치해야 한다.0x603870은 입력 문자열 중간 어떤 부분을 가르키는게 분명한데, 정확히 판단하기 어렵다.한번 프로그램에서 유저 입력을 받는 부분을 찾아보자.
read_line함수 내부skip함수에서fgets를 찾을 수 있었다.00000000004013f9 <skip>: 4013f9: 53 push %rbx 4013fa: /----> 48 63 05 5f 23 20 00 movslq 0x20235f(%rip),%rax # 603760 <num_input_strings> 401401: | 48 8d 3c 80 lea (%rax,%rax,4),%rdi 401405: | 48 c1 e7 04 shl $0x4,%rdi 401409: | 48 81 c7 80 37 60 00 add $0x603780,%rdi 401410: | 48 8b 15 51 23 20 00 mov 0x202351(%rip),%rdx # 603768 <infile> 401417: | be 50 00 00 00 mov $0x50,%esi 40141c: | e8 5f f7 ff ff call 400b80 <fgets@plt> 401421: | 48 89 c3 mov %rax,%rbx 401424: | 48 85 c0 test %rax,%rax 401427: | /-- 74 0c je 401435 <skip+0x3c> 401429: | | 48 89 c7 mov %rax,%rdi 40142c: | | e8 8b ff ff ff call 4013bc <blank_line> 401431: | | 85 c0 test %eax,%eax 401433: \--|-- 75 c5 jne 4013fa <skip+0x1> 401435: \-> 48 89 d8 mov %rbx,%rax 401438: 5b pop %rbx 401439: c3 retfgets함수의 첫 번째 인자,%rdi가 유저의 문자열 인풋을 받는 버퍼 포인터가 된다.코드를 보면
%rdi는0x603780 + num_input_strings * 5 * 2^4가 된다.즉, 1페이즈 입력은
0x603780, 2페이즈 입력은0x6037d0,
3페이즈는0x603830, 4페이즈는0x603880이렇게 저장된다.숨겨진 페이즈를 찾기 위한 주소는
0x603870이다.0x603870~0x60387f는\0이다.
결국 4페이즈 입력을 읽는 것과 다름 없다.4페이즈 정답 끝에
DrEvil을 넣어보자.> Border relations with Canada have never been better. > 1 2 4 8 16 32 > 0 207 > 7 0 DrEvil > ionefg > 4 3 2 1 6 5 Curses, you've found the secret phase! But finding it and solving it are quite different...Secret_phase 해체
함수 진입 방법을 알았으니 이제 함수를 살펴보자.
0000000000401242 <secret_phase>: 401242: 53 push %rbx 401243: e8 56 02 00 00 call 40149e <read_line> 401248: ba 0a 00 00 00 mov $0xa,%edx 40124d: be 00 00 00 00 mov $0x0,%esi 401252: 48 89 c7 mov %rax,%rdi 401255: e8 76 f9 ff ff call 400bd0 <strtol@plt> 40125a: 48 89 c3 mov %rax,%rbx 40125d: 8d 40 ff lea -0x1(%rax),%eax 401260: 3d e8 03 00 00 cmp $0x3e8,%eax 401265: /-- 76 05 jbe 40126c <secret_phase+0x2a> 401267: | e8 ce 01 00 00 call 40143a <explode_bomb> 40126c: \-> 89 de mov %ebx,%esi 40126e: bf f0 30 60 00 mov $0x6030f0,%edi 401273: e8 8c ff ff ff call 401204 <fun7> 401278: 83 f8 02 cmp $0x2,%eax 40127b: /-- 74 05 je 401282 <secret_phase+0x40> 40127d: | e8 b8 01 00 00 call 40143a <explode_bomb> 401282: \-> bf 38 24 40 00 mov $0x402438,%edi 401287: e8 84 f8 ff ff call 400b10 <puts@plt> 40128c: e8 33 03 00 00 call 4015c4 <phase_defused> 401291: 5b pop %rbx 401292: c3 ret전반부, 먼저 input을 읽고 다음에
strtol함수를 호출하고 있다.0000000000401242 <secret_phase>: 401242: 53 push %rbx 401243: e8 56 02 00 00 call 40149e <read_line> 401248: ba 0a 00 00 00 mov $0xa,%edx 40124d: be 00 00 00 00 mov $0x0,%esi 401252: 48 89 c7 mov %rax,%rdi 401255: e8 76 f9 ff ff call 400bd0 <strtol@plt> 40125a: 48 89 c3 mov %rax,%rbxlong int num = strtol(input, NULL, 10);숫자는
0x3e8 + 1(1001) 보다 작으면 안되는 듯 하다.0000000000401242 <secret_phase>: /* .. */ 40125d: 8d 40 ff lea -0x1(%rax),%eax 401260: 3d e8 03 00 00 cmp $0x3e8,%eax 401265: /-- 76 05 jbe 40126c <secret_phase+0x2a> 401267: | e8 ce 01 00 00 call 40143a <explode_bomb>이후
fun7함수의 첫째 인자로0x6030f0를, 둘째 인자로 입력한 숫자를 전달하였다.0000000000401242 <secret_phase>: /* .. */ 40126e: bf f0 30 60 00 mov $0x6030f0,%edi 401273: e8 8c ff ff ff call 401204 <fun7> 401278: 83 f8 02 cmp $0x2,%eax 40127b: /-- 74 05 je 401282 <secret_phase+0x40> 40127d: | e8 b8 01 00 00 call 40143a <explode_bomb> 401282: \-> bf 38 24 40 00 mov $0x402438,%edi 401287: e8 84 f8 ff ff call 400b10 <puts@plt> 40128c: e8 33 03 00 00 call 4015c4 <phase_defused> 401291: 5b pop %rbx함수의 결과 값은 2가 되어야 한다.
.data에서0x6030f0를 살펴본다.6030f0 24000000 00000000 10316000 00000000 $........1`..... 603100 30316000 00000000 00000000 00000000 01`............. 603110 08000000 00000000 90316000 00000000 .........1`..... 603120 50316000 00000000 00000000 00000000 P1`............. 603130 32000000 00000000 70316000 00000000 2.......p1`..... 603140 b0316000 00000000 00000000 00000000 .1`............. 603150 16000000 00000000 70326000 00000000 ........p2`..... 603160 30326000 00000000 00000000 00000000 02`............. 603170 2d000000 00000000 d0316000 00000000 -........1`..... 603180 90326000 00000000 00000000 00000000 .2`............. 603190 06000000 00000000 f0316000 00000000 .........1`..... 6031a0 50326000 00000000 00000000 00000000 P2`............. 6031b0 6b000000 00000000 10326000 00000000 k........2`..... 6031c0 b0326000 00000000 00000000 00000000 .2`.............관상을 보아하니 값 - 포인터 - 포인터 구조가 눈에 띈다. 이진 트리를 암시하는 지도 모르겠다.
fun7함수를 보자0000000000401204 <fun7>: 401204: /-------> 48 83 ec 08 sub $0x8,%rsp 401208: | 48 85 ff test %rdi,%rdi 40120b: /--|-------- 74 2b je 401238 <fun7+0x34> 40120d: | | 8b 17 mov (%rdi),%edx 40120f: | | 39 f2 cmp %esi,%edx 401211: | | /-- 7e 0d jle 401220 <fun7+0x1c> 401213: | | | 48 8b 7f 08 mov 0x8(%rdi),%rdi 401217: | +-----|-- e8 e8 ff ff ff call 401204 <fun7> 40121c: | | | 01 c0 add %eax,%eax 40121e: | | /--|-- eb 1d jmp 40123d <fun7+0x39> 401220: | | | \-> b8 00 00 00 00 mov $0x0,%eax 401225: | | | 39 f2 cmp %esi,%edx 401227: | | +----- 74 14 je 40123d <fun7+0x39> 401229: | | | 48 8b 7f 10 mov 0x10(%rdi),%rdi 40122d: | \--|----- e8 d2 ff ff ff call 401204 <fun7> 401232: | | 8d 44 00 01 lea 0x1(%rax,%rax,1),%eax 401236: | +----- eb 05 jmp 40123d <fun7+0x39> 401238: \-----|----> b8 ff ff ff ff mov $0xffffffff,%eax 40123d: \----> 48 83 c4 08 add $0x8,%rsp 401241: c3 ret먼저 첫 번째 인자
%rdi가 0, 즉NULL포인터면 -1을 리턴하는 게 눈에 띈다.0000000000401204 <fun7>: /* .. */ 40120d: 8b 17 mov (%rdi),%edx 40120f: 39 f2 cmp %esi,%edx 401211: 7e 0d jle 401220 <fun7+0x1c>이후 포인터의 정수값과 input number를 비교한다.
0000000000401204 <fun7>: /* .. */ /* NO jle */ 401213: 48 8b 7f 08 mov 0x8(%rdi),%rdi 401217: e8 e8 ff ff ff call 401204 <fun7> 40121c: 01 c0 add %eax,%eax 40121e: eb 1d jmp 40123d <fun7+0x39> /* DONE */ /* jle */ 401220: b8 00 00 00 00 mov $0x0,%eax 401225: 39 f2 cmp %esi,%edx 401227: 74 14 je 40123d <fun7+0x39> /* IF EQAUL - DONE */ 401229: 48 8b 7f 10 mov 0x10(%rdi),%rdi 40122d: e8 d2 ff ff ff call 401204 <fun7> 401232: 8d 44 00 01 lea 0x1(%rax,%rax,1),%eax 401236: eb 05 jmp 40123d <fun7+0x39> /* DONE */생긴 걸 딱 보니 이진 탐색 트리 이다.
6030f0 24000000 00000000 10316000 00000000 $........1`..... 603100 30316000 00000000 00000000 00000000 01`............. 603110 08000000 00000000 90316000 00000000 .........1`..... 603120 50316000 00000000 00000000 00000000 P1`............. 603130 32000000 00000000 70316000 00000000 2.......p1`..... 603140 b0316000 00000000 00000000 00000000 .1`............. 603150 16000000 00000000 70326000 00000000 ........p2`..... 603160 30326000 00000000 00000000 00000000 02`............. 603170 2d000000 00000000 d0316000 00000000 -........1`..... 603180 90326000 00000000 00000000 00000000 .2`............. 603190 06000000 00000000 f0316000 00000000 .........1`..... 6031a0 50326000 00000000 00000000 00000000 P2`............. 6031b0 6b000000 00000000 10326000 00000000 k........2`..... 6031c0 b0326000 00000000 00000000 00000000 .2`.............출력값을 보며 떠듬더듬 트리를 일부만 그려 보자 (depth 2 까지만)
root(0x24) ---- 0x32----0x6b | |-------0x2d | |------------- 0x08----0x16 |-------0x06왼쪽 탐색 시
fun7값이 두 배, 오른쪽 탐색 시fun7값이 두 배 + 1이 된다.최종
fun7값이 2가 되려면 간단하게 왼쪽-오른쪽 에 있는 값0x16을 입력 해주면 되겠다. (((0)*2 + 1)*2)
22를 입력한다.> 22 Wow! You've defused the secret stage! Congratulations! You've defused the bomb!끝.
- 첫 번째 인자(