Happy Swamp CTF -> Journey

Hi everybody, it’s a shiny new day for a write-up! The past two days were really busy in ZenHack headquarter: we decided to deep dive into Swamp CTF!

The write-up I want to show you is the solution of Journey, the second Reversing challenge. This is a samplle output of the program:

As you play this game, there will be many adventures for you to take,
quests on the side of this great journey.
This is one of the quests here, and you may not know it yet. You will
know when you complete the test, because all of the die will have been
cast in your favor.
Prove your worth, enter a password to continue!

> I'm a Tucano

Mission failed! You must try again, giving up was never an answer if
you have gotten this far!

Basically, it wants a password. Let’s try to guess what it does with radare2. But first, I have to unpack the binary with UPX (yes, it was all scrambled…).

The binary is now readable!

The main function of journey just print that wall of text. There is a scanf:

0x080488cb      8d45e2         lea eax, [INPUTSTR]
0x080488ce      50             push eax
0x080488cf      68ecb20b08     push str.17s  (which is "%17s")
0x080488d4      e897670000     call sym.__isoc99_scanf

It reads a string of 17 non blank characters. It can’t be pwned :\ The interesting part of the binary is the following:

     0x080488eb      8945cc         mov dword [STRLEN], eax
     0x080488ee      c745d0000000.  mov dword [VARIABLE], 0
     0x080488f5      c745d89153d2.  mov dword [BIGNUM_LOW], 0x67d25391
     0x080488fc      c745dc3b8f32.  mov dword [BIGNUM_HIGH], 0x328f3b
     0x08048903      c745c8000000.  mov dword [COUNTER], 0
 ,=< 0x0804890a      eb55           jmp 0x8048961               ;[2]
.--> 0x0804890c      8b45d8         mov eax, dword [BIGNUM_LOW]
:|   0x0804890f      8b55dc         mov edx, dword [BIGNUM_HIGH]
:|   0x08048912      6a00           push 0
:|   0x08048914      6a0a           push 0xa                    ; 10
:|   0x08048916      52             push edx
:|   0x08048917      50             push eax
:|   0x08048918      e843020000     call sym.__moddi3           ;[3]
:|   0x0804891d      83c410         add esp, 0x10
:|   0x08048920      8945d0         mov dword [VARIABLE], eax
:|   0x08048923      8b45d8         mov eax, dword [BIGNUM_LOW]
:|   0x08048926      8b55dc         mov edx, dword [BIGNUM_HIGH]
:|   0x08048929      6a00           push 0
:|   0x0804892b      6a0a           push 0xa                    ; 10
:|   0x0804892d      52             push edx
:|   0x0804892e      50             push eax
:|   0x0804892f      e8bc000000     call sym.__divdi3           ;[4]
:|   0x08048934      83c410         add esp, 0x10
:|   0x08048937      8945d8         mov dword [BIGNUM_LOW], eax
:|   0x0804893a      8955dc         mov dword [BIGNUM_HIGH], edx
:|   0x0804893d      8d55e2         lea edx, [INPUTSTR]
:|   0x08048940      8b45c8         mov eax, dword [COUNTER]
:|   0x08048943      01d0           add eax, edx
:|   0x08048945      0fb600         movzx eax, byte [eax]
:|   0x08048948      89c2           mov edx, eax
:|   0x0804894a      8b45d0         mov eax, dword [VARIABLE]
:|   0x0804894d      29c2           sub edx, eax
:|   0x0804894f      89d0           mov eax, edx
:|   0x08048951      89c1           mov ecx, eax
:|   0x08048953      8d55e2         lea edx, [INPUTSTR]
:|   0x08048956      8b45c8         mov eax, dword [COUNTER]
:|   0x08048959      01d0           add eax, edx
:|   0x0804895b      8808           mov byte [eax], cl
:|   0x0804895d      8345c801       add dword [COUNTER], 1
:`-> 0x08048961      8b45c8         mov eax, dword [COUNTER]
:    0x08048964      3b45cc         cmp eax, dword [STRLEN]
`==< 0x08048967      7ca3           jl 0x804890c;
     0x08048969      83ec08         sub esp, 8
     0x0804896c      68f1b20b08     push str.theresanotherstep
     0x08048971      8d45e2         lea eax, [local_1eh]
     0x08048974      50             push eax
     0x08048975      e806f9ffff     call fcn.08048280           ;[2]
     0x0804897a      83c410         add esp, 0x10
     0x0804897d      8945d4         mov dword [local_2ch], eax
     0x08048980      837dd400       cmp dword [local_2ch], 0
 ,=< 0x08048984      7532           jne 0x80489b8

It seems a bit though, isn’t it?

Let’s reverse it.

.--> 0x0804890c      8b45d8         mov eax, dword [BIGNUM_LOW]
:|   0x0804890f      8b55dc         mov edx, dword [BIGNUM_HIGH]
:|   0x08048912      6a00           push 0
:|   0x08048914      6a0a           push 0xa                    ; 10
:|   0x08048916      52             push edx
:|   0x08048917      50             push eax
:|   0x08048918      e843020000     call sym.__moddi3           ;[3]
:|   0x0804891d      83c410         add esp, 0x10
:|   0x08048920      8945d0         mov dword [VARIABLE], eax

FIRST TRICKY PART

What’s that strange sym.__moddi3? It’s basically a%b, where a,b -> long. This is why there are two push on the stack for each argument. The first one is BIGNUM (divided in HIGH and LOW), while the second is 10 (in 64 bit, so 63 \x00 and then \x0a). Then, the reminder result is put in VARIABLE.

:|   0x0804891d      83c410         add esp, 0x10
:|   0x08048920      8945d0         mov dword [VARIABLE], eax
:|   0x08048923      8b45d8         mov eax, dword [BIGNUM_LOW]
:|   0x08048926      8b55dc         mov edx, dword [BIGNUM_HIGH]
:|   0x08048929      6a00           push 0
:|   0x0804892b      6a0a           push 0xa                    ; 10
:|   0x0804892d      52             push edx
:|   0x0804892e      50             push eax
:|   0x0804892f      e8bc000000     call sym.__divdi3           ;[4]

The program then computes the division of BIGNUM and 10 (which is performed by sym.__divdi3, again it’s division between long)…

:|   0x08048937      8945d8         mov dword [BIGNUM_LOW], eax
:|   0x0804893a      8955dc         mov dword [BIGNUM_HIGH], edx

… and stores the new BIGNUM in its original location.

SECOND TRICKY PART

:|   0x0804893d      8d55e2         lea edx, [INPUTSTR]
:|   0x08048940      8b45c8         mov eax, dword [COUNTER]
:|   0x08048943      01d0           add eax, edx
:|   0x08048945      0fb600         movzx eax, byte [eax]
:|   0x08048948      89c2           mov edx, eax
:|   0x0804894a      8b45d0         mov eax, dword [VARIABLE]
:|   0x0804894d      29c2           sub edx, eax

The program takes the vlaue of the calculated reminder and subtracts is from the current char pointed by INPUTSTR+COUNTER.

:|   0x0804894f      89d0           mov eax, edx
:|   0x08048951      89c1           mov ecx, eax
:|   0x08048953      8d55e2         lea edx, [INPUTSTR]
:|   0x08048956      8b45c8         mov eax, dword [COUNTER]
:|   0x08048959      01d0           add eax, edx
:|   0x0804895b      8808           mov byte [eax], cl
:|   0x0804895d      8345c801       add dword [COUNTER], 1
:`-> 0x08048961      8b45c8         mov eax, dword [COUNTER]
:    0x08048964      3b45cc         cmp eax, dword [STRLEN]
`==< 0x08048967      7ca3           jl 0x804890c;

It’s time for checking if the cycles has to be repeated. The guard is the length of the input string. Basically, this for read each character in the input string.

THIRD TRICKY PART

0x0804896c      68f1b20b08     push str.theresanotherstep
0x08048971      8d45e2         lea eax, [INPUTSTR]
0x08048974      50             push eax
0x08048975      e806f9ffff     call fcn.08048280           ;[2]
0x0804897a      83c410         add esp, 0x10
0x0804897d      8945d4         mov dword [local_2ch], eax
0x08048980      837dd400       cmp dword [local_2ch], 0
0x08048984      7532           jne 0x80489b8

Wait wait wait wait. There is a comparison between 0 and the result of that function. Which arguments does it take? The input string and… a constant string. Remember that Journey manipulated INPUTSTR with reminders, divisions, subtractions and so on. If the result is zero, then it prints a greetings (the flag is flag{<INPUTSTR>}). The binary isn’t stripped, so… which function is that? It’s a normal strcmp, dynamically linked using the .plt.got table:

DATA XREF from 0x08048280 (fcn.08048280)
0x080ea038      .dword 0x0805b740 ; sym.strcmp  

So, if the manipulated string is equal to theresanotherstep the job is done.

All the ingredients have been introduced. Let’s hack this challenge!

The Intuition

If you didn’t fell asleep until now than you’re only few steps away to the solution. Let me recap what does Journey do:

  • Takes an input string -> INPUTSTR
  • for each char in INPUTSTR:
    • it calculates INPUTSTR[i] = INPUTSTR[i] - BIGNUM & 10
    • BIGNUM=BIGNUM/10
  • check if the manipulated string is equal to a const string.

What does it mean to divide and take the mod of a long int number?

It’s simple: extract the last digit of the number. So, the algorithm subtracts the last digit of BIGNUM from INPUTSTR. Given the const string, here I present the algorithm I used to reverse the process:

target = 'theresanotherstep'
maxn = '14231234143212433'
result = []
for i in range(len(target)):
    sub = maxn[len(target) - i -1]
    result.append(chr(ord(target[i]) + int(sub)))
print(''.join(result))

Let’s run it, to obtain the correct INPUTSTR: wkitfudrpxkgsvviq.

The flag is flag{wkitfudrpxkgsvviq}.