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?
.--> 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
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.
:| 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.
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!
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:
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}.