CMU 15-213 Bomb Lab
Bomb Lab
This is the second lab of course CMU 15-213. I have to say that, unlike datalab, this lab is fairly ‘logical’ and fun to play with. The idea of looking into assembly code to get a fundamental understanding of how programs actually got compiled into machine level language is absolutely effective and genius in teaching.
Make sure you’ve solved the puzzles by yourself before checking my solutions!
If you find any mistakes in this blog, you’re most welcome to leave a comment on it.
Records
- Disassemble the executable file into assembly code by:
1
objdump -D bomb > bomb.s
Phase 1
Obviously we gotta look into the assembly code of
phase_1:1
2
3
4
5
6
7
8
90000000000400ee0 <phase_1>:
400ee0:448 83 ec 08 sub $0x8,%rsp
400ee4:4be 00 24 40 00 mov $0x402400,%esi
400ee9:4e8 4a 04 00 00 call 401338 <strings_not_equal>
400eee:485 c0 test %eax,%eax
400ef0:474 05 je 400ef7 <phase_1+0x17>
400ef2:4e8 43 05 00 00 call 40143a <explode_bomb>
400ef7:448 83 c4 08 add $0x8,%rsp
400efb:4c3 retEven more obvious we should take a look into function
<strings_not_equal>:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
390000000000401338 <strings_not_equal>:
401338:441 54 push %r12
40133a:455 push %rbp
40133b:453 push %rbx
40133c:448 89 fb mov %rdi,%rbx
40133f:448 89 f5 mov %rsi,%rbp
401342:4e8 d4 ff ff ff call 40131b <string_length>
401347:441 89 c4 mov %eax,%r12d
40134a:448 89 ef mov %rbp,%rdi
40134d:4e8 c9 ff ff ff call 40131b <string_length>
401352:4ba 01 00 00 00 mov $0x1,%edx
401357:441 39 c4 cmp %eax,%r12d
40135a:475 3f jne 40139b <strings_not_equal+0x63>
40135c:40f b6 03 movzbl (%rbx),%eax
40135f:484 c0 test %al,%al
401361:474 25 je 401388 <strings_not_equal+0x50>
401363:43a 45 00 cmp 0x0(%rbp),%al
401366:474 0a je 401372 <strings_not_equal+0x3a>
401368:4eb 25 jmp 40138f <strings_not_equal+0x57>
40136a:43a 45 00 cmp 0x0(%rbp),%al
40136d:40f 1f 00 nopl (%rax)
401370:475 24 jne 401396 <strings_not_equal+0x5e>
401372:448 83 c3 01 add $0x1,%rbx
401376:448 83 c5 01 add $0x1,%rbp
40137a:40f b6 03 movzbl (%rbx),%eax
40137d:484 c0 test %al,%al
40137f:475 e9 jne 40136a <strings_not_equal+0x32>
401381:4ba 00 00 00 00 mov $0x0,%edx
401386:4eb 13 jmp 40139b <strings_not_equal+0x63>
401388:4ba 00 00 00 00 mov $0x0,%edx
40138d:4eb 0c jmp 40139b <strings_not_equal+0x63>
40138f:4ba 01 00 00 00 mov $0x1,%edx
401394:4eb 05 jmp 40139b <strings_not_equal+0x63>
401396:4ba 01 00 00 00 mov $0x1,%edx
40139b:489 d0 mov %edx,%eax
40139d:45b pop %rbx
40139e:45d pop %rbp
40139f:441 5c pop %r12
4013a1:4c3 retFrom the code we can see that the funcion first compares the length of the two strings and then compares each character.
If we type in
helloas a ‘test’ input for this phase, we can find out that it is the first call forstring_lengththat calculates the length of our input string, for%eaxis set to5(as the length ofhello) after it returns. (With the help of gdb)Then this
5is moved into%r12at:1
401347:441 89 c4 mov %eax,%r12d
Then compared with the second length calculated at:
1
2401357:441 39 c4 cmp %eax,%r12d
40135a:475 3f jne 40139b <strings_not_equal+0x63>
So the idea is simple: just step into the second
string_lengthand see what is at the memory address stored in the register corresponding to the first argument of a function call, which is%rdi:Step into the second <string_length>
1
2
3
4(gdb) print /x $rdi
$1 = 0x402400
(gdb) print (char *) 0x402400
$2 = 0x402400 "Border relations with Canada have never been better."And we’re done for phase 1.
Phase 2
As usual, assembly:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
260000000000400efc <phase_2>:
400efc:455 push %rbp
400efd:453 push %rbx
400efe:448 83 ec 28 sub $0x28,%rsp
400f02:448 89 e6 mov %rsp,%rsi
400f05:4e8 52 05 00 00 call 40145c <read_six_numbers>
400f0a:483 3c 24 01 cmpl $0x1,(%rsp)
400f0e:474 20 je 400f30 <phase_2+0x34>
400f10:4e8 25 05 00 00 call 40143a <explode_bomb>
400f15:4eb 19 jmp 400f30 <phase_2+0x34>
400f17:48b 43 fc mov -0x4(%rbx),%eax
400f1a:401 c0 add %eax,%eax
400f1c:439 03 cmp %eax,(%rbx)
400f1e:474 05 je 400f25 <phase_2+0x29>
400f20:4e8 15 05 00 00 call 40143a <explode_bomb>
400f25:448 83 c3 04 add $0x4,%rbx
400f29:448 39 eb cmp %rbp,%rbx
400f2c:475 e9 jne 400f17 <phase_2+0x1b>
400f2e:4eb 0c jmp 400f3c <phase_2+0x40>
400f30:448 8d 5c 24 04 lea 0x4(%rsp),%rbx
400f35:448 8d 6c 24 18 lea 0x18(%rsp),%rbp
400f3a:4eb db jmp 400f17 <phase_2+0x1b>
400f3c:448 83 c4 28 add $0x28,%rsp
400f40:45b pop %rbx
400f41:45d pop %rbp
400f42:4c3 retImmediately we see this
<read_six_numbers>, so1 2 3 4 5 6is an ideal test string we should put in here.Assembly of
read_six_numbers:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18000000000040145c <read_six_numbers>:
40145c:448 83 ec 18 sub $0x18,%rsp
401460:448 89 f2 mov %rsi,%rdx
401463:448 8d 4e 04 lea 0x4(%rsi),%rcx
401467:448 8d 46 14 lea 0x14(%rsi),%rax
40146b:448 89 44 24 08 mov %rax,0x8(%rsp)
401470:448 8d 46 10 lea 0x10(%rsi),%rax
401474:448 89 04 24 mov %rax,(%rsp)
401478:44c 8d 4e 0c lea 0xc(%rsi),%r9
40147c:44c 8d 46 08 lea 0x8(%rsi),%r8
401480:4be c3 25 40 00 mov $0x4025c3,%esi
401485:4b8 00 00 00 00 mov $0x0,%eax
40148a:4e8 61 f7 ff ff call 400bf0 <__isoc99_sscanf@plt>
40148f:483 f8 05 cmp $0x5,%eax
401492:47f 05 jg 401499 <read_six_numbers+0x3d>
401494:4e8 a1 ff ff ff call 40143a <explode_bomb>
401499:448 83 c4 18 add $0x18,%rsp
40149d:4c3 ret- We can see from the assembly code that this function does not explicitly use anything stored in
%rdiwhile manipulating%rsia lot, which is pretty strange at first glance. - It turns out that the value stored inside
%rdiis implicitly passed tosscanfas the address to hold the user input. - We can trace back to
mainto see where%rdiis set afterread_line:1
2
3
4
5
6
7
8
9# ...Phase 1
400e3f:4e8 80 07 00 00 call 4015c4 <phase_defused>
400e44:4bf a8 23 40 00 mov $0x4023a8,%edi
400e49:4e8 c2 fc ff ff call 400b10 <puts@plt>
400e4e:4e8 4b 06 00 00 call 40149e <read_line>
400e53:448 89 c7 mov %rax,%rdi
400e56:4e8 a1 00 00 00 call 400efc <phase_2>
400e5b:4e8 64 07 00 00 call 4015c4 <phase_defused>
# Phase 3... - It is set as the pointer pointing towards the string returned by
read_line.
- We can see from the assembly code that this function does not explicitly use anything stored in
There seems to be a lot going on before invoking
sscanf, but it’s mainly preparing space for user input on the stack.In short:
%rdipassed all along tosscanfas input string.%rsiholds the pointer pointing to the address of the buffer which is to store the six numbers parsed bysscanf.%rdx,%rcx,%r8,%r9holding the first four addresses of each of the target buffer block to hold the parsed numbers, while the rest 2 addresses are placed on the stack.sscanfthen set the values stored in those addresses to the six input numbers.- After
sscanfreturns, compare the return value with0x5. If the return value, which represents the number of the values parsed, is less or equal to 5, then explode the bomb. - Free the stack frame and return.
1 | 401467:448 8d 46 14 lea 0x14(%rsi),%rax |
- This is where the last two addresses of the target buffer are placed on the stack, and passed to
sscanf.
After reading six numbers from user input, first check whether the first number is
0x1:1
2400f0a:483 3c 24 01 cmpl $0x1,(%rsp)
400f0e:474 20 je 400f30 <phase_2+0x34>Then there is a loop determining whether the input numbers are of an expected pattern:
1
2
3
4
5
6
7
8
9
10
11
12400f17:48b 43 fc mov -0x4(%rbx),%eax
400f1a:401 c0 add %eax,%eax
400f1c:439 03 cmp %eax,(%rbx)
400f1e:474 05 je 400f25 <phase_2+0x29>
400f20:4e8 15 05 00 00 call 40143a <explode_bomb>
400f25:448 83 c3 04 add $0x4,%rbx
400f29:448 39 eb cmp %rbp,%rbx
400f2c:475 e9 jne 400f17 <phase_2+0x1b>
400f2e:4eb 0c jmp 400f3c <phase_2+0x40>
400f30:448 8d 5c 24 04 lea 0x4(%rsp),%rbx
400f35:448 8d 6c 24 18 lea 0x18(%rsp),%rbp
400f3a:4eb db jmp 400f17 <phase_2+0x1b>Can be written as pseudocode like:
1
2
3
4
5
6int rax;
for(int rbx = 0x7fffffffd3d4; rbx != 0x7fffffffd3e8; rbx += 4) {
rax = *(rbx - 4);
rax += rax;
if (rax != *rbx) explode_bomb();
}To this stage, the answer can not be more obvious.
Phase 3
Assembly:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
370000000000400f43 <phase_3>:
400f43:448 83 ec 18 sub $0x18,%rsp
400f47:448 8d 4c 24 0c lea 0xc(%rsp),%rcx
400f4c:448 8d 54 24 08 lea 0x8(%rsp),%rdx
400f51:4be cf 25 40 00 mov $0x4025cf,%esi
400f56:4b8 00 00 00 00 mov $0x0,%eax
400f5b:4e8 90 fc ff ff call 400bf0 <__isoc99_sscanf@plt>
400f60:483 f8 01 cmp $0x1,%eax
400f63:47f 05 jg 400f6a <phase_3+0x27>
400f65:4e8 d0 04 00 00 call 40143a <explode_bomb>
400f6a:483 7c 24 08 07 cmpl $0x7,0x8(%rsp)
400f6f:477 3c ja 400fad <phase_3+0x6a>
400f71:48b 44 24 08 mov 0x8(%rsp),%eax
400f75:4ff 24 c5 70 24 40 00 jmp *0x402470(,%rax,8)
400f7c:4b8 cf 00 00 00 mov $0xcf,%eax
400f81:4eb 3b jmp 400fbe <phase_3+0x7b>
400f83:4b8 c3 02 00 00 mov $0x2c3,%eax
400f88:4eb 34 jmp 400fbe <phase_3+0x7b>
400f8a:4b8 00 01 00 00 mov $0x100,%eax
400f8f:4eb 2d jmp 400fbe <phase_3+0x7b>
400f91:4b8 85 01 00 00 mov $0x185,%eax
400f96:4eb 26 jmp 400fbe <phase_3+0x7b>
400f98:4b8 ce 00 00 00 mov $0xce,%eax
400f9d:4eb 1f jmp 400fbe <phase_3+0x7b>
400f9f:4b8 aa 02 00 00 mov $0x2aa,%eax
400fa4:4eb 18 jmp 400fbe <phase_3+0x7b>
400fa6:4b8 47 01 00 00 mov $0x147,%eax
400fab:4eb 11 jmp 400fbe <phase_3+0x7b>
400fad:4e8 88 04 00 00 call 40143a <explode_bomb>
400fb2:4b8 00 00 00 00 mov $0x0,%eax
400fb7:4eb 05 jmp 400fbe <phase_3+0x7b>
400fb9:4b8 37 01 00 00 mov $0x137,%eax
400fbe:43b 44 24 0c cmp 0xc(%rsp),%eax
400fc2:474 05 je 400fc9 <phase_3+0x86>
400fc4:4e8 71 04 00 00 call 40143a <explode_bomb>
400fc9:448 83 c4 18 add $0x18,%rsp
400fcd:4c3 retFrom the judgment towards the return value of
sscanf:1
2
3
4400f5b:4e8 90 fc ff ff call 400bf0 <__isoc99_sscanf@plt>
400f60:483 f8 01 cmp $0x1,%eax
400f63:47f 05 jg 400f6a <phase_3+0x27>
400f65:4e8 d0 04 00 00 call 40143a <explode_bomb>We can see that the number of the expected user input should be more than 1, also:
1
2
3
4400f6a:483 7c 24 08 07 cmpl $0x7,0x8(%rsp)
400f6f:477 3c ja 400fad <phase_3+0x6a>
# ...
400fad:4e8 88 04 00 00 call 40143a <explode_bomb>For function
sscanf,%rdiholds the address of the raw input,%esiholds theformatstring, thusrdxandrcxholds the two addresses where the program put the two parsed numbers to.
- The reason why I know the wanted inputs are numbers is that I’ve tried them in cli.
- So, the first input should be less or equal to
0x7(also non-negative forjareads unsigned values comparison result). As a result1 2should be an ideal test input.
- Like phase 2,
%rdiis passed frommainfunction, pointing to the address of user input string.
Then the ‘bomb’ put the second input into
%eaxand jump to somewhere in a jump table:1
2400f71:48b 44 24 08 mov 0x8(%rsp),%eax
400f75:4ff 24 c5 70 24 40 00 jmp *0x402470(,%rax,8)The syntax here in the second line of code means:
- Jump to address
0x402470 + 0 + (%rax) * 0x8
- Jump to address
So according to our test input, the value at address stored in
%raxshould be0x1, Thus the target address of thisjmpshould be located at0x402470 + 0 + 1 * 0x8 = 0x402478, which is:1
2(gdb) x/wx 0x402478
0x402478: 0x00400fb9Which is:
1
2
3
4
5
6400fb9:4b8 37 01 00 00 mov $0x137,%eax
400fbe:43b 44 24 0c cmp 0xc(%rsp),%eax
400fc2:474 05 je 400fc9 <phase_3+0x86>
400fc4:4e8 71 04 00 00 call 40143a <explode_bomb>
400fc9:448 83 c4 18 add $0x18,%rsp
400fcd:4c3 retWhich means the correct second input corresponding to
0x1as the first input is0x137 = 311.
We can therefore reverse the whole jump table:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18int expected;
switch (first_input) {
case 0: expected = 0xcf; break;
case 1: expected = 0x137; break;
case 2: expected = 0x2c3; break;
case 3: expected = 0x100; break;
case 4: expected = 0x185; break;
case 5: expected = 0xce; break;
case 6: expected = 0x2aa; break;
case 7: expected = 0x147; break;
default:
explode_bomb();
}
if (second_input != expected)
explode_bomb();
Phase 4
Assembly:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23000000000040100c <phase_4>:
40100c:448 83 ec 18 sub $0x18,%rsp
401010:448 8d 4c 24 0c lea 0xc(%rsp),%rcx
401015:448 8d 54 24 08 lea 0x8(%rsp),%rdx
40101a:4be cf 25 40 00 mov $0x4025cf,%esi
40101f:4b8 00 00 00 00 mov $0x0,%eax
401024:4e8 c7 fb ff ff call 400bf0 <__isoc99_sscanf@plt>
401029:483 f8 02 cmp $0x2,%eax
40102c:475 07 jne 401035 <phase_4+0x29>
40102e:483 7c 24 08 0e cmpl $0xe,0x8(%rsp)
401033:476 05 jbe 40103a <phase_4+0x2e>
401035:4e8 00 04 00 00 call 40143a <explode_bomb>
40103a:4ba 0e 00 00 00 mov $0xe,%edx
40103f:4be 00 00 00 00 mov $0x0,%esi
401044:48b 7c 24 08 mov 0x8(%rsp),%edi
401048:4e8 81 ff ff ff call 400fce <func4>
40104d:485 c0 test %eax,%eax
40104f:475 07 jne 401058 <phase_4+0x4c>
401051:483 7c 24 0c 00 cmpl $0x0,0xc(%rsp)
401056:474 05 je 40105d <phase_4+0x51>
401058:4e8 dd 03 00 00 call 40143a <explode_bomb>
40105d:448 83 c4 18 add $0x18,%rsp
401061:4c3 retEasy part:
sscanfuser input, write two numbers at address%rsp + 0x8and%rsp + 0xc.- The first input should be non-negative and less or equal to
0xe. - Set
%rdxto0xe. Set%rsito0x0. Set%rdito the first user input. - call
<func4>.
Let’s take a look into
func4:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
230000000000400fce <func4>:
400fce:448 83 ec 08 sub $0x8,%rsp
400fd2:489 d0 mov %edx,%eax
400fd4:429 f0 sub %esi,%eax
400fd6:489 c1 mov %eax,%ecx
400fd8:4c1 e9 1f shr $0x1f,%ecx
400fdb:401 c8 add %ecx,%eax
400fdd:4d1 f8 sar $1,%eax
400fdf:48d 0c 30 lea (%rax,%rsi,1),%ecx
400fe2:439 f9 cmp %edi,%ecx
400fe4:47e 0c jle 400ff2 <func4+0x24>
400fe6:48d 51 ff lea -0x1(%rcx),%edx
400fe9:4e8 e0 ff ff ff call 400fce <func4>
400fee:401 c0 add %eax,%eax
400ff0:4eb 15 jmp 401007 <func4+0x39>
400ff2:4b8 00 00 00 00 mov $0x0,%eax
400ff7:439 f9 cmp %edi,%ecx
400ff9:47d 0c jge 401007 <func4+0x39>
400ffb:48d 71 01 lea 0x1(%rcx),%esi
400ffe:4e8 cb ff ff ff call 400fce <func4>
401003:48d 44 00 01 lea 0x1(%rax,%rax,1),%eax
401007:448 83 c4 08 add $0x8,%rsp
40100b:4c3 retWe can see that the calculation for
%ecxis actually fixed, which means whatever the input numbers are,%ecxwill be0x7during the two comparisons:1
2
3
4
5
6
7
8
9
10
11# ...
400fe2:439 f9 cmp %edi,%ecx
400fe4:47e 0c jle 400ff2 <func4+0x24>
400fe6:48d 51 ff lea -0x1(%rcx),%edx
400fe9:4e8 e0 ff ff ff call 400fce <func4>
# ...
400ff7:439 f9 cmp %edi,%ecx
400ff9:47d 0c jge 401007 <func4+0x39>
400ffb:48d 71 01 lea 0x1(%rcx),%esi
400ffe:4e8 cb ff ff ff call 400fce <func4>
# ...Also we notice that each time the function returns from a recursion, it doubles the value in
%raxand increments it by 1.As the assembly code we can see after
func4returns:1
2
3
4
5
6# ...
40104d:485 c0 test %eax,%eax
40104f:475 07 jne 401058 <phase_4+0x4c>
# ...
401058:4e8 dd 03 00 00 call 40143a <explode_bomb>
# ...We definitely don’t want
%raxto be non-zero. As a result, we should pass a value tofunc4that bothjleandjgefires, which means%edishould equal to%ecxat the moment of comparison.Note:Turns out
func4is doing something similiar to a binary search, while the return value is not the offset/index of the target value.So as long as the function goes into this branch:
1
2
3
4
5400fe4:47e 0c jle 400ff2 <func4+0x24>
400fe6:48d 51 ff lea -0x1(%rcx),%edx
400fe9:4e8 e0 ff ff ff call 400fce <func4>
400fee:401 c0 add %eax,%eax
400ff0:4eb 15 jmp 401007 <func4+0x39>And get a return value 0 inside the recurrsion, we can keep
%raxas 0.Really weird a binary search function does not return an index, hmm.
Since we’ve already know that
%ecxwill be a fixed0x7on the first call, the value of%ediis now revealed.The second input is an easy zero:
1
2
3
4
5
6# ...
401051:483 7c 24 0c 00 cmpl $0x0,0xc(%rsp)
401056:474 05 je 40105d <phase_4+0x51>
401058:4e8 dd 03 00 00 call 40143a <explode_bomb>
40105d:448 83 c4 18 add $0x18,%rsp
401061:4c3 ret
Phase 5
Assembly:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
410000000000401062 <phase_5>:
401062:453 push %rbx
401063:448 83 ec 20 sub $0x20,%rsp
401067:448 89 fb mov %rdi,%rbx
40106a:464 48 8b 04 25 28 00 mov %fs:0x28,%rax
401071:400 00
401073:448 89 44 24 18 mov %rax,0x18(%rsp)
401078:431 c0 xor %eax,%eax
40107a:4e8 9c 02 00 00 call 40131b <string_length>
40107f:483 f8 06 cmp $0x6,%eax
401082:474 4e je 4010d2 <phase_5+0x70>
401084:4e8 b1 03 00 00 call 40143a <explode_bomb>
401089:4eb 47 jmp 4010d2 <phase_5+0x70>
40108b:40f b6 0c 03 movzbl (%rbx,%rax,1),%ecx
40108f:488 0c 24 mov %cl,(%rsp)
401092:448 8b 14 24 mov (%rsp),%rdx
401096:483 e2 0f and $0xf,%edx
401099:40f b6 92 b0 24 40 00 movzbl 0x4024b0(%rdx),%edx
4010a0:488 54 04 10 mov %dl,0x10(%rsp,%rax,1)
4010a4:448 83 c0 01 add $0x1,%rax
4010a8:448 83 f8 06 cmp $0x6,%rax
4010ac:475 dd jne 40108b <phase_5+0x29>
4010ae:4c6 44 24 16 00 movb $0x0,0x16(%rsp)
4010b3:4be 5e 24 40 00 mov $0x40245e,%esi
4010b8:448 8d 7c 24 10 lea 0x10(%rsp),%rdi
4010bd:4e8 76 02 00 00 call 401338 <strings_not_equal>
4010c2:485 c0 test %eax,%eax
4010c4:474 13 je 4010d9 <phase_5+0x77>
4010c6:4e8 6f 03 00 00 call 40143a <explode_bomb>
4010cb:40f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
4010d0:4eb 07 jmp 4010d9 <phase_5+0x77>
4010d2:4b8 00 00 00 00 mov $0x0,%eax
4010d7:4eb b2 jmp 40108b <phase_5+0x29>
4010d9:448 8b 44 24 18 mov 0x18(%rsp),%rax
4010de:464 48 33 04 25 28 00 xor %fs:0x28,%rax
4010e5:400 00
4010e7:474 05 je 4010ee <phase_5+0x8c>
4010e9:4e8 42 fa ff ff call 400b30 <__stack_chk_fail@plt>
4010ee:448 83 c4 20 add $0x20,%rsp
4010f2:45b pop %rbx
4010f3:4c3 retLength of the input string should be 6:
1
2
3
440107a:4e8 9c 02 00 00 call 40131b <string_length>
40107f:483 f8 06 cmp $0x6,%eax
401082:474 4e je 4010d2 <phase_5+0x70>
401084:4e8 b1 03 00 00 call 40143a <explode_bomb>The core logic of this function is at here:
1
2
3
4
5
6
7
8
940108b:40f b6 0c 03 movzbl (%rbx,%rax,1),%ecx
40108f:488 0c 24 mov %cl,(%rsp)
401092:448 8b 14 24 mov (%rsp),%rdx
401096:483 e2 0f and $0xf,%edx
401099:40f b6 92 b0 24 40 00 movzbl 0x4024b0(%rdx),%edx
4010a0:488 54 04 10 mov %dl,0x10(%rsp,%rax,1)
4010a4:448 83 c0 01 add $0x1,%rax
4010a8:448 83 f8 06 cmp $0x6,%rax
4010ac:475 dd jne 40108b <phase_5+0x29>What this while-loop is doing is basically pick the latter 4 bits of each character of the input string, and add the number represented by that 4 bits to
0x4024b0to get another byte.By the way, the target string wanted is
flyers:1
2
34010b3:4be 5e 24 40 00 mov $0x40245e,%esi
4010b8:448 8d 7c 24 10 lea 0x10(%rsp),%rdi
4010bd:4e8 76 02 00 00 call 401338 <strings_not_equal>1
2(gdb) print (char *) 0x40245e
$1 = 0x40245e "flyers"So the way to get the target string is to seek the correct letters in the string located at
0x4024b0, and prepare the characters with the corresponding last 4 bits.We can print out what exactly is stored at
0x4024b0:1
2
3(gdb) x/16c 0x4024b0
0x4024b0 <array.3449>:4109 'm' 97 'a' 100 'd' 117 'u' 105 'i' 101 'e' 114 'r' 115 's'
0x4024b8 <array.3449+8>:4110 'n' 102 'f' 111 'o' 116 't' 118 'v' 98 'b' 121 'y' 108 'l'1
2m a d u i e r s n f o t v b y l
0 1 2 3 4 5 6 7 8 9 a b c d e fString
flyerswould require such serial of index:9 f e 5 6 7. The input should be a string, so we might take a look at the ASCII table:ASCII
Dec Hex Binary Char 69 45 01000101 E 70 46 01000110 F 71 47 01000111 G 72 48 01001000 H 73 49 01001001 I 74 4A 01001010 J 75 4B 01001011 K 76 4C 01001100 L 77 4D 01001101 M 78 4E 01001110 N 79 4F 01001111 O 80 50 01010000 P 81 51 01010001 Q 82 52 01010010 R 83 53 01010011 S 84 54 01010100 T 85 55 01010101 U 86 56 01010110 V 87 57 01010111 W 88 58 01011000 X 89 59 01011001 Y 90 5A 01011010 Z 91 5B 01011011 [ 92 5C 01011100 \ 93 5D 01011101 ] 94 5E 01011110 ^ 95 5F 01011111 _ 96 60 01100000 ` 97 61 01100001 a 98 62 01100010 b 99 63 01100011 c 100 64 01100100 d 101 65 01100101 e 102 66 01100110 f 103 67 01100111 g 104 68 01101000 h 105 69 01101001 i 106 6A 01101010 j 107 6B 01101011 k 108 6C 01101100 l 109 6D 01101101 m 110 6E 01101110 n 111 6F 01101111 o 112 70 01110000 p 113 71 01110001 q 114 72 01110010 r 115 73 01110011 s 116 74 01110100 t 117 75 01110101 u 118 76 01110110 v 119 77 01110111 w 120 78 01111000 x 121 79 01111001 y 122 7A 01111010 z 123 7B 01111011 { 124 7C 01111100 | 125 7D 01111101 } 126 7E 01111110 ~ 127 7F 01111111 DEL To get an input with
9 f e 5 6 7as the four last bits of each character:ionefgY_^UVW- …
Phase 6
Assembly:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
8800000000004010f4 <phase_6>:
4010f4:441 56 push %r14
4010f6:441 55 push %r13
4010f8:441 54 push %r12
4010fa:455 push %rbp
4010fb:453 push %rbx
4010fc:448 83 ec 50 sub $0x50,%rsp
401100:449 89 e5 mov %rsp,%r13
401103:448 89 e6 mov %rsp,%rsi
401106:4e8 51 03 00 00 call 40145c <read_six_numbers>
40110b:449 89 e6 mov %rsp,%r14
40110e:441 bc 00 00 00 00 mov $0x0,%r12d
401114:44c 89 ed mov %r13,%rbp
401117:441 8b 45 00 mov 0x0(%r13),%eax
40111b:483 e8 01 sub $0x1,%eax
40111e:483 f8 05 cmp $0x5,%eax
401121:476 05 jbe 401128 <phase_6+0x34>
401123:4e8 12 03 00 00 call 40143a <explode_bomb>
401128:441 83 c4 01 add $0x1,%r12d
40112c:441 83 fc 06 cmp $0x6,%r12d
401130:474 21 je 401153 <phase_6+0x5f>
401132:444 89 e3 mov %r12d,%ebx
401135:448 63 c3 movslq %ebx,%rax
401138:48b 04 84 mov (%rsp,%rax,4),%eax
40113b:439 45 00 cmp %eax,0x0(%rbp)
40113e:475 05 jne 401145 <phase_6+0x51>
401140:4e8 f5 02 00 00 call 40143a <explode_bomb>
401145:483 c3 01 add $0x1,%ebx
401148:483 fb 05 cmp $0x5,%ebx
40114b:47e e8 jle 401135 <phase_6+0x41>
40114d:449 83 c5 04 add $0x4,%r13
401151:4eb c1 jmp 401114 <phase_6+0x20>
401153:448 8d 74 24 18 lea 0x18(%rsp),%rsi
401158:44c 89 f0 mov %r14,%rax
40115b:4b9 07 00 00 00 mov $0x7,%ecx
401160:489 ca mov %ecx,%edx
401162:42b 10 sub (%rax),%edx
401164:489 10 mov %edx,(%rax)
401166:448 83 c0 04 add $0x4,%rax
40116a:448 39 f0 cmp %rsi,%rax
40116d:475 f1 jne 401160 <phase_6+0x6c>
40116f:4be 00 00 00 00 mov $0x0,%esi
401174:4eb 21 jmp 401197 <phase_6+0xa3>
401176:448 8b 52 08 mov 0x8(%rdx),%rdx
40117a:483 c0 01 add $0x1,%eax
40117d:439 c8 cmp %ecx,%eax
40117f:475 f5 jne 401176 <phase_6+0x82>
401181:4eb 05 jmp 401188 <phase_6+0x94>
401183:4ba d0 32 60 00 mov $0x6032d0,%edx
401188:448 89 54 74 20 mov %rdx,0x20(%rsp,%rsi,2)
40118d:448 83 c6 04 add $0x4,%rsi
401191:448 83 fe 18 cmp $0x18,%rsi
401195:474 14 je 4011ab <phase_6+0xb7>
401197:48b 0c 34 mov (%rsp,%rsi,1),%ecx
40119a:483 f9 01 cmp $0x1,%ecx
40119d:47e e4 jle 401183 <phase_6+0x8f>
40119f:4b8 01 00 00 00 mov $0x1,%eax
4011a4:4ba d0 32 60 00 mov $0x6032d0,%edx
4011a9:4eb cb jmp 401176 <phase_6+0x82>
4011ab:448 8b 5c 24 20 mov 0x20(%rsp),%rbx
4011b0:448 8d 44 24 28 lea 0x28(%rsp),%rax
4011b5:448 8d 74 24 50 lea 0x50(%rsp),%rsi
4011ba:448 89 d9 mov %rbx,%rcx
4011bd:448 8b 10 mov (%rax),%rdx
4011c0:448 89 51 08 mov %rdx,0x8(%rcx)
4011c4:448 83 c0 08 add $0x8,%rax
4011c8:448 39 f0 cmp %rsi,%rax
4011cb:474 05 je 4011d2 <phase_6+0xde>
4011cd:448 89 d1 mov %rdx,%rcx
4011d0:4eb eb jmp 4011bd <phase_6+0xc9>
4011d2:448 c7 42 08 00 00 00 movq $0x0,0x8(%rdx)
4011d9:400
4011da:4bd 05 00 00 00 mov $0x5,%ebp
4011df:448 8b 43 08 mov 0x8(%rbx),%rax
4011e3:48b 00 mov (%rax),%eax
4011e5:439 03 cmp %eax,(%rbx)
4011e7:47d 05 jge 4011ee <phase_6+0xfa>
4011e9:4e8 4c 02 00 00 call 40143a <explode_bomb>
4011ee:448 8b 5b 08 mov 0x8(%rbx),%rbx
4011f2:483 ed 01 sub $0x1,%ebp
4011f5:475 e8 jne 4011df <phase_6+0xeb>
4011f7:448 83 c4 50 add $0x50,%rsp
4011fb:45b pop %rbx
4011fc:45d pop %rbp
4011fd:441 5c pop %r12
4011ff:441 5d pop %r13
401201:441 5e pop %r14
401203:4c3 retHoly, that is quite a large piece of code.
Well, its core logic can be cut into several parts.
Checking Input
The input is parsed by
read_six_numbersas the one explained before.Then the function perform a loop in order to check whether any input is less than 6 (and also larger than 0), and to ensure that each number is unique to others:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2140110e:441 bc 00 00 00 00 mov $0x0,%r12d
401114:44c 89 ed mov %r13,%rbp
401117:441 8b 45 00 mov 0x0(%r13),%eax
40111b:483 e8 01 sub $0x1,%eax
40111e:483 f8 05 cmp $0x5,%eax
401121:476 05 jbe 401128 <phase_6+0x34>
401123:4e8 12 03 00 00 call 40143a <explode_bomb>
401128:441 83 c4 01 add $0x1,%r12d
40112c:441 83 fc 06 cmp $0x6,%r12d
401130:474 21 je 401153 <phase_6+0x5f>
401132:444 89 e3 mov %r12d,%ebx
401135:448 63 c3 movslq %ebx,%rax
401138:48b 04 84 mov (%rsp,%rax,4),%eax
40113b:439 45 00 cmp %eax,0x0(%rbp)
40113e:475 05 jne 401145 <phase_6+0x51>
401140:4e8 f5 02 00 00 call 40143a <explode_bomb>
401145:483 c3 01 add $0x1,%ebx
401148:483 fb 05 cmp $0x5,%ebx
40114b:47e e8 jle 401135 <phase_6+0x41>
40114d:449 83 c5 04 add $0x4,%r13
401151:4eb c1 jmp 401114 <phase_6+0x20>Pseudocode:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23// r13 points to the current input number
int *r13 = rsp;
int r12 = 0;
while (1) {
int *rbp = r13;
int rax = *r13;
rax -= 1;
if (rax > 0x5) explode_bomb();
r12 += 1;
if (r12 == 6) break;
for (int rbx = r12; rbx <= 0x5; rbx ++) {
rax = rbx;
rax = nums[rax];
if (rax == *rbp) explode_bomb();
}
r13 += 4;
}
Subtract Each Number From 7
Then the function subtract each of the six input number from 7:
1
2
3
4
5
6
7
8
9401153:448 8d 74 24 18 lea 0x18(%rsp),%rsi
401158:44c 89 f0 mov %r14,%rax
40115b:4b9 07 00 00 00 mov $0x7,%ecx
401160:489 ca mov %ecx,%edx
401162:42b 10 sub (%rax),%edx
401164:489 10 mov %edx,(%rax)
401166:448 83 c0 04 add $0x4,%rax
40116a:448 39 f0 cmp %rsi,%rax
40116d:475 f1 jne 401160 <phase_6+0x6c>Pseudocode:
1
2
3
4
5
6
7int rcx = 7;
for (int rax = 0; rax <= 5; rax++) {
int rdx = rcx;
rdx -= nums[rax];
nums[rax] = rdx;
}
Load Linked List
After that, the function load six nodes of a linked list onto the stack:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1840116f:4be 00 00 00 00 mov $0x0,%esi
401174:4eb 21 jmp 401197 <phase_6+0xa3>
401176:448 8b 52 08 mov 0x8(%rdx),%rdx
40117a:483 c0 01 add $0x1,%eax
40117d:439 c8 cmp %ecx,%eax
40117f:475 f5 jne 401176 <phase_6+0x82>
401181:4eb 05 jmp 401188 <phase_6+0x94>
401183:4ba d0 32 60 00 mov $0x6032d0,%edx
401188:448 89 54 74 20 mov %rdx,0x20(%rsp,%rsi,2)
40118d:448 83 c6 04 add $0x4,%rsi
401191:448 83 fe 18 cmp $0x18,%rsi
401195:474 14 je 4011ab <phase_6+0xb7>
401197:48b 0c 34 mov (%rsp,%rsi,1),%ecx
40119a:483 f9 01 cmp $0x1,%ecx
40119d:47e e4 jle 401183 <phase_6+0x8f>
40119f:4b8 01 00 00 00 mov $0x1,%eax
4011a4:4ba d0 32 60 00 mov $0x6032d0,%edx
4011a9:4eb cb jmp 401176 <phase_6+0x82>We can see it from memory
0x6032d0:1
2
3
4
5
6
7
8x/wx 0x6032d0
0x6032d0 <node1>:40x0000014c
(gdb) x/wx 0x6032d0 + 0x4
0x6032d4 <node1+4>:40x00000001
(gdb) x/wx 0x6032d0 + 0x8
0x6032d8 <node1+8>:40x006032e0
(gdb) x/wx 0x6032e0
0x6032e0 <node2>:40x000000a8There are six nodes in the linked list, their values are as follow:
1
2
3
4
5
6node1: 332
node2: 168
node3: 924
node4: 691
node5: 477
node6: 443values are shown as decimal numbers
They are loaded on to the upper area of the stack:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27┌──────────────┐
+0x48 │ node_addr[5] │
├──────────────┤
│ node_addr[4] │
├──────────────┤
│ node_addr[3] │
├──────────────┤
│ node_addr[2] │
├──────────────┤
│ node_addr[1] │
├──────────────┤
+0x20 │ node_addr[0] │
├──────────────┤
│ ... │
├──────────────┤
+0x18 │ int arr[5] │
├──────────────┤
│ int arr[4] │
├──────────────┤
│ int arr[3] │
├──────────────┤
│ int arr[2] │
├──────────────┤
│ int arr[1] │
├──────────────┤
+0x00 │ int arr[0] │ <--- %rsp
└──────────────┘The order of the nodes is the same as user input subtracted from 7. For example if the user input
6 5 4 3 2 1, then the nodes pointed by the address on the stack isnode1 node2 node3 node4 node5 node6, upwards.
Reorder linked list
Then the function would reorder the linked list, while the old order is a straight from 1 to 6.
1
2
3
4
5
6
7
8
9
10
11
124011ab:448 8b 5c 24 20 mov 0x20(%rsp),%rbx
4011b0:448 8d 44 24 28 lea 0x28(%rsp),%rax
4011b5:448 8d 74 24 50 lea 0x50(%rsp),%rsi
4011ba:448 89 d9 mov %rbx,%rcx
4011bd:448 8b 10 mov (%rax),%rdx
4011c0:448 89 51 08 mov %rdx,0x8(%rcx)
4011c4:448 83 c0 08 add $0x8,%rax
4011c8:448 39 f0 cmp %rsi,%rax
4011cb:474 05 je 4011d2 <phase_6+0xde>
4011cd:448 89 d1 mov %rdx,%rcx
4011d0:4eb eb jmp 4011bd <phase_6+0xc9>
4011d2:448 c7 42 08 00 00 00 movq $0x0,0x8(%rdx)This would reorder the linked list by the order of the addresses on the stack. The nodes are now pointing upwards after the loop, from the perspective of the addresses on the stack.
Examine The Order
The final loop would check whether the new order of the linked nodes are descending to their values.
1
2
3
4
5
6
7
8
94011da:4bd 05 00 00 00 mov $0x5,%ebp
4011df:448 8b 43 08 mov 0x8(%rbx),%rax
4011e3:48b 00 mov (%rax),%eax
4011e5:439 03 cmp %eax,(%rbx)
4011e7:47d 05 jge 4011ee <phase_6+0xfa>
4011e9:4e8 4c 02 00 00 call 40143a <explode_bomb>
4011ee:448 8b 5b 08 mov 0x8(%rbx),%rbx
4011f2:483 ed 01 sub $0x1,%ebp
4011f5:475 e8 jne 4011df <phase_6+0xeb>A reminder of the linked list:
1
2
3
4
5
6node1: 332
node2: 168
node3: 924
node4: 691
node5: 477
node6: 443Obviously the expected order is :
3 -> 4 -> 5 -> 6 -> 1 -> 2.
Conclusion
From these four parts we can see that the function is basically manipulating the user input, and then examine whether the order is as expected or not.
The expected order(nodes & input):
1
3 -> 4 -> 5 -> 6 -> 1 -> 2
The order before reorder(nodes & input):
1
2
33 -> 4 -> 5 -> 6 1 -> 2 ─┐
│ │
└─────────────────────────┘The order before being subtracted from 7 (input):
1
4 3 2 1 6 5
Which is the answer.
Phew!
End
- Title: CMU 15-213 Bomb Lab
- Author: Last
- Created at : 2026-07-21 09:17:10
- Link: https://blog.imlast.top/2026/07/21/cmu15213-bomblab/
- License: This work is licensed under CC BY-NC-SA 4.0.