HKCERT CTF 2021 Postmortem (II): Harder Crypto Challenges

In this part, three harder crypto challenges will be covered: Tenet: The Plagarism, Sratslla SEA and Sign in Please, Again.

FreeRider / Tenet: The Plagarism (Crypto)⌗

Challenge Summary⌗

平日我又講 對住你講
email要check deadline要追
前日我提咗 你嗰part嘅功課
點解變咗我最立糯

The deadline for writing challenges is coming!

Mystiz, who claimed himself not well-known reusing challenges, decided to free-ride and plagarize challenges from HKCERT CTF 2020. Maybe you can reuse the solve script last year for the flag.

Ciphertext:

6ccb80c46c19243a37633d316a66871ca70ec8a44f48a80134f31d8d27f920c6bd5d810831833221d0f282130d2c222de38c2080ef995b2ad10dc5af8518

Attachments: challenge.py

Suppose that the flag matches the regular expression hkcert21\{\w{35}\}. We define an encryption algorithm, $\mathcal{E}$, with a 16-byte key $k_1k_2...k_{16}$. Let $m$ be the message we would like to encrypt (all of the counters are set to zero):

1. Encrypt $m$ with AES-CTR using the key k1 00 00 00 ... 00 ($k_1$ followed by 15 null bytes) and denote it by $t_1$.
2. Encrypt $t_1$ with AES-CTR using the key k2 00 00 00 ... 00 and denote it by $t_2$.
3. ...
4. Encrypt $t_{15}$ with AES-CTR using the key k16 00 00 00 ... 00 and denote it by $t_{16}$.
5. Return $t_{16}$ as the ciphertext.

$\mathcal{E}$ is used to encrypt the message Congratulations! [FLAG] and we are given its ciphertext. The objective is to recover the flag. Notably, the challenge is highly referenced from Tenet in HKCERT CTF 2020.

Solution⌗

Note that AES-CTR is a stream cipher. The bitstream would be the same if we supply AES-CTR with the same key and the same counter.

AES.new(key=key[ 0: 1] + b'\0'*15, mode=AES.MODE_CTR, counter=Counter.new(128, initial_value=0))
AES.new(key=key[ 1: 2] + b'\0'*15, mode=AES.MODE_CTR, counter=Counter.new(128, initial_value=0))
AES.new(key=key[ 2: 3] + b'\0'*15, mode=AES.MODE_CTR, counter=Counter.new(128, initial_value=0))
AES.new(key=key[ 3: 4] + b'\0'*15, mode=AES.MODE_CTR, counter=Counter.new(128, initial_value=0))
# ...

There are only 256 possible bitstreams by AES-CTR. Let $b_{kj}$ be the $j$-th bit of the bitstream if the key is k 00 00 00 ... 00. If we encrypt the message $m_1 m_2 ... m_n$ (represented in bits) with key $k_1 k_2 ... k_{16}$, then the $j$-th bit of the ciphertext, $c_j$, will be:

\[\begin{aligned} c_j &= t_{15, j} \oplus b_{k_{16}, j} = (t_{14, j} \oplus b_{k_{15}, j}) \oplus b_{k_{16}, j} = ... \\ &= m_j \oplus b_{k_{1}, j} \oplus b_{k_{2}, j} \oplus ... \oplus b_{k_{16}, j} \end{aligned}\]

Solving linear equations⌗

We are given the entire ciphertext, i.e., all of the $c_j$'s. Suppose that we know (we do!) some of the $m_j$'s as well, then we have

\[m_j \oplus c_j = b_{k_{1}, j} \oplus b_{k_{2}, j} \oplus ... \oplus b_{k_{16}, j}.\]

Here we have 16 unknowns: $k_1$, $k_2$, ..., $k_{16}$. This however does not bring us insights solving the problem. Luckily we can rewrite the above equation:

\[m_j \oplus c_j = x_0 b_{0, j} \oplus x_1 b_{1, j} \oplus ... \oplus x_{255} b_{255, j}.\]

Now $b_{i, j}$ are all known because we can generate the bitstream ourselves. We now have 256 unknowns: $x_0, x_1, ..., x_{255}$ (each of them is either a 0 or an 1). Ideally, if we know $m_{j_1}, m_{j_2}, ..., m_{j_{256}}$, then:

\[\begin{cases}\begin{matrix} m_{j_1} \oplus c_{j_1} &=& x_0 b_{0, j_1} & \oplus & x_1 b_{1, j_1} & \oplus & ... & \oplus & x_{255} b_{255, j_1} \\ m_{j_2} \oplus c_{j_2} &=& x_0 b_{0, j_2} & \oplus & x_1 b_{1, j_2} & \oplus & ... & \oplus & x_{255} b_{255, j_2} \\ &&&\vdots \\ m_{j_{256}} \oplus c_{j_{256}} &=& x_0 b_{0, j_{256}} & \oplus & x_1 b_{1, j_{256}} & \oplus & ... & \oplus & x_{255} b_{255, j_{256}} \\ \end{matrix}\end{cases}.\]

We have 256 linear equations and 256 unknowns. This is similar to what we learnt in the secondary school, except that there are much more equations and unknowns. Also, the $+$ operation is replaced by $\oplus$.

Every bit matters⌗

We are given the ciphertext. Where do we gather 256 message bits? From challenge.py we know that

1. the flag matches the regular expression hkcert21\{\w{35}\}, and
2. the message encrypted is Congratulations! [FLAG].

Apparently we know 27 bytes (i.e., 216 bits):

1. the 26-byte prefix Congratulations! hkcert21{ and
2. the one-byte suffix }.

However, knowing that content of the flag matches \w{35}, the most significant bit for each byte would be 0. That said, we have an additional 35 bits, resulting in 251 bits in total.

Since we need only five bits, we can do either exhaust five unknown bits or do it mathematically. In this writeup, we will do the latter.

Let's build a $251 \times 256$ matrix $A$ and a $251 \times 1$ matrix $b$, with entries being 0 or 1:

\[ A = \left[\begin{matrix} b_{0, j_1} & b_{1, j_1} & b_{2, j_1} & ... & b_{255, j_1} \\ b_{0, j_2} & b_{1, j_2} & b_{2, j_2} & ... & b_{255, j_2} \\ && \vdots \\ b_{0, j_{251}} & b_{1, j_{251}} & b_{2, j_{251}} & ... & b_{255, j_{251}} \\ \end{matrix}\right], b = \left[\begin{matrix} m_{j_1} + c_{j_1} \\ m_{j_2} + c_{j_2} \\ \vdots \\ m_{j_{251}} + c_{j_{251}} \end{matrix}\right] \]

We can find a particular solution $x_0$ (such that $A \cdot x_0 = b$) and a set of $\Delta x$s (such that $A \cdot \Delta x = 0$). Then $x = x_0 + \Delta x$ is also a root of $A \cdot x = b$. The below snippet written in Sagemath finds all the roots $x$ such that $Ax = b$:

x0 = A.solve_right(b)
for dx in A.right_kernel():
    x = x0+dx # This is a root such that A*x = b.

Solution script⌗

This is the solution script written in Sagemath.

import re
from Crypto.Util import Counter
from Crypto.Cipher import AES

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

#                      C o n g r a t u l a t i o n s ! _ h k c e r t 2 1 {                                                                       }
known = bytes.fromhex('ffffffffffffffffffffffffffffffffffffffffffffffffffff8080808080808080808080808080808080808080808080808080808080808080808080ff')
m =     bytes.fromhex('436f6e67726174756c6174696f6e732120686b6365727432317b00000000000000000000000000000000000000000000000000000000000000000000007d')
c =     bytes.fromhex('6ccb80c46c19243a37633d316a66871ca70ec8a44f48a80134f31d8d27f920c6bd5d810831833221d0f282130d2c222de38c2080ef995b2ad10dc5af8518')

keystreams = []
for k in range(256):
    cipher = AES.new(bytes([k]) + b'\0'*15, AES.MODE_CTR, counter=Counter.new(128, initial_value=int(0)))
    keystreams.append(
        cipher.encrypt(b'\0'*len(c))
    )

A = []
b = []

for i, (rc, mc, cc) in enumerate(zip(known, m, c)):
    for j in range(8):
        if (rc>>j) & 1 == 0: continue
        mb = (mc>>j) & 1
        cb = (cc>>j) & 1

        row = [(k[i]>>j) & 1 for k in keystreams]

        A.append(row)
        b.append(mb^^cb)

F = GF(2)
A = Matrix(F, A)
b = vector(F, b)

print(f'Expecting {2**(A.ncols() - A.rank())} candidates to be guessed ({A.ncols()} unknowns vs {A.nrows()} equations)')

x0 = A.solve_right(b)
for dx in A.right_kernel():
    x = x0+dx

    flag = c
    for k, xc in zip(keystreams, x):
        if xc == 0: continue
        flag = xor(flag, k)
    flag = flag.decode()
    if not re.match(r'Congratulations! hkcert21\{\w+\}', flag): continue
    print(f'[*] Flag recovered: {flag}')

集合吧！地球保衛隊 / Sratslla SEA (Crypto)⌗

Challenge Summary⌗

一加一加一再合成做注碼
若然加多一位相信事情就變化
就回隊吧 尊貴的磚瓦
去抵抗風化

AddRoundKey, SubBytes, ShiftRows and MixColumns are four crucial components are AES. They are used to protect the world in 2021. I wonder what will happen if some of them is out of function.

nc HOST PORT

Attachments: chall.py, aes.py

We will use the Advanced Encryption Standard (AES) for encryption in the challenge. Let $k_0k_1k_2...k_{15}$ be a 16-byte key and let $K_n := k_nk_nk_nk_n$ for $n = 0, 1, 2, ..., 15$. When connected to the server, $k_0k_1k_2...k_{15}$ is randomly created and we are able to access the below functions for 128 times:

1. [ark secret] encrypts $K_0K_1K_2K_3$ without the AddRoundKey operation and returns the ciphertext.
2. [sb secret] encrypts $K_4K_5K_6K_7$ without the SubBytes operation and returns the ciphertext.
3. [sr secret] encrypts $K_8K_9K_{10}K_{11}$ without the ShiftRows operation and returns the ciphertext.
4. [mc secret] encrypts $K_{12}K_{13}K_{14}K_{15}$ without the MixColumns operation and returns the ciphertext.
5. [ark data] (resp. [sb data], [sr data] or [mc data]) encrypts a 16-byte user-defined data without the AddRoundKey operation (resp. SubBytes, ShiftRows or MixColumns) and returns the ciphertext.

We are also given a 64-byte encrypted flag when connected to the server. The goal is to collect enough information for the key in 128 calls and decrypt for the flag.

Background⌗

This challenge is inspired by the group C AllStar. The group has four people, and AES consists of four subfunctions. Coincidence? I think not.

There is a question in Cryptography Stack Exchange¹ saying that it was easy to attack without any of the components. I found it really hard when setting up the first draft of the challenge... Back then I only gave [ark data], [sb data], [sr data] and [mc data] to the players. Well, that was a bad decision because I spent one week not solving it. I also tweeted about that in the middle... Yeah, this is what happened at that time.

Solution⌗

Recovering $k_0$, $k_1$, $k_2$ and $k_3$ with one call⌗

The AddRoundKey step is where the key mixed with the state. Since the key is not used elsewhere, the same plaintext would be encrypted to the same ciphertext with any key. We can recover $K_0K_1K_2K_3$ by calling ark secret and decrypting with an arbitrary key (while skipping AddRoundKey).

# [*] 1 oracle call
r.sendlineafter(b'> ', 'ark secret')
c = bytes.fromhex(r.recvline().decode())

cipher = AES(b'\0'*16)
cipher._add_round_key = no_op
m = cipher.decrypt(c)
assert m[0::4] == m[1::4] == m[2::4] == m[3::4]
key[0:4] = m[0::4]

Recovering $k_4$, $k_5$, $k_6$ and $k_7$ with 2 calls⌗

The SubBytes step is the only place where non-linearity in AES is introduced. Under $\text{GF}(2^{128})$, the ciphertext $c$ of a given plaintext $m$ satisfies $c = S \cdot m + T_k$ for some $S, T_k \in \text{GF}(2^{128})$ with $S \neq 0$ and $T_k$ is dependent to the key $k$.

Lemma. Let $k$ be a key. $\text{Dec}_k(c) = S^{-1}(c + T_k)$.

Proof.

\[\begin{aligned} c &= S \cdot \text{Dec}_k(c) + T_k \\ S \cdot \text{Dec}_k(c) &= c + T_k \\ \text{Dec}_k(c) &= S^{-1}(c + T_k)\qquad\qquad \blacksquare \end{aligned}\]

Theorem. Let $k$ and $k'$ be two keys. Let also $c_0 = \text{Enc}_k(0)$ and $c_1 = \text{Enc}_k(m)$. Then

\[m = \text{Dec}_{k'}(c_0) + \text{Dec}_{k'}(c_1).\]

Proof.

\[\begin{aligned} \text{Dec}_{k'}(c_0) + \text{Dec}_{k'}(c_1) &= S^{-1}(c_0 + T_{k'}) + S^{-1}(c_1 + T_{k'}) \\ &= S^{-1} (c_0 + T_{k'} + c_1 + T_{k'}) = S^{-1} (c_0 + c_1) \\ &= S^{-1} [\text{Enc}_k(0) + \text{Enc}_k(m)] = S^{-1} [T_k + S \cdot m + T_k] \\ &= S^{-1}(S \cdot m) = m \qquad\qquad\qquad\qquad\qquad\qquad\qquad \blacksquare \end{aligned}\]

From the above theorem, we can recover four bytes of the key with 16 oracle calls.

# [*] +2 oracle calls (3 in total)
r.sendlineafter(b'> ', 'sb data 00000000000000000000000000000000')
c0 = bytes.fromhex(r.recvline().decode())
r.sendlineafter(b'> ', 'sb secret')
c1 = bytes.fromhex(r.recvline().decode())
cipher = AES(b'\0'*16)
cipher._inv_sub_bytes = no_op
m = xor(cipher.decrypt(c0), cipher.decrypt(c1))
assert m[0::4] == m[1::4] == m[2::4] == m[3::4]
key[4:8] = m[0::4]

Recovering $k_{12}$, $k_{13}$, $k_{14}$ and $k_{15}$ with 65 calls⌗

MixColumns is the primary source of diffusion in AES. If MixColumns is dropped in AES, one byte of message would correspond to one byte of the ciphertext.

It can be proved (I did it by experiment) that the $k$-th byte of the message would affect only $(9k\ \text{mod}\ 16)$-th byte of the ciphertext. We can recover $k_8$ up to $k_{11}$ by encrypting those 64 messages:

\[\begin{aligned} & \text{Enc}_k(\texttt{00 01 02 03 00 01 02 03 00 01 02 03 00 01 02 03}) \\ & \text{Enc}_k(\texttt{04 05 06 07 04 05 06 07 04 05 06 07 04 05 06 07}) \\ & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \vdots \\ & \text{Enc}_k(\texttt{FC FD FE FF FC FD FE FF FC FD FE FF FC FD FE FF}) \end{aligned}\]

cs = []
for i in range(64):
    m = bytes([4*i + j%4 for j in range(16)])
    r.sendlineafter(b'> ', f'mc data {m.hex()}')
    c = bytes.fromhex(r.recvline().decode())
    c = bytes([c[9*k%16] for k in range(16)]) # Rearrange so that m[i] will affect c[i] instead of c[9i mod 16]
    cs.append(c)

r.sendlineafter(b'> ', 'mc secret')
c = bytes.fromhex(r.recvline().decode())
c = [c[9*i%16] for i in range(16)]

# This is the last four bytes of the key
for i in range(64):
    for j in range(16):
        if cs[i][j] != c[j]: continue
        key[12 + j//4] = 4*i + j%4

Reducing the search space for $k_8$, $k_9$, $k_{10}$ and $k_{11}$ with 60 calls⌗

Without ShiftRows, each byte of the message affects four bytes (instead of 16 bytes) of the ciphertext. That said, for $0 \leq m < 256$ be one byte and $c_{m,j}$ be a 4-byte subblock for $j = 1, 2, 3, 4$. Let $c_{m,1}c_{m,2}c_{m,3}c_{m,4}$ is the ciphertext of a message block of 16 $m$'s, i.e.:

\[c_{m,1}c_{m,2}c_{m,3}c_{m,4} = \text{Enc}_k(\overline{m\ m\ m\ m}\ \overline{m\ m\ m\ m}\ \overline{m\ m\ m\ m}\ \overline{m\ m\ m\ m})\]

In this case, the ciphertext of the message $\overline{m_1m_1m_1m_1}\ \overline{m_2m_2m_2m_2}\ \overline{m_3m_3m_3m_3}\ \overline{m_4m_4m_4m4}$ would be $c{m1,1}c{m2,2}c{m3,3}c{m_4,4}$.

Since mc secret is $K_{12}K_{13}K_{14}K_{15}$ encrypted, its corresponding ciphertext would be $c_{k_{12},1}c_{k_{13},2}c_{k_{14},3}c_{k_{15},4}$. To recover those $k_i$'s, we can encrypt the below 256 messages to compute a lookup table:

\[\begin{aligned} c_{0,1}c_{0,2}c_{0,3}c_{0,4} &= \text{Enc}_k(\overline{\texttt{00 00 00 00}}\texttt{ }\overline{\texttt{00 00 00 00}}\texttt{ }\overline{\texttt{00 00 00 00}}\texttt{ }\overline{\texttt{00 00 00 00}}) \\ c_{1,1}c_{1,2}c_{1,3}c_{1,4} &= \text{Enc}_k(\overline{\texttt{01 01 01 01}}\texttt{ }\overline{\texttt{01 01 01 01}}\texttt{ }\overline{\texttt{01 01 01 01}}\texttt{ }\overline{\texttt{01 01 01 01}}) \\ & \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\vdots \\ c_{255,1}c_{255,2}c_{255,3}c_{255,4} &= \text{Enc}_k(\overline{\texttt{FF FF FF FF}}\texttt{ }\overline{\texttt{FF FF FF FF}}\texttt{ }\overline{\texttt{FF FF FF FF}}\texttt{ }\overline{\texttt{FF FF FF FF}}) \\ \end{aligned}\]

Then we can identify $k_{12} = m$ by looking for $c_{k_{12},1} = c_{m, 1}$ and so on. However, owing to budget issues (the number of oracles are limited), we could not afford sending another 256 requests. We can however send 59 requests to reduce the search space. Depending on the number of $k_i$'s are less than 59, the search space is reduced:

There are around 20% that there are only less than 40K candidates to test through (which could be exhausted within one second). We can reconnect to the server until this happens.

# [*] +60 oracle calls (128 in total)
# Try to reduce the search space by 23% (or even more if there is a match)
cs = []
for i in range(59):
    m = bytes([i])*16
    r.sendlineafter(b'> ', f'sr data {m.hex()}')
    c = bytes.fromhex(r.recvline().decode())
    cs.append(c)

r.sendlineafter(b'> ', 'sr secret')
c = bytes.fromhex(r.recvline().decode())

matched = 0
candidates = [list(range(59, 256)) for _ in range(4)]
for i in range(59):
    for j in range(4):
        if cs[i][4*j:4*j+4] != c[4*j:4*j+4]: continue
        candidates[j] = [i]
        matched += 1

total = (256-59)**(4-matched)
print(f'{matched}/4 bytes matched (the more the better). Need to search {total} AES keys.')

for subkey in tqdm(itertools.product(*candidates), total=(256-59)**(4-matched)):
    key[8:12] = subkey
    cipher = RealAES.new(bytes(key), RealAES.MODE_ECB)
    m = cipher.decrypt(c_flag)
    if not m.startswith(b'hkcert21{'): continue
    print(f'The flag is found! {m}')
    break

約定的夢幻島 / Sign In Please, Again (Crypto)⌗

Challenge Summary⌗

不枉我們奮鬥過 和壞人拼搏過
燃亮如熊熊烈火
當初有誰諷刺過 胡亂抨擊過 亦也走得過
或誰也會照笑 笑我傻 說這裏也有折磨
卻有你有我 曾無懼逐關過
重新開始我們上多課

Okay. My secure authentication system was proved insecure (see here) as it got exploited last year by a bunch of bad guys. I improved the system and you would not be able to eavesdrop the passwords ever again.

nc HOST PORT

Attachments: chall.py

Define the below authentication algorithm $\mathcal{P}$. Suppose that a user have a $n$ character-long password, $p_1p_2...p_n$:

1. The server generates a 4-byte salt $s_1s_2s_3s_4$ and generate a permutation of $\{1, 2, ..., n+5\}$, denote it as $\sigma$.
2. A user
   • generates one byte of pepper $r$,
   • denotes $x_k = p_k$ for $k = 1, 2, ..., n$, $x_{n+k} = s_k$ for $k = 1, 2, ..., 4$ and $x_{n+5} = r$,
   • computes $y_k = x_{\sigma(k)}$ for $k = 1, 2, ..., n+5$ and $h := \text{SHA256}(y_1y_2...y_{n+5})$, and
   • send $h$ to the server.
3. The server computes $h'$ from $p_1p_2...p_n$, the salt $s_1s_2s_3s_4$ and all $r \in [0, 256)$. If there exists $r$ such that $h = h'$, the user is authenticated.

The netcat service implements the above algorithm $\mathcal{P}$ and the player, who acts as the man in-the-middle, can play with below operations in a total of 50 times:

1. [🕵️] The player impersonates the server and sends a salt $s_1s_2s_3s_4$ and surjective mapping $\sigma: \{1, 2, ..., k\} \rightarrow \{1, 2, ..., 21\}$ to the user. The user replies with a digest $h$. By surjective $\sigma$ should satisfy the below condition:
   • For all $v = 1, 2, ..., 21$, there exists $u \in \{1, 2, ..., k\}$ such that $\sigma(u) = v$.
2. [🖥️] The server sends a permutation $\sigma$ and a salt $s_1s_2s_3s_4$. If the player supplies with a valid digest $h$, the server replies with the flag.

Solution⌗

Merkle-Damgard scheme and length extension attack⌗

SHA-256 is operated under the Merkle-Damgard scheme and length extension attack is a well-known attack regarding the scheme. Please refer to asecuritysite.com for more details of the attack. Note that the attack is largely related to the challenge, so please prepared for that.

In the following, we use $h' = \mathcal{H}(h, m_1m_2...m_{64})$ where $\mathcal{H}$ is a Merkle-Damgard function (this time the SHA-256 function). $h$ and $h'$ are the hash values before and after the transition, and $m_1m_2...m_{64}$ is the 64-byte message block. Also, we will use $h_0$ as the initial hash value. For SHA-256,

h0 = 0x6a09e667bb67ae853c6ef372a54ff53a510e527f9b05688c1f83d9ab5be0cd19

Recovering a pepper probabilisticly⌗

We can control $\sigma$ and the salt $s_1s_2s_3s_4$. A major difference between this challenge and its predecessor, Sign in Please, is the existence of a pepper byte. We are allowed to trigger 40 more calls. It seems that recovering a random pepper byte would be a big challenge, which is true.

Suppose $\sigma$ is the identity permutation (i.e., pbox = [0, 1, 2, ..., 20]). That said, the permutated password is simply the password, salt and pepper concatenated. If also $s_1 = s_2 = s_3 = s_4 = \text{00}$, the final hash would be $h_1$, where

\[\begin{aligned} h_1 &= \mathcal{H}(h_0, \underbrace{p_1 p_2 ... p_{16}}_{1,\ ...,\ 16} \underbrace{s_1 s_2 s_3 s_4}_{17,\ ...,\ 20} \underbrace{r}_{21} \underbrace{\text{80}}_{22} \underbrace{\text{00 00 ... 00}}_{23,\ ...,\ 63} \underbrace{\text{A8}}_{64}) \\ &= \mathcal{H}(h_0, \underbrace{p_1 p_2 ... p_{16}}_{1,\ ...,\ 16} \underbrace{\text{00 00 00 00}}_{17,\ ...,\ 20} \underbrace{r}_{21} \underbrace{\text{80}}_{22} \underbrace{\text{00 00 ... 00}}_{23,\ ...,\ 63} \underbrace{\text{A8}}_{64}). \end{aligned}\]

For the second call, we let $s_1 = \text{00}, s_2 = x, s_3 = \text{80}, s_4 = \text{A8}$, and let $\sigma$ be:

pbox = [0, 1, 2, ..., 15, 16, 16, 16, 16, 17, 18, 16, 16, ..., 16, 19, 20]
#       0  1  2       15  16  17  18  19  20  21  22  23  ...  62  63  64

Denote the above $\sigma$ by $\sigma^*$. The permutated password is 65 bytes long, thus there will be two blocks supplied to the Merkle-Damgard scheme. In this case, suppose that $h_1'$ and $h_2'$ are the intermediate and the final hashes. We denote the pepper this time to be $r'$ (which may or may not equal to $r$):

\[\begin{aligned} h_1' &= \mathcal{H}(h_0, \underbrace{p_1 p_2 ... p_{16}}_{1,\ ...,\ 16} \underbrace{s_1 s_1 s_1 s_1}_{17,\ ...,\ 20} \underbrace{s_2}_{21} \underbrace{s_3}_{22} \underbrace{s_1 s_1 ... s_1}_{24,\ ...,\ 63} \underbrace{s_4}_{64}) \\ &= \mathcal{H}(h_0, \underbrace{p_1 p_2 ... p_{16}}_{1,\ ...,\ 16} \underbrace{\text{00 00 00 00}}_{17,\ ...,\ 20} \underbrace{x}_{21} \underbrace{\text{80}}_{22} \underbrace{\text{00 00 ... 00}}_{24,\ ...,\ 63} \underbrace{\text{A8}}_{64}). \\ h_2' &= \mathcal{H}(h_1', \underbrace{r'}_{65} \underbrace{\text{00 00 ... 00}}_{66,\ ...,\ 126} \underbrace{\text{02}}_{127} \underbrace{\text{08}}_{128}) \end{aligned}\]

The goal is to check whether $r = x$. If it happens, we have $h_1 = h_1'$. We can compute $t_0, t_1, ..., t_{255}$ from $h_1$ with:

\[t_{j} := \mathcal{H}(h_1, \underbrace{j}_{65} \underbrace{\text{00 00 ... 00}}_{66,\ ...,\ 126} \underbrace{\text{02}}_{127} \underbrace{\text{08}}_{128})\]

If there is a $j \in \{0, 1, ..., 255\}$ such that $h_2' = t_j$, then we can say that either

1. $r = x$, or
2. we found a hash collision for SHA-256 (which is far more unlikely)

Improving the probability by increasing the number of calls⌗

Unfortunately, with two calls the probability of finding $r = x$ would be $1/256$, which is pretty infeasible. However, the probability can be increased to around 64% if we send 32 calls in the below way:

1. 🕵️ 16 times with $\sigma$ being the identity permutation and $s_1 = s_2 = s_3 = s_4 = \text{00}$ and put the hash outputs in the set $\mathcal{U}$.
2. For $k = \text{00}, \text{01}, \text{02}, ..., \text{0F}$, 🕵️ with $\sigma = \sigma^*$, and $s_1 = \text{00}, s_2 = k, s_3 = \text{80}, s_4 = \text{A8}$. Let $v_k$ be the hash output.

If there exists $h \in \mathcal{U}, v_r$ and $j \in \{0, 1, ..., 255\}$ such that the below expression holds, then we know that the pepper used for obtaining $h$ is $r$:

\[v_k := \mathcal{H}(h, \underbrace{j}_{65} \underbrace{\text{00 00 ... 00}}_{66,\ ...,\ 126} \underbrace{\text{02}}_{127} \underbrace{\text{08}}_{128})\]

Recovering the password character-by-character⌗

Now we have a hash $h$ which is computed from a known pepper $r$. The remaining issue would be pretty evident, yet a bit different from the predecessor. If we want to retrieve $p_n$, we can let $s_1 = \text{00}, s_2 = r, s_3 = \text{80}, s_4 = \text{A8}$ and set $\sigma$ to be

pbox = [0, 1, 2, ..., 15, 16, 16, 16, 16, 17, 18, 16, 16, ..., 16, 19, n,  20]
#       0  1  2       15  16  17  18  19  20  21  22  23  ...  62  63  64  65

Eventually, we recovered the password and can successfully get the flag via 🖥️.

hkcert21{1t_d03sn7_h31p_by_4dd1n9_p3pp3r5}