[WRITE-UP] Information Security Competition – CTF

Intro

Hi everyone, I’m Bích Sơn Nhật, a K17 student in the Software Engineering faculty at the University of Information Technology - VNU-HCM. Recently I took part in the WANNAGAME FRESHMAN 2022 CTF and placed 29th out of 59 teams with Team BirthdayCake, whose only member was bichsonnhat (myself). The contest’s categories were quite diverse (Cryptography, Pwnable, Forensic/Misc, …), but I’m not a CTF specialist, so I only focused on the Programming category, and fortunately I solved 3 challenges within 2 days and got all 3 First Bloods. Today I’ll write up the Programming Challenges I solved, which are: Threesum Problem, The Shortest Path, and MITM.

Threesum Problem

Problem: Given an array of $n$ elements, count the number of triples $(i, j, k)$ satisfying $a_i + a_j + a_k = S$ .

At first I agonized over this one quite a bit, thinking the constraint would be huge, but after downloading the test cases and checking, the limit was only $n \leq 3000$ . My first idea was to binary search over the array to count the result, but after thinking it over I decided to just brute-force it to save myself the trouble 🙈

/// C++ Solution Code

int ans = 0;
for (int i = 1; i + 2 <= n; ++i){
    for (int j = i + 1; j + 1 <= n; ++j){
         for (int k = j + 1; k <= n; ++k){
             ans += (a[i] + a[j] + a[k] == S);
         }
     }
}

cout << ans << '\n';

The Shortest Path

Problem: Given an $n \times n$ matrix ( $n \leq 20$ ), where $a_{ij}$ is the cost of travelling from $i$ to $j$ . Find the minimum cost to visit all $n$ locations, passing through each location exactly once. Note that you’re allowed to start from any location you like.

Actually, the solution approach was already hinted at in the problem statement — this is a variant of TSP (Travelling Salesman Problem), and the optimal algorithm for it is Bitmask DP (bitmask dynamic programming). At first I didn’t read the latter part of the statement carefully, so I assumed we had to start from location $1$ , and spent 2 hours debugging before realizing I’d misread the problem 😞. To save time, I decided to just try every location by swapping location $1$ and location $i$ ( $2 \leq i \leq n$ ) with each other, which meant rebuilding the matrix after every swap.

/// C++ Solution Swap 1 & k

for (int k = 1; k <= 20; ++k){

    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n; ++j){
            dist[i][j] = save[i][j];
        }
    }

    vector <int> a, b;

    for (int i = 1; i <= n; ++i){
        a.push_back(dist[1][i]);
        b.push_back(dist[k][i]);
    }

    for (int i = 0; i < n; ++i){

        if (i + 1 == 1 || i + 1 == k) continue;
        dist[k][i + 1] = a[i];
        dist[1][i + 1] = b[i];
    }

    dist[1][1] = dist[k][k] = 0;

    for (int i = 1; i <= n; ++i){
        if (i == 1 || i == k) continue;
        for (int j = 1; j <= n; ++j){
            dist[i][j] = dist[j][i];
        }
    }

    for (int i = 0; i <= n; ++i){
        for (int j = 0; j <= (1 << (n + 1)); ++j){
            memo[i][j] = 0;
        }
    }

    for (int i = 1; i <= n; ++i){
        ans = min(ans, dp(i, (1 << (n + 1)) - 1));
    }

}

DP Bitmask Source Code:

long long dp(int i, int mask){
    if (mask == ((1 << i) | 3))
        return dist[1][i];

    if (memo[i][mask] != 0)
        return memo[i][mask];

    long long res = 1e18;

    for (int j = 1; j <= n; j++)
        if ((mask & (1 << j)))
            res = min(res, dp(j, mask & (~(1 << i))) + dist[j][i]);
    return memo[i][mask] = res;
}

MITM

At first I wasn’t planning to attempt this one, since I read the problem statement and had no idea what it was asking 😦. But after asking the problem author, I learned that I had to download the .py file and analyze the problem through the provided source code.

I checked what the file contained:

MAXNUM = 10000000000000000
from random import randint
from secret import flag
from hashlib import sha256
def xor(a,b):
    return bytes([i^j for i,j in zip(a,b)])

arr = [randint(0, MAXNUM) for i in range(40)]
choice = [randint(0,1) for i in range(40)]
SUM = sum([i*j for i , j in zip(arr,choice)])
key = ''.join(str(i) for i in choice)
key = sha256(key.encode()).digest()

encrypt_flag = xor(flag.encode(), key)


print("Array :", arr)
print("Sum :", SUM)
#print(choice)
print("Encrypted flag :", encrypt_flag)
#print(xor(encrypt_flag, key))
# Array : [2598518492671225, 8179816363958449, 7404314384623807, 5036318129031785, 7561847828708907, 8810344945409856, 6802835477023830, 660775698577317, 6377835037958658, 5165653195950165, 5542182643266967, 8877017134340898, 7019762314080100, 5473217947093964, 5756053470367204, 6532571242263709, 9570025266332532, 7253491621003594, 570694512472223, 3928852819486391, 9419484349130866, 7231862012400760, 8471268887369720, 2064798807663638, 2463399225362608, 2933953912021332, 7404602394427554, 6864510477948829, 5953144542900222, 4727398111173660, 8953568444836994, 6186179598281467, 3950282663156437, 5074454322540355, 929515103368296, 2217898009467944, 7917815503532629, 2666540036871100, 1285546515475019, 6688163578190488]
# Sum : 86547527340532708
# Encrypted flag : b'3\xeb$b@\x8e\xa0E\xc8H\x08\xc0H3\x054\x0b\xbc\xb95\x81\xeb\xc1R\x97z\xe0qN\xe90N'

After reading it I still didn’t understand a thing; after some research, I guessed the problem was essentially this:

Problem: Given a sequence of $n$ integers ( $n \leq 40$ ) and an integer $Sum$ , find a way to choose elements from the array so that the sum of the chosen elements equals $Sum$ . Output a $Choice$ array with values $[0, 1]$ .

After reading this problem, the idea of subset enumeration / Meet in the middle immediately came to mind, and I got straight to coding.

Source code for splitting the set:

void Pre_Compute(long long a[], li arr[], int n, int id){
    for (int i = 0; i < (1 << n); ++i){
        long long sum = 0;
        for (int j = 0; j < n; ++j){
            if (i & (1 << j)) {
                sum += a[j + id];
                arr[i].second.push_back(j + id);
            }
        }
        arr[i].first = sum;
    }
}

Source code for finding the $Choice$ array — since the problem requires the $Choice$ array to be in $[0, 1]$ form, I’ll output the answer where $0$ means not chosen and $1$ means element $i$ is chosen.

Pre_Compute(a, x, n / 2, 0);
Pre_Compute(a, y, n - n / 2, n / 2);
int nx = 1 << (n / 2);
int ny = 1 << (n - n / 2);

sort(y, y + ny);

int pos_x = -1, pos_y = -1;

for (int i = 0; i < nx; ++i){
    long long cur = S - x[i].first;

    int l = 0, r = ny - 1;

    if (pos_y != -1) break;

    while (l <= r){
        int mid = (l + r) >> 1;

        long long cal = y[mid].first;

        if (cal == cur){
            pos_x = i; pos_y = mid;
            break;
        }

        if (cal < cur){
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
}

vector <bool> choice(n);

for (auto &p : x[pos_x].second){
    choice[p] = true;
}

for (auto &p : y[pos_y].second){
    choice[p] = true;
}

for (int i = 0; i < n; ++i){
    cout << choice[i];
}

After running it on the provided test, I got the following answer sequence:

1010000110011101011100001001100110110010

Finally, to get the Flag, all I had to do was XOR the keys I just found with encrypt_flag:

from hashlib import sha256
def xor(a,b):
    return bytes([i^j for i,j in zip(a,b)])

keys = '1010000110011101011100001001100110110010'
keys = sha256(key.encode()).digest()

encrypt_flag = b'3\xeb$b@\x8e\xa0E\xc8H\x08\xc0H3\x054\x0b\xbc\xb95\x81\xeb\xc1R\x97z\xe0qN\xe90N'

print(xor(key, encrypt_flag))

And we get the Flag as shown in the image:

W1{Za Warudo ,toki wo tomare!!!}

Through this competition I drew many personal lessons and gained a lot of experience for upcoming contests.

Thanks to the organizing committee of the Information Security Lab - UIT InSecLab for creating this contest, giving K17 freshmen the chance to experience it at the University of Information Technology - VNU-HCM.

Thanks everyone for reading.

[WRITE-UP] Information Security Competition – CTF – "WANNAGAME FRESHMAN 2022"

Intro

Threesum Problem

The Shortest Path

MITM