HKCERT CTF 2024 Quals Writeup (I): RSA LCG and Pigeon Post

Black Bauhinia co-organizes the HKCERT CTF for the fifth year. I wrote 18 challenges (in 11 series) this year and here is a series of blog posts covering all of them. I will cover two cryptography series in the first part: RSA LCG and Pigeon Post.

The numbers in the “Solves” column are the number of solves in the secondary, tertiary, open and international divisions respectively. There are 165, 75, 131 and 817 teams respectively in the four categories.

RSA LCG (0)⌗

Challenge Summary⌗

Mandela once said, “Don’t generate RSA primes with insecure PRNGs”. As a LCG-holic, I am not going to listen to him. What will go wrong?

Note: There is a step-by-step guide to the challenge.

Attachment: rsalcg-0_da1eb1b1ce5e8a986adab74b60656f81.zip

We are given the RSA public key $(n, e)$ and an encrypted flag encrypted by the key. The primes for the public modulus $n$ are generated by a LCG (linear congruential generator) with the below function:

def get_prime(lcg, bits):
    while True:
        p = 0
        for i in range(bits//lcg.bits):
            p <<= lcg.bits
            p |= lcg.next()

        if p.bit_length() != bits: continue
        if not is_prime(p): continue

        return p

In this challenge, a LCG is given by $x_{i+1} = (a x_i + c) \ \text{mod}\ 2^b$, and we are given $a, c, b$. Additionally, we are also given that $x_0$ (the seed) is odd and $0 < x_0 < 2^{16}$. The goal is to recover the flag.

Solution⌗

We know that the seed is at most 16-bit long, and it is odd. Therefore the possible seeds are 1, 3, 5, …, 65535.

There is a solve script in the attachment, which enumerates all the possible seeds and checks whether the generated $n$ is correct. If so, we will simply compute $\phi(n)$ and also the private modulus $d$. The given solve script takes approximately 8 hours to finish because get_prime(lcg, bits=1024) is slow.

The solution provided in the walkthrough suggested generating one prime (namely $p$) per seed. If $n$ is a multiple of $p$, then the seed is the seed used to generate the outputs. In that case, we can retrieve the flag in about two hours:

hkcert24{0k4y_th1s_1s_n0t_ev3n_vu1n3r4b1e_b3c4u5e_0f_1cgs}

Although it works, is_prime is time-consuming and we don’t have to check whether a number generated is prime. If the generated $p$ is a factor of $n$, we can claim also that the seed generated is correct. The running time is then reduced to two minutes.

def main():
    lcgs = [LCG(bits=128, a=181525535962623036141846439269075744717, c=115518761677956575882056543847720910703, seed=seed) for seed in range(1, 2**16, 2)]
    n = SNIPPED # 4811...8689
    e = SNIPPED # 65537
    c = SNIPPED # 3459...2291

    for lcg in track(itertools.cycle(lcgs)):
        p = generate_number(lcg, 1024)
        if p.bit_length() != 1024: continue
        if n % p != 0: continue
        break

    ps = [p] + [get_prime(lcg, 1024) for _ in range(3)]
    phi = (ps[0] - 1) * (ps[1] - 1) * (ps[2] - 1) * (ps[3] - 1)
    d = pow(e, -1, phi)
    m = pow(c, d, n)
    flag = int(m).to_bytes((int(m).bit_length()+7)//8, 'big')
    print(f'{flag = }')

RSA LCG (1)⌗

Challenge Summary⌗

Lu Xun once said, “Don’t generate RSA primes with insecure PRNGs”. As a LCG-holic, I am not going to listen to him. What will go wrong?

Attachment: rsalcg-1_4ac18c5a078fd5f5df7a11f16a47a919.zip

This challenge is similar to RSA LCG (0). We are still given $a, c, b$, but $c = 0$ and $x_0$ is 256 bits long. The goal is to recover the flag.

lcg = LCG(
  bits=256,
  a=102197201962123846389438942955101245465045811321520032783251514372432272871077,
  c=0
)

Solution⌗

Suppose that $x_0$ is the unknown seed of the LCG. Let $x_1, x_2, …$ be its outputs, and $p_1, p_2, p_3, p_4$ be the prime factors of the public modulus $n$.

Here $p_i = 2^{768} x_{4k_i+1} + 2^{512} x_{4k_i+2} + 2^{256} x_{4k_i+3} + x_{4k_i+4}$ for $i = 1, 2, 3, 4$.

In this challenge, we have $x_n = a^n x_0\ \text{mod}\ 2^{256}$ since $c = 0$.

$$ \begin{aligned} n & \equiv p_1 \cdot p_2 \cdot p_3 \cdot p_4 \\ & \equiv x_{4k_1+4} \cdot x_{4k_2+4} \cdot x_{4k_3+4} \cdot x_{4k_4+4} \\ & \equiv a^{4k_1+4} x_0 \cdot a^{4k_2+4} x_0 \cdot a^{4k_3+4} x_0 \cdot a^{4k_4+4} x_0 \\ & \equiv a^{4k_1+4k_2+4k_3+4k_4+16} x_0^4 \ (\text{mod}\ 2^{256}) \end{aligned} $$

We can exhaust $k := 4k_1+4k_2+4k_3+4k_4+16$ and solve the quartic polynomial

$$x_0^4 \equiv a^{-k} \cdot n \ (\text{mod}\ 2^{256})$$

for the possible seeds. For each candidate, we can simply generate the primes with that seed and see if the resulting $n$ is the given public modulus.

RSA LCG (2)⌗

Challenge Summary⌗

Einstein once said, “Don’t generate RSA primes with insecure PRNGs”. As a LCG-holic, I am not going to listen to him. What will go wrong?

Attachment: rsalcg-2_e3e055ff4893dcc6392f71b1e6adfbeb.zip

This challenge is similar to RSA LCG (0) and (1), except that $a = 1$. The goal is to recover the flag.

lcg = LCG(
  bits=256,
  a=1,
  c=14258939715516539295587731120991968901228171455016001595761489750577784177213
)

Solution⌗

Finding the possible values for $p_i$ under a modulus⌗

In this challenge, $a = 1$. Thus $x_k = x_0 + kc\ (\text{mod}\ 2^{256})$.

Remarkably, $x_{k+1}$ would either be $x_k + c$ or $x_k + c - 2^{256}$. We can denote that by $x_{k+1} = x_k + c - 2^{256} \cdot y_k$, with $y_k \in {0, 1}$.

We take a closer look to

$$ \begin{aligned} p_i &= 2^{768} x_{4k_i + 1} + 2^{512} x_{4k_i + 2} + 2^{256} x_{4k_i + 3} + x_{4k_i + 4} \\ &= 2^{768} x_{4k_i + 1} + 2^{512} (x_{4k_i + 1} + c - 2^{256} y_{4k_i + 1}) \\ &\qquad + 2^{256} [x_{4k_i + 1} + 2c - 2^{256} (y_{4k_i + 1} + y_{4k_i + 2})] \\ &\qquad + [x_{4k_i + 1} + 3c - 2^{256} (y_{4k_i + 1} + y_{4k_i + 2} + y_{4k_i + 3})] \\ &= (2^{768} + 2^{512} + 2^{256} + 1) x_{4k_i + 1} + (2^{512} + 2 \cdot 2^{256} + 3)c \\ &\qquad - (2^{768} + 2^{512} + 2^{256})y_{4k_i+1} - (2^{512} + 2^{256})y_{4k_i+2} - 2^{256}y_{4k_i+3} \end{aligned} $$

We can eliminate $x_{4k_i + 1}$ by taking modulo $q := 2^{768} + 2^{512} + 2^{256} + 1$:

$$ \begin{aligned} p_i \equiv (2^{512} + 2 \cdot 2^{256} + 3) c- (2^{768} + 2^{512} + 2^{256})y_{4k_i + 1} - (2^{512} + 2^{256})y_{4k_i + 2} - 2^{256}y_{4k_i + 3} \ (\text{mod}\ q). \end{aligned} $$

The only unknowns here would be $y_{4k_i + 1}, y_{4k_i + 2}, y_{4k_i + 3} \in {0, 1}$, and this implies that there are only 8 possible values for $p_i \ \text{mod}\ q$.

By exhausing all of the $y_{4k_i + j}$’s ($i = 1, 2, 3, 4$ and $j = 1, 2, 3$) and checking against $n \equiv p_1 \cdot p_2 \cdot p_3 \cdot p_4\ (\text{mod}\ q)$, we can filter out a list of possible $p_i$’s such that $p_i\ \text{mod}\ q$.

Finding the gaps⌗

Let $a_i = p_i \ \text{mod}\ q$. We would like to find $k_1, k_2, k_3$ and $k_4$.

$$ p_i = x_{4k_i + 1}q + a_i = (x_1 + 4k_ic - 2^{256} z_i) \cdot q + a_i. $$

Here $0 \leq z_i \leq 4k_i$.

Taking modulo $q^2$ on $n = p_1 \cdot p_2 \cdot p_3 \cdot p_4$, we have a linear congruence

$$ b_1q \cdot x_1 + b_2q \cdot z_1 + \dots + b_5q \cdot z_4 + b_6q \cdot k_1 + \dots + b_9q \cdot k_4 + b_{10}q \ \equiv 0 \ (\text{mod}\ q^2) $$

where $x_1, z_1, z_4, k_1, …, k_4$ are unknowns defined above and $b_1, b_2, …, b_{10}$ are constants (not computed for simplicity). We can divide the whole equation by $q$ and obtain

$$ b_1 \cdot x_1 + b_2 \cdot z_1 + … + b_5 \cdot z_4 + b_6 \cdot k_1 + … + b_9 \cdot k_4 + b_{10} \ \equiv 0 \ (\text{mod}\ q) $$

We estimate that $z_i, k_i \approx 2^{10}$ with the prime number theorem. The above linear congruence has 768 bits of information and $256 + 10 \cdot 8 = 336$ bits of unknown. We then can use LLL to recover the unknowns.

$$ \left[\begin{matrix} b_1 & 1 & & & \\ b_2 & & 1 & & \\ \vdots & & & \ddots & \\ b_{10} & & & & 1 \\ q & & & & \\ \end{matrix}\right] $$

The target vector would be $[0, x_1, z_1, z_2, z_3, z_4, k_1, k_2, k_3, k_4, 1]$.

Post-mortem: Solving some variants⌗

After the competition, grhkm mentioned that brute-force is doable. We discussed some variants and checked which would be solvable by the two approaches.

Denote the three parameters by $\alpha$, $\beta$, $\gamma$, defined by:

• $\alpha$ is the number of bits of each of the primes,
• $\beta$ is the number of bits of the LCG outputs, and
• $\gamma$ is the number of primes used for the RSA modulus

The three parameters would appear below in the source code of the challenge:

if __name__ == '__main__':
    FLAG = os.environb.get(b'FLAG', b'hkcert24{***REDACTED***}')

    lcg = LCG(bits=β, a=1) # 👈 β

    print(f'{lcg = }')

    ps = [get_prime(lcg, bits=α) for _ in range(γ)] # 👈 α and γ
    n = reduce(mul, ps)
    e = 0x10001

    m = int.from_bytes(FLAG, 'big')
    c = pow(m, e, n)

    print(f'{n = }')
    print(f'{e = }')
    print(f'{c = }')

LLL worked in all of the below variants:

1. $\alpha = 1024$, $\beta = 256$, $\gamma = 4$ (the original setting).
2. $\alpha = 2048$, $\beta = 512$, $\gamma = 4$.
3. $\alpha = 1024$, $\beta = 256$, $\gamma = 8$.
4. $\alpha = 1024$, $\beta = 128$, $\gamma = 4$.

RSA LCG (3)⌗

Challenge Summary⌗

Mona Lisa once said, “Don’t generate RSA primes with insecure PRNGs”. As a LCG-holic, I am not going to listen to her. What will go wrong?

Attachment: rsalcg-3_2650a0f5d36a4474c939126200e68849.zip

This challenge is similar to RSA LCG (0), (1) and (2), except that $x_0 \equiv 1 \ (\text{mod}\ 2^{128})$. The goal is to recover the flag.

lcg = LCG(
  bits=256,
  a=14766004292360945258404852367497617471774948936126805425073927394403062559771,
  c=101392444572529008969348961056906071660419768871029068095780498478077435335658
)

Solution⌗

Finding the gaps⌗

Since $x_0 \equiv 1 \ (\text{mod}\ 2^{128})$ and $x_k \equiv a^k x_0 + (1 + a + \dots + a^{k-1}) \cdot c \ (\text{mod}\ 2^{256})$, we have

$$ x_k \equiv a^k + (1 + a + \dots + a^{k-1}) \cdot c\ (\text{mod}\ 2^{128}). $$

Let $p_i \equiv 5^{d_i} \ (\text{mod}\ 2^{128})$ and $n \equiv 5^d\ (\text{mod}\ 2^{128})$ for some $d, d_1, d_2, d_3, d_4$. Also, $5$ has order $2^{126}$, so we have

$$ \begin{aligned} & 5^d \equiv n \equiv p_1 \cdot p_2 \cdot p_3 \cdot p_4 \equiv 5^{d_1} \cdot 5^{d_2} \cdot 5^{d_3} \cdot 5^{d_4} \equiv 5^{d_1 + d_2 + d_3 + d_4} \ (\text{mod}\ 2^{128}). \\ & \qquad \Longrightarrow d \equiv d_1 + d_2 + d_3 + d_4 \ (\text{mod}\ 2^{126}) \end{aligned} $$

We can also explicitly find $0 \leq d < 2^{126}$ such that $5^d \equiv n \ (\text{mod}\ 2^{128})$. Now only $d_1$, $d_2$, $d_3$ and $d_4$ are unknown.

Additionally, as $p_i = 2^{768} x_{4k_i+1} + 2^{512} x_{4k_i+2} + 2^{256} x_{4k_i+3} + x_{4k_i+4}$,

$$ 5^{d_i} \equiv p_i \equiv x_{4k_i + 4} \ (\text{mod}\ 2^{128}) \Longrightarrow d_i \equiv \log x_{4k_i + 4}\ (\text{mod}\ 2^{126}). $$

Also, $k_i$’s should be small ($\approx 4 \cdot 2^{10}$) according again to the prime number theorem. We can rearrange the terms such that there are two unknowns per side:

$$ d - d_1 - d_2 \equiv d_3 + d_4\ (\text{mod}\ 2^{126}). $$

We thus can recover $(k_1, k_2, k_3, k_4) = (595, 1597, 2848, 3158)$ with the meet-in-the-middle approach – this reduces the time complexity to $\mathcal{O}(k^4)$ to $\mathcal{O}(k^2)$. With $d_i$’s, we can recover $p_i\ \text{mod}\ 2^{128}$.

Recovering the seed⌗

After that, we want to recover $x_0$ from the $k_i$’s. The relation below is a degree four polynomial with $x_0$ being its only unknown:

$$ n \equiv \prod_{i=1}^4 x_{4k_i + 4} \equiv \prod_{i=1}^4 [a^{4k_i+4} \cdot x_0 + (1 + a + \dots + a^{4k_i+3}) \cdot c]\ (\text{mod}\ 2^{256}). $$

Thus, we can solve for $x_0$ under modulo $2^{256}$. There are multiple possible $x_0$, but only one of them is the correct seed:

x0 = 0xd3e29c8b17c4aafe25d58c16003611a300000000000000000000000000000001

We are able to recover all the $p_i$’s with the correct seed. Finally, we can compute the private exponent, $d$, and decrypt the ciphertext:

hkcert24{i5_th1s_y3t_4n0th3r_l33tc0d3_f0ur_sum_qu3s71on?}

Pigeon Post (1)⌗

Challenge Summary⌗

In 1860, our antagonists Alice and Byron are trying to communicate. As the pigeon, you are the one who carry the messages between. To prevent that the message being eavesdropped, they were running a key exchange protocol and communicate encrypted afterwards.

You are convinced by our protagonist, Ozetta to get the secret message from their communication. Isn’t the secret encrypted?

Note: There is a step-by-step guide to the challenge.

Attachment: pigeon-1_8223e865166251a956801a7112fe3dad.zip

We act as the pigeon-in-the-middle between Alice and Byron. They will run a handshake protocol (using the Diffie-Hellman key exchange algorithm) and establish secure communication (using AES-CTR). As the pigeon, our objective is to intercept the communication and retrieve the flag.

Solution⌗

As a pigeon in the middle, we can interrupt the handshake process. Instead of sending Alice’s public key to Byron, and Byron’s public key to Alice, we can send our public key, $P := g^p\ \text{mod}\ p$ to them (here $P$ and $p$ are our public and private key).

With that, the shared key between Alice and us would be

$$ s_\text{AP} \equiv g^{ap} \ (\text{mod}\ p). $$

More importantly, we can derive the shared key ourselves. Thus we can decrypt the messages from Alice, and encrypt the messages back. This also happens in the communication between Byron and us.

While Alice thinks she is talking to Byron securely, her messages are actively eavesdropped by us. We can decrypt the message from Alice using the key $s_\text{AP}$, encrypt it with $s_\text{BP}$ and send it to Byron (and the other way round). With that, we can decrypt the second message from Alice for the flag:

hkcert24{y0u_n33d_t0_4u7h3n71a73_th3_0th3r_p4r7y_s3cur31y_t0_4v01d_7h3_p1ge0n_1n_th3_m1dd13}

Pigeon Post (2)⌗

Challenge Summary⌗

In 1861, our antagonists Alice and Byron noticed that Ozetta is actively sniffing their messages. They decided to look for you for transmitting their messages, but this time they have already come up with a key beforehand.

Can you retrieve their secret this time?

Attachment: pigeon-2_89c2d274e99f6ce5f776b691869a83ad.zip

This challenge is similar to the last part, except that the handshake is already initiated. In this case, we are no longer able to impersonate ourselves as Alice to Byron, nor Byron to Alice.

Solution⌗

We can intercept the messages between Alice and Byron. If the pigeon in the middle is benign, this is what Alice and Byron communicate:

Byron → Alice: what is the flag? I have the secret [SECRET]
Alice → Byron: the flag is hkcert24{...}
Byron → Alice: nice flag!
Alice → Byron: :)

On the other hand, below is the conversation if Alice sends a corrupted flag:

Alice → Byron: the flag is [CORRUPTED]
Byron → Alice: too bad...
Alice → Byron: what happened?

As the pigeon, we can distinguish the encrypted what happened? from :) by looking at the length of its ciphertext. The lengths would respectively be 22 and 10.

Notably, the nonce for the CTR mode is used to generate keystreams deterministicly. Additionally, if we have a ciphertext $c_1$ which corresponds to the message $m_1$, we can change $m_1$ to $m_2 := m_1 \oplus d$ by xorring $d$ on the 9th byte and onwards. Mathematically:

$$ \left\{\begin{aligned} & c_1 = \text{nonce} \ \| \ (m \oplus k) \\ & c_2 = \text{nonce} \ \| \ (m \oplus d \oplus k) \end{aligned}\right. $$

For instance, if the ciphertext $c_1$ below corresponds to the message hkcert24{X, then $c_2$ would decrypt into hkcert24{}, as $\texttt{58} \oplus \texttt{7d} = \texttt{25}$:

c1 = bytes.fromhex('0000000000000000 000000000000000000 00')
c2 = bytes.fromhex('0000000000000000 000000000000000000 25')

When Byron receives the ciphertexts, he will respond too bad... and nice flag! respectively. We then can replay the messages to Alice to deduce whether this is a valid flag.

To recover the first byte of the flag, we can truncate the ciphertext to 18 bytes and exhaust the last byte of the ciphertext.

As an example, assume that a ciphertext for the flag is $\texttt{000000}\dots\texttt{00}$:

c = bytes.fromhex('0000000000000000 000000000000000000 00') # hkcert24{0 - ❌
c = bytes.fromhex('0000000000000000 000000000000000000 01') # hkcert24{1 - ❌
# ...
c = bytes.fromhex('0000000000000000 000000000000000000 4d') # hkcert24{} - ✅

After that, we can truncate the ciphertext to 19 bytes, and exhaust the last byte to retrieve the second byte. Repeating the process, we will receive the flag:

hkcert24{0n3_c4n_4ls0_l34k_1nf0rm4710n_fr0m_th3_l3n9th}