No, we did not win. I see that coming and took a screenshot during the game.

BSides Ahmedabad CTF 2021 is organized by @zer0pts. That implies that players could spend a day happily working on the challenges. I enjoyed working on the challenges a lot. I'll go through the harder crypto challenges and the reversing challenge called Collapsed License in this blog post.

SSSS.RNG⌗

Challenge Summary⌗

Let $p$ be a 512-bit prime and $a, b, g_0 \in [2, p)$. Let $\mathcal{G}$ be a PRNG and let $g_k$ be the $k$-th output from $\mathcal{G}$, given by

\[g_k = (a\cdot g_{k-1} + b)\ \text{mod}\ p.\]

Let $\text{f}(x) := g_1 + g_2 x + g_3 x^2 + g_4 x^3 + g_5 x^4 + g_6 x^5$ be a polynomial over $\mathbb{Z}_p$. Suppose that we are given $p$, $\text{f}(1), \text{f}(2), \text{f}(3), \text{f}(4)$ and $c = \text{f}(\text{flag})$. The objective is to compute $\text{flag}$.

Solution⌗

We let $t = g_1$. Then

\[\begin{aligned} \text{f}(x) = t &+ (at + b) x + (a^2t + ab + b) x^2 + (a^3t + a^2b + ab + b) x^3 \\ & + (a^4t + a^3b + a^2b + ab + b) x^4 + (a^5t + a^4b + a^3b + a^2b + ab + b) x^5 \end{aligned}\]

Since we are given $\text{f}(1), ..., \text{f}(4)$, then we have relations in terms of $a, b, t$. By using Gröbner basis, we are able to get $a, b$ and $t$ (Please refer to my blog post on benaloh in DiceCTF 2021 about Grobner basis). After we have $a, b$ and $t$, we can find the roots of $\text{f}(m) = c$. One of the roots $m$ is the flag - Neko{7h3_SSSS_way_wa5_imp3rf3c7}.

Fp = GF(p)
P.<a, b, t> = PolynomialRing(Fp)

I = []

for x, y in vs:
    I.append(
        t +
        (a * t + b) * x^1 +
        (a^2 * t + a*b + b) * x^2 +
        (a^3 * t + a^2*b + a*b + b) * x^3 +
        (a^4 * t + a^3*b + a^2*b + a*b + b) * x^4 +
        (a^5 * t + a^4*b + a^3*b + a^2*b + a*b + b) * x^5 -
        y
    )

I = ideal(I)
B = I.groebner_basis()
print(B)
# [
#   a + 2266836953589743257351224509273439729689541525677993833001930920472782742737910602275706868772676759946821904069905859968756597270976151522409326524927600,
#   b + 2788740700292957168049099171058712103000578129267348979215398750092376230150013503532084224750557141914333611578327023620351350891306875949435645505020009,
#   t + 2396732332549055902303832537638214877286359297511891847206728175987402024672248779417486082181632073168252809943847197628520807355008794399778015958945044
# ]
a = -2266836953589743257351224509273439729689541525677993833001930920472782742737910602275706868772676759946821904069905859968756597270976151522409326524927600
b = -2788740700292957168049099171058712103000578129267348979215398750092376230150013503532084224750557141914333611578327023620351350891306875949435645505020009
t = -2396732332549055902303832537638214877286359297511891847206728175987402024672248779417486082181632073168252809943847197628520807355008794399778015958945044

P.<x> = PolynomialRing(Fp)
f = t + \
    (a * t + b) * x^1 + \
    (a^2 * t + a*b + b) * x^2 + \
    (a^3 * t + a^2*b + a*b + b) * x^3 + \
    (a^4 * t + a^3*b + a^2*b + a*b + b) * x^4 + \
    (a^5 * t + a^4*b + a^3*b + a^2*b + a*b + b) * x^5 - \
    c

for m, _ in f.roots():
    m = int(m)
    flag = int.to_bytes(m, (m.bit_length()+7)//8, 'big')
    print(flag)

ECC-RSA 2⌗

Challenge Summary⌗

Let $n = p\cdot q$ with $p$ and $q$ being 512-bit primes. An elliptic curve $\mathcal{C}$ is given by:

\[\mathcal{C}:\quad y^2 \equiv x^3 + a x + b\ (\text{mod}\ n),\]

where $a = -3$. Let $P \in \mathcal{C}$ and let $m_0, m_1, ... \in [0, 256)$ be the characters of the flag. The $k$-th character of the flag $m_k$ is encrypted to $c_k$ (here $e = 65537$):

\[c_k \equiv ((2^k\cdot P)_x \cdot m_k)^e \ (\text{mod}\ n).\]

Given $n, a, b$ and $c_0, c_1, ...$. It is known that the flag satisfies the format Neko{\w+}, the objective is to recover the flag.

Solution⌗

Part I: Elliptic curve doubling⌗

It is another time I looked up how a point in elliptic curve is doubled. Suppose that $Q = (x_1, y_1)$ and $2Q = (x_2, y_2)$:

\[\begin{cases} & \lambda = (3x_1^2 + a) / 2y_1 \\ & x_2 = \lambda^2 - 2x_1 \\ & y_2 = \lambda(x_1 - x_2) - y_1 \end{cases}\]

We can express $x_2$ in terms of $x_1$:

\[\begin{aligned} x_2 &= \lambda^2 - 2x_1 = \left(\frac{3x_1^2 + a}{2y_1}\right)^2 - 2x_1 = \frac{(3x_1^2 + a)^2}{4y_1^2} - 2x_1 = \frac{(3x_1^2 + a)^2}{4(x_1^3 + ax_1 + b)} - 2x_1 \\ &= \frac{9x_1^4 + 6ax_1^2 + a^2 - 8x_1^4 - 8ax_1^2 - 8bx_1}{4(x_1^3 + ax_1 + b)} = \frac{x_1^4 - 2ax_1^2 - 8bx_1 + a^2}{4(x_1^3 + ax_1 + b)} \end{aligned}\]

From above, we could recover the $x$-coordinate of $2Q$ if we have the $x$-coordinate of $Q$. Inductively, we can recover the $x$-coordinates of $4Q$, $8Q$, $16Q$, etc... Wait, we don't even have an $x$-coordinate yet.

Part II: Recovering the $x$-coordinate of $P$⌗

Let $x_0$ and $x_1$ be the $x$-coordinates of $P$ and $2P$. We know the prefix of the flag, i.e., $m_0, ..., m_4$. That said, we have ${x_0}^e = c_0 / {m_0}^e$, ${x_1}^e = c_1 / {m_1}^e$ and so on. From the previous part, we can express $x_1$ in terms of $x_0$. In that way we have two polynomials that shares a common root $x_0$:

\[\begin{cases} & A(x) = x^e - c_0 / {m_0}^e \\ & B(x) = (x^4 - 2ax^2 - 8bx + a^2)^e - [4(x^3 + ax + b)]^e \cdot c_1 / {m_1}^e \end{cases}\]

Since $x_0$ is a common root of the polynomials, we can compute $g(x) := \gcd(A(x), B(x))$ with half GCD algorithm (or Euclidean algorithm but it is significantly slower).

Part III: Finishing up⌗

Now we have $x_0, x_1, ...$. Since each ciphertext corresponds to one byte of the flag, we can easily generate $(x_k \cdot m_k)^e\ \text{mod}\ n$ for all $m_k \in [0, 256)$. This can serve as a lookup table to get $c_k$ from $m_k$. After all, the flag is Neko{h4lf_gcd_g0es_brrr...}.

They Were Eleven⌗

Challenge Summary⌗

Suppose that we have a 111-byte message $m$. Let $p_1, p_2, ..., p_{11}, q_1, q_2, ..., q_{11}$ be 512-bit primes and $r_1, r_2, ..., r_{11} \in [0, 2^{11})$.

We are given $n_i = p_i\cdot q_i$ and $c_i = m^{11}\cdot r_i\ \text{mod}\ n_i$ for $i = 1, 2, ..., 11$. The objective is to recover $m$.

Solution⌗

Part I: Comparing with the broadcast attack⌗

It looked very similar to broadcast attack. $e = 11$ and we have 11 messages encrypted with different moduli. The only difference is the each ciphertext is multiplied with a 11-bit number. I think of Chinese remainder theorem that is used by the broadcast attack (hereby $N_k = (\prod{n_i}) / n_k$):

\[c = \left(\sum_{k=1}^{11} c_i \cdot N_k \cdot ({N_k}^{-1}\ \text{mod}\ n_k)\right)\ \text{mod}\ N.\qquad[\dagger]\]

On a second thought, $c$ is not meaningful at all. Although $c$ is not useful, the expression actually helped.

Part II: When in doubt, use lattice⌗

One thing that caught my attention is the size of $m$. It is 111-byte long, which is a bit short when compiled to the moduli. Does it mean that it is a "short solution" of a system of equations? The picture is clearer if we substitute $c_k = m^{11}\cdot r_k$ on $[\dagger]$:

\[c = \left(\sum_{k=1}^{11} m^{11} \cdot r_k \cdot N_k \cdot ({N_k}^{-1}\ \text{mod}\ n_k)\right)\ \text{mod}\ N.\]

Right, this is still useless. The only difference is those problematic $r_i$'s. If we remove those $r_k$'s our world would be much cleaner:

\[m^{11} = \left(\sum_{k=1}^{11} m^{11} \cdot N_k \cdot ({N_k}^{-1}\ \text{mod}\ n_k)\right)\ \text{mod}\ N.\]

In particular, $m^{11}$ is $9768 = 111 \cdot 8 \cdot 11$ bits long. Since $N$ is $11264 = 1024 \cdot 11$ bits long, $m^{11}$ is considered short. Maybe we can find short $r_1, r_2, ..., r_{11}$ such that

\[m^{11} = \left(\sum_{k=1}^{11} c_k \cdot N_k \cdot ({N_k}^{-1}\ \text{mod}\ n_k) \cdot {r_k}^{-1}\right)\ \text{mod}\ N.\]

I don't know how to formulate ${r_k}^{-1}$ in lattice for small $r_k$'s. Luckily we can rewrite the equation (denote $R = \prod r_i$ and $R_k = R / r_k$) by multiplying $R$ on both sides:

\[m^{11} R = \left(\sum_{k=1}^{11} c_k \cdot N_k \cdot ({N_k}^{-1}\ \text{mod}\ n_k) \cdot R_k\right)\ \text{mod}\ N.\]

Well, it doesn't sound lucky at all. Hear me out: The left hand side is now 9889 bits long. There are 11 unknowns on the right hand side, namely $R_1, R_2, ..., R_{11}$. Each of them is 88 bits long. There are total of 10857 bits, which is still smaller than 11264. Now we can try putting the whole thing in a lattice:

\[\left[\begin{matrix} -1 & 1 & 0 & ... & 0 \\ c_1 \cdot N_1 \cdot {N_1}^{-1} & 0 & 1 & ... & 0 \\ &&\vdots \\ c_{11} \cdot N_{11} \cdot {N_{11}}^{-1} & 0 & 0 & ... & 1 \\ N & 0 & 0 & ... & 0 \end{matrix}\right]\]

Note. I used ${N_{k}}^{-1}$ as a shorthand for ${N_{k}}^{-1}\ \text{mod}\ n_k$. That was too long.

It is expected that $(0, m^{11}R, R_1, R_2, ..., R_{11})$ is an vector spanned by the lattice. It could be found assigning appropriate weights to the vectors and perform LLL. I exhausted $r_1$ and computed $R := r_1R_1$. After that, we can derive $m$ from $m^{11}R$ and $R$. Finally, those integral $m$'s could be the flag.

Neko{th3_5tud3nts_0f_spac3_univ3rsity_sh0u1d_b3_wis3_1ik3_a_cat}

Addendum⌗

Updated 2021.11.10 16:30 (HKT).

maple3142 suggested that $m^{11}R$ should be $m^{11}R'$ where $R' = \text{lcm}(r_1, r_2, ..., r_{11})$. This is correct, and below is a shorter vector that should be contained in the lattice:

\[(0, m^{11}R', R'_1, R'_2, ..., R'_{11}),\]

where $R' = \text{lcm}(r_1, r_2, ..., r_{11})$ and $R'_k = R' / r_k$. Note that $(0, m^{11}R, R_1, R_2, ..., R_{11})$ is an integer multiple of the above vector. That said, this vector is still spanned by the lattice, but it would not be one of the vectors those constitute to the basis. We can use the same way to solve the problem with the new vector.

Solve script⌗ 

xs = [...] # omitted

ns = [n for c, n in xs]
cs = [c for c, n in xs]

N = product(ns)
Ns = [int(N/n) for n in ns]
Ninvs = [int(pow(int(Nc), -1, int(n))) for Nc, n in zip(Ns, ns)]

bounds = [2^11264, 2^11264 // 2^9889] + [2^11264 // 2^110 for _ in range(11)]
Q = diagonal_matrix(bounds)

A = Matrix(13, 13)

if True:
    A[0,   0  ] = -1
    A[12,  0  ] = N
for i in range(11):
    A[i+1, 0  ] = int(cs[i] * Ns[i] * Ninvs[i] % N)
for i in range(12):
    A[i,   i+1] = 1

A *= Q
A = A.LLL()
A /= Q

for row in A:
    if row[0] != 0: continue
    if row[-1] < 0: row = -row
    if min(row[1:]) < 0: continue

    # Guess k1
    for k1 in range(1, 2**11):
        k_prod = k1 * row[2]
        if row[1] % k_prod != 0: continue
        c1 = int(row[1] // k_prod)
        m = c1^(1/11)
        if m != int(m): continue
        flag = int(m)
        flag = flag.to_bytes(111, 'big')
        print(flag)

# Neko{th3_5tud3nts_0f_spac3_univ3rsity_sh0u1d_b3_wis3_1ik3_a_cat}

Collapsed License⌗

Challenge Summary⌗

We are given a binary executable compiled in C++ (luckily unstripped). It reads a "license file" and valiates it, and prints us the flag if the license file is valid.

Solution⌗

Part I: What is a valid license?⌗

I understood the validation logic after spending some time reversing the binary. A valid license file should be 8192 bytes long (i.e., 65536 bits). It is converted into a $256 \times 256$ grid with each entry being either 0 or 1. There should be exactly 256 set bits, satisfying both conditions:

  • Each row (and each column) should contain exactly one set bit.
  • Suppose that $(x_1, y_1)$ and $(x_2, y_2)$ are two distinct set bits in the grid. If $(x_1', y_1')$ and $(x_2', y_2')$ are two set bits satisfying $x_1 - x_2 = x_1' - x_2'$ and $y_1 - y_2 = y_1' - y_2'$, then $(x_1', y_1') = (x_1, y_1)$ and $(x_2', y_2') = (x_2, y_2)$.

Let $(0, y_0), (1, y_1), ..., (63, y_{63})$ be the coordinates of the set bits. The below conditions are equivalent to the above ones:

  • $y_0, y_1, ..., y_{63}$ are all distinct, and
  • $y_1 - y_0, y_2 - y_1, ..., y_{63} - y_{62}$ are all distinct, and
  • $y_2 - y_0, y_3 - y_1, ..., y_{63} - y_{61}$ are all distinct, and
  • ...
  • $y_{62} - y_0, y_{63} - y_1$ are all distinct.
What is the array called? According to ptr-yudai, the array $y_0, y_1, …, y_{n-1}$ is called a Costas array. We need to find such an array when $n = 256$.

Part II: A symbolic solution⌗

I wrote a script with Z3. It worked for $n$ is as small as 10-ish. When $n = 256$ my laptop crashed after running the program for 30 minutes.

from z3 import *

n = 256
s = Solver()

y = [Int(f'y{i}') for i in range(n)]
for i in range(n): s.add(And(y[i] >= 0, y[i] < n))
s.add(Distinct(y))
for d in range(1, n):
    s.add(Distinct([y[i]-y[i-d] for i in range(d, n)]))

assert s.check() == sat
md = s.model()

y0 = [md.evaluate(y[i]).as_long() for i in range(n)]

grid = [[0 for _ in range(256)] for _ in range(256)]

for x, y in enumerate(y0):
    grid[x][y] = 1

with open('test', 'wb') as f:
    for i in range(256):
        for j in range(0, 256, 8):
            by = sum(b<<k for k, b in enumerate(grid[i][j:j+8]))
            by = bytes([by])
            f.write(by)

Part III: The adrenaline rush when my laptop was crashed⌗

I am really excited able to think of the correct solution.

I was forced to work on paper and pen when my laptop was crashed. Suppose that $(0, y_0), (1, y_1), ..., (63, y_{63})$ are the coordinates of the set bits.

There are a number of failed attempts, like $y_k = \sum_{i=0}^{k} i$. At some point of time I think of primitive roots, which led me to the final solution.

Claim. Let $g$ be a primitive root under modulo 257. Below is a valid solution:

\[y_k = (g^k\ \text{mod}\ 257)-1,\]

for $k = 0, 1, 2, ..., 255$.

Proof.

Since g is a primitive root under modulo 257, $g^0, g^1, ..., g^{255}$ are all distinct. That said, $y_k$'s are all distinct.

Also, let $d > 0$. Suppose that $y_{i+d} - y_i = y_{j + d} - y_j$ for $0 \leq i, j \leq 255-d$.

\[\begin{aligned} & g^i (g^d - 1) \equiv y_{i+d} - y_i \equiv y_{j + d} - y_j \equiv g^j (g^d - 1)\ (\text{mod}\ 257)\\ & \Longrightarrow i = j \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\blacksquare \end{aligned}\]

I substituted $g = 3$ to created a license file. Sending the license to the server, we have the flag:

Neko{c4n_U_f1nd_0ut_h0w_m4ny_v4L1d_l1c3ns3_3x1St5?}