HKCERT CTF 2023 Postmortem (I): Easier Crypto Challenges
This is yet another moment that Black Bauhinia coorganizes 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:
Challenge Name  Category  Difficulty  Score  Solves  

The Art of Embarrassment  Crypto  β  150  0       
Sign me a Flag (I)  Crypto  π£  150  19  25  37  31 
Sign me a Flag (II)  Crypto  ββ  250  0  0  5  6 
Solitude, Solitude, Solitude  Crypto  β  150  0  5  10  17 
baDES  Crypto  π£  200  5  20  20  15 
Maybe Someday  Crypto  βββ  350    0  5  4 
Cipher Bridging Service  Crypto  ββββ  450  0  10  3  5 
RSA Triooo  Crypto  βββββ  500    0  1  2 
Hackforces  Misc  βββ  300  5  6  8  8 
ISA Jump Scare  Pwn  π£  200  12  20  30  15 
ISA Jogger  Pwn  ββ  200  5  15  27  13 
The Flag Game  Reverse  ββ  200  8  10  19  8 
Loot and Scoot  Reverse  βββββ  500  0  0  3  3 
Stepbystep 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: idealcipher.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^{1} 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 128bit 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 256bit 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}$):
 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_{2n1}m_{2n}$.
 Generate a 2byte IV, given by $C_0$.
 Compute $C_1 := \mathcal{E}(C_0 \oplus M_1)$, $C_2 := \mathcal{E}(C_1 \oplus M_2)$, …, $C_n := \mathcal{E}(C_{n1} \oplus M_n)$.
 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
 $C_0 = \texttt{d14b}_{16}$,
 $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
 $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_{i1} \oplus M_i) = \mathcal{E}(C_{j1} \oplus M_j)$. Since $\mathcal{E}$ is injective (i.e., no two plaintexts encrypt to the same ciphertext), we then have $C_{i1} \oplus M_i = C_{j1} \oplus M_j$. Rearranging the terms, we have
$${\color{red}M_i} \oplus {\color{red}M_j} = C_{i1} \oplus C_{j1}.$$
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:
 $M_{18} \oplus M_{21} = \texttt{5b55}_{16}$ (line 159),
 $M_{18} \oplus M_{27} = \texttt{0450}_{16}$ (line 615),
 $M_{25} \oplus M_{27} = \texttt{5f04}_{16}$ (line 762),
 $M_6 \oplus M_{18} = \texttt{063a}_{16}$ (line 887),
 $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: signmeaflagi.zip
In this challenge, we are given a remote oracle and is allowed to perform the below operations:
sign [key_client] [message]
: Signs an arbitrary message that does not contain the substringflag
.verify [signature]
: Verifies the signature for the messagegib 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{HMACSHA256}(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 exclusiveor (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 16byte, 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:
 Call $\text{Sign}(\texttt{00}, \text{hello world})$ and denote it by $\hat{s_1}$.
 Compute $\text{HMACSHA256}(\texttt{00}, \text{hello world})$, $\text{HMACSHA256}(\texttt{01}, \text{hello world})$, $\text{HMACSHA256}(\texttt{02}, \text{hello world})$, ….
 Eventually, there will be a $u_1$ such that $\text{HMACSHA256}(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:
 Call $\text{Sign}(\texttt{0000}, \text{hello world})$ and denote it by $\hat{s_1}$.
 Compute $\text{HMACSHA256}(\texttt{0000}, \text{hello world})$, $\text{HMACSHA256}(\texttt{0001}, \text{hello world})$, …, $\text{HMACSHA256}(\texttt{ffff}, \text{hello world})$.
 Eventually, there will be a $u_1$ such that $\text{HMACSHA256}(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: signmeaflagii.zip
This challenge is similar to Sign me a Flag (I), except that
 the
xor
implementation comes frompwntools
this time,  we have 65536 oracle calls, and
 let $\text{id}$ be the number of sequence number of the oracle call. The signature becomes
$$\text{Sign}(k_\mathcal{C}, m) := \text{HMACSHA256}(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{HMACSHA256}(k, \texttt{0test})$ and the second call is $\text{HMACSHA256}(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 XORed.
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 onebyte long.
The HMAC framework⌗
Firstly, if a HMAC key is shorter than 64 bytes, there will be a zeropadding. With the padding, the below HMAC functions have the same digest.
$$\begin{aligned} & \text{HMACSHA256}(\texttt{12}\ \texttt{34}, m) \\ & \quad= \text{HMACSHA256}(\texttt{12}\ \texttt{34}\ \texttt{00}, m) \\ & \quad= \text{HMACSHA256}(\texttt{12}\ \texttt{34}\ \texttt{00}\ \texttt{00}_{16}, m) \\ & \quad= \dots \\ & \quad= \text{HMACSHA256}(\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:
 Call $\text{Sign}(\mathcal{O}, m)$ and denote it by $\hat{s}$, here $\mathcal{O}$ being 16 null bytes.
 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)$.
 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:
 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)$.
 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:
 $\text{id}$ being
1
and $m$ being337hello world
,  $\text{id}$ being
13
and $m$ being37hello world
, and  $\text{id}$ being
133
and $m$ being7hello 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:
 [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.  [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 0
s as the message and 16 null bytes as the key. The following table shows the first 21 oracle calls.
$\text{id}$  Message  Key  Purpose 

0  0000  0000...00  Serves as a reference for future calls 
1  0000  0000...00  Serves as a reference for future calls 
2  0000  0000...00  Serves as a reference for future calls 
3  0000  0000...00  Serves as a reference for future calls 
4  0000  0000...00  Serves as a reference for future calls 
5  0000  0000...00  Serves as a reference for future calls 
6  0000  0000...00  Serves as a reference for future calls 
7  000  0000...00  Serves as a reference for future calls 
8  000  0000...00  Serves as a reference for future calls 
9  000  0000...00  Serves as a reference for future calls 
10  000  0000...00 00  Checks whether the 1st byte of $k_\mathcal{S}$ is $\texttt{00}$ 
11  000  0000...00  Serves as a reference for future calls 
12  000  0000...00  Serves as a reference for future calls 
13  000  0000...00  Serves as a reference for future calls 
14  000  0000...00  Serves as a reference for future calls 
15  000  0000...00  Serves as a reference for future calls 
16  000  0000...00  Serves as a reference for future calls 
17  000  0000...00  Serves as a reference for future calls 
18  000  0000...00  Serves as a reference for future calls 
19  000  0000...00  Serves as a reference for future calls 
20  000  0000...00 01  Checks whether the 1st byte of $k_\mathcal{S}$ is $\texttt{01}$ 
Since there is a 120second 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 2561th 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 degree9 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}

Matthew Green (2013): “The Ideal Cipher Model (Wonky)"
https://blog.cryptographyengineering.com/2013/04/11/wonkerymailbagidealciphers/ ↩︎