Disclaimer: I'm not asking for the solution to this problem, but for you to point out the particular areas or techniques of reverse engineering that I need to improve at in order to solve this problem myself.

The code in question comes from the game "Sourcery," it's basically a CTF inside a game. The game doesn't give you the ability to debug or modify the code whatsoever, so the problem to solve here is to find an input that will make `verify_code` return 1.

So far I had the idea of trying to brute force the solution, i.e. trying all possible codes until I find one that works. The range of acceptable characters for the code is all printable ascii chars, and we need to figure out 16 chars, which seems like it would take too much time to brute force unless you were able to reduce the character range.

The thing that is making this hard for me to mentally analyze is that it seems like if you change one character, it can change the effect that successive characters have on the execution path.

Any ideas how to approach this?

``````; int verify_code(char *code)
verify_code:
push esi
push ebp
mov ebp, esp
sub esp, 8

push dword [ebp + 12]
call strlen
cmp eax, 16
; the code must be 16 characters long.

mov esi, [ebp + 12]
mov edx, 0xfa

mov al, [esi]
rol edx, 5
xor dl, al

mov al, [esi+1]
rol edx, 3
xor dl, al

mov al, [esi+2]
rol edx, 1
xor dl, al

mov al, [esi+3]
rol edx, 9
xor dl, al

mov cl, dl
and cl, 15
cmp [esi+4], cl

rol edx, 12
xor dl, cl
mov cl, dl
and cl, 15
cmp [esi+5], cl

rol edx, 3
xor dl, cl
mov cl, dl
and cl, 15
cmp [esi+6], cl

rol edx, 1
xor dl, cl
mov cl, dl
and cl, 15
cmp [esi+7], cl

rol edx, 13
xor dl, cl
mov cl, dl
and cl, 15
cmp [esi+8], cl

rol edx, 9
xor dl, cl
mov cl, dl
and cl, 15
cmp [esi+9], cl

rol edx, 7
xor dl, cl
mov cl, dl
and cl, 15
cmp [esi+10], cl

rol edx, 2
xor dl, cl
mov cl, dl
and cl, 15
cmp [esi+11], cl

rol edx, 5
xor dl, cl
mov cl, dl
and cl, 15
cmp [esi+12], cl

rol edx, 6
xor dl, cl
mov cl, dl
and cl, 15
cmp [esi+13], cl

rol edx, 3
xor dl, cl
mov cl, dl
and cl, 15
cmp [esi+14], cl

rol edx, 4
xor dl, cl
mov cl, dl
and cl, 15
cmp [esi+15], cl

mov al, 1
mov esp, ebp
pop ebp
pop esi
ret 4

xor al, al
mov esp, ebp
pop ebp
pop esi
ret 4
``````

if the ctf does not give you the ability to debug
lift it to something else and emulate
basically rol() is not reversible per se
you may have to bit wrangle with this

here is a python lifted manipulation of first character

``````#rol copy paste from https://gist.github.com/trietptm/5cd60ed6add5adad6a34098ce255949a
max_bits =16
rol = lambda val, r_bits, max_bits: \
(val << r_bits%max_bits) & (2**max_bits-1) | \
((val & (2**max_bits-1)) >> (max_bits-(r_bits%max_bits)))

#========================start of emul=================
input = "abcdefghijklmnop"              # 16 long char*
esi= input                              # mov esi, [ebp + 12]
edx=0xfa                                # mov edx, 0xfa
al=esi[0:1]                             # mov al, [esi] ==> 'a = 0x61 ==> 97'
edx = rol(edx,5,max_bits)               # rol edx, 5    ==>  0x1f40
dl  = ( (edx & 0x000000ff) ^ ord(al))   # xor dl,al     ==>  0x1f21
edx = (edx & 0xffffff00) | dl  + 0xab   # add dl, 0xab  ==>  0x1fcc
print (hex(edx))
``````

or you can use debugger like ollydbg,x64dbg etc and assemble this inside and single step through this or use emulators like unicorn after converting this mnemonic into suitable hex with say keystone

here is a python confirmation (basically a rol ,5 on a 32bit just appends 5 0x0 at the end )

``````C:\>python -c "print(hex((int(bin(0xfa)+'00000',2)^ord('a'))+0xab))"
0x1fcc
``````

with this block you are constrained to an input range of only {a,b,c,..p}

``````mov cl, dl    (assuming dl spans {0...255}
and cl, 15    (dl & 0x0f willl span {0x0..0xf}
add cl, 'a'   {adding 0x0 to 0x61 will make it constrained to a..a+15 ==>
a to p and 5 the charecter must be the result of first 4 charecters manipulated result }
cmp [esi+4], cl
``````
• If the above code can be assembled into object code, the code can be emulated
• If the above code can be assembled into object code and then linked into a stand-alone executable, you can analyze it however you like

I'm not good at or interested in trying to perform computations like these mentally or tracing them out on paper, so if I was in this kind of situation I would first try to wrangle this code into a form that can be assembled into a stand-alone executable (for example, there needs to be a ‘_start’ or ‘main’). If this can be done, symbolic execution coupled with an SMT solver can be used to find solutions automatically (angr). From my perspective, successfully creating a binary executable out of this code is the ideal solution.

An alternative approach is emulation. After having assembled the above code using the Keystone engine, analysis can be performed via Unicorn or the Qiling framework.

After looking over the assembly source again, I realized that the last 12 characters of the code depended completely on the values of the first 4. Because of this, you can generate the last 12 characters from the first 4. The code can be lifted (as suggested by other answers) with some small modifications to the code to perform writes instead of cmp+jne. Note: The encryption method is basically a Feistel cipher.

Below is the modified lifted code I used to generate the flag:

``````section .text
global _start
_start:
call generate_code
mov edx, 16     ;message length
mov ecx, msg    ;message to write
mov ebx, 1      ;file descriptor (stdout)
mov eax, 4      ;system call number (sys_write)
int 0x80        ;syscall
jmp _done
_done:
mov eax, 1      ;system call number (sys_exit)
int 0x80        ;syscall

generate_code:
push esi
push ebp
mov ebp, esp

mov esi, msg
mov edx, 0xfa

mov al, [esi]
rol edx, 5
xor dl, al

mov al, [esi+1]
rol edx, 3
xor dl, al

mov al, [esi+2]
rol edx, 1
xor dl, al

mov al, [esi+3]
rol edx, 9
xor dl, al

mov cl, dl
and cl, 15
mov [esi+4], cl

rol edx, 12
xor dl, cl
mov cl, dl
and cl, 15
mov [esi+5], cl

rol edx, 3
xor dl, cl
mov cl, dl
and cl, 15
mov [esi+6], cl

rol edx, 1
xor dl, cl
mov cl, dl
and cl, 15
mov [esi+7], cl

rol edx, 13
xor dl, cl
mov cl, dl
and cl, 15
mov [esi+8], cl

rol edx, 9
xor dl, cl
mov cl, dl
and cl, 15
mov [esi+9], cl

rol edx, 7
xor dl, cl
mov cl, dl
and cl, 15
mov [esi+10], cl

rol edx, 2
xor dl, cl
mov cl, dl
and cl, 15
mov [esi+11], cl

rol edx, 5
xor dl, cl
mov cl, dl
and cl, 15
mov [esi+12], cl

rol edx, 6
xor dl, cl
mov cl, dl
and cl, 15
mov [esi+13], cl

rol edx, 3
xor dl, cl
mov cl, dl
and cl, 15
mov [esi+14], cl

rol edx, 4
xor dl, cl
mov cl, dl
and cl, 15
mov [esi+15], cl

mov al, 1
mov esp, ebp
pop ebp
pop esi
ret

section .data
msg db  '0000000000000000', 16
``````
• why was the code removed?
– julian
Apr 4, 2020 at 20:08
• Added it back for posterity. Mar 21, 2021 at 20:15