How to reason about this rotating XOR problem?

Question

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.
    jne .bad

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

    mov al, [esi]
    rol edx, 5
    xor dl, al
    add dl, 0xab

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

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

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

    mov cl, dl
    and cl, 15
    add cl, 'a'
    cmp [esi+4], cl
    jne .bad

    rol edx, 12
    xor dl, cl
    add dl, 0x87
    mov cl, dl
    and cl, 15
    add cl, 'a'
    cmp [esi+5], cl
    jne .bad

    rol edx, 3
    xor dl, cl
    add dl, 0xef
    mov cl, dl
    and cl, 15
    add cl, 'C'
    cmp [esi+6], cl
    jne .bad

    rol edx, 1
    xor dl, cl
    add dl, 0x10
    mov cl, dl
    and cl, 15
    add cl, 'f'
    cmp [esi+7], cl
    jne .bad

    rol edx, 13
    xor dl, cl
    add dl, 0x9a
    mov cl, dl
    and cl, 15
    add cl, 'e'
    cmp [esi+8], cl
    jne .bad

    rol edx, 9
    xor dl, cl
    add dl, 0xa8
    mov cl, dl
    and cl, 15
    add cl, 'D'
    cmp [esi+9], cl
    jne .bad

    rol edx, 7
    xor dl, cl
    add dl, 0xca
    mov cl, dl
    and cl, 15
    add cl, 'D'
    cmp [esi+10], cl
    jne .bad

    rol edx, 2
    xor dl, cl
    add dl, 0x91
    mov cl, dl
    and cl, 15
    add cl, 'c'
    cmp [esi+11], cl
    jne .bad

    rol edx, 5
    xor dl, cl
    add dl, 0x86
    mov cl, dl
    and cl, 15
    add cl, 'A'
    cmp [esi+12], cl
    jne .bad

    rol edx, 6
    xor dl, cl
    add dl, 0xf1
    mov cl, dl
    and cl, 15
    add cl, 'e'
    cmp [esi+13], cl
    jne .bad

    rol edx, 3
    xor dl, cl
    add dl, 0x1f
    mov cl, dl
    and cl, 15
    add cl, 'B'
    cmp [esi+14], cl
    jne .bad

    rol edx, 4
    xor dl, cl
    add dl, 0x90
    mov cl, dl
    and cl, 15
    add cl, 'f'
    cmp [esi+15], cl
    jne .bad

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

.bad:
    xor al, al
    mov esp, ebp
    pop ebp
    pop esi
    ret 4

julian · Answer 1 · 2020-03-19T12:42:31.303

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.

Keystone tutorial
a somewhat related question, in which Keystone and Unicorn were used to assemble and analyze some object code: Is there a handy assembly to mock app conversion tool?

blabb · Answer 2 · 2020-03-18T12:35:37.490

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

P. Private · Accepted Answer · 2021-03-21T20:19:54.177

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
add dl, 0xab

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

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

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

mov cl, dl
and cl, 15
add cl, 'a'
mov [esi+4], cl

rol edx, 12
xor dl, cl
add dl, 0x87
mov cl, dl
and cl, 15
add cl, 'a'
mov [esi+5], cl

rol edx, 3
xor dl, cl
add dl, 0xef
mov cl, dl
and cl, 15
add cl, 'C'
mov [esi+6], cl

rol edx, 1
xor dl, cl
add dl, 0x10
mov cl, dl
and cl, 15
add cl, 'f'
mov [esi+7], cl

rol edx, 13
xor dl, cl
add dl, 0x9a
mov cl, dl
and cl, 15
add cl, 'e'
mov [esi+8], cl

rol edx, 9
xor dl, cl
add dl, 0xa8
mov cl, dl
and cl, 15
add cl, 'D'
mov [esi+9], cl

rol edx, 7
xor dl, cl
add dl, 0xca
mov cl, dl
and cl, 15
add cl, 'D'
mov [esi+10], cl

rol edx, 2
xor dl, cl
add dl, 0x91
mov cl, dl
and cl, 15
add cl, 'c'
mov [esi+11], cl

rol edx, 5
xor dl, cl
add dl, 0x86
mov cl, dl
and cl, 15
add cl, 'A'
mov [esi+12], cl

rol edx, 6
xor dl, cl
add dl, 0xf1
mov cl, dl
and cl, 15
add cl, 'e'
mov [esi+13], cl

rol edx, 3
xor dl, cl
add dl, 0x1f
mov cl, dl
and cl, 15
add cl, 'B'
mov [esi+14], cl

rol edx, 4
xor dl, cl
add dl, 0x90
mov cl, dl
and cl, 15
add cl, 'f'
mov [esi+15], cl

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


section .data
    msg db  '0000000000000000', 16

Added it back for posterity. – P. Private Mar 21 '21 at 20:15 — P. Private, Mar 21 '21 at 20:15

How to reason about this rotating XOR problem?

3 Answers3