RGBCTF 2020

Competition on CTFTime: RGB CTF

Final position: #58/1047

This was the first CTF I ever participated in with a team. We almost made it into the top 50, which I consider to be a big success!

I did Misc, Pwn, Web and the special ZTC challenges (and honestly mostly just Misc, as I am still quite a noob). Here I present an overview of the problems that I solved.

Misc

I generally excel at Misc challenges, as I have a lot of algorithmic knowledge and random knowledge about quirks of different tools. However, the algorithmic challenges in this contest were rather uninspired, as were the names for the challenges. I really enjoyed the Laser challenges though.

Differences

We are given a .java file. I opened it in a text editor and some characters were denoted by question marks. So I made a copy and replaced the characters with ones that would make the code compile.

Now the obvious thing to do would be to take pairs of differing characters in the two files, and apply some function to them. It turned out that applying the difference function (as implied by the title) gives the flag.

I lost the original script that I used but it would have been equivalent to the following:

# Read two files as byte arrays
file1_b = bytearray(open(sys.argv[1], 'rb').read())
file2_b = bytearray(open(sys.argv[2], 'rb').read())

# Set the length to be the smaller one
size = len(file1_b)

for i in range(size):
    ans = abs(file1_b[i] - file2_b[i])
    if ans != 0:
        print(chr(ans), end='')

Picking Up The Pieces

This was just a straightforward implementation of the Dijkstra algorithm. Just find the shortest path and print the string formed by concatenating letters along the way: it will contain the flag. Here is the code (written in C++):

#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;
using namespace std;

const int N = 1e6+10;
// contains a vertex, a distance, and the string so far
struct tres{
    int v;
    ll d;
    string s;
    tres(){}
    tres(int a, ll b, string c){v=a;d=b;s=c;}
};

vector<tres> E[N];
ll Dist[N];

int main(){
    fastIO;
    int a, b;
    ll dist;
    string s;
    // read the vertices and construct neighbour lists
    for(auto &i: Dist) i = -1;
    while(cin>>a>>b>>dist>>s){
        E[a].pb(tres(b, dist, s));
        E[b].pb(tres(a, dist, s));
    }
    // create a min priority queue by distance so far and initialize it
    // with an empty state
    auto comp = []( tres a, tres b ) { return a.d > b.d; };
    priority_queue<tres, vector<tres>, decltype(comp)>Q(comp);
    Q.push(tres(1, 0, ""));
    ll one = 1;
    // the minimal distance so far; set to large number initially
    ll mini = one<<60;
    // in case there are multiple paths that take the same distance
    vector<tres>ans;
    // do dijkstra
    while(Q.size()){
        cerr<<Q.size()<<endl;
        tres f = Q.top();
        Q.pop();
        if(f.d > mini)break;
        if(f.v == 200000)mini = f.d, ans.pb(f);
        if(Dist[f.v] != -1)continue;
        Dist[f.v] = f.d;
        cerr<<f.v<<" "<<E[f.v].size()<<endl;
        for(auto i: E[f.v]){
            // push any new paths to the queue
            if(Dist[i.v] != -1)continue;
            Q.push(tres(i.v, i.d + f.d, f.s + i.s));
        }
    }
    // print any answers found
    for(auto i: ans){
        cout<<i.v<<" "<<i.d<<" "<<i.s<<endl;
    }
}

[another witty algo challenge name]

This was even easier than the Dijkstra challenge above, a simple DFS traversal marking visited nodes on the way will do. Here is the code:

#include <bits/stdc++.h>
using namespace std;

string S[5000];
bool Vis[5000][5000];

void dfs(int i, int j){
    Vis[i][j] = 1;
    if(i != 0 && S[i-1][j] == '1' && !Vis[i-1][j])dfs(i-1, j);
    if(j != 0 && S[i][j-1] == '1' && !Vis[i][j-1])dfs(i, j-1);
    if(i != 4999 && S[i+1][j] == '1' && !Vis[i+1][j])dfs(i+1, j);
    if(j != 4999 && S[i][j+1] == '1' && !Vis[i][j+1])dfs(i, j+1);
}

int main(){
    fastIO;
    for(int i=0; i<5000; i++)cin>>S[i];
    int ans = 0;
    for(int i = 0; i<5000; i++){
        for(int j=0; j<5000; j++){
            if(S[i][j] == '1' && !Vis[i][j]){
                // we found a new disconnected component
                ans += 1;
                // mark all nodes in this connected component
                dfs(i, j);
            }
        }
    }
    cout<<ans;
}

[insert creative algo chall name]

This problem required an understanding of a bit of maths but wasn’t tricky either. There are a few observations that we have to make:

  • Since the set of initial values contains different powers of $2$, any collection of these elements correspond to a unique sum

    • We can therefore think of each subset as equivalent to the sum of its elements

  • We can choose to order these subsets in some way and try to assign a number to subset $i$ only after we assign a number to subset $i-1$.

  • The order in which we assign the numbers does not matter, so we can also assign these in some prespecified order that we choose.

There are a few ways to exploit the observations above, but here is the one I used:

  • Define a function that takes the number of elements left to assign (nums), the number of subsets still left empty (empty), and calculates the number of assignments for this case.

  • Clearly the answer is $1$ if nums == empty, as no subset can be left empty.

  • Otherwise we recursively calculate the number of assignments if we assign the largest remaining number to each of the subsets.

And here is the code (it can be optimized a bit more, but even this takes less than a second):

#include <bits/stdc++.h>
using namespace std;

long long ans = 0;
void recurse(int nums, int empty){
    if(empty == nums){
        ans++;
        return;
    }
    // assign to non-empty subsets
    for(int i=0; i<4-empty; i++){
        recurse(nums-1, empty);
    }
    // assign to next empty subset
    if(empty != 0)recurse(nums-1, empty-1);
}

int main(){
    fastIO;
    recurse(12, 4);
    cout<<ans;
}

Laser 1 - Factoring

It is a bit difficult to comment the code for this language, but the algorithm I performed is the naive one that loops n times, and checks for divisibility.

I use $2$ stacks: the first one stores the initial number and the final answer:

<counter> <initial_number> <divisors found in increasing order>

The second stack is just the first one copied over to do computations on the counter and the initial number:

  • Check divisibility (RU%⌝)

    • If it is divisible, we replicate the current counter and rotate it to the back (rd), as it is part of the answer

  • Check if counter is less than initial number (RUl!⌝), and exit the program once it is

When the counter reaches the initial number, we pop the first $2$ elements and are left with the answer (pp#). Here is the code:

i1>RU%⌝P  >RUl!⌝P)\
      \Prd/    P   
  \               /
               p
               p
               #

Laser 2 - Sorting

This challenge was more complicated and required nested loops. I implemented a variation of selection sort, where I select the largest element from the list each time until there are none left. My stacks are organized as follows:

  • The bottom stack contains the initial list, as well as a counter of the inner loop.

  • The second stack contains the current largest element found so far, as well as performs computations to compare it to other list elements.

  • The third stack contains the answer (as computed so far).

Here is the code:

>c⌝us>( ⌝ suUwD dsU rurdg!⌝p >wDu      \
                          \pu/
        \ UsUdDDp  \
     \                                 /
\                  /
  U
  U
  #

  • c⌝ pushes the size of the remaining list to the bottom stack. If it is empty, move $2$ stacks up and halt (UU#)

  • us pushes an element from the list into the second stack as the smallest element found so far in the remaining list, ( decrements the counter for the inner loop

  • If the counter reaches $0$, we have gone over all remaining elements and chose the smallest one

    • UsUdDDp pushes this element to the end of the top stack, and pops the counter for the start of the next outer loop iteration

  • suUwD dsU rurdg! does several things:

    • rotates the remaining list

    • pushes the first element to the second stack

    • duplicates both elements on the second stack and compares them

    • pushes the larger of the $2$ elements to the bottom stack, leaving the smaller one on the second stack

    which is the main parts of the selection sort. Repeat this until we rotate through the whole list.

Ye Old PRNG

This particular challenge wasn’t very difficult. Looking in the Wikipedia page for PRNG algorithms we can see that the oldest one of them is the middle-square method, which turned out to be the one used in this challenge. We needed to do $10$ correct guesses of the next number generated, which can be pretty easily done by hand. I wrote a quick python script to calculate the next number, and performed the communication by hand.

Pwn

I only did one of the Pwn challenges, the one that didn’t require anything more than code inspection. This is a clear indication that I lack the knowledge in this area and should invest some time to learn the techniques.

Object Oriented Programming

We are given multiple Java files that are heavily obfuscated, and need to make sense of them to figure out the flag. The code is short, so we can quickly figure out the following:

  • We need to input a password that is $16$ characters long

  • The hash of this algorithm should equate the string javautil

  • The hashing function takes $4$ characters at a time and produces $2$ characters of output

  • The way the output is produced is as follows:

    • The first $2$ characters correspond to a class name

    • The second $2$ characters correspond to a function name in that class. $3$ times we replace these $2$ characters with the output of that function, and after the last iteration we are left with the hashed block value.

Basically for each of the hash blocks "ja", "va", "ut", "il" we want to find $2$ letter strings c, x, y, z, such that class c has functions x, y, z returning y, z, "ja" (or one of the other blocks) respectively. Such chains x -> y -> z -> "ja" can be easily found by inspection, starting by looking for "ja" in one of the classes. The password is then a combination of such c+x pairs, which is in human readable format and can be wrapped into a flag.

Web

I was only able to solve one of the challenges. The challenges seemed fun and I thought I was close to some of them, but I clearly still lack experience.

Tic Tac Toe

We are presented with a Tic Tac Toe board and are asked to beat the AI for the flag.

The way I solved this challenge is to set a breakpoint in the browser on a click event. Then I clicked on the board and examined the accessible variables. One of them seemed like the current state of the game board, so I changed the state to be winning for me, and that gave me the flag.

[ZTC]

This category was more misc than the Misc category. Most challenges required reading some form of QR code, and were somewhat enjoyable, as they gave me a reason to explore Krita and Blender, which I meant to do at some point anyways.

Ralphie!

This challenge was pretty obvious in the sense that there was a faint QR code in one part of the image. I used Krita to increase the contrast and was left with 3 different colours that made up the QR code. Blue was obviously to be kept, as it contained the main features of the QR code (the corners).

This challenge wasn’t too difficult, but took me a bit of time to get familiar with Krita. I basically did the following

  • turned the colours into different shades of black

  • used the color adjustment curves (Ctrl + m) to completely hide some of the colours, and make others black

  • Try to read the QR code

  • Repeat for the $4$ colour combinations containing blue

$2$ combinations returned nothing, one combination returned a fake flag, and the last one I tried was the one I actually needed.

peepdis

This was a 3d model file, which could be opened by Blender, and that’s what I chose as I was planning on learning some Blender anyways.

When opened, the model is clearly a 3d representation of a QR code, but there are a few issues:

  • The whole model is grey, with certain parts sticking out.

  • There was a fair amount of specular shading, making it impossible to simply take the picture of the QR code.

    • Also I know nothing about how to change the shading of an object in Blender

It took me some time to get used to Blender movement commands. The first thing I tried was the bisector tool: I though I would bisect along the plane of the QR code, leaving only the sticking out faces. This would have been a great idea, but after bisecting I realised that the outside and inside flip sides at some points in the model, and I can’t just choose one of the faces of the QR code. What a terribly designed model!

Then I realised that I can just select a bunch of faces and delete them. So I ended up deleting the unnecessary faces one layer at a time, which was surprisingly satisfying.

Once I got the faces removed, it took a bit more tweaking to increase the contrast between the QR code and the background, but I was eventually able to get the flag. And now I have some understanding of how Blender works!

Contents