Apollon Development

Google CTF ⁠— Enter Space-Time Coordinates

As this is my first article regarding CTF on this blog, let's have a short foreword on what CTF is

"Capture The Flag" (CTF) competitions (in the cybersecurity sense) are not related to running outdoors or playing first-person shooters. Instead, they consist of a set of computer security puzzles (or challenges) involving reverse-engineering, memory corruption, cryptography, web technologies, and more. When players solve them they get a "flag," a secret string which can be exchanged for points. The more points a team earns, the higher up it moves in rank.

(source: https://buildyourfuture.withgoogle.com/events/ctf/)

Challenge #1 Enter Space-Time Coordinates

The challenge gives me a file to download plus an input box to enter the flag. I can instantly see that it's a ZIP archive that contains two files log.txt and rand2

~/DEV/googleCTF/beginner_01 file 00c2a73eec8abb4afb9c3ef3a161b64b451446910535bfc0cc81c2b04aa132ed 00c2a73eec8abb4afb9c3ef3a161b64b451446910535bfc0cc81c2b04aa132ed: Zip archive data, at least v2.0 to extract   ~/DEV/googleCTF/beginner_01 7z x 00c2a73eec8abb4afb9c3ef3a161b64b451446910535bfc0cc81c2b04aa132ed   7-Zip [64] 16.02 : Copyright (c) 1999-2016 Igor Pavlov : 2016-05-21 Extracting archive: 00c2a73eec8abb4afb9c3ef3a161b64b451446910535bfc0cc81c2b04aa132ed ... Files: 2 ...   ~/DEV/googleCTF/beginner_01 l total 28K drwxr-xr-x 5 retard staff 160 Jun 23 12:55 . drwxr-xr-x 3 retard staff 96 Jun 23 12:52 .. -rw-r--r-- 1 retard staff 9.1K Jun 22 12:36 00c2a73eec8abb4afb9c3ef3a161b64b451446910535bfc0cc81c2b04aa132ed -rw-r--r-- 1 retard staff 247 Jun 22 12:36 log.txt -rw-r--r-- 1 retard staff 8.6K Jun 22 12:36 rand2

File analysis

Quick look at the files shows that log.txt is just a plain text file that contains sample output from rand2. The latter is an x86-64 ELF  which I won't be able to run on my OS thus I'll need help of a VM.

~/DEV/googleCTF/beginner_01 file rand2 rand2: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=0208fc60863053462fb733436cef1ed23cb6c78f, not stripped

Being fast

I know that flags have CTF{<string>} format so I try to strip it out from the binary

~/DEV/googleCTF/beginner_01 strings rand2 | grep CTF Arrived at the flag. Congrats, your flag is: CTF{welcome_to_googlectf}

which returns the correct flag.

This isn't over — the exciting part

This article extends its content by analysing the executable and attempting to retrieve the flag using the "legit" way.

Running the binary

[10:49:01][mike@ringo.do][~]$ ./rand2 Travel coordinator 0: AC+79 3888 - 216962008568460, 147040004211149 1: Pliamas Sos - 67729623095916, 263977973375261 2: Ophiuchus - 223228825802917, 3615573480879 3: Pax Memor -ne4456 Hi Pro - 138298806623793, 23337201455323 4: Camion Gyrin - 211234283428212, 183565730161491 5: CTF - <REDACTED>   Enter your destination's x coordinate: >>> 1 Enter your destination's y coordinate: >>> 2 Arrived somewhere, but not where the flag is. Sorry, try again.

The program expects me to input two coordinates and then prints failure message followed by termination.

By running the program again I can see that the coordinates for destinations labeled 0-4 have changed. And so they do every time I run it, thus I assume that correct x/y coordinates, that I'm supposed to input, are also different each time I run the application.

Looking inside the binary

The application is fairly small. Quick look at the functions list shows that there are basically two user defined functions — main and next_destination

~/DEV/googleCTF/beginner_01 r2 -Aq -c "afl" rand2 0x00000710 1 42 entry0 0x00000740 4 50 -> 40 sym.deregister_tm_clones 0x00000780 4 66 -> 57 sym.register_tm_clones 0x000007d0 5 58 -> 51 entry.fini0 0x00000700 1 6 sym..plt.got 0x00000810 1 10 entry.init0 0x00000680 3 23 sym._init 0x00000a60 1 1 sym.__libc_csu_fini 0x00000a64 1 9 sym._fini 0x00000a00 4 93 sym.__libc_csu_init 0x00000872 10 385 main 0x0000081a 1 88 sym.next_destination 0x000006b0 1 6 sym.imp.puts 0x000006c0 1 6 sym.imp.printf 0x00000000 2 25 loc.imp._ITM_deregisterTMCloneTable 0x000006d0 1 6 sym.imp.strcmp 0x000006e0 1 6 sym.imp.time 0x000006f0 1 6 sym.imp.__isoc99_scanf 0x000001a8 1 35 fcn.000001a8 0x0000021a 1 30 fcn.0000021a

Next I'll look for interesting strings. I can see that strings at lines 16 and 17 are fairly close to each other.

~/DEV/googleCTF/beginner_01 r2 -Aq -c "iz" rand2 [Strings] Num Paddr Vaddr Len Size Section Type String 000 0x00000a78 0x00000a78 10 11 (.rodata) ascii AC+79 3888 001 0x00000a83 0x00000a83 11 12 (.rodata) ascii Pliamas Sos 002 0x00000a8f 0x00000a8f 9 10 (.rodata) ascii Ophiuchus 003 0x00000a99 0x00000a99 24 25 (.rodata) ascii Pax Memor -ne4456 Hi Pro 004 0x00000ab2 0x00000ab2 12 13 (.rodata) ascii Camion Gyrin 005 0x00000ac3 0x00000ac3 18 19 (.rodata) ascii Travel coordinator 006 0x00000ad6 0x00000ad6 10 11 (.rodata) ascii %zu: %s - 007 0x00000ae1 0x00000ae1 10 11 (.rodata) ascii <REDACTED> 008 0x00000aec 0x00000aec 9 10 (.rodata) ascii %zu, %zu\n 009 0x00000af8 0x00000af8 44 45 (.rodata) ascii \nEnter your destination's x coordinate:\n>>> 010 0x00000b30 0x00000b30 43 44 (.rodata) ascii Enter your destination's y coordinate:\n>>> 011 0x00000b60 0x00000b60 70 71 (.rodata) ascii Arrived at the flag. Congrats, your flag is: CTF{welcome_to_googlectf} 012 0x00000ba8 0x00000ba8 63 64 (.rodata) ascii Arrived somewhere, but not where the flag is. Sorry, try again.

I discover they both reside in main function which is too large to be pasted here so I'll just show the important part.

~/DEV/googleCTF/beginner_01 r2 -Aq -c "axt 0x00000b60" rand2 main 0x9cf [DATA] lea rdi, str.Arrived_at_the_flag._Congrats__your_flag_is:_CTF_welcome_to_googlectf ~/DEV/googleCTF/beginner_01 r2 -Aq -c "[email protected]" rand2 / (fcn) main 385 | int main (int argc, char **argv, char **envp); [.. cut ..] | 0x0000098b 488d45d8 lea rax, [var_28h] | 0x0000098f 4889c6 mov rsi, rax | 0x00000992 488d3d8c0100. lea rdi, [0x00000b25] ; "%zu" ; const char *format | 0x00000999 b800000000 mov eax, 0 | 0x0000099e e84dfdffff call sym.imp.__isoc99_scanf ; int scanf(const char *format) | 0x000009a3 b800000000 mov eax, 0 | 0x000009a8 e86dfeffff call sym.next_destination | 0x000009ad 4889c2 mov rdx, rax | 0x000009b0 488b45e0 mov rax, qword [var_20h] | 0x000009b4 4839c2 cmp rdx, rax | ,=< 0x000009b7 7522 jne 0x9db | | 0x000009b9 b800000000 mov eax, 0 | | 0x000009be e857feffff call sym.next_destination | | 0x000009c3 4889c2 mov rdx, rax | | 0x000009c6 488b45d8 mov rax, qword [var_28h] | | 0x000009ca 4839c2 cmp rdx, rax | ,==< 0x000009cd 750c jne 0x9db | || 0x000009cf 488d3d8a0100. lea rdi, str.Arrived_at_the_flag._Congrats__your_flag_is:_CTF_welcome_to_googlectf ; 0xb60 ; "Arrived at the flag. Congrats, your flag is: CTF{welcome_to_googlectf}" ; const char *s | || 0x000009d6 e8d5fcffff call sym.imp.puts ; int puts(const char *s) | || ; CODE XREFS from main (0x9b7, 0x9cd) | ``-> 0x000009db 488d3dc60100. lea rdi, str.Arrived_somewhere__but_not_where_the_flag_is._Sorry__try_again. ; 0xba8 ; "Arrived somewhere, but not where the flag is. Sorry, try again." ; const char *s | 0x000009e2 e8c9fcffff call sym.imp.puts ; int puts(const char *s) | 0x000009e7 b800000000 mov eax, 0 | 0x000009ec 4883c438 add rsp, 0x38 ; '8' | 0x000009f0 5b pop rbx | 0x000009f1 5d pop rbp \ 0x000009f2 c3 ret

I see that once second input is scanned in line 16 and stored in [var_28], it begins to check if the value scanned earlier [var_20] matches output from next_destination.

It's worth to note here that in case of success by reaching line 30, the code will not jump anywhere thus it'll continue the normal flow and print the error message too at line 33. Line 38 exits main function.

Next destination

The whole logic of getting the right number resides in next_destination and looks like so

~/DEV/googleCTF/beginner_01 r2 -Aq -c "[email protected]_destination" rand2 / (fcn) sym.next_destination 88 | sym.next_destination (); | ; CALL XREFS from main (0x918, 0x925, 0x9a8, 0x9be) | 0x0000081a 55 push rbp | 0x0000081b 4889e5 mov rbp, rsp | 0x0000081e 488b15730820. mov rdx, qword [obj.seed]; MOV rdx = [0x201098] = 0x0 rsi ; [0x201098:8]=0 | 0x00000825 48b86de6ecde. movabs rax, 0x5deece66d | 0x0000082f 480fafc2 imul rax, rdx | 0x00000833 488d480b lea rcx, [rax + 0xb] | 0x00000837 ba01000100 mov edx, 0x10001 | 0x0000083c 4889c8 mov rax, rcx | 0x0000083f 48f7e2 mul rdx | 0x00000842 4889c8 mov rax, rcx | 0x00000845 4829d0 sub rax, rdx | 0x00000848 48d1e8 shr rax, 1 | 0x0000084b 4801d0 add rax, rdx | 0x0000084e 48c1e82f shr rax, 0x2f ; '/' | 0x00000852 4889c2 mov rdx, rax | 0x00000855 48c1e230 shl rdx, 0x30 | 0x00000859 4829c2 sub rdx, rax | 0x0000085c 4889c8 mov rax, rcx | 0x0000085f 4829d0 sub rax, rdx | 0x00000862 4889052f0820. mov qword [obj.seed], rax ; [0x201098:8]=0 | 0x00000869 488b05280820. mov rax, qword [obj.seed]; MOV rax = [0x201098] = 0x0 rsi ; [0x201098:8]=0 | 0x00000870 5d pop rbp \ 0x00000871 c3 ret

This function doesn't take any arguments but it relies on global variable seed which is assigned at the end of this function but also right after the program starts, right here

~/DEV/googleCTF/beginner_01r.Arrived_at_the_flag._Congrats__your_flag_is:_CTF_welcome_to_googlectf r2 -Aq -c "[email protected]" rand2 / (fcn) main 385 | int main (int argc, char **argv, char **envp); | ; DATA XREF from entry0 (0x72d) | 0x00000882 bf00000000 mov edi, 0 ; time_t *timer | 0x00000887 e854feffff call sym.imp.time ; time_t time(time_t *timer) | 0x0000088c 488905050820. mov qword [obj.seed], rax ; [0x201098:8]=0

So the initial seed value is current time in seconds. This explains why the output for the 0-4 coordinates was changing every time the application ran.

Getting it straight

Now that I know how the numbers are generated, let's get back to the program output presented above. Looking at the code (which I won't paste here) I see that the values are posted in Little Endian, so taking first 4 numbers from the output...

0: AC+79 3888 - 216962008568460, 147040004211149
1: Pliamas Sos - 67729623095916, 263977973375261

... the order of them being generated is

current_timestamp -> 147040004211149 -> 216962008568460 -> 263977973375261 -> 67729623095916

Coding time

Alright so to get the next two values it should be enough to port next_destination function using last coordinate as the seed.

First lets get the fn contents in a bit more humane format.

~/DEV/googleCTF/beginner_01 r2 -Aq -s sym.next_destination -c "pdd" rand2 /* r2dec pseudo code output */ /* rand2 @ 0x81a */ #include <stdint.h>   int64_t next_destination (void) { rdx = *(obj.seed); rax = 0x5deece66d; rax *= rdx; rcx = rax + 0xb; edx = 0x10001; rax = rcx; rdx:rax = rax * rdx; rax = rcx; rax -= rdx; rax >>= 1; rax += rdx; rax >>= 0x2f; rdx = rax; rdx <<= 0x30; rdx -= rax; rax = rcx; rax -= rdx; *(obj.seed) = rax; rax = *(obj.seed); return rax; }

Using this I could almost 1:1 port it to python, however there were two things that were interesting in this pseudo.

First is line 12 which suggests that only lower 32 bits of RAX register are going to be replaced leaving the higher one in tact, but the fact is that they are upper 32 bits are going to be zeroed out. I don't know if that's just what Intel CPUs are doing but I couldn't find consistent information about that (not that I looked for it for too long ;) ).

The second one is line 14 which does int64*int64 multiplication but since CPU can't handle storing int128, it'll split it between RAX and RDX, where only RDX (higher 64 bits) are relevant as RAX is going to be overwritten in the next line anyway.

The rest is pretty straightforward and results in following implementation in Python

INP = [starting coords]   for _ in xrange(2): RCX = (0x5deece66d * INP + 0xb) & 0xFFFFFFFFFFFFFFFF RDX = ((RCX * 0x10001) & 0xFFFFFFFFFFFFFFFF0000000000000000) >> 64 & 0xFFFFFFFFFFFFFFFF REX = (RCX - RDX >> 0x1) + RDX >> 0x2f INP = RCX - (REX << 0x30) + REX   print INP

I'm ready to get to the solution so I run the app again

[12:19:40][mike@ringo.do][~]$ ./rand2 Travel coordinator 0: AC+79 3888 - 217775620312513, 2683675001140 1: Pliamas Sos - 168450969743591, 105097633830264 2: Ophiuchus - 72938930641326, 164579878170982 3: Pax Memor -ne4456 Hi Pro - 201763021740063, 122835696529048 4: Camion Gyrin - 136325874086749, 156797157427592 5: CTF - <REDACTED>   Enter your destination's x coordinate: >>>

Passing the last coords [136325874086749] to the script to get the following output

276442800644230
215910236710096
[Finished in 0.2s]
[12:19:40][mike@ringo.do][~]$ ./rand2 Travel coordinator 0: AC+79 3888 - 217775620312513, 2683675001140 1: Pliamas Sos - 168450969743591, 105097633830264 2: Ophiuchus - 72938930641326, 164579878170982 3: Pax Memor -ne4456 Hi Pro - 201763021740063, 122835696529048 4: Camion Gyrin - 136325874086749, 156797157427592 5: CTF - <REDACTED>   Enter your destination's x coordinate: >>> 276442800644230 Enter your destination's y coordinate: >>> 215910236710096 Arrived at the flag. Congrats, your flag is: CTF{welcome_to_googlectf} Arrived somewhere, but not where the flag is. Sorry, try again.

Got it! As mentioned before, I also see the unsuccessful message which probably wasn't author's intention.

But wait, there's more

To exhaust this CTF completely, let's try to reverse this function to get the exact time the application was ran.

The problem here is that this is one way function and there's high chance of getting different input than it was in reality.

To help me solve this challenge without having to reverse this function, I'll use Z3 Prover that will help me with that.

from z3 import *   s = Solver()   TARGET = BitVecVal(2683675001140, 128) RCX = BitVec('RCX', 128) RBX = BitVec('RBX', 128) RDX = BitVec('RDX', 128) REX = BitVec('REX', 128)   s.add( RCX == (0x5deece66d * RDX + 0xb) & 0xFFFFFFFFFFFFFFFF, RBX == ((RCX * 0x10001) & 0xFFFFFFFFFFFFFFFF0000000000000000) >> 64, REX == ((RCX - RBX >> 0x1) + RBX >> 0x2f), TARGET == ((RCX - (REX << 0x30)) + (REX)) )   if s.check() == sat: print s.model()

As you can see in the source code I already hardcoded first coordinate [2683675001140] which was the next one after the timestamp.

The script output is as follows

[RBX = 65030,
 REX = 65029,
 RCX = 18304038944192185135,
 RDX = 9651221813524801844]
[Finished in 0.3s]

As predicted the searched value RDX doesn't contain valid timestamp. It simply satisfies the equation. To help Z3 a little bit lets add some constraints. We know I ran the script somewhere between year 2017 and 2020 (hopefully :-)) so I can modify the script like so

from z3 import *   s = Solver()   TARGET = BitVecVal(2683675001140, 128) RCX = BitVec('RCX', 128) RBX = BitVec('RBX', 128) RDX = BitVec('RDX', 128) REX = BitVec('REX', 128)   s.add( RDX < 1600000000, RDX > 1500000000, RCX == (0x5deece66d * RDX + 0xb) & 0xFFFFFFFFFFFFFFFF, RBX == ((RCX * 0x10001) & 0xFFFFFFFFFFFFFFFF0000000000000000) >> 64, REX == ((RCX - RBX >> 0x1) + RBX >> 0x2f), TARGET == ((RCX - (REX << 0x30)) + (REX)) )   if s.check() == sat: print s.model()

This time I get much more close-to-reality output

[RBX = 8790,
 REX = 8790,
 RCX = 2474167728961658590,
 RDX = 1561285183]
[Finished in 8.4s]

[1561285183] would be 23/06/2019 12:19 in GMT+1 which also matches the hour in the terminal. Solved!