HKCERT CTF 2023 Postmortem (I): Easier Crypto Challenges

This is yet another moment that Black Bauhinia co-organizes HKCERT CTF. This year, I am slightly more productive than the previous years and wrote 13 challenges for the CTF. There are three blog posts in this series, where I will respectively cover the author’s solutions to the easier crypto challenges, the harder crypto challenges and the remaining challenges.

The below is the list of challenges:

Step-by-step challenges are marked by 👣 in the “Difficulty” column. The numbers in the “Solves” column are the number of solves in the secondary, tertiary, open and international divisions respectively. For some challenges that are not released to that division, the solve count will be represented by -. Finally, there are 144, 102, 166 and 303 teams respectively in the four categories.

The Art of Embarrassment⌗

Challenge Summary⌗

I implemented the ideal cipher model. Would it be too wasteful if I am using that to encrypt the flag?

Attachment: ideal-cipher.zip

In this challenge, we are given a block cipher, $\mathcal{E}$, implemented with the ideal cipher model. The trimmed flag are encrypted with $\mathcal{E}$ using cipher block chaining (CBC) mode with 13337 different keys. We are given the ciphertext of all the encrypted, trimmed flag. The objective is to recover the flag.

Solution⌗

What is the ideal cipher model?⌗

When you receive a ciphertext that is encrypted by the ideal cipher model, it is impossible to know what the message is – it is equally likely that the ciphertext is encrypted from a particular message in the message space (the set of all messages).

Matthew Green¹ mentioned a way to encrypt messages with the ideal cipher model. We will maintain a table of three columns: $(m, c, k)$, which respectively represents the message, the ciphertext and the key. Suppose that we want to encrypt a message $m_0$ using the key $k_0$ and assume that there is a trusted party who will work on the steps below for us:

• If there is a row such that $m = m_0$ and $k = k_0$, extract $c$ from that row and that would be the ciphertext.
• Otherwise, generate a perfectly random $c_0$ until there are no rows with $c = c_0$ and $k = k_0$. Add $(m_0, c_0, k_0)$ to the table and return $c_0$ as the ciphertext.

For example, we assume that there are only 4 plaintexts in the world: $\texttt{0}, \texttt{1}, \texttt{2}, \texttt{3}$. The message will always encrypt into 🍎, 🍋, 🥝 and 🍇.

• Someone wants to encrypt $\texttt{0}$ using 🔑. The trusted party
  • generates a random ciphertext: 🥝,
  • appends $(m, c, k) = (\texttt{0}, 🥝, 🔑)$ to the table, and
  • returns 🥝 as the ciphertext.
• Someone wants to encrypt $\texttt{2}$ using 🔑. The trusted party
  • generates a random ciphertext: 🍎.
  • appends $(m, c, k) = (\texttt{2}, 🍎, 🔑)$ to the table, and
  • returns 🍎 as the ciphertext.
• Someone wants to encrypt $\texttt{0}$ using 🔑. The trusted party
  • finds that $(m, c, k) = (\texttt{0}, 🥝, 🔑)$ satisfies $m = \texttt{0}$ and $k = 🔑$, and
  • returns 🥝 as the ciphertext.
• Someone wants to encrypt $\texttt{1}$ using 🔑. The trusted party
  • generates a random ciphertext: 🍎,
  • finds that $(m, c, k) = (\texttt{2}, 🍎, 🔑)$ satisfies $c = 🍎$ and $k = 🔑$,
  • generates a random ciphertext: 🍋,
  • appends $(m, c, k) = (\texttt{1}, 🍋, 🔑)$ to the table, and
  • returns 🍋 as the ciphertext.
• Someone wants to encrypt $\texttt{2}$ using 🗝️. The trusted party
  • generates a random ciphertext: 🥝,
  • appends $(m, c, k) = (\texttt{2}, 🥝, $🗝️$)$ to the table, and
  • returns 🥝 as the ciphertext.

This is the final table after the above operations:

For a given key 🔑 in the toy example above, the ciphertexts of a cipher would be a permutation of 🍎, 🍋, 🥝 and 🍇. Since we have to exhaust the $4!$ possible settings in an ideal cipher, there will be at least $4!$ keys.

It is surreal to implement the ideal cipher model. If there are $n$ plaintexts, there will be $n!$ keys. Effectively we will need a $\log_2 n!$-bit key for ideal ciphers. If we want to implement an ideal 128-bit block cipher, the key size should be $4.3 \times 10^{40}$ bits long. That is much longer than the keys in AES, which is at most 256-bit long.

The block size in the ideal cipher for the challenge is only 16 bits long, thus the keys can be permutations of $\{\texttt{0000}_{16}, \texttt{0001}_{16}, …, \texttt{ffff}_{16}\}$.

The CBC mode of operation⌗

The block size of $\mathcal{E}$ is 2 bytes. To encrypt the message of arbitrary length, we will need a cipher mode of operation. This time we are using the CBC mode of operation, and this is how we encrypt a message of length $2n$ (given by $m_1m_2…m_{2n}$):

1. Chop the message into blocks of 2 bytes, i.e., it will be separated into $n$ blocks: $M_1 := m_1m_2$, $M_2 := m_3m_4$, …, $M_n := m_{2n-1}m_{2n}$.
2. Generate a 2-byte IV, given by $C_0$.
3. Compute $C_1 := \mathcal{E}(C_0 \oplus M_1)$, $C_2 := \mathcal{E}(C_1 \oplus M_2)$, …, $C_n := \mathcal{E}(C_{n-1} \oplus M_n)$.
4. Return $C_0, C_1, C_2, …, C_n$ as the ciphertext.

For instance, if we use a key such that $\mathcal{E}(\texttt{95c9}_{16}) = \texttt{0217}_{16}$ and $\mathcal{E}(\texttt{21f1}_{16}) = \texttt{1337}_{16}$, then one ciphertext of $\texttt{448223e6}_{16}$ could be $\texttt{d14b02171337}_{16}$, because

1. $C_0 = \texttt{d14b}_{16}$,
2. $C_1 = \mathcal{E}(C_0 \oplus M_1) = \mathcal{E}(\texttt{d14b}_{16} \oplus \texttt{4482}_{16}) = \mathcal{E}(\texttt{95c9}_{16}) = \texttt{0217}_{16}$, and
3. $C_2 = \mathcal{E}(C_1 \oplus M_2) =\mathcal{E}(\texttt{0217}_{16} \oplus \texttt{23e6}_{16}) = \mathcal{E}(\texttt{21f1}_{16}) = \texttt{1337}_{16}$.

A vulnerability⌗

If $C_i = C_j$ for some $i, j > 0$ with $i \neq j$, we have $\mathcal{E}(C_{i-1} \oplus M_i) = \mathcal{E}(C_{j-1} \oplus M_j)$. Since $\mathcal{E}$ is injective (i.e., no two plaintexts encrypt to the same ciphertext), we then have $C_{i-1} \oplus M_i = C_{j-1} \oplus M_j$. Rearranging the terms, we have

$${\color{red}M_i} \oplus {\color{red}M_j} = C_{i-1} \oplus C_{j-1}.$$

For instance, there are 13337 encrypted flags from the transcript. On line 153, we have a ciphertext that satisfies $C_2 = C_{18}$:

5504c2087dd3e1a714cdceb53f020c7ba2052342b660db52de2d583f89f033f71802aa5c7dd3...
        ****                                                            ****

From above, this yields $M_2 \oplus M_{18} = \texttt{c208}_{16} \oplus \texttt{aa5c}_{16} = \texttt{6854}_{16}$. These are a few more relations derived from the transcript:

1. $M_{18} \oplus M_{21} = \texttt{5b55}_{16}$ (line 159),
2. $M_{18} \oplus M_{27} = \texttt{0450}_{16}$ (line 615),
3. $M_{25} \oplus M_{27} = \texttt{5f04}_{16}$ (line 762),
4. $M_6 \oplus M_{18} = \texttt{063a}_{16}$ (line 887),
5. $M_7 \oplus M_{11} = \texttt{1a46}_{16}$ (line 1318)…

and so on. We have 67 relations like above to restrict $M_1, M_2, …, M_{27}$. Eventually, we can express $M_2, M_3, …, M_{27}$ in terms of $M_1$. We can exhaust $M_1$ and thus retrieve the flag, i.e., $(M_1, M_2, …, M_{27})$:

hkcert23{1t_15_57111_vu1n3ra6l3_wh3n_c1ph3r7ext_bl0ck5_col1id35}

Sign me a Flag (I)⌗

Challenge Summary⌗

No gib flag? No flag!

Note: This is a easier version of the Sign me a Flag (II) challenge, and there is a guide for this challenge here.

Attachment: sign-me-a-flag-i.zip

In this challenge, we are given a remote oracle and is allowed to perform the below operations:

1. sign [key_client] [message]: Signs an arbitrary message that does not contain the substring flag.
2. verify [signature]: Verifies the signature for the message gib flag pls.

Let $k_\mathcal{C}$, $k_\mathcal{S}$ and $m$ be the client’s key, the server’s key and the message respectively. The signature of $m$ is given by

$$\text{Sign}(k_\mathcal{C}, m) := \text{HMAC-SHA256}(k_\mathcal{C} \oplus k_\mathcal{S}, m).$$

Note that $k_\mathcal{S}$ will not be given to the player. The goal is to recover the signature of the message gib flag pls while fixing $k_\mathcal{C}$ to be 16 null bytes.

Solution⌗

The exclusive-or (XOR) operator⌗

In this challenge, the XOR operation of two operands, $a$ and $b$ (i.e., $a \oplus b$) is given below:

def xor(a, b):
    return bytes(u^v for u, v in zip(a, b))

Specifically, when the two strings are of different lengths, the output string has a length of the shorter input string. For example,

$$\begin{aligned} \texttt{000102}_{16} \oplus \texttt{12345678}_{16} &= \texttt{123554}_{16} \\ \texttt{00010203}_{16} \oplus \texttt{123456}_{16} &= \texttt{123554}_{16} \end{aligned}$$

Now assume that $k$ is a 16-byte, secret value, and assume that

$$k \oplus \texttt{00}_{16} = \texttt{40}_{16},$$

then we know the first byte of $k$ would be $\texttt{40}_{16}$.

Solving the challenge⌗

From the guide provided to the players during the CTF, we are able to fully recover the secret in 16 oracle calls, one byte at a time. This is how we recover the first byte of the secret:

1. Call $\text{Sign}(\texttt{00}, \text{hello world})$ and denote it by $\hat{s_1}$.
2. Compute $\text{HMAC-SHA256}(\texttt{00}, \text{hello world})$, $\text{HMAC-SHA256}(\texttt{01}, \text{hello world})$, $\text{HMAC-SHA256}(\texttt{02}, \text{hello world})$, ….
3. Eventually, there will be a $u_1$ such that $\text{HMAC-SHA256}(u_1, \text{hello world}) = \hat{s_1}$. In this case, the first byte of $k_\mathcal{S}$ would be $u_1$.

We can slightly modify the above heuristic to recover two bytes at a time. To recover the first two bytes of the secret:

1. Call $\text{Sign}(\texttt{0000}, \text{hello world})$ and denote it by $\hat{s_1}$.
2. Compute $\text{HMAC-SHA256}(\texttt{0000}, \text{hello world})$, $\text{HMAC-SHA256}(\texttt{0001}, \text{hello world})$, …, $\text{HMAC-SHA256}(\texttt{ffff}, \text{hello world})$.
3. Eventually, there will be a $u_1$ such that $\text{HMAC-SHA256}(u_1, \text{hello world}) = \hat{s_1}$. In this case, the first two bytes of $k_\mathcal{S}$ would be $u_1$.

With that, we can recover the server’s key in 8 oracle calls. We then can create a valid signature and retrieve the flag: hkcert23{l34k1n9_th3_k3y_b1t_6y_bi7_1s_fun}.

Sign me a Flag (II)⌗

Challenge Summary⌗

No gib flag? No flag!

Note: This is a harder version of the Sign me a Flag (I) challenge.

Attachment: sign-me-a-flag-ii.zip

This challenge is similar to Sign me a Flag (I), except that

1. the xor implementation comes from pwntools this time,
2. we have 65536 oracle calls, and
3. let $\text{id}$ be the number of sequence number of the oracle call. The signature becomes

$$\text{Sign}(k_\mathcal{C}, m) := \text{HMAC-SHA256}(k_\mathcal{C} \oplus k_\mathcal{S}, \text{id} \ ||\ m).$$

For example, the signing $\text{Sign}(k_\mathcal{C}, \texttt{test})$ and $\text{Sign}(k_\mathcal{C}, \texttt{foo})$ at the first and second calls (sequence numbers being 0 and 1) would be respectively $\text{HMAC-SHA256}(k, \texttt{0test})$ and the second call is $\text{HMAC-SHA256}(k, \texttt{1foo})$. Hereby $k = k_\mathcal{C} \oplus k_\mathcal{S}$.

The goal is unchanged. That is to recover the signature of the message gib flag pls while fixing $k_\mathcal{C}$ to be 16 null bytes.

Solution⌗

The new XOR operator⌗

The implementation of the xor method in pwntools is different: When the operands are two strings of different lengths, the shorter string will first be repeated until the lengths are equal. The resulting strings will be XOR-ed.

For example,

$$\begin{aligned} \texttt{000102}_{16} \oplus \texttt{12345678}_{16} &= \texttt{00010200}_{16} \oplus \texttt{12345678}_{16} = \texttt{12355478}_{16} \\ \texttt{00010203}_{16} \oplus \texttt{123456}_{16} &= \texttt{00010203}_{16} \oplus \texttt{12345612}_{16} = \texttt{12355411}_{16} \end{aligned}$$

With this change, we can guarantee that $k_\mathcal{C} \oplus k_\mathcal{S}$ is at least 16 bytes. We can no longer generate one byte keys by making $k_\mathcal{C}$ to be one-byte long.

The HMAC framework⌗

Firstly, if a HMAC key is shorter than 64 bytes, there will be a zero-padding. With the padding, the below HMAC functions have the same digest.

$$\begin{aligned} & \text{HMAC-SHA256}(\texttt{12}\ \texttt{34}, m) \\ & \quad= \text{HMAC-SHA256}(\texttt{12}\ \texttt{34}\ \texttt{00}, m) \\ & \quad= \text{HMAC-SHA256}(\texttt{12}\ \texttt{34}\ \texttt{00}\ \texttt{00}_{16}, m) \\ & \quad= \dots \\ & \quad= \text{HMAC-SHA256}(\texttt{12}\ \texttt{34}\ \underbrace{\texttt{00}\ \texttt{00} \ \dots \ \texttt{00}_{16}}_{\text{62 null bytes}}, m). \end{aligned}$$

Assuming that the $\text{id}$ is not prepended to the message. We can leak the first byte of $k_\mathcal{S}$ with 257 calls:

1. Call $\text{Sign}(\mathcal{O}, m)$ and denote it by $\hat{s}$, here $\mathcal{O}$ being 16 null bytes.
2. Call $\text{Sign}(\mathcal{O} \ || \ \texttt{00}_{16}, m)$, $\text{Sign}(\mathcal{O} \ || \ \texttt{01}_{16}, m)$, …, $\text{Sign}(\mathcal{O} \ || \ \texttt{ff}_{16}, m)$.
3. Eventually, there will be a $u_1$ such that $\text{Sign}(\mathcal{O} \ || \ u_1, m) = \hat{s}$. In this case, the first byte of $k_\mathcal{S}$ would be $u_1$.

To recover the second byte, we need an additional 256 oracle calls:

1. Call $\text{Sign}(\mathcal{O} \ || \ u_1 \ || \ \texttt{00}_{16}, m)$, $\text{Sign}(\mathcal{O} \ || \ u_1 \ || \ \texttt{01}_{16}, m)$, …, $\text{Sign}(\mathcal{O} \ || \ u_1 \ || \ \texttt{ff}_{16}, m)$.
2. There will be a $u_2$ such that $\text{Sign}(\mathcal{O} \ || \ u_1 \ || \ u_2, m) = \hat{s}$, and the second byte of $k_\mathcal{S}$ would be $u_2$.

With the above algorithm, we can fully recover $k_\mathcal{S}$ with 4097 calls. Unfortunately, we made an wrong assumption that $\text{id}$ is not prepended to the message. Now it is time to eliminate it.

What is being said is not what being meant⌗

Recall that a concatenated message is given by $\text{id} \ || \ m$, and we want to have multiple pairs of $(\text{id}, m)$s having the same concatenated message. We can do it by exploiting the ambiguity. For instance, when given the concatenated message 1337hello world, we are unable to determine what the original $\text{id}$ and $m$ are. It might be intuitive to think that $\text{id}$ and $m$ are respectively 1337 and hello world, but there are actually three other possibilities:

1. $\text{id}$ being 1 and $m$ being 337hello world,
2. $\text{id}$ being 13 and $m$ being 37hello world, and
3. $\text{id}$ being 133 and $m$ being 7hello world.

We can see that there is an ambiguity introduced – there are multiple ways to parse the output. To solve the challenge, I partitioned the oracle calls into two groups:

1. [Check call] Condition: If $\text{id} > 0$ and $\text{id} \equiv 0 \ (\text{mod}\ 10)$.
   We can refer to an earlier oracle call to check whether one byte of $k_\mathcal{S}$ equals to a particular value.
2. [Reference call] Condition: Happens otherwise.
   We can use this oracle call as a reference for the future.

For instance, oracle #1 and #10 can respectively become a reference and a look up call. For the two oracles, if we set

• the message to be 0000 and the key to be 16 null bytes for oracle #1, and
• the message to be 000 and the key to be 17 null bytes for oracle #10,

and if the first byte of $k_\mathcal{S}$ is $\texttt{00}$, the two oracle calls would yield the same digest.

Additionally, we are using multiple zeroes in oracle #1 because it can also be used by oracles #100, #1000 and #10000. Also, for simplicity, I use a bunch of 0s as the message and 16 null bytes as the key. The following table shows the first 21 oracle calls.

Since there is a 120-second limit in each connection and we are given 65536 oracle calls, I am often asked during the CTF if we can actually use up the calls before the timeout.

The answer is yes – we can do it in batch. In most of the time, we do not need an immediate response from the server and thus can group the requests. In this way, we do not need to complete 65536 round trips.

We can send up to the 2561-th call in batch to find the first byte of $k_\mathcal{S}$, the subsequent 2560 calls to find the next byte, and so on. By sending all the 40691 calls in 16 batches, we will be getting the flag:

hkcert23{y0u_h4v3_t0_el1m1n4t3_am6igu17y_7o_m1tig4t3_4mb19ui7y_4t74ck5}

Solitude, Solitude, Solitude⌗

Challenge Summary⌗

Yet another implementation of Shamir’s Secret Sharing. Of course you don’t have privileges and can only get one share.

Attachment: solitude.zip

When connected to the server, an odd number of 1024 bits is generated as the modulus $p$. The server also created a degree-9 polynomial $\text{f}$ with coefficients being $[0, p)$ such that $\text{f}(0) = \text{secret}$. We are only given the value of $p$.

The user is then asked to send an integer $x$ such that $x \not\equiv 0 \ (\text{mod}\ p)$, and the server will return the corresponding share (i.e., $\text{f}(x)\ \text{mod}\ p$). The goal is to recover $\text{secret}$.

Solution⌗

For Shamir’s secret sharing, it is advised that $p$ to be a prime number. Well, this is not our case – the $p$s generated are odd.

To exploit, we can reconnect to the server until $p$ is a multiple of 3.

Denote $\text{f}(x) = \text{secret} + a_1 x + a_2 x^2 + … + a_9 x^9$. If we set $x = p/3$, the share we get is

$$\begin{aligned} \text{f}(p/3) &= \text{secret} + a_1 (p/3) + … + a_9 (p/3)^9 \\ &= \text{secret} + (p/3) \left[a_1 + … + a_9 (p/3)^8\right] \\ &= \text{secret} + \alpha, \end{aligned}$$

where $\alpha \ \text{mod} \ p$ is either $0$, $p/3$ or $2p/3$. The probability of it being 0 is about 1/3. Thus, if we reconnect to the server until $p$ is a multiple of 3, we can send $p/3$ and there is a 1/3 chance for $y$ being the secret. All in all, there is a 1/9 chance to retrieve the flag in a single connection:

hkcert23{th4ts_why_y0u_w4n7_a_pr1m3_m0du1u5_f0r_s5s}