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.
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}.
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}.
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}.
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^14^ 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}.
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, and luckily the key can be recovered in around 22 minutes with pypy3. We have the flag kurenaifCTF{twice_reloaded_mersenne_twister}.