HKCERT CTF 2021 Postmortem (I): Easier Crypto Challenges

Black Bauhinia coorganized HKCERT CTF 2021 and helped 95% of the technical stuffs, including challenge setting, platform development, infrastructure and etc. I will be writing a series of blog posts talking about the contest, and the first four would be the writeups of the challenges those I wrote.

In the first blog post, we will be going through four easier crypto challenges: A Joke Cipher, Cipher Mode Picker, Key Backup Service 1 and Key Backup Service 2.

小諧星 / A Joke Cipher (Crypto)⌗

Challenge Summary⌗

早知不可獲勝
擠出喜感做諧星
無力當 你們崇尚的精英
有幸獻醜的 小丑 都不失敬

In the beginning of 2020, Khaled A. Nagaty invented a cryptosystem based on key exchange. The cipher is faster than ever... It is impossible to break, right?

To solve this challenge, you need to read the source code chall.py. Try to get those questions answered:

• Can shared_key generated from y_A and y_B?
• If so, how do we calculate m from c and shared_key?
• How can we convert the number m into a flag that is in the format hkcert21{...}?

The challenge implements Nagaty's Cryptosystem¹ which no one knows why it is a cryptosystem. Initially, a prime $p$ is determined. Alice and Bob respectively derive a private key $x_A$ and a public key $y_A := x_A\ \text{mod}\ p$ (resp. $x_B$ and $y_B := x_B\ \text{mod}\ p$). A shared key is computed by Alice with $s = y_A \cdot {y_B}^2 \cdot x_A\ \text{mod}\ p$. Finally, the message $m$ is encrypted by $m \cdot s$.

In the challenge, we are given $p$, $y_A$, $y_B$ and an encrypted flag $c$. The objective is to recover the flag.

Solution⌗

It is easy to compute the shared key $s$ given $y_A$ and $y_B$:

\[s = {y_A}^2 \cdot {y_B}^2\ \text{mod}\ p.\]

With $s$, we can easily recover the message $m$ from ciphertext $c$ by $m = c / s$.

Freedom / Cipher Mode Picker (Crypto)⌗

Challenge Summary⌗

Freedom where's our freedom?
Freedom what would it be
Can you tell me what's the reason?
Reason that meant to be

Every slightest mistake in cryptography would lead to a disastrous result. Let's see what will happen when you allow end-users to pick the mode of operation...

  nc HOST PORT

A 16-byte key and a 16-byte IV is generated when connected to the server. We are able to use each of the below encryption functions once, to encrypt either a given message or the 80-byte flag:

# 1. AES-ECB
cipher = AES.new(key, AES.MODE_ECB)
# 2. AES-CBC
cipher = AES.new(key, AES.MODE_CBC, iv)
# 3. AES-CFB
cipher = AES.new(key, AES.MODE_CFB, iv, segment_size=128)
# 4. AES-OFB
cipher = AES.new(key, AES.MODE_OFB, iv)
# 5. AES-CTR
cipher = AES.new(key, AES.MODE_CTR, counter=Counter.new(16, prefix=iv[:14]))

The goal is to recover the flag.

Motivation⌗

This challenge is intended to be entry-level for students to learn block cipher mode of operations.

Solution⌗

Suppose that we are encrypting a message $m_1, m_2, ..., m_n$. Let's define the ciphertexts (in different modes of operation) mathematically:

\[\begin{aligned} & c^\text{(ECB)}_k := \text{Enc}(m_k) \\ & c^\text{(CBC)}_k := \text{Enc}(m_k \oplus c^\text{(CBC)}_{k-1}) \\ & c^\text{(CFB)}_k := \text{Enc}(c^\text{(CFB)}_{k-1}) \oplus m_k \\ & c^\text{(OFB)}_k := \text{Enc}^{k}(\text{IV}) \oplus m_k \\ & c^\text{(CTR)}_k := \text{Enc}(\text{IV} + k) \oplus m_k \end{aligned},\]

where $c^\text{(CBC)}_0 = c^\text{(CFB)}_0 = \text{IV}$.

To solve the challenge, we do not need to use all of the modes. Instead, we need to encrypt 80 null bytes with the CBC mode. In that way we have:

\[\begin{aligned} & c^\text{(CBC)}_1 = \text{Enc}(m_1 \oplus c^\text{(CBC)}_0) = \text{Enc}(0 \oplus \text{IV}) = \text{Enc}(\text{IV}) \\ & c^\text{(CBC)}_2 = \text{Enc}(m_2 \oplus c^\text{(CBC)}_1) = \text{Enc}(0 \oplus \text{Enc}(\text{IV})) = \text{Enc}^2(\text{IV}) \\ & c^\text{(CBC)}_3 = \text{Enc}(m_3 \oplus c^\text{(CBC)}_2) = \text{Enc}(0 \oplus \text{Enc}^2(\text{IV})) = \text{Enc}^3(\text{IV}) \\ & c^\text{(CBC)}_4 = \text{Enc}(m_4 \oplus c^\text{(CBC)}_3) = \text{Enc}(0 \oplus \text{Enc}^3(\text{IV})) = \text{Enc}^4(\text{IV}) \\ & c^\text{(CBC)}_5 = \text{Enc}(m_5 \oplus c^\text{(CBC)}_4) = \text{Enc}(0 \oplus \text{Enc}^4(\text{IV})) = \text{Enc}^5(\text{IV}) \end{aligned}\]

Let $\hat{m_1}, \hat{m_2}, ..., \hat{m_5}$ be the flag. We can encrypt the flag with the OFB mode and obtain:

\[c^\text{(OFB)}_k = \text{Enc}^k(\text{IV}) \oplus \hat{m_k}\]

for $k = 1, 2, ..., 5$. After all, we can compute $\hat{m_k} := c^\text{(CBC)}_k \oplus c^\text{(OFB)}_k$ for $k = 1, 2, ..., 5$ to recover the flag.

長話短說 / Key Backup Service 1 (Crypto)⌗

Challenge Summary⌗

長話𥚃短說
但察覺太短
或者真正意義
並不需要說穿

Note: This is part one of a two-part series. Part two: Braceless / Key Backup Service 2.

Mystiz made a key vault which could encrypts his darkest secrets (i.e., the flag). Everything is protected with a bank-level encryption (i.e., a 256-bit key). You are welcome to look at the encrypted secrets and praise his cryptographic knowledge.

  nc HOST PORT

When connected to the server, a 32-byte master secret $x$ is generated. We are able to call the below functions at a total of 17 times:

1. [SEND] Returns the ciphertext, i.e., $m^e\ \text{mod}\ n$, of an arbitrary given message $m$ with the current key $\mathcal{K}$.
2. [PKEY] Generates a set of RSA key and assign to $\mathcal{K} = (n, e)$.
3. [BACKUP] Returns the encrypted secret, i.e., $x^{e}\ \text{mod}\ n$, with the current key $\mathcal{K}$.
4. [FLAG] Encrypts the flag with the key $x$ under AES-CBC.

Additionally, the public exponent is $e = 17$ and the 512-bit primes for the moduli is generated by a PRNG, seeded by the below snippet:

# 256 bits for random-number generator
N = 0xcdc21452d0d82fbce447a874969ebb70bcc41a2199fbe74a2958d0d280000001
G = 0x5191654c7d85905266b0a88aea88f94172292944674b97630853f919eeb1a070
H = 0x7468657365206e756d6265727320617265206f6620636f757273652073757321

# The primes for the public exponent. id is a randomly generated 256-bit integer.
p = generate_prime(x + int.to_bytes(pow(G, id, N), 32, 'big'))
q = generate_prime(x + int.to_bytes(pow(H, id, N), 32, 'big'))

Solution⌗

We are often told that we need $\geq e$ ciphertexts to perform the broadcast attack, which is not always true. We could recover $m$ as soon as $m^e < n_1n_2 ... n_k$ - that said, if $m$ is significantly smaller than the modulus, we do not need $e$ messages.

In our scenario, $n$ is 1024 bits long but the master secret $x$ is only 256 bits long. Since $256\cdot17 = 4352 < 5120 = 1024\cdot5$, we can recover $x$ given

\[\begin{cases} c_1 \equiv x^{17}\ (\text{mod}\ n_1) \\ c_2 \equiv x^{17}\ (\text{mod}\ n_2) \\ c_3 \equiv x^{17}\ (\text{mod}\ n_3) \\ c_4 \equiv x^{17}\ (\text{mod}\ n_4) \\ c_5 \equiv x^{17}\ (\text{mod}\ n_5) \end{cases}.\]

We need three oracle calls to obtain one set of $x^{17}\ \text{mod}\ n_k$:

1. PKEY to update $\mathcal{K}$ to $n = n_k$ and $e = 17$,
2. BACKUP to obtain $x^{17}\ \text{mod}\ n_k$ without knowing $n_k$,
3. SEND -1 to obtain $(-1)^{17} \text{mod}\ n_k$, which is $n_k - 1$.

After collecting $(c_1, n_1)$, $(c_2, n_2)$, ..., $(c_5, n_5)$, we can use Chinese remainder theorem to find $x^{17}\ \text{mod}\ n_1n_2...n_5$. Since $0 \leq x^{17} < n_1n_2...n_5$, we can directly take the 17th root of $x^{17}$ for $x$.

Finally, we can use FLAG to obtain the encrypted flag. Since we already have the key, we are able to decrypt for the flag.

Braceless / Key Backup Service 2 (Crypto)⌗

Challenge Summary⌗

根本不介意
擠逼都市像有點失智
迷迷魂魂 十二萬轉 oh oh oh
根本不介意
喜歡失意又跌多幾次
就算跌崩 一隻牙齒

Note: This is part two of a two-part series. Part one: 長話短說 / Key Backup Service I.

Mystiz is really lazy. He expects that someone would crack the bank-level encryption, but he doesn't care about that. After all, the darkest secret is not that dark.

He decided to change the numbers and release it to the public again. Now crack it!

The challenge is identical to 長話短說 / Key Backup Service I, with three changes:

1. $e = 17$ is changed to $e = 65537$,
2. The number of oracle calls is increased from 17 to 65537,
3. We do not have the netcat service anymore. Instead, we have a transcript of an interaction. It includes one FLAG operation, followed by 16384 sequences of the below operations: PKEY, SEND 2, SEND 3 and BACKUP.

Motivation⌗

This is a sequel of the challenge 長話短說 / Key Backup Service I, but I actually made this earlier than the other challenge. I was inspired by Austin Allshouse's talk in DEFCON this year and it is the first time learning batch GCD.

My initial plan is to create a netcat service that generates RSA keys based on the master secret. I later reject the idea because it is very slow and memory intensive to generate a lot of keys. Alas, it appeared in RCTF as Uncommon Factor II.

Solution⌗

The three constants $N$, $G$ and $H$ finally comes to play in the second part of the challenge:

N = 0xcdc21452d0d82fbce447a874969ebb70bcc41a2199fbe74a2958d0d280000001
G = 0x5191654c7d85905266b0a88aea88f94172292944674b97630853f919eeb1a070
H = 0x7468657365206e756d6265727320617265206f6620636f757273652073757321

In particular, $G^{2^{25}} \equiv 1\ \text(mod\ N)$. Since one of the primes, $p$, is generated with seed $G^x\ \text{mod}\ N$, there are only $2^{25}$ possible values. It is known that there is a collision when there are $\sqrt{2^{25}} \approx 5800$ numbers - that said, there will be a shared prime factor in around $5800$ generated public moduli. There exists $i, j$ such that $\gcd(n_i, n_j) > 1$.

We can recover a small multiple of $n_1, n_2, ..., n_{16384}$ from the transcript. Let $c_2$ and $c_3$ be the outputs of SEND 2 and SEND 3. We could recover a small multiple of $n$ by $\gcd(2^{65537} - c_2, 3^{65537} - c_3)$.

With 16384 $n$'s, we can apply the batch GCD algorithm² and find common factors to find some prime $p$ such that $p$ is a common factor of $n_i$ and $n_j$ for some $i, j$.