RGBCTF 2020 Writeups

ctf web algo

13 Jul 2020

13 minute read

These are the writeups for the challenges I enjoyed solving during RGBCTF 2020, as a part of the Pwnzorz team. We ended 24th, because unfortunately only another member and I had time to participate this time.

Laser

Now I really enjoyed the laser challenges, where you had to implement a trivial algorithm in a difficult language made by the ctf organizers.

Laser is a 2-D language designed to be relatively simple to read code in, even if you have never seen the language before.

Like many 2-D langauges, Laser has an instruction pointer that executes the one character instructions it encounters. The instruction pointer starts at the top left and initially points right. The pointer can wrap around the program and termination only occurs on error or the termination character #. The memory structure is a list of stacks. There are only two types in Laser: String and Number. Numbers are java Longs.

Laser will push any one digit integer it encounters onto the current stack. To input a multi-digit integer, surround the integer with single quotes (''). To input a string, surround the string with double quotes (""). Note that the instruction pointer will still parse mirrors (next section) as normal when reading strings. To force the interpreter to ignore mirrors, use raw mode and surround your string with backticks (````)

Laser 1

rgbCTF{l4s3rs_4r3_c00l_r1ght}

laser-1

So we simply had to list the factors of the input number.

I chose to implement a simple algorithm:

We’ll go through the program, in Laser:

ir > ruru%  ⌜\
            pp
            u
            r
            su
v     ⌜=1r  <<
U  \(p< 
#

Laser 2

rgbCTF{1_f33l_y0ur_p41n_trust_m3}

laser-2

So we need to find a way to sort the stack. This post explains a nice way of doing this, by having a tempStack. Check it out for an explanation of the algorithm.

>c⌜psUs>c⌜prUrwDg⌜pwv
  p      >       >pv  
  >U#              U
                   w
^DD                <
       ^            <

How it works:

General Misc

[another witty algo challenge name]

This is pretty simple. You get a list of 5000 by 5000 grid of ones and zeros, and you have to print the number of islands in the grid.

An island is a collections of ones where each one is adjacent to another one in the island. For a cell to be adjacent to another cell, they must share an edge.

Submit the number wrapped in the flag format, like rgbCTF{123}

So pretty simple, all you needed to do was traverse the input of ones and zeros, and when you cross a one, you use a recursive function that marks the adjacent ones as already being part of an island. Whenever we meet a one that has not been marked this way, we know that it is part of a new island and we call the function on it.

Program:

#include <bits/stdc++.h>
using namespace std;
// struct for island positions
struct Position {
	bool val, marked = 0;
};
Position island[5000][5000];
// checks if coords are valid
bool isValid (int x, int y)
{
	return x < 5000 && x >= 0 && y < 5000 && y >= 0;
}
void checkIsland(int x, int y) {
    // adjacent indexes
	int dirs[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
	for(int i = 0; i < 4; i++)
	{
		int currX = x + dirs[i][0], currY = y + dirs[i][1];
        // mark all adjacent ones as already being part of an island
		if (isValid(currX, currY) && island[currY][currX].val && !island[currY][currX].marked)
		{
			island[currY][currX].marked = 1;
			checkIsland(currX, currY);
		}
	}
}
int main()
{
	for(int y = 0; y < 5000; y++) {
		for(int x = 0; x < 5000; x++) {
			char val;
			cin >> val;
            // get boolean input
			if (val == '0') island[y][x].val = 0;
			else island[y][x].val = 1;
		}
	}
	int nbIslands = 0;
	for(int y = 0; y < 5000; y++) {
		for(int x = 0; x < 5000; x++)
		{
            // increment island counter whenever you meet an unmarked one
			if (island[y][x].val && !island[y][x].marked)
				{
					nbIslands++;
					checkIsland(x, y);
				}
		}
	}
	cout << nbIslands;
}

rgbctf{119609}

[insert creative algo chall name]

https://pastebin.com/pKNVLkTs

So this challenge is basically asking you to generate the partitions of a set and to sum the subsets of each result if the partition is of length x. We can add this list of sums to a set, that way we make sure that our valid solutions are unique. And the length of that set will be the result.

x = 4
n = 12
r = []

# generate initial list
for i in range(n):
    r.append(pow(2, i))

# function that generates all valid partitions
def partition(collection):
    if len(collection) == 1:
        yield [ collection ]
        return

    first = collection[0]
    for smaller in partition(collection[1:]):
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[ first ] + subset]  + smaller[n+1:]
        yield [ [ first ] ] + smaller
        
nbSols = 0
sols = set()
for n, p in enumerate(partition(r), 1):
    # check that the partition is valid and matches the constraint that its len is == x
    if len(p) == x:
        sums = [sum(l) for l in p]
        # get the sum of each subset and convert it to a frozenset so we can add it as a unique solution
        sols.add(frozenset(sums))
print(len(sols))

rgbctf{611501}

Web

I will only be providing a solve for the Countdown challenge, because I enjoyed solving it.

countdown

By looking at the source, we can notice that the server sets a signed session cookie that sets the time when the flag will be revealed:

	<script type="text/javascript">
			window.addEventListener('load', function() {
			    var cookie = Cookies.get('session');
			    var data = cookie.split('.')[0].replace(/_/g, '/').replace(/-/g, '+');
			    var data = JSON.parse(atob(data));
			    var end = moment.utc(data['end']);
			    setInterval(function() {
			    	var dur = moment.duration(end.diff(moment.utc()));
			    	var disp = dur.get("days") + "d " + dur.get("hours") + "h " + dur.get("minutes") + "m " + dur.get("seconds") + "s";
			    	document.getElementById("countdown").innerHTML = disp; 
			    }, 1000);
			});
		</script>

What we want to do is to create a cookie that, when read by the server, will tell it that the time has passed and it can finally reveal the flag. To do this, we need to figure out how the cookie is signed and reverse-engineer its signature so the server will treat it as valid.

A request header tells us that the server is running:

Server: Werkzeug/1.0.1 Python/3.6.9

Flask uses that server software, so we can presume the session system is Flask’s.

Flask signs its tokens with a APPLICATION_KEY that is set by the developer often encrypted with the HMAC algorithm. The homepage directly tells us that Time is key., a hint that the secret key was actually simply Time.

So I ran my own local flask server with the same key and set a session cookie end (the same one used by the website) whose value was a timestamp from a past date.

Server code:

from flask import Flask, session

app = Flask(__name__)
app.config['SECRET_KEY'] = 'Time'


@app.route('/')
def index():
    session['end'] = "2020-07-13 16:33:59+0000" 
    return ""


if __name__ == '__main__':
    app.run()

All I had to do was copy the cookie, replace the session cookie of the actual website with the one I had gotten, and the server would read this correctly signed session cookie, notice that the end event had already passed, and it would give me the flag (I only used pico for a quick edit, I actually use nvim or vscode):

demo

Thanks to the organisers, it was really fun!