Alpha
Presentation
Subject:
Asked my sister her opinion about CS majors: "Akward and Smelly". Typical ME cope.
Author: Atzr
We are also given a binary called chal.
If we execute it, we have this:
$ ./chal
FLAG: hello
Incorrect!
Trying to solve with angr
The first thing I do in any of these challenges is to run angr on it.
angr is an open-source binary analysis platform for Python. It combines both static and dynamic symbolic (“concolic”) analysis, providing tools to solve a variety of tasks.
This tool is very powerful and you can even solve challenges without even looking at the binary.
To do so, I look at the strings in the binary to get the validation word.
$ strings chal
[---]
FLAG:
Correct!
Incorrect!
[---]
I can now build a small script. It just tries to find an input that gets “Correct” in stdout.
import angr
p = angr.Project("chal")
state = p.factory.entry_state()
def is_success(s):
return b"Correct" in s.posix.dumps(1)
def is_fail(s):
return b"Incorrect" in s.posix.dumps(1)
ex = p.factory.simulation_manager(state)
ex.explore( find = is_success , avoid=is_fail )
if len(ex.found):
print(ex.found[0].posix.dumps(0))
else:
print("Not found")
But unfortunately:
$ python3 first_try.py
Not found
Static analysis
Let’s now open the binary using IDA.
If I try to go to the main function, IDA is not able to decompile it. Therefore, I will have to work with the assembly.
Let’s try to figure out what this code does. After setting up the stack frame, it does this:
mov byte ptr [rbp-11h], 1
- it puts 1 in rbp-11h
mov rax, cs:off_4010 ; “FLAG: “ mov rdi, rax mov eax, 0 call _printf
- it prints ‘FLAG: ‘
mov rdx, cs:stdin lea rax, [rbp-60h] mov esi, 40h ; ‘@’ mov rdi, rax call _fgets
- it reads a maximum of 0x40 values from the input and it stores them in rbp-60h
movzx eax, byte ptr [rbp-57h]
- it moves rbp-57h, so the 10th character (0x60 - 0x57 + 1 because it is zero indexed) in eax.
And then:
nop dq 48FFFFFD89E8C737h, 894800002CBA058Bh, 0B8FFFFFD3AE8C7h dq 64F8558B48000000h, 2825142B48h, 0C9FFFFFD41E80574h
So I should get a SIGILL for Illegal Instruction right?
I can check this by launching the program with gdb.
0x00007fffffffdbe0│+0x0000: 0x00000a6f6c6c6568 ("hello\n"?) ← $rsp
0x00007fffffffdbe8│+0x0008: 0x0000000000000000
0x00007fffffffdbf0│+0x0010: 0x0000000000000000
0x00007fffffffdbf8│+0x0018: 0x0000000000000000
0x00007fffffffdc00│+0x0020: 0x0000000000000000
0x00007fffffffdc08│+0x0028: 0x0000000000000000
0x00007fffffffdc10│+0x0030: 0x0000000000000000
0x00007fffffffdc18│+0x0038: 0x0000000000000000
─────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
→ 0x555555555350 (bad)
0x555555555351 (bad)
0x555555555352 call 0x5555555550e0 <fgets@plt>
0x555555555357 mov rax, QWORD PTR [rip+0x2cba] # 0x555555558018
0x55555555535e mov rdi, rax
0x555555555361 call 0x5555555550a0 <puts@plt>
─────────────────────────────────────────────────────────────────────────────────────────────── threads ────
[#0] Id 1, Name: "chal", stopped 0x555555555350 in ?? (), reason: SIGILL
───────────────────────────────────────────────────────────────────────────────────────────────── trace ────
[#0] 0x555555555350 → (bad)
[#1] 0x7ffff7c2a1ca → __libc_start_call_main(main=0x555555555310, argc=0x1, argv=0x7fffffffdd68)
[#2] 0x7ffff7c2a28b → __libc_start_main_impl(main=0x555555555310, argc=0x1, argv=0x7fffffffdd68, init=<optimized out>, fini=<optimized out>, rtld_fini=<optimized out>, stack_end=0x7fffffffdd58)
[#3] 0x555555555125 → hlt
Just by running it, I as expected have a SIGILL. So what is happening?
Let’s see in IDA if we can find something that explains that. I didn’t find anything that justified that behavior, so I opened Ghidra.
Using this tool, I found an interesting function _INIT_1, which is a global constructor. Basically, it is a function that is called before the program is run to initialize the program.
void _INIT_1(void)
{
long lVar1;
sigaction *psVar2;
long in_FS_OFFSET;
sigaction local_a8;
long local_10;
local_10 = *(long *)(in_FS_OFFSET + 0x28);
psVar2 = &local_a8;
for (lVar1 = 0x13; lVar1 != 0; lVar1 = lVar1 + -1) {
(psVar2->__sigaction_handler).sa_handler = (__sighandler_t)0x0;
psVar2 = (sigaction *)&psVar2->sa_mask;
}
local_a8.__sigaction_handler.sa_handler = FUN_001011e9;
sigemptyset(&local_a8.sa_mask);
local_a8.sa_flags = 4;
sigaction(4,&local_a8,(sigaction *)0x0);
if (local_10 != *(long *)(in_FS_OFFSET + 0x28)) {
/* WARNING: Subroutine does not return */
__stack_chk_fail();
}
return;
}
I noticed that the function defines a signal handler for the signal 4, which is indeed SIGILL.
I will now have a look at the function FUN_001011e9.
void FUN_001011e9(undefined8 param_1,undefined8 param_2,long param_3)
{
uint local_1c;
*(code **)(param_3 + 0xa8) = FUN_00101310;
for (local_1c = 0; local_1c < 0x40; local_1c = local_1c + 1) {
FUN_00101310[local_1c] = (code)((byte)FUN_00101310[local_1c] ^ (&DAT_00102020)[DAT_0010403c]);
DAT_0010403c = DAT_0010403c + 1;
}
DAT_00101350 = 0x37;
return;
}
Basically, this function rewrites some values at FUN_00101310, which is main. This means that main is changing each time there is a SIGILL signal.
To check so, I will launch gdb again.
Dynamic analysis
I now know that a SIGILL is sent but it is catched by the signal handler.
When arriving on this bad instruction:
───────────────────────────────────────────────────────────────── stack ────
0x00007fffffffdaf0│+0x0000: 0x00000a6f6c6c6568 ("hello\n"?) ← $rsp
0x00007fffffffdaf8│+0x0008: 0x0000000000000000
0x00007fffffffdb00│+0x0010: 0x0000000000000000
0x00007fffffffdb08│+0x0018: 0x0000000000000000
0x00007fffffffdb10│+0x0020: 0x0000000000000000
0x00007fffffffdb18│+0x0028: 0x0000000000000000
0x00007fffffffdb20│+0x0030: 0x0000000000000000
0x00007fffffffdb28│+0x0038: 0x0000000000000000
─────────────────────────────────────────────────────────── code:x86:64 ────
→ 0x555555555350 (bad)
0x555555555351 (bad)
0x555555555352 call 0x5555555550e0 <fgets@plt>
0x555555555357 mov rax, QWORD PTR [rip+0x2cba] # 0x555555558018
0x55555555535e mov rdi, rax
0x555555555361 call 0x5555555550a0 <puts@plt>
─────────────────────────────────────────────────────────────── threads ────
[#0] Id 1, Name: "chal", stopped 0x555555555350 in ?? (), reason: SIGILL
───────────────────────────────────────────────────────────────── trace ────
[#0] 0x555555555350 → (bad)
[#1] 0x7ffff7c2a1ca → __libc_start_call_main(main=0x555555555310, argc=0x1, argv=0x7fffffffdc78)
[#2] 0x7ffff7c2a28b → __libc_start_main_impl(main=0x555555555310, argc=0x1, argv=0x7fffffffdc78, init=<optimized out>, fini=<optimized out>, rtld_fini=<optimized out>, stack_end=0x7fffffffdc68)
[#3] 0x555555555125 → hlt
────────────────────────────────────────────────────────────────────────────
I can now just si (for stepi) in gdb to enter in the signal handler.
───────────────────────────────────────────────────────────────────────────────────────────────── stack ────
0x00007fffffffcdf8│+0x0000: 0x00007ffff7c45330 → <__restore_rt+0000> mov rax, 0xf ← $rsp
0x00007fffffffce00│+0x0008: 0x0000000000000007 ← $rdx
0x00007fffffffce08│+0x0010: 0x0000000000000000
0x00007fffffffce10│+0x0018: 0x0000000000000000
0x00007fffffffce18│+0x0020: 0x0000000000000002
0x00007fffffffce20│+0x0028: 0x0000000000000000
0x00007fffffffce28│+0x0030: 0x00005555555596b6 → 0x0000000000000000
0x00007fffffffce30│+0x0038: 0x0000000000000410
─────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x5555555551d9 nop DWORD PTR [rax+0x0]
0x5555555551e0 endbr64
0x5555555551e4 jmp 0x555555555160
→ 0x5555555551e9 endbr64
0x5555555551ed push rbp
0x5555555551ee mov rbp, rsp
0x5555555551f1 mov DWORD PTR [rbp-0x24], edi
0x5555555551f4 mov QWORD PTR [rbp-0x30], rsi
0x5555555551f8 mov QWORD PTR [rbp-0x38], rdx
─────────────────────────────────────────────────────────────────────────────────────────────── threads ────
[#0] Id 1, Name: "chal", stopped 0x5555555551e9 in ?? (), reason: SINGLE STEP
───────────────────────────────────────────────────────────────────────────────────────────────── trace ────
[#0] 0x5555555551e9 → endbr64
[#1] 0x7ffff7c45330 → __restore_rt()
[#2] 0x555555555350 → (bad)
[#3] 0x7ffff7c2a1ca → __libc_start_call_main(main=0x555555555310, argc=0x1, argv=0x7fffffffdc78)
[#4] 0x7ffff7c2a28b → __libc_start_main_impl(main=0x555555555310, argc=0x1, argv=0x7fffffffdc78, init=<optimized out>, fini=<optimized out>, rtld_fini=<optimized out>, stack_end=0x7fffffffdc68)
[#5] 0x555555555125 → hlt
────────────────────────────────────────────────────────────────────────────────────────────────────────────
I will not try to understand exactly what this code is doing, it just modifies the main code. I am just going to finish to see where we go back afterwards.
───────────────────────────────────────────────────────────────────────────────────────────────── stack ────
0x00007fffffffce00│+0x0000: 0x0000000000000007 ← $rsp
0x00007fffffffce08│+0x0008: 0x0000000000000000
0x00007fffffffce10│+0x0010: 0x0000000000000000
0x00007fffffffce18│+0x0018: 0x0000000000000002
0x00007fffffffce20│+0x0020: 0x0000000000000000
0x00007fffffffce28│+0x0028: 0x00005555555596b6 → 0x0000000000000000
0x00007fffffffce30│+0x0030: 0x0000000000000410
0x00007fffffffce38│+0x0038: 0x0000000000000001
─────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x7ffff7c45320 nop
0x7ffff7c45321 data16 cs nop WORD PTR [rax+rax*1+0x0]
0x7ffff7c4532c nop DWORD PTR [rax+0x0]
→ 0x7ffff7c45330 <__restore_rt+0000> mov rax, 0xf
0x7ffff7c45337 <__restore_rt+0007> syscall
0x7ffff7c45339 <__restore_rt+0009> nop DWORD PTR [rax+0x0]
0x7ffff7c45340 <__libc_sigaction+0000> endbr64
0x7ffff7c45344 <__libc_sigaction+0004> push rbp
0x7ffff7c45345 <__libc_sigaction+0005> mov r8, rdx
─────────────────────────────────────────────────────────────────────────────────────────────── threads ────
[#0] Id 1, Name: "chal", stopped 0x7ffff7c45330 in __restore_rt (), reason: TEMPORARY BREAKPOINT
───────────────────────────────────────────────────────────────────────────────────────────────── trace ────
[#0] 0x7ffff7c45330 → __restore_rt()
[#1] 0x555555555310 → movsx ebx, al
────────────────────────────────────────────────────────────────────────────────────────────────────────────
I am now in a function called __restore_rt. By looking on the internet, I found this function does:
movq $__NR_rt_sigreturn, %rax syscall
So it justs put the return value in rax and do a syscall, which will make the program go back to the “real” code.
In gdb, I will just do si twice.
───────────────────────────────────────────────────────────────────────────────────────────────── stack ────
0x00007fffffffdaf0│+0x0000: 0x00000a6f6c6c6568 ("hello\n"?) ← $rsp
0x00007fffffffdaf8│+0x0008: 0x0000000000000000
0x00007fffffffdb00│+0x0010: 0x0000000000000000
0x00007fffffffdb08│+0x0018: 0x0000000000000000
0x00007fffffffdb10│+0x0020: 0x0000000000000000
0x00007fffffffdb18│+0x0028: 0x0000000000000000
0x00007fffffffdb20│+0x0030: 0x0000000000000000
0x00007fffffffdb28│+0x0038: 0x0000000000000000
─────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x555555555309 call 0x5555555550c0 <__stack_chk_fail@plt>
0x55555555530e leave
0x55555555530f ret
→ 0x555555555310 movsx ebx, al
0x555555555313 movzx eax, BYTE PTR [rbp-0x60]
0x555555555317 movsx r12d, al
0x55555555531b movzx eax, BYTE PTR [rbp-0x54]
0x55555555531f movsx edx, al
0x555555555322 movzx eax, BYTE PTR [rbp-0x53]
─────────────────────────────────────────────────────────────────────────────────────────────── threads ────
[#0] Id 1, Name: "chal", stopped 0x555555555310 in ?? (), reason: SINGLE STEP
───────────────────────────────────────────────────────────────────────────────────────────────── trace ────
[#0] 0x555555555310 → movsx ebx, al
────────────────────────────────────────────────────────────────────────────────────────────────────────────
I am now back into the main function (it is at 0x1310), but it is not the same one, as the signal handler modified it.
If I have a look at more instruction, by doing x /20i $rip, I have:
gef➤ x /20i $rip
=> 0x555555555310: movsx ebx,al
0x555555555313: movzx eax,BYTE PTR [rbp-0x60]
0x555555555317: movsx r12d,al
0x55555555531b: movzx eax,BYTE PTR [rbp-0x54]
0x55555555531f: movsx edx,al
0x555555555322: movzx eax,BYTE PTR [rbp-0x53]
0x555555555326: movsx eax,al
0x555555555329: mov esi,edx
0x55555555532b: mov edi,eax
0x55555555532d: call 0x55555555564a
0x555555555332: mov esi,r12d
0x555555555335: mov edi,eax
0x555555555337: call 0x5555555556c8
0x55555555533c: mov esi,ebx
0x55555555533e: mov edi,eax
0x555555555340: call 0x55555555553b
0x555555555345: cmp eax,0x1326
0x55555555534a: sete al
0x55555555534d: movzx edx,al
0x555555555350: (bad)
I see a bunch of instructions followed by a bad, so there will be another SIGILL, that will be caugh in the signal handler, that will modifies main, etc…
To confirm this, I want to dump the memory of the process right now, to see if I can see in IDA or Ghidra if something else as changed. To do so, I will first have the look at the memory mapping of the process, by running info proc map.
gef➤ info proc map
process 29123
Mapped address spaces:
Start Addr End Addr Size Offset Perms objfile
0x555555554000 0x555555555000 0x1000 0x0 r--p /home/ap/Desktop/CTF/l3ak2k25/Alpha/chal
0x555555555000 0x555555556000 0x1000 0x1000 rwxp /home/ap/Desktop/CTF/l3ak2k25/Alpha/chal
0x555555556000 0x555555557000 0x1000 0x2000 r--p /home/ap/Desktop/CTF/l3ak2k25/Alpha/chal
0x555555557000 0x555555559000 0x2000 0x2000 rw-p /home/ap/Desktop/CTF/l3ak2k25/Alpha/chal
0x555555559000 0x55555557a000 0x21000 0x0 rw-p [heap]
0x7ffff7c00000 0x7ffff7c28000 0x28000 0x0 r--p /usr/lib/x86_64-linux-gnu/libc.so.6
0x7ffff7c28000 0x7ffff7db0000 0x188000 0x28000 r-xp /usr/lib/x86_64-linux-gnu/libc.so.6
0x7ffff7db0000 0x7ffff7dff000 0x4f000 0x1b0000 r--p /usr/lib/x86_64-linux-gnu/libc.so.6
0x7ffff7dff000 0x7ffff7e03000 0x4000 0x1fe000 r--p /usr/lib/x86_64-linux-gnu/libc.so.6
0x7ffff7e03000 0x7ffff7e05000 0x2000 0x202000 rw-p /usr/lib/x86_64-linux-gnu/libc.so.6
0x7ffff7e05000 0x7ffff7e12000 0xd000 0x0 rw-p
0x7ffff7f92000 0x7ffff7f95000 0x3000 0x0 rw-p
0x7ffff7fbd000 0x7ffff7fbf000 0x2000 0x0 rw-p
0x7ffff7fbf000 0x7ffff7fc3000 0x4000 0x0 r--p [vvar]
0x7ffff7fc3000 0x7ffff7fc5000 0x2000 0x0 r-xp [vdso]
0x7ffff7fc5000 0x7ffff7fc6000 0x1000 0x0 r--p /usr/lib/x86_64-linux-gnu/ld-linux-x86-64.so.2
0x7ffff7fc6000 0x7ffff7ff1000 0x2b000 0x1000 r-xp /usr/lib/x86_64-linux-gnu/ld-linux-x86-64.so.2
0x7ffff7ff1000 0x7ffff7ffb000 0xa000 0x2c000 r--p /usr/lib/x86_64-linux-gnu/ld-linux-x86-64.so.2
0x7ffff7ffb000 0x7ffff7ffd000 0x2000 0x36000 r--p /usr/lib/x86_64-linux-gnu/ld-linux-x86-64.so.2
0x7ffff7ffd000 0x7ffff7fff000 0x2000 0x38000 rw-p /usr/lib/x86_64-linux-gnu/ld-linux-x86-64.so.2
0x7ffffffdd000 0x7ffffffff000 0x22000 0x0 rw-p [stack]
0xffffffffff600000 0xffffffffff601000 0x1000 0x0 --xp [vsyscall]
I want to dump where the program is located in memory, so I will dump between 0x555555554000 and 0x555555560000.
gef➤ dump memory dump.bin 0x555555554000 0x555555560000
I can now open this new file using IDA. I have some warning will loading it, but I can just ignore them.
If I go to the main function, I can see as expected that it has changed.
As the last instruction in the original main was movzx eax, byte ptr [rbp-57h], and the new one starts with movsx ebx, al, I think the real code executed is just the concatenation of all the main functions.
My plan is:
- scripting gdb to get all the dumps of the different versions of main
- scripting to get a file with all the objdump of the function (only the part between 0x1310 and 0x134D as it is the place of the main function)
- and then analyse the code and get the flag
Scripting GDB
This part is not the hardest part, but it is important to get all the different part of the code executed. To do so, my plan is to do exactly what I’ve done before:
- continue (will stop at SIGILL)
- si (to go inside the signal handler)
- finish (to end the function)
- si x2 (to end the __restore_rt)
- dump memory dump_X.bin 0x555555554000 0x555555560000 (with X the number of the iteration)
It’s my first time doing a gdb script, but it is quite simple.
import gdb
gdb.execute("start")
i = 1
while True:
try:
gdb.execute("continue")
gdb.execute("si")
gdb.execute("finish")
gdb.execute("si")
gdb.execute("si")
gdb.execute(f"dump memory dump_{i}.bin 0x555555554000 0x555555560000")
i += 1
except gdb.error as e:
print(f"Error encountered: {e} at iteration {i}")
break
You can just run it by doing:
gdb --command gdb_script.py ./chal
And after typing the input needed, you will get all the memory dumps. In total, I have 38 memory dumps.
Let’s now do a script to get all the commands run in the different main functions into one big block.
Scripting objdump
The idea of this part is to get a big assembly code with all the usefull code in it. To do so, I am going to extract all the code between 0x1310 and 0x134D (I will use 0x1350 as a delimiter in my script as it is the first bad instruction).
import subprocess
output = open('interesting_asm.txt', 'w')
def extract_interesting_data(file):
global output
result = subprocess.run(
['objdump', '-D', '-b', 'binary', '-mi386:x86-64', '-Mintel', file],
capture_output=True, text=True, check=True
)
lines = result.stdout.splitlines()
i = 0
while '1310:' not in lines[i]:
i += 1
while '1350:' not in lines[i]:
output.write(lines[i] + '\n')
i += 1
print(f"Extraction from {file} completed.")
extract_interesting_data("chal")
for i in range(1, 39):
extract_interesting_data(f"dump_{i}.bin")
output.close()
I have chose here to use Intel syntax as it is the same as IDA.
By running that script, I get the interesting_asm.txt file with all the interesting instructions that is being run by the program.
Static analysis again
Let’s analyse the new file that I got. We recognize a certain pattern:
134b: 0f b6 45 a9 movzx eax,BYTE PTR [rbp-0x57]
134f: 90 nop
1310: 0f be d8 movsx ebx,al
1313: 0f b6 45 a0 movzx eax,BYTE PTR [rbp-0x60]
1317: 44 0f be e0 movsx r12d,al
131b: 0f b6 45 ac movzx eax,BYTE PTR [rbp-0x54]
131f: 0f be d0 movsx edx,al
1322: 0f b6 45 ad movzx eax,BYTE PTR [rbp-0x53]
1326: 0f be c0 movsx eax,al
1329: 89 d6 mov esi,edx
132b: 89 c7 mov edi,eax
132d: e8 18 03 00 00 call 0x164a
1332: 44 89 e6 mov esi,r12d
1335: 89 c7 mov edi,eax
1337: e8 8c 03 00 00 call 0x16c8
133c: 89 de mov esi,ebx
133e: 89 c7 mov edi,eax
1340: e8 f6 01 00 00 call 0x153b
1345: 3d 26 13 00 00 cmp eax,0x1326
134a: 0f 94 c0 sete al
134d: 0f b6 d0 movzx edx,al
1310: 0f b6 45 ef movzx eax,BYTE PTR [rbp-0x11]
1314: 21 d0 and eax,edx
1316: 85 c0 test eax,eax
1318: 0f 95 c0 setne al
131b: 88 45 ef mov BYTE PTR [rbp-0x11],al
The program is taking four of my characters, put them in ebx, r12, edx and eax, then calls three functions: the first one with eax and edx, the second one with the returned value of the first function and r12, the third one with the returned value of the second function and ebx. It then compares the resulting value to a number.
The rbp-0x11 is the place where we keep the result of our previous iteration, to check if all the steps are been passed. During the first static analysis, I showed you that this value was initialised with 1. If I have a look at the end of the interesting_asm.txt:
1310: 80 7d ef 00 cmp BYTE PTR [rbp-0x11],0x0
1314: 74 11 je 0x1327
1316: 48 8b 05 fb 2c 00 00 mov rax,QWORD PTR [rip+0x2cfb] # 0x4018
131d: 48 89 c7 mov rdi,rax
1320: e8 7b fd ff ff call 0x10a0
1325: eb 0f jmp 0x1336
1327: 48 8b 05 f2 2c 00 00 mov rax,QWORD PTR [rip+0x2cf2] # 0x4020
132e: 48 89 c7 mov rdi,rax
1331: e8 6a fd ff ff call 0x10a0
1336: b8 00 00 00 00 mov eax,0x0
133b: 48 83 c4 50 add rsp,0x50
133f: 5b pop rbx
1340: 41 5c pop r12
1342: 5d pop rbp
If I look at 0x131d+0x2cfb=0x4018 and 0x132e+0x2cf2=0x4020 in IDA, I find this:
.data:0000000000004018 dq offset aCorrect ; "Correct!"
.data:0000000000004020 dq offset aIncorrect ; "Incorrect!"
So the objective is to get rbp - 0x11 to 1, so I can get the Correct!. As seen before, the input must pass all the different comparaison.
Let’s have a look now in IDA at the different other function that the program is calling.
__int64 __fastcall sub_164A(unsigned int a1, unsigned int a2)
{
unsigned int v3; // [rsp+14h] [rbp-14h]
int v4; // [rsp+18h] [rbp-10h]
unsigned int i; // [rsp+1Ch] [rbp-Ch]
v3 = 0;
v4 = 1;
for ( i = 0; i < 0x20; ++i )
{
v3 += v4 * (((a2 >> i) & 1) + ((a1 >> i) & 1) - ((a2 >> i) & 1) * ((a1 >> i) & 1));
v4 *= 2;
}
return v3;
}
__int64 __fastcall sub_16C8(int a1, int a2)
{
unsigned int v3; // [rsp+Ch] [rbp-Ch]
unsigned int i; // [rsp+10h] [rbp-8h]
v3 = 0;
for ( i = 0; i < 0x20; ++i )
v3 += (((unsigned __int8)(a1 >> i) + (unsigned __int8)(a2 >> i)) & 1) << i;
return v3;
}
__int64 __fastcall sub_153B(int a1, int a2)
{
int v3; // [rsp+8h] [rbp-10h]
int v4; // [rsp+Ch] [rbp-Ch]
unsigned int i; // [rsp+10h] [rbp-8h]
v3 = 0;
v4 = ((unsigned int)a1 >> 31) + (a1 ^ (a1 >> 31));
for ( i = ((unsigned int)a2 >> 31) + (a2 ^ (a2 >> 31)); i; i >>= 1 )
{
v3 += v4 & -(i & 1);
v4 *= 2;
}
return (v3 ^ -((a2 ^ (unsigned int)a1) >> 31)) + ((a2 ^ (unsigned int)a1) >> 31);
}
__int64 __fastcall sub_1401(int a1, int a2)
{
int v3; // [rsp+14h] [rbp-34h]
int v4; // [rsp+18h] [rbp-30h]
int v5; // [rsp+18h] [rbp-30h]
int i; // [rsp+1Ch] [rbp-2Ch]
int j; // [rsp+20h] [rbp-28h]
unsigned int v8; // [rsp+24h] [rbp-24h]
int k; // [rsp+28h] [rbp-20h]
int v10; // [rsp+34h] [rbp-14h]
int v11; // [rsp+3Ch] [rbp-Ch]
v3 = 0;
v4 = 1;
for ( i = 0; i < 32; ++i )
v3 |= !((a2 >> i) & 1) << i;
for ( j = 0; j < 32; ++j )
{
v11 = v4 ^ (v3 >> j) & 1;
v4 &= (v3 >> j) & 1;
v3 = v3 & ~(1 << j) | (v11 << j);
}
v8 = 0;
v5 = 0;
for ( k = 0; k < 32; ++k )
{
v10 = v5 ^ (v3 >> k) & 1 ^ (a1 >> k) & 1;
v5 = (a1 >> k) & 1 & (v5 | (v3 >> k) & 1) | v5 & (v3 >> k) & 1;
v8 |= v10 << k;
}
return v8;
}
__int64 __fastcall sub_15B8(unsigned int a1, int a2)
{
unsigned int v3; // [rsp+8h] [rbp-20h]
unsigned int v4; // [rsp+Ch] [rbp-1Ch]
unsigned int i; // [rsp+10h] [rbp-18h]
int v6; // [rsp+14h] [rbp-14h]
unsigned int j; // [rsp+18h] [rbp-10h]
v3 = 0;
v4 = 1;
for ( i = 0; i < 0x20; ++i )
{
v6 = 1;
for ( j = 0; j < i; ++j )
v6 *= 2;
v3 += v6 * ((a2 >> i) & 1 & (a1 / v4) & 1);
v4 *= 2;
}
return v3;
}
__int64 __fastcall sub_1381(int a1, int a2)
{
int v3; // [rsp+14h] [rbp-14h]
unsigned int v4; // [rsp+18h] [rbp-10h]
unsigned int i; // [rsp+1Ch] [rbp-Ch]
v3 = 0;
v4 = 0;
for ( i = 0; i < 0x20; ++i )
{
v4 |= (1 << i) & (v3 ^ a2 ^ a1);
v3 = 2 * ((1 << i) & (a2 & (v3 | a1) | v3 & a1));
}
return v4;
}
Each of these functions is only doing a basic operation between its two arguments. To find out this, you can just transcript these function in python, and by trying some values you will find that:
def sub_164a(a1, a2):
return a1 | a2
def sub_16c8(a1, a2):
return a1 ^ a2
def sub_153b(a1, a2):
return a2 * a1
def sub_1401(a1, a2):
return a1 - a2
def sub_15b8(a1, a2):
return a1 & a2
def sub_1381(a1, a2):
return a1 + a2
Now, I just need to build a script to parse interesting_asm.txt and write a python script that uses z3 to solve this equations.
Scripting z3
Here is my script doing so:
LEN = 24
f = open("z3_solve.py", "w")
f.write(f"""
from z3 import *
def sub_164a(a1, a2):
return a1 | a2
def sub_16c8(a1, a2):
return a1 ^ a2
def sub_153b(a1, a2):
return a2 * a1
def sub_1401(a1, a2):
return a1 - a2
def sub_15b8(a1, a2):
return a1 & a2
def sub_1381(a1, a2):
return a1 + a2
LEN = {LEN}
s = String('s')
solver = Solver()
solver.add(Length(s) == LEN)
def OrdAt(inp, i):
return StrToCode(SubString(inp, i, 1))
for i in range(LEN):
c = OrdAt(s, i)
solver.add(And(c >= 33, c <= 126))
""")
def compute_place(value):
return 0x60 - value
registers = ["ebx", "r12", "edx", "eax"]
register_index = 0
args = ["eax, edx", "eax, r12", "eax, ebx"]
args_index = 0
with open("interesting_asm.txt", "r") as data:
for line in data:
if "movzx eax,BYTE PTR [rbp-0x" in line:
reg = line.split("movzx eax,BYTE PTR [rbp-0x")[-1][:2]
reg = int(reg, 16)
if reg == 0x11:
continue
f.write(f"{registers[register_index]} = Int2BV(OrdAt(s, {compute_place(reg)}), 32)\n")
register_index += 1
if register_index >= len(registers):
register_index = 0
elif "call" in line:
call = (line.split("call 0x")[-1]).strip()
if call not in ["164a", "16c8", "153b", "1401", "15b8", "1381"]:
continue
f.write(f"eax = sub_{call}({args[args_index]})\n")
args_index += 1
if args_index >= len(args):
args_index = 0
elif "cmp eax,0x" in line:
value = int(line.split("cmp eax,0x")[-1].strip(), 16)
f.write(f"solver.add(eax == BitVecVal({hex(value)},32))\n")
elif "132a: 85 c0 test eax,eax" in line:
f.write("solver.add(eax == BitVecVal(0,32))\n")
f.write("""
if solver.check() == sat:
print(solver.model()[s])
else:
print("unsat")
""")
f.close()
There is only one edge case: one time there is no cmp, but a test eax, eax to check if eax equals 0.
By running this script, you will get this one:
from z3 import *
def sub_164a(a1, a2):
return a1 | a2
def sub_16c8(a1, a2):
return a1 ^ a2
def sub_153b(a1, a2):
return a2 * a1
def sub_1401(a1, a2):
return a1 - a2
def sub_15b8(a1, a2):
return a1 & a2
def sub_1381(a1, a2):
return a1 + a2
LEN = 24
s = String('s')
solver = Solver()
solver.add(Length(s) == LEN)
def OrdAt(inp, i):
return StrToCode(SubString(inp, i, 1))
for i in range(LEN):
c = OrdAt(s, i)
solver.add(And(c >= 33, c <= 126))
ebx = Int2BV(OrdAt(s, 9), 32)
r12 = Int2BV(OrdAt(s, 0), 32)
edx = Int2BV(OrdAt(s, 12), 32)
eax = Int2BV(OrdAt(s, 13), 32)
eax = sub_164a(eax, edx)
eax = sub_16c8(eax, r12)
eax = sub_153b(eax, ebx)
solver.add(eax == BitVecVal(0x1326,32))
ebx = Int2BV(OrdAt(s, 20), 32)
r12 = Int2BV(OrdAt(s, 22), 32)
edx = Int2BV(OrdAt(s, 10), 32)
eax = Int2BV(OrdAt(s, 14), 32)
eax = sub_164a(eax, edx)
eax = sub_1401(eax, r12)
eax = sub_16c8(eax, ebx)
solver.add(eax == BitVecVal(0xffffffc0,32))
ebx = Int2BV(OrdAt(s, 2), 32)
r12 = Int2BV(OrdAt(s, 12), 32)
edx = Int2BV(OrdAt(s, 10), 32)
eax = Int2BV(OrdAt(s, 7), 32)
eax = sub_16c8(eax, edx)
eax = sub_1401(eax, r12)
eax = sub_1401(eax, ebx)
solver.add(eax == BitVecVal(0xffffffb9,32))
ebx = Int2BV(OrdAt(s, 11), 32)
r12 = Int2BV(OrdAt(s, 16), 32)
edx = Int2BV(OrdAt(s, 7), 32)
eax = Int2BV(OrdAt(s, 20), 32)
eax = sub_16c8(eax, edx)
eax = sub_15b8(eax, r12)
eax = sub_153b(eax, ebx)
solver.add(eax == BitVecVal(0x22e2,32))
ebx = Int2BV(OrdAt(s, 7), 32)
r12 = Int2BV(OrdAt(s, 15), 32)
edx = Int2BV(OrdAt(s, 8), 32)
eax = Int2BV(OrdAt(s, 1), 32)
eax = sub_153b(eax, edx)
eax = sub_16c8(eax, r12)
eax = sub_153b(eax, ebx)
solver.add(eax == BitVecVal(0x44126,32))
ebx = Int2BV(OrdAt(s, 20), 32)
r12 = Int2BV(OrdAt(s, 8), 32)
edx = Int2BV(OrdAt(s, 1), 32)
eax = Int2BV(OrdAt(s, 22), 32)
eax = sub_16c8(eax, edx)
eax = sub_16c8(eax, r12)
eax = sub_164a(eax, ebx)
solver.add(eax == BitVecVal(0x73,32))
ebx = Int2BV(OrdAt(s, 1), 32)
r12 = Int2BV(OrdAt(s, 11), 32)
edx = Int2BV(OrdAt(s, 20), 32)
eax = Int2BV(OrdAt(s, 18), 32)
eax = sub_164a(eax, edx)
eax = sub_1381(eax, r12)
eax = sub_16c8(eax, ebx)
solver.add(eax == BitVecVal(0xe5,32))
ebx = Int2BV(OrdAt(s, 21), 32)
r12 = Int2BV(OrdAt(s, 4), 32)
edx = Int2BV(OrdAt(s, 0), 32)
eax = Int2BV(OrdAt(s, 13), 32)
eax = sub_153b(eax, edx)
eax = sub_153b(eax, r12)
eax = sub_15b8(eax, ebx)
solver.add(eax == BitVecVal(0x50,32))
ebx = Int2BV(OrdAt(s, 22), 32)
r12 = Int2BV(OrdAt(s, 6), 32)
edx = Int2BV(OrdAt(s, 12), 32)
eax = Int2BV(OrdAt(s, 4), 32)
eax = sub_1381(eax, edx)
eax = sub_16c8(eax, r12)
eax = sub_16c8(eax, ebx)
solver.add(eax == BitVecVal(0x8c,32))
ebx = Int2BV(OrdAt(s, 6), 32)
r12 = Int2BV(OrdAt(s, 3), 32)
edx = Int2BV(OrdAt(s, 19), 32)
eax = Int2BV(OrdAt(s, 17), 32)
eax = sub_1401(eax, edx)
eax = sub_15b8(eax, r12)
eax = sub_15b8(eax, ebx)
solver.add(eax == BitVecVal(0,32))
ebx = Int2BV(OrdAt(s, 5), 32)
r12 = Int2BV(OrdAt(s, 18), 32)
edx = Int2BV(OrdAt(s, 2), 32)
eax = Int2BV(OrdAt(s, 3), 32)
eax = sub_16c8(eax, edx)
eax = sub_1381(eax, r12)
eax = sub_153b(eax, ebx)
solver.add(eax == BitVecVal(0x19a0,32))
ebx = Int2BV(OrdAt(s, 14), 32)
r12 = Int2BV(OrdAt(s, 6), 32)
edx = Int2BV(OrdAt(s, 0), 32)
eax = Int2BV(OrdAt(s, 18), 32)
eax = sub_153b(eax, edx)
eax = sub_15b8(eax, r12)
eax = sub_1381(eax, ebx)
solver.add(eax == BitVecVal(0x40,32))
ebx = Int2BV(OrdAt(s, 5), 32)
r12 = Int2BV(OrdAt(s, 4), 32)
edx = Int2BV(OrdAt(s, 2), 32)
eax = Int2BV(OrdAt(s, 2), 32)
eax = sub_15b8(eax, edx)
eax = sub_164a(eax, r12)
eax = sub_15b8(eax, ebx)
solver.add(eax == BitVecVal(0x52,32))
ebx = Int2BV(OrdAt(s, 15), 32)
r12 = Int2BV(OrdAt(s, 12), 32)
edx = Int2BV(OrdAt(s, 9), 32)
eax = Int2BV(OrdAt(s, 0), 32)
eax = sub_16c8(eax, edx)
eax = sub_153b(eax, r12)
eax = sub_1401(eax, ebx)
solver.add(eax == BitVecVal(0x7cc,32))
ebx = Int2BV(OrdAt(s, 11), 32)
r12 = Int2BV(OrdAt(s, 21), 32)
edx = Int2BV(OrdAt(s, 12), 32)
eax = Int2BV(OrdAt(s, 17), 32)
eax = sub_153b(eax, edx)
eax = sub_1381(eax, r12)
eax = sub_16c8(eax, ebx)
solver.add(eax == BitVecVal(0x21f4,32))
ebx = Int2BV(OrdAt(s, 17), 32)
r12 = Int2BV(OrdAt(s, 22), 32)
edx = Int2BV(OrdAt(s, 12), 32)
eax = Int2BV(OrdAt(s, 22), 32)
eax = sub_15b8(eax, edx)
eax = sub_1381(eax, r12)
eax = sub_16c8(eax, ebx)
solver.add(eax == BitVecVal(0xad,32))
ebx = Int2BV(OrdAt(s, 17), 32)
r12 = Int2BV(OrdAt(s, 23), 32)
edx = Int2BV(OrdAt(s, 16), 32)
eax = Int2BV(OrdAt(s, 23), 32)
eax = sub_16c8(eax, edx)
eax = sub_15b8(eax, r12)
eax = sub_153b(eax, ebx)
solver.add(eax == BitVecVal(0x69,32))
ebx = Int2BV(OrdAt(s, 21), 32)
r12 = Int2BV(OrdAt(s, 1), 32)
edx = Int2BV(OrdAt(s, 0), 32)
eax = Int2BV(OrdAt(s, 2), 32)
eax = sub_1401(eax, edx)
eax = sub_15b8(eax, r12)
eax = sub_1401(eax, ebx)
solver.add(eax == BitVecVal(0xffffffbf,32))
ebx = Int2BV(OrdAt(s, 2), 32)
r12 = Int2BV(OrdAt(s, 0), 32)
edx = Int2BV(OrdAt(s, 22), 32)
eax = Int2BV(OrdAt(s, 14), 32)
eax = sub_153b(eax, edx)
eax = sub_16c8(eax, r12)
eax = sub_153b(eax, ebx)
solver.add(eax == BitVecVal(0x73f8c,32))
ebx = Int2BV(OrdAt(s, 20), 32)
r12 = Int2BV(OrdAt(s, 18), 32)
edx = Int2BV(OrdAt(s, 15), 32)
eax = Int2BV(OrdAt(s, 4), 32)
eax = sub_1401(eax, edx)
eax = sub_153b(eax, r12)
eax = sub_1401(eax, ebx)
solver.add(eax == BitVecVal(0x35b,32))
ebx = Int2BV(OrdAt(s, 1), 32)
r12 = Int2BV(OrdAt(s, 5), 32)
edx = Int2BV(OrdAt(s, 8), 32)
eax = Int2BV(OrdAt(s, 1), 32)
eax = sub_1401(eax, edx)
eax = sub_153b(eax, r12)
eax = sub_153b(eax, ebx)
solver.add(eax == BitVecVal(0x3102,32))
ebx = Int2BV(OrdAt(s, 6), 32)
r12 = Int2BV(OrdAt(s, 3), 32)
edx = Int2BV(OrdAt(s, 16), 32)
eax = Int2BV(OrdAt(s, 14), 32)
eax = sub_1401(eax, edx)
eax = sub_1381(eax, r12)
eax = sub_1401(eax, ebx)
solver.add(eax == BitVecVal(0xffffffda,32))
ebx = Int2BV(OrdAt(s, 11), 32)
r12 = Int2BV(OrdAt(s, 21), 32)
edx = Int2BV(OrdAt(s, 21), 32)
eax = Int2BV(OrdAt(s, 23), 32)
eax = sub_16c8(eax, edx)
eax = sub_15b8(eax, r12)
eax = sub_15b8(eax, ebx)
solver.add(eax == BitVecVal(0x2,32))
ebx = Int2BV(OrdAt(s, 6), 32)
r12 = Int2BV(OrdAt(s, 19), 32)
edx = Int2BV(OrdAt(s, 13), 32)
eax = Int2BV(OrdAt(s, 23), 32)
eax = sub_15b8(eax, edx)
eax = sub_1381(eax, r12)
eax = sub_1401(eax, ebx)
solver.add(eax == BitVecVal(0x63,32))
ebx = Int2BV(OrdAt(s, 4), 32)
r12 = Int2BV(OrdAt(s, 16), 32)
edx = Int2BV(OrdAt(s, 23), 32)
eax = Int2BV(OrdAt(s, 11), 32)
eax = sub_1381(eax, edx)
eax = sub_16c8(eax, r12)
eax = sub_16c8(eax, ebx)
solver.add(eax == BitVecVal(0xd9,32))
ebx = Int2BV(OrdAt(s, 8), 32)
r12 = Int2BV(OrdAt(s, 3), 32)
edx = Int2BV(OrdAt(s, 13), 32)
eax = Int2BV(OrdAt(s, 13), 32)
eax = sub_153b(eax, edx)
eax = sub_16c8(eax, r12)
eax = sub_1381(eax, ebx)
solver.add(eax == BitVecVal(0x3562,32))
ebx = Int2BV(OrdAt(s, 8), 32)
r12 = Int2BV(OrdAt(s, 1), 32)
edx = Int2BV(OrdAt(s, 15), 32)
eax = Int2BV(OrdAt(s, 21), 32)
eax = sub_15b8(eax, edx)
eax = sub_16c8(eax, r12)
eax = sub_164a(eax, ebx)
solver.add(eax == BitVecVal(0x71,32))
ebx = Int2BV(OrdAt(s, 11), 32)
r12 = Int2BV(OrdAt(s, 2), 32)
edx = Int2BV(OrdAt(s, 15), 32)
eax = Int2BV(OrdAt(s, 14), 32)
eax = sub_15b8(eax, edx)
eax = sub_1401(eax, r12)
eax = sub_16c8(eax, ebx)
solver.add(eax == BitVecVal(0xffffffa0,32))
if solver.check() == sat:
print(solver.model()[s])
else:
print("unsat")
Which gives:
$ python3 z3_solve.py
"L3AK{R3m0V&_Qu@n~iF!3rs}"
$ ./chal
FLAG: L3AK{R3m0V&_Qu@n~iF!3rs}
Correct!
Conclusion
This challenge was a fun one. I learned how to script gdb, which is quite simple. However, after reading some write-ups about this challenge, I saw that many of them were doing only static analysis, and just analyse the signal handler function to understand how the main function is being decoded each round. It is for sure an easier solution, and maybe next time I should spend more time on my first static analysis before launching gdb.