Credits. Thumbnail credit goes to Quasar! 🎉

vss is an interesting crypto challenge in BalsnCTF, which ended up having 9 solves. I took around 2.5 hours to solve the challenge. This challenge reminds me the yet another PRNG challenge from pbctf 2021 (challenge description, writeup written by @maple3142 and @rkm0959), but with a setting which looked harder. I was pretty surprised that LLL worked, too.

lfsr is another crypto challenge in BalsnCTF with 6 solvers. In the challenge, the output bits are computed nonlinearly from the LFSR states. Given that I knew almost nothing about LFSR, I just came up with the attack by myself… Well, I am not quite a paper guy and I couldn’t read.

vss⌗

Challenge Summary⌗

When connected to the server, two 512-bit numbers $x, y$ will be generated. We are allowed to get up to around 180 sets of $(a_i, b_i, c_i, p_i, g_i, v_i, q_i)$ such that:

  1. $u_i = (a_i + b_ix + c_iy)\ \text{mod}\ p_i$, and
  2. $v_i = g_i^{u_i}\ \text{mod}\ q_i$.

The goal is to recover $x$ and $y$.

Why 180 sets of data? Although not explicitly mentioned in the challenge, there is a 30-second timeout for the remote connection. You can only get around 180 sets of $(a_i, b_i, c_i, p_i, g_i, v_i, q_i)$ within the timeout.

Solution⌗

TL;DR. My approach, like 95% of the crypto challenges I solved, uses LLL.

Part I: Discrete log for the win?⌗

After understanding the challenge statement, I immediately think that we can generate until $q_i-1$ is smooth. In that way, we can easily recover $u_i$ from $v_i, g_i$ and $q_i$ using Pohlig-Hellman algorithm. Unfortunately, generating such primes is hard. I generated around 20K sets and none of the $q_i-1$ is $2^{24}$-smooth (i.e., all the prime factors are not greater than $2^{24}$).

With that said, finding one such $q_i$ is difficult. What makes the situation worse is that we actually need two such $q_i$’s to recover $x$ and $y$.

Part II: Taking a step backwards⌗

We are forced to give up recovering a full $u_i$ because discrete log is difficult. Good that we can still recover part of it. Assume that we know

$$q-1 = {r_1}^{k_1} {r_2}^{k_2} … {r_m}^{k_m} s$$

with $r_1, r_2, …, r_m$ are small primes (for instance, they are all smaller than $2^{24}$). Denote $\gamma = {r_1}^{k_1} {r_2}^{k_2} … {r_m}^{k_m}$ and we can recover $v := u\ \text{mod}\ \gamma$ using Pohlig-Hellman. Let’s formulate what we have for now. We have multiple tuples $(a_i, b_i, c_i, v_i, p_i, \gamma_i)$ such that

$$v_i = a_i + b_i{\color{red}x} + c_i{\color{red}y}\ \text{mod}\ p_i\ \text{mod}\ \gamma_i.$$

If we intend not writing the whole thing using modulo, we will introduce two more unknown, integral variables $(s_i, t_i)$:

$$v_i = a_i + b_i{\color{red}x} + c_i{\color{red}y} - p_i{\color{red}s_i} - \gamma_i{\color{red}t_i},$$

with $0 \leq t_i < p_i / \gamma_i$. If we look at the modular congruence modulo $p_i$, then we have

$$a_i - v_i + b_i{\color{red}x} + c_i{\color{red}y} - \gamma_i{\color{red}t_i} \equiv 0 \ (\text{mod}\ p_i).$$

Suppose that we have 40 sets of $(a_i, b_i, c_i, v_i, p_i, \gamma_i)$ such that $\gamma_i > 2^{32}$. Assuming each congruence carries 512 bits of information, then we have $512 \times 40 = 20480$ bits of information. We also have $512 \times 2 + 480 \times 40 = 20224$ bits of unknown because $x, y$ is of 512 bits and each of the $t_i$’s is of 480 bits long. Since we have more information than the unknown, we can apply LLL to solve the system - below is the lattice:

$$A = \left[\begin{array}{cccc|ccc|cccc} a_1 - v_1 & a_2 - v_2 & \dots & a_{40} - v_{40} & 1 & & & & & & \\ b_1 & b_2 & \dots & b_{40} & & 1 & & & & & \\ c_1 & b_2 & \dots & c_{40} & & & 1 & & & & \\ \hline -r_1 & & & & & & & 1 & & & \\ & -r_2 & & & & & & & 1 & & \\ & & \ddots & & & & & & & \ddots & \\ & & & -r_{40} & & & & & & & 1 \\ \hline -p_1 & & & & & & & & & & \\ & -p_2 & & & & & & & & & \\ & & \ddots & & & & & & & & \\ & & & -p_{40} & & & & & & & \end{array}\right].$$

The lattice spans the vector $\mathbf{v} = \left[\begin{array}{cccc|ccc|c}0 & 0 & \dots & 0 & 1 & x & y & l_1 & l_2 & \dots & l_{40} \end{array}\right]$ because

$$\begin{aligned} & \left[\begin{array}{cccc|ccc|cccc}0 & 0 & \dots & 0 & 1 & x & y & l_1 & l_2 & \dots & l_{40} \end{array}\right] \\ & \qquad = \left[\begin{array}{ccc|cccc|cccc}1 & x & y & l_1 & l_2 & \dots & l_{40} & t_1 & t_2 & \dots & t_{40} \end{array}\right] \cdot A \end{aligned}$$

$\mathbf{v}$ can be found applying LLL if we set appropriate weights. LLL for the win! We can recover $x$ and $y$ and thus the flag: BALSN{commitments_leak_too_much_QwQ}.

lfsr⌗

Challenge Summary⌗

Note. In the challenge, the operations are done in $\text{GF}(2)$. That said, $+$ is actually the $\oplus$ (XOR) operation and $\times$ is the AND operation.

Let $\mathcal{L}$ be a LFSR with key $(s_0, s_1, …, s_{127})$, and for $i \geq 0$,

$$s_{i+128} = s_{i} + s_{i+1} + s_{i+2} + s_{i+7}.$$

Let the output bits $y_0, y_1, …$ defined by

$$\begin{aligned} y_i &= s_i + s_{i+16} + s_{i+32} + s_{i+120} + s_i s_{i+8} + s_i s_{i+32} + s_{i+8} s_{i+64} + s_{i+16} s_{i+32} \\ &\qquad + s_i s_{i+8} s_{i+64} + s_{i+16} s_{i+32} s_{i+64} + s_i s_{i+8} s_{i+16} s_{i+64} s_{i+120} + s_{i+8} s_{i+16} s_{i+32} s_{i+64} s_{i+120}. \end{aligned}$$

We are given the first 8192 bits of the output (i.e., $y_0, y_1, …, y_{8191}$). The goal is to recover the key (i.e., $s_0, s_1, …, s_{127}$).

Solution⌗

Part I: Why multiple of eight?⌗

Let $y_i := b(s_i, s_{i+8}, s_{i+16}, s_{i+32}, s_{i+120})$ for simplicity.

We can see that, for instance, $y_0$, depends on $s_0, s_8, s_{16}, s_{32}, s_{64}$ and $s_{120}$. The indexes of the states are all multiples of eight. Furthermore, this happens on $y_{8i}$ every every integer $i$:

$$\begin{aligned} y_{8i} &= b(s_{8i}, s_{8(i+1)}, s_{8(i+2)}, s_{8(i+4)}, s_{8(i+15)}). \end{aligned}$$

We have $y_0, y_8, …, y_{8 \times 1023}$. Combining above, we have 1024 equations with 1039 unknowns (the unknowns being $s_0, s_8, …, s_{8 \times 1038}$). Therefore, it is expected to get around $2^{15}$ possible sets of $s_0, s_8, …, s_{8304}$ from $y_0, y_8, …, y_{8184}$.

Similarly, we can use $y_1, y_9, …, y_{8185}$ to recover $s_1, s_9, …, s_{8305}$, use $y_2, y_{10}, …, y_{8186}$ to recover $s_2, s_{10}, …, s_{8306}$ and so on.

$2^{15}$ is not an accurate estimate! In average, there are far more than $2^{15}$ such $s_i$’s from those $y_i$’s when the number of terms increases. Fortunately the number of $s_i$’s does not affect a lot on the solution.

Now back to the topic. How do we get $s_0, s_8, …, s_{8(l-1)}$ from $y_0, y_8, …, y_{8(l-16)}$? We can perform a search (breadth-first search here):

  1. Initialize the solution list $\mathcal{S}$ with the $2^{15}$ elements: $(0, 0, 0, …, 0)$, $(0, 0, 0, …, 1)$, …, and $(1, 1, 1, …, 1)$.
  2. Let $\mathbf{s}$ be the first element in the list.
    If $\mathbf{s}$ has $l$ entries, return $\mathcal{S}$.
  3. Remove $\mathbf{s} = (\tilde s_0, \tilde s_8, …, \tilde s_{8(k+14)})$ from $\mathcal{S}$.
    For each $\tilde s_{8(k+15)} \in \{0, 1\}$, if $y_{8k} = b(\tilde s_{8k}, \tilde s_{8(k+1)}, \tilde s_{8(k+2)}, \tilde s_{8(k+4)}, \tilde s_{8(k+15)})$, append $(\tilde s_0, \tilde s_8, …, \tilde s_{8(k+14)}, \tilde s_{8(k+15)})$ to $\mathcal{S}$.
  4. Go back to step 2.

We know $(s_0, s_8, …, s_{8(l-1)}) \in \mathcal{S}$ because all the below equations hold:

$$\left\{\begin{aligned} y_0 &= b(s_0, s_8, s_{16}, s_{32}, s_{120}) \\ y_8 &= b(s_8, s_{16}, s_{24}, s_{40}, s_{128}) \\ & \qquad \vdots \\ y_{8(l-16)} &= b(s_{8(l-16)}, s_{8(l-15)}, s_{8(l-14)}, s_{8(l-12)}, s_{8(l-1)}). \end{aligned}\right.$$

Regarding the notation. I use $\tilde s_i$’s instead of $s_i$’s because they are not necessary the correct ones.

Part II: How to get the key from undecillions of $s_i$’s?⌗

Why undecillions? Suppose that we have $2^{15}$ sets of $s_0, s_8, …$, $2^{15}$ sets of $s_1, s_9, …$ and so on. There are $2^{15 \times 8} \approx 10^{36}$ sets of $s_0, s_1, s_2, …$ in total.

Let’s use the above algorithm to find these four sets of numbers:

  1. $(\tilde s_0, \tilde s_8, …, \tilde s_{504}, \tilde s_{512}, …, \tilde s_{632}) \in \mathcal{S}_0$ (80 terms),
  2. $(\tilde s_1, \tilde s_9, …, \tilde s_{505}) \in \mathcal{S}_1$ (64 terms),
  3. $(\tilde s_2, \tilde s_{10}, …, \tilde s_{506}) \in \mathcal{S}_2$ (64 terms), and
  4. $(\tilde s_7, \tilde s_{15}, …, \tilde s_{511}) \in \mathcal{S}_7$ (64 terms).
8192 bits? I don’t need that. The challenge can be solved 513 consecutive bits, ideally, with my approach.

Recall the state transition: $s_{i+128} = s_i + s_{i+1} + s_{i+2} + s_{i+7}$ for all integer $i \geq 0$. Let’s define a set $\mathcal{T}_0$ (transformed from $\mathcal{S}_0$) by:

$$\mathcal{T}_0 = \{(\tilde s_0 + \tilde s_{128}, \tilde s_8 + \tilde s_{136}, …, \tilde s_{504} + \tilde s_{632}) \in \{0, 1\}^{64} \ | \ (\tilde s_0, \tilde s_8, …, \tilde s_{632} \in \mathcal{S}_0)\}$$

We can see that

$$\left\{\begin{aligned} & \mathbf{t}_0 := (s_0 + s_{128}, s_8 + s_{136}, …, s_{504} + s_{632}) \in \mathcal{T}_0 \\ & \mathbf{s}_1 := (s_1, s_9, …, s_{505}) \in \mathcal{S}_1 \\ & \mathbf{s}_2 := (s_2, s_{10}, …, s_{506}) \in \mathcal{S}_2 \\ & \mathbf{s}_7 := (s_7, s_{15}, …, s_{511}) \in \mathcal{S}_7, \end{aligned}\right.$$

and eventually $\mathbf{t}_0 + \mathbf{s}_1 + \mathbf{s}_2 + \mathbf{s}_7 = (0, 0, …, 0)$.

We can precompute every $\tilde \mathbf{t}_{0,i} + \tilde \mathbf{s}_{1,j} \in \{0, 1\}^{64}$, where $\tilde \mathbf{t}_{0,i} \in \mathcal{T}_0$ and $\tilde \mathbf{s}_{1,j} \in \mathcal{S}_1$, and store all of them in the set $\mathcal{L}$. After that, we can check if there exists $i, j$ such that

$$\tilde \mathbf{t}_{0,i} + \tilde \mathbf{s}_{1,j} = \tilde \mathbf{s}_{2,k} + \tilde \mathbf{s}_{7,l},$$

for all $\tilde \mathbf{s}_{2,k} \in \mathcal{S}_2$ and $\tilde \mathbf{s}_{7,l} \in \mathcal{S}_7$. If that is the case (which is very rare!), we can try to recover $s_0, s_1, …, s_{127}$ and see if it generates the same output bits as given. After the key is recovered, then we can recover the flag: BALSN{almost_linear_too_easy}.