# kurenaif 1K Subscriptions Challenges

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

.

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

```
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 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-independent^{2}. 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^{32}, which is too much), and luckily the key can be recovered in around 22 minutes with pypy3. `kurenaifCTF{twice_reloaded_mersenne_twister}`

.