Translation

This post is also available in Simplified Chinese.

The endless exams finally ended, and after half a year I returned to competing with my AAA teammates—and to staying up all night. We solved five of the six reverse-engineering challenges. The remaining one, RL_Env, appeared to involve machine learning; I did not even understand what it was asking us to do.

stream

This was a Rust challenge, fortunately with symbols. After opening it in IDA, the first argument to std::rt::lang_start_internal identifies the Rust main function.

 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

do
{
    v5 = v1;
    v6 = v2 % v1;
    *((_BYTE *)&v13 + (v4 & 0x1F)) = *(_BYTE *)(v3 + v6);
    *(_OWORD *)&v9[16] = v14;
    *(_OWORD *)v9 = v13;
    rand_chacha::guts::init_chacha::ha09fa0e953c784d5(v19, v9, "", 8LL);
    *(_OWORD *)&v9[40] = v20;
    *(_OWORD *)&v9[24] = v19[1];
    *(_OWORD *)&v9[8] = v19[0];
    v15 = *(_OWORD *)v9;
    v16 = *(_OWORD *)&v9[16];
    v17 = *(_OWORD *)&v9[32];
    v18 = *((_QWORD *)&v20 + 1);
    v21 = 64LL;
    v22[15] = 0LL;
    v22[14] = 0LL;
    v22[13] = 0LL;
    v22[12] = 0LL;
    v22[11] = 0LL;
    v22[10] = 0LL;
    v22[9] = 0LL;
    v22[8] = 0LL;
    v22[7] = 0LL;
    v22[6] = 0LL;
    v22[5] = 0LL;
    v22[4] = 0LL;
    v22[3] = 0LL;
    v22[2] = 0LL;
    v22[1] = 0LL;
    v22[0] = 0LL;
    v24 = *((_QWORD *)&v20 + 1);
    v23[2] = *(_OWORD *)&v9[32];
    v23[1] = *(_OWORD *)&v9[16];
    v23[0] = *(_OWORD *)v9;
    rand_chacha::guts::refill_wide::h2ceeff1c2be61c9f((char *)v23 + 8, 10LL, v22);
    v21 = 1LL;
    *(_BYTE *)(v3 + v6) ^= LOBYTE(v22[0]);
    ++v4;
    v2 += 7LL;
    v1 = v5;
}
while (v5 != v4);

After the file is read, the main encryption occurs in this loop. A quick Rust test showed that rand_chacha::guts::{init_chacha, refill_wide} are not public, so the compiler must have inlined them. The guts.rs source shows that refill_wide takes the round count as its second argument; the ten-round variant corresponds to ChaCha20Rng. IDA debugging shows that generated bytes fill the buffer at v22, while *(_BYTE *)(v3 + v6) ^= LOBYTE(v22[0]); XORs only the first generated byte into the plaintext. The inlined init_chacha comes from ChaCha20Rng::from_seed, using the 32 bytes beginning at v9 as its key. *((_BYTE *)&v13 + (v4 & 0x1F)) = *(_BYTE *)(v3 + v6); inserts one plaintext byte into the key on each iteration, then XORs the resulting PRNG byte with that same byte. Each round therefore has only 256 possibilities and can be brute-forced. Plaintext bytes are selected in the order 4, 11, 18, and so on. Initially the key is all zeroes; insert and brute-force the first byte, then continue successively. Restricting candidates to ASCII resolves later ambiguities.

Since I did not know Rust and could not find a suitable equivalent implementation, I wrapped the random-number generator in Rust and wrote the main solver in Python.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

use std::env;
use rand_chacha::rand_core::{RngCore,SeedableRng};
use rand_chacha::ChaCha20Rng;

fn main() {
    let mut key:[u8;32]=[0;32];
    let args: Vec<String> = env::args().collect();
    let arg1=&args[1];
    for i in 0..32 {
        let x = u8::from_str_radix(&arg1[i*2..i*2+2], 16).unwrap();
        key[i]=x;
    }
    let mut result=[0u8;256];
    let mut rng=ChaCha20Rng::from_seed(key);
    rng.fill_bytes(&mut result);
    println!("{}",result[0]);
}

 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

import copy
import os

TARGET = [154, 122, 66, 146, 60, 227, 27, 164, 184, 114, 150, 47, 1, 152, 94, 41, 34, 245, 154, 20, 13, 76,
          24, 42, 56, 65, 212, 243, 169, 232, 96, 238, 218, 3, 220, 28, 161, 134, 18, 254, 24, 66, 137, 128, 145, 220]

def do_rust(key):
    s = ''.join(map(lambda x: '{:02x}'.format(x), key))
    p = os.popen('./target/debug/st {}'.format(s), 'r')
    return int(p.readline())

def solve(s, index, pos, key):
    if(index == 46):
        print(''.join(map(chr, s)))
        return
    for x in range(256):
        newkey = copy.copy(key)
        newkey[index % 32] = x
        r = do_rust(newkey)
        if(x ^ r == TARGET[pos % 46]):
            print(index)
            news = copy.copy(s)
            news[pos % 46] = x
            solve(news, index+1, pos+7, newkey)

solve([0]*46, 0, 4, [0]*32)

flag: *ctf{EbXZCOD56vEHNSofFvRHG7XtgFJXcUXUGnaaaaaa}

wherekey

I installed a libc 2.31 signature and changed the opaque jnz in main to jmp, allowing IDA to disassemble it. The program even calls listen and send to transmit data to itself, purely to increase the reversing workload.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

v2[dword_4C8570 / 64] |= 1LL << (dword_4C8570 % 64);
v2[dword_4C8520 / 64] |= 1LL << (dword_4C8520 % 64);
sub_44E080(1024LL, v2, 0LL, 0LL, 0LL);
if ((v2[dword_4C8520 / 64] & (1LL << (dword_4C8520 % 64))) != 0)
    sub_40223C();
if ((v2[dword_4C8570 / 64] & (1LL << (dword_4C8570 % 64))) != 0)
{
    v0 = ((__int64 (__fastcall *)(void *))((char *)&sub_401D44 + 1))(&unk_4C5120);
    sub_411D40(v0);
    sub_402072();
    v1 = ((__int64 (__fastcall *)(void *))((char *)&sub_401D44 + 1))(&unk_4C5130);
    sub_411D40(v1);
}

The OR operations above are the expanded FD_SET(fd, set) macro, and the AND operations below are FD_ISSET; both accompany select. Data received from the TTY is passed to sub_402072(), revealing five packets of five bytes each. sub_40223C() handles socket packets and forwards them to sub_4022DE(__int64 a1). Each five-byte group is multiplied by bytes extracted from 'flag{are_you_sure_friend}', forming five linear systems whose coefficient matrix is the constant string. After removing the opaque branches, the comparison target is unk_4C5150. I reused an old Gaussian-elimination implementation to invert the matrix and multiplied it by each of the five vectors to recover the plaintext.

 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

FL = 'flag{are_you_sure_friend}'

EP = [[ord(FL[5*i+j]) for i in range(5)]for j in range(5)]

INV = [0 for i in range(257)]

for i in range(257):
    for j in range(257):
        if (i*j) % 257 == 1:
            INV[i] = j
            break

EXT = [EP[i]+[1 if i == j else 0 for j in range(5)]for i in range(5)]

def show(martix):
    for i in range(5):
        print(martix[i])

def add(martix, k, line1, line2):
    for i in range(10):
        martix[line2][i] = (k*martix[line1][i]+martix[line2][i]) % 257

def mul(martix, x, line):
    for i in range(10):
        martix[line][i] = (martix[line][i]*x) % 257

def swap(martix, line1, line2):
    for i in range(20):
        martix[line1][i], martix[line2][i] = martix[line2][i], martix[line1][i]

def mulline(martix, x):
    y = [0]*5
    for i in range(5):
        for j in range(5):
            y[i] += martix[i][j]*x[j]
        y[i] = (y[i]) % 257
    return y

for i in range(5):
    if INV[EXT[i][i]] == 0:
        for k in range(i+1, 5):
            if INV[EXT[k][i]] != 0:
                swap(EXT, i, k)
                break
        else:
            raise ValueError
    mul(EXT, INV[EXT[i][i]], i)
    for j in range(5):
        if j == i:
            continue
        add(EXT, (-EXT[j][i]) % 257, i, j)

DP = [EXT[i][5:] for i in range(5)]

show(DP)

QUESTION = [0x38, 0x6D, 0x4B, 0x4B, 0xB9, 0x8A, 0xF9, 0x8A, 0xBB, 0x5C, 0x8A, 0x9A,
            0xBA, 0x6B, 0xD2, 0xC6, 0xBB, 0x05, 0x90, 0x56, 0x93, 0xE6, 0x12, 0xBD, 0x4F]

s = ''
for i in range(5):
    q = QUESTION[i*5:i*5+5]
    s += ''.join(map(chr, mulline(DP, q)))
print(s)

flag: *CTF{Ha23_f0n_9nd_G0od-1uck-OH}

ChineseGame

This binary is also statically linked, so I applied libc and libstdc++ signatures. It maintains a ten-element linked list whose nodes store numbers; only whether each number exceeds 100 matters. Writing values above 100 as + and those below as -, the initial state is +-++++++++ and the target is all -. The input is a binary string selecting between two operations, reminiscent of the Chinese Rings puzzle. Each operation takes a position from the table at dword_5D5140. If all following nodes have state +---…—or no following node exists—the selected position is set to + or -; otherwise nothing happens. A teammate noticed that the positions in dword_5D5140 already describe the correct solution sequence, so we only needed to determine whether each operation flips + to - or vice versa.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

a = [1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3,
     ...
     1, 2, 1, 3, 1, 2, 1]

s = ''
init = [1, 0]+[1]*8
for x in a:
    x = 10-x
    if(init[x] == 1):
        s += '0'
    else:
        s += '1'
    init[x] = 1-init[x]
print(init,s)

flag: *CTF{4ncient_G4me_Fr0m_4ncient_Ch1na!}

Favourite Architecure flag0

My teammates had already reversed part of this challenge before I joined. The flag is 0x59 bytes long. Its first 0x29 bytes use ChaCha20, recognizable from the key-expansion constant 'expand 32-byte k'; other D. J. Bernstein designs such as Salsa20, Ed25519, and Ed448 likewise contain distinctive strings. Extracting the fixed key and ciphertext is enough to decrypt this part. The remaining 0x30 bytes use TEA modified to 16 rounds. Wikipedia provides the following reference implementation:

 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

#include <stdint.h>

void encrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0, i; /* set up */
    uint32_t delta=0x9e3779b9; /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3]; /* cache key */
    for (i=0; i < 32; i++) { /* basic cycle start */
        sum += delta;
        v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
    } /* end cycle */
    v[0]=v0; v[1]=v1;
}

void decrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0xC6EF3720, i; /* set up */
    uint32_t delta=0x9e3779b9; /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3]; /* cache key */
    for (i=0; i<32; i++) { /* basic cycle start */
        v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
        v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        sum -= delta;
    } /* end cycle */
    v[0]=v0; v[1]=v1;
}

In decrypt, sum=0xC6EF3720 is the accumulated value of adding delta during every encryption round. With only 16 rounds, change it to sum=(0x9e3779b9*16)&0xffffffff=0xe3779b90 and decrypt normally.

flag: flag{have_you_tried_ghidra9.2_decompiler_if_you_have_hexriscv_plz_share_it_with_me_thx:P}

1rep

This program was produced by compiling Perl with perlcc. I compiled a small Perl script myself and found that all such programs call the following functions from main in order:

1
2
3
4
5
6

perl_init(v20);
perl_init1(v20);
dl_init(v20);
perl_init2(v20);
*((_DWORD *)&_0 - 28) = perl_run(v20);
destruct_main(v20);

My compiled sample showed that v20 is a PerlInterpreter*. Unlike Cython, perlcc does not translate the script into equivalent C; it prepares variables and bytecode, then hands everything to the Perl VM represented by this object. My first idea was to use a debugger’s appcall mechanism to extract bytecode from the VM. libperl exposes perl_dump_all(), so I broke at perl_run in gdb, changed RIP to perl_dump_all, and continued. It dumped a huge optree that was still unreadable. I then discovered Perl’s B::Deparse module and, following a Stack Overflow answer, used Perl_eval_pv to inject and execute code inside the PerlInterpreter.

1

use B::Deparse; B::Deparse->compile->()

That injection decompiled only the small initial check. After removing its wrapper, the flag contains 16 bytes validated by kwvIJu. I injected additional B::Deparse functionality to decompile specific functions:

1
2
3
4

use B::Deparse;
$deparse = B::Deparse->new("-sC");
$body = $deparse->coderef2text(\&func);
print "$body\n";

For unknown reasons, kwvIJu itself would not decompile. Other functions revealed the pattern: each checks the flag’s first hexadecimal character, switches among 16 branches, and calls another function to process the remainder. Near .rodata:00000000032E6CAF, IDA showed the string Correct. Disassembling the preceding afRNDz revealed that it prints Correct, so the task became finding which switch function calls it. The preceding xmecUK calls afRNDz; following callers upward recovered the final 14 flag bytes. I could not find the function calling the beginning of this chain, so I brute-forced the first two bytes and obtained the flag.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

from pwn import *

for x in range(16):
    for y in range(16):
        s = '*ctf{'+hex(x)[2:]+hex(y)[2:]+'4bb0982b39baa2}'
        assert(len(s) == 22)
        r = process('./bin')
        r.sendline(s)
        t = r.recvall()
        print(t)
        if 'Correct' in t:
            print(s)

flag: *ctf{7a4bb0982b39baa2}