idekCTF 2022* Writeup

idekCTF 2022* definitely has a fun and inspiring set of cryptography challenges. I played with @blackb6a and we solved 8 of the 10 crypto challenges.

In this blog post, I’ll include my solution on three of them: Primonumerophobia (10 solves), Chronophobia (5 solves) and Decidophobia (3 solves).

Primonumerophobia⌗

Challenge Summary⌗

Let $T = \{0, 4, 6, 10, 16, 18, 24, 28, 30, 34, 36, 40, 42, 44, 45\}$. An initial state $(t_0, t_1, …, t_{46})$ with $t_0, t_1, …, t_{46} \in \{0, 1\}$ is generated and define

$$t_{i+47} = \bigoplus_{k \in T} t_{i+k} = t_i \oplus t_{i+4} \oplus … \oplus t_{i+45}$$

for $i \geq 0$. Two 512-bit primes $p$ and $q$ are generated by getting 512 consecutive bits from the LFSR state, i.e., $p$ and $q$ are the first two 512-bit primes in

$$\begin{aligned} v_0 & := 2^{511} t_0 + 2^{510} t_1 + … + t_{511} \\ v_1 & := 2^{511} t_{512} + 2^{510} t_{513} + … + t_{1023} \\ & \vdots \\ v_k & := 2^{511} t_{512k} + 2^{510} t_{512k+1} + … + t_{512k+511} \\ & \vdots \end{aligned}$$

It is given that $p = v_{1159}$ and $q = v_{1606}$. We are also given a RSA public key $n = pq$, $e = 65537$ and an encrypted flag $c$. The goal is to recover the flag.

n = 78189483779073760819769596415493404181115737255987326126790953924148600157623709942134043192581448967829591214999561812461790206591977861764710056434977125005626712442593271233036617073503751799983263888626278748439349756982639988997517983470845431197233107232933125334078771472039280629203017666578936360521
c = 39952631182502523101053953538875437560829302998610236142339435591980522271590392249355510253125310494063081880512061476177621613835835483055753316172267380484804011034657479491794064534740537749793563744927827732170347495398050941609682485707331552759412916426691849669362897656967530464847648838434750188588

Solution⌗

Assuming that the initial state is $t_0, t_1, …, t_{46}$. Then

$$\begin{cases} p = 2^{511} t_{593408} + 2^{510} t_{503409} + … + 2 t_{593919} \\ q = 2^{511} t_{822272} + 2^{510} t_{822273} + … + 2 t_{822783} \end{cases}.$$

Furthermore, for all $n \geq 0$, we can express $t_n$ in terms of $t_0, t_1, …, t_{46}$.

Since $p$ and $q$ are 512-bit primes, $t_{593408} = t_{593919} = t_{822272} = t_{822783} = 1$. We also can brute-force the lowest 24 bits of $p$ to obtain the lowest 24 bits of $q$. In that way, we have 50 bits of $t_j$’s:

• $t_{593408}$ (the MSB); $t_{593896}, t_{593897}, …, t_{593919}$ (the 24 lowest bits) from $p$, and
• $t_{822272}; t_{822760}, t_{822761}, …, t_{822783}$ from $q$.

If we let $(s_0, s_1, …, s_{49}) := (t_{593408}, t_{593897}, …, t_{822783})$ and write every $t_i$ in terms of $s_j$’s (i.e., change of basis), we can effectively obtain $\tilde{p}$ and $\tilde{q}$ (guesses for $p$ and $q$ in each brute force attempt) and check if they are the factors of $n$.

Effectively, we can recover the prime factors if $n$, compute the private key and decrypt the flag: idek{th3_prim3_g3n3r4ti0n_is_c001_but_n0t_s3cur3_QAQ}

p = 0x9b95ba6e07875ef81ac1f20401e93fd68f486f1023460f5430094c581fdf09bad2b88e7341af13ed6fc767f920786269223a3a99a9303b716c5ba754ff70c549
q = 0xb735588161082688a93c6cfc2b664dfae13c936979b29d5431c4da306a3e6d9cc371600318d17452e749702f9fd889709f18cec6fdb0c5eb93f13800889ce101

Chronophobia⌗

Challenge Summary⌗

Let $p, q$ be two 512-bit primes and let $n = pq$. Let also $k \in [128, 256]$ and $t \in [0, n)$. We are given $k$ and $t$. Denote $\text{f}(u)$ by

$$\text{f}(u) = u^{2^{2^k}}\ \text{mod}\ n.$$

We can send at most 1336 different $u$’s. Denote $v = \text{f}(u)$ and we will get the number of digits in $v$ and the first 200 digits of $v$. The goal is to compute $\text{f}(t)$ in 2 minutes.

Solution⌗

To start with, we can send $t, t^2, …, t^m$ to the server and obtain $\text{f}(t), \text{f}(t^2), …, \text{f}(t^m)$.

Let’s denote $v_i := \text{f}(t^i) = {\color{lightgreen}a_i} + {\color{pink}x_i}$ with $a_i$ and $x_i$ are respectively the known and the unknown digits of $v_i$. It is expected that $x_i$ has 360 bits and $a_i$ has 664 bits.

We can look at the below relation:

$$\text{f}(t^{i + j}) \equiv t^{2^{2^k} (i+j)} \equiv t^{2^{2^k} i} \cdot t^{2^{2^k} j} \equiv \text{f}(t^i) \cdot \text{f}(t^j) \quad (\text{mod}\ n).$$

If we substitute $a_i, a_j, a_{i+j}, x_i, x_j, x_{i+j}$ and denote $y_{ij} := x_i x_j$, we have

$$\begin{aligned} & a_{i+j} + x_{i+j} \equiv (a_i + x_i) \cdot (a_j + x_j) \equiv a_i a_j + a_i x_j + a_j x_i + x_i x_j \quad (\text{mod}\ n) \\ \Longrightarrow \quad & a_j {\color{pink}x_i} + a_i {\color{pink}x_j} -{\color{pink}x_{i+j}} + (a_i a_j - a_{i+j}) + {\color{pink}y_{ij}} \equiv 0 \quad (\text{mod}\ n) \end{aligned}$$

The above congruence has around $360 \times 3 + 720 \times 1 = 1800$ unknown bits while carrying $1024$ bits of information, which is clearly not enough. On the other hand, when $i = j$, we also have $1440$ and $1024$ bits of unknown and information, respectively.

$$2 a_i {\color{pink}x_i} - {\color{pink}x_{2i}} + (a_i^2 - a_{2i}) + {\color{pink}y_{ii}} \equiv 0 \quad (\text{mod}\ n).$$

However, the congruences above could give us more information than unknowns in the long run. Below is an example where we use four congruences with $x_1, x_2, x_3, x_4$:

$$\left\{\begin{array}{rcrcrcrcccc} 2 a_1 {\color{pink}{x_1}} & - & {\color{pink}{x_2}} & & & & & + & ({a_1}^2 - a_2) & \equiv & -{\color{pink}{y_{11}}} \\ a_2 {\color{pink}{x_1}} & + & a_1 {\color{pink}{x_2}} & - & {\color{pink}{x_3}} & & & + & (a_1 a_2 - a_3) & \equiv & -{\color{pink}{y_{12}}} \\ a_3 {\color{pink}{x_1}} & & & + & a_1 {\color{pink}{x_3}} & - & {\color{pink}{x_4}} & + & (a_1 a_3 - a_4) & \equiv & -{\color{pink}{y_{13}}} \\ & & 2 a_2 {\color{pink}{x_2}} & & & - & {\color{pink}{x_4}} & + & ({a_2}^2 - a_4) & \equiv & -{\color{pink}{y_{22}}} \\ \end{array}\right. \quad (\text{mod}\ n)$$

There are around $4320$ unknown bits and $4096$ information bits. With this idea, we can expand further and use six congruences with $x_1, x_2, …, x_5$. Let’s convert this into a lattice as an example:

$$\left[\begin{array}{cccc|ccccc} {a_1}^2 - a_2 & a_1 a_2 - a_3 & a_1 a_3 - a_4 & {a_2}^2 - a_4 & 1 & & & & \\ 2a_1 & a_2 & a_3 & & & 1 & & & \\ -1 & a_1 & & 2a_2 & & & 1 & & \\ & -1 & a_1 & & & & & 1 & \\ & & -1 & -1 & & & & & 1 \\ \hline n & & & \\ & n & & \\ & & n & \\ & & & n \\ \end{array}\right]$$

I expected to retrieve the vector

$$\left[\begin{array}{cccc|ccccc} -y_{11} & -y_{12} & -y_{13} & -y_{22} & 1 & x_1 & x_2 & x_3 & x_4 \end{array}\right]$$

if the size of the information is small enough. Since $4320 > 4096$, I did not expect it to work. However, I obtained a vector which could served as the correct solution:

$$\left[\begin{array}{cccc|ccccc} -y_{11} & -y_{12} & -y_{13}+x_4 & -y_{22}+x_4 & 1 & x_1 & x_2 & x_3 & 0 \end{array}\right].$$

As we can see, $x_4$ magically merged into $y_{13}$ and $y_{22}$. In this way the size of the unknown is smaller than the size of the information (i.e. $4320 - 360 = 3960 < 4096$). Effectively, we can obtain $x_1$ and compute the solution. This bring us the flag:

idek{St@rburst_str3@m!!!}

Decidophobia⌗

Challenge Summary⌗

[RSA] Define three 512-bit primes $p, q, r$ and let $n = pqr$. Let $m \in [0, 2^{1500})$, $e = 65537$ and $c = m^e\ \text{mod}\ n$. We are given $n$ and $c$.

[Oblivious transfer] On the other hand, define two 384-bit primes $P$ and $Q$ and let $N = PQ$. Let also $E = 65537$ and $E \cdot D \equiv 1 (\text{mod}\ \phi(N))$.

Let $x_1, x_2, x_3 \in [0, N)$. We are given $x_1, x_2$ and $x_3$. We are then asked to give an integer $v$. We will be given $c_1, c_2$ and $c_3$, where

$$\begin{cases} c_1 = \left(\left(v - x_1\right)^D + p\right)\ \text{mod}\ N \\ c_2 = \left(\left(v - x_2\right)^D + q\right)\ \text{mod}\ N \\ c_3 = \left(\left(v - x_3\right)^D + r\right)\ \text{mod}\ N \end{cases}.$$

The objective is to find $m$.

Solution⌗

When we set $v = x_1$, we can effectively make $c_1 = p$. However, we also have

$$\begin{cases} c_2 \equiv (v - x_2)^D + q \qquad (\text{mod}\ N) \\ c_3 \equiv (v - x_3)^D + r \qquad (\text{mod}\ N) \end{cases}.$$

Rearranging the terms, we have

$$\begin{cases} (c_2 - q)^E \equiv v - x_2 \qquad (\text{mod}\ N) \\ (c_3 - r)^E \equiv v - x_3 \qquad (\text{mod}\ N) \end{cases},$$

and the only unknowns here are $q$ and $r$. If we multiply $(pq)^E$ to the both side of the second equation, we then have $p^E q^E (v - x_3) \equiv (pq)^E (c_3 - r)^E \equiv (pqc_3 - n)^E$, thus having

$$(pc_3 {\color{pink}q} - n)^E - p^E (v - x_3) {\color{pink}q}^E \equiv 0 \qquad (\text{mod}\ N).$$

Now we have two polynomials $\text{f}$ and $\text{g}$ such that $\text{f}(q) \equiv \text{g}(q) \equiv 0 \ (\text{mod}\ N)$. Since the value of $\text{gcd}(\text{f}, \text{g})$ is likely to be $x-q$, we can effectively recover $q$ and fully factor $n$. Finally, we got the flag and the first blood 🩸!

idek{H0n3sty_1s_th3_b3st_p0l1cy?_N0p3_b3c4us3_w3_ar3_h@ck3rs!}