kurenaif 1K Subscriptions Challenges

On 13 February, 2021, kurenaif (@fwarashi) has released five challenges celebrating the 1000-subscription in the YouTube channel¹. 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.

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$.

Since we are given 50 bits, we are able to a possible range of $x_{310}$ (there are around 2¹⁴ 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-independent². 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 2³², which is too much), and luckily the key can be recovered in around 22 minutes with pypy3. kurenaifCTF{twice_reloaded_mersenne_twister}.

My Gist