On 13 February, 2021, kurenaif (@fwarashi) has released five challenges celebrating the 1000-subscription in the YouTube channel1. Being locked at home in Lunar New Year, I have nothing else to do. Therefore I decided to attempt those challenges, which is available on GitHub.

Note. The writeup is actually compiled on the same day. It is published on 21 Feburary to not spoil the challenges.

p_p_rsa

Challenge Summary

In the challenge, we are given a RSA public key and an ciphertext $c$ (of message $m$). However, there is a twist that $n = p^2$. The objective is to recover $m$.

Solution

Since $n = p^2$, it is very simple to factorize $n$ by taking its square root. Also, $\varphi(n) = p(p-1)$. With this, we can compute $d$ and thus the message $m$: kurenaifCTF{phi_is_not_p-1_p-1}.

My Gist

redundant_rsa

Challenge Summary

In this challenge, we are given $n$, $c_3 := m^3\ (\text{mod}\ n)$ and $c_{65537} := m^{65537}\ (\text{mod}\ n)$. The objective is to recover $m$.

Solution

This is a simplified version of common modulus attack of RSA. In particular, since $21846 \times 3 - 65537 = 1$, we have

\[m \equiv m^{21846 \times 3 - 65537} \equiv (m^3)^{21846}\cdot m^{-65537} \equiv {c_3}^{21846}\cdot {c_{65537}}^{-1}\ (\text{mod}\ n).\]

With above, we are able to recover the flag: kurenaifCTF{you_4re_redundant_master}.

My Gist

the_big_five

Challenge Summary

In this challenge, we are given five consecutive values, i.e., $x_0, x_1, ..., x_4$ generated from the LCG. The objective is to predict the sixth, $x_5$.

Solution

Let's recall how the numbers from LCG are generated. If we have three constants $a, b, m$, then

\[x_{i+1} \equiv ax_i + b\ (\text{mod}\ m).\]

In particular, $m$ is a prime. To recover $x_5$, my approach is to recover $m, a, b$ in order.

Part I: Recovering $m$

To recover $m$, we try to eliminate $a$ and $b$ using the known variables.

\[ \begin{cases}\begin{aligned} x_2 - x_1 &\equiv a(x_1 - x_0) \\ x_3 - x_2 &\equiv a(x_2 - x_1) \\ x_4 - x_3 &\equiv a(x_3 - x_2) \end{aligned}\end{cases}\ (\text{mod}\ m). \]

Since $x_1 - x_0, x_2 - x_1, x_3 - x_2$ and $x_4 - x_3$ form a geometric sequence, we have

\[ \begin{cases}\begin{aligned} (x_2 - x_1)^2 &\equiv (x_1 - x_0)(x_3 - x_2) \\ (x_3 - x_2)^2 &\equiv (x_2 - x_1)(x_4 - x_3) \end{aligned}\end{cases}\ (\text{mod}\ m). \]

In this way, $(x_2 - x_1)^2 - (x_1 - x_0)(x_3 - x_2)$ and $(x_3 - x_2)^2 - (x_2 - x_1)(x_4 - x_3)$ are both multiples of $m$. Taking their GCD, we might have a small multiple of $m$. In this challenge, the GCD is already equal to $m = 176112297761995517109581492781981180247$.

Part II: Recovering $a$ and $b$

It is evident to recover $a$ and $b$. To recover them, we can simply compute

\[ \begin{aligned} a &= (x_2 - x_1)\cdot(x_1 - x_0)^{-1}\ (\text{mod}\ m), \\ b &= x_1 - ax_0\ (\text{mod}\ m). \end{aligned} \]

In this way,

\[ \begin{cases}\begin{aligned} a &= 113087371900439262017597367409533441772 \\ b &= 157951423074341581392962154768234193107 \end{aligned}\end{cases}. \]

As we have $m, a$ and $b$, we can recover $x_5 = 74994485449019875805749743810715945771$. Using it as the key and decrypting, we have kurenaifCTF{Less_numbers_are_better}.

My Gist

the_onetime_pad

Challenge Summary

In this challenge, we are given a 361-bit ciphertext (the bits are given by $c_0, c_1, ..., c_{360}$) that is xorred with keystream generated from a LCG, i.e.,

\[c_i = m_i \oplus k_i\ \forall i = 0, 1, ..., 360.\]

This time the modulus $m$ and the multiplier $a = 2$ of the LCG are given. However, only the lowest bit is returned each time. Mathematically,

\[ \begin{cases}\begin{aligned} x_i &= 2x_{i-1}\ \text{mod}\ m \\ k_i &= x_i\ \text{mod}\ 2 \end{aligned}\end{cases}. \]

It is also notable that the $m_{311} = m_{312} = ... = m_{360} = 0$.

Solution

In short, this is LSB oracle in disguise. Since $m_{311} = m_{312} = ... = m_{360} = 0$, we have $k_{311} = c_{311}, k_{312} = c_{312}, ..., k_{360} = c_{360}$. Maybe we can try to recover $x_{310}$?

Let's consider these two cases.

Case 1. Suppose that we have $0 \leq x_{310} < n/2$. Then $x_{311} = 2x_{310}$ and $k_{311} = 0$.
Case 2. Suppose that we have $n/2 \leq x_{310} < n$. Then $x_{311} = 2x_{310} - m$ and $k_{311} = 1$.

digraph {
  r_00[label="[0, n)"]
  r_10[label="[0, n/2)"]
  r_11[label="[n/2, n)"]
  r_20[label="[0, n/4)"]
  r_21[label="[n/4, n/2)"]
  r_22[label="[n/2, 3n/4)"]
  r_23[label="[3n/4, n)"]
  r_30[label="[0, n/8)"]
  r_31[label="[n/8, n/4)"]
  r_32[label="[n/4, 3n/8)"]
  r_33[label="[3n/8, n/2)"]
  r_34[label="[n/2, 5n/8)"]
  r_35[label="[5n/8, 3n/4)"]
  r_36[label="[3n/4, 7n/8)"]
  r_37[label="[7n/8, n)"]

  r_00->r_10[label=0]
  r_00->r_11[label=1]
  r_10->r_20[label=0]
  r_10->r_21[label=1]
  r_11->r_22[label=0]
  r_11->r_23[label=1]
  r_20->r_30[label=0]
  r_20->r_31[label=1]
  r_21->r_32[label=0]
  r_21->r_33[label=1]
  r_22->r_34[label=0]
  r_22->r_35[label=1]
  r_23->r_36[label=0]
  r_23->r_37[label=1]
}

Since we are given 50 bits, we are able to a possible range of $x_{310}$ (there are around 214 possibilities). From $x_{310}$, it is easy to recover $x_{-1}$ (the initial state) and generate the corresponding keystreams. We can exhaust all of them, and found that $x_{310} = 1251194628942649321$ is the correct state: kurenaifCTF{lowest_bit_oracle_is_funny}.

My Gist

three_values_twister

Challenge Summary

In this challenge, we are given 624th, 851th and 1078th number generated from mt_rand() via PHP 7.4.3. The objective is to find the 2048th number generated.

Solution

Well, the maximum possible value of mt_rand() is $2^{31}-1 = 2147483647$ and it is platform-independent2. We can simply exhaust the key space and try to decrypt the message. The key space can be exhausted in around 2.5 hours (my script iterates through 0 up to 232, which is too much), and luckily the key can be recovered in around 22 minutes with pypy3. kurenaifCTF{twice_reloaded_mersenne_twister}.

My Gist