Because there are not many Crypto listed in the "Stock Market", I decided to join our Webb-expert Web-expert Ozetta for bounty hunting in web, and we got all web challenges done this time. The writeup of the web challenges can be found here.

lwsr ($285, 20 solves)

Challenge Summary

Suppose that $q = 16411$.

When connected to the server, a LWE private key $s \in \mathbb{Z}_q^{128}$ and 384 sets of public key $(p_1, r_1), (p_2, r_2), ..., (p_{384}, r_{384}) \in \mathbb{Z}_q^{128} \times \mathbb{Z}_q$ are also generated. Also, a LFSR state $t = (t_1, t_2, ..., t_{384})$ with $t_1, t_2, ..., t_{384} \in \{0, 1\}$ is generated.

The flag is encrypted bit-by-bit. The ciphertext of the $i$-th bit of the message, $m_i$, is defined by:

\[\begin{cases} c_{i, 0} &= (t_1 \cdot p_1 + t_2 \cdot p_2 + ... + t_{384} \cdot p_{384})\ \text{mod}\ q \\ c_{i, 1} &= (t_1 \cdot r_1 + t_2 \cdot r_2 + ... + t_{384} \cdot r_{384} + 8205m_i)\ \text{mod}\ q \end{cases}\]

Additionally, after a bit is encrypted, the LFSR state is updated with

\[(t'_1, t'_2, ..., t'_{384}) := \left(t_2, t_3, ..., \text{NEXT}(t_1, t_2, ..., t_{384})\right).\]

We are given $(p_1, r_1), (p_2, r_2), ..., (p_{384}, r_{384})$ and encrypted flag $(c_{1,0}, c_{1,1}), (c_{2,0}, c_{2,1}), ...$. We are then able to access the decryption oracle. The goal is to recover the flag.

Solution

Denote $p_i = (p_{i, 1}, p_{i, 2}, ..., p_{i, 128})$ and $c_{k, 0} = (c_{k, 0, 1}, c_{k, 0, 2}, ..., c_{k, 0, 128})$ with $p_{i, j}, c_{k, 0, j} \in \mathbb{Z}_q$. Let's make $c_{1, 0, j}$ in terms of $p_{i, j}$'s:

\[c_{1, 0, j} = (t_1 \cdot p_{1, j} + t_2 \cdot p_{2, j} + ... + t_{384} \cdot p_{384, j})\ \text{mod}\ q.\]

Now we have 128 equations with unknowns $t_1, t_2, ..., t_{384}$. Denote

\[t_{k+385} := \text{NEXT}(t_{k+1}, t_{k+2}, ..., t_{k+384})\]

for $k \geq 0$, then we have 384 equations when we consider $c_{2, 0, j}$, $c_{3, 0, j}$ and $c_{4, 0, j}$:

\[\begin{aligned} c_{2, 0, j} = (t_2 \cdot p_{1, j} + t_3 \cdot p_{2, j} + ... + t_{385} \cdot p_{384, j})\ \text{mod}\ q, \\ c_{3, 0, j} = (t_3 \cdot p_{1, j} + t_4 \cdot p_{2, j} + ... + t_{386} \cdot p_{384, j})\ \text{mod}\ q, \\ c_{4, 0, j} = (t_4 \cdot p_{1, j} + t_5 \cdot p_{2, j} + ... + t_{387} \cdot p_{384, j})\ \text{mod}\ q. \end{aligned}\]

Since we have 387 unknowns $(t_1, t_2, ..., t_{387})$ and 512 equations, we can recover $(t_1, t_2, ..., t_{387})$ by solving the linear system under modulo $q$. With that, we can substitute the unknowns to $c_{i, 1}$'s to recover the flag.

def lfsr(state):
    # x^384 + x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + x + 1
    mask   = (1 << 384) - (1 << 377) + 1
    newbit = bin(state & mask).count('1') & 1
    return (state >> 1) | (newbit << 383)
    
# ============

q = 16411
Fq = GF(q)

# sample.log includes a simple transcript connecting to the server.
with open('sample.log') as f:
    lines = f.readlines()

pk = eval(lines[1])

outputs = []
for line in lines[3:355]:
    outputs.append(eval(line))

A = Matrix(Fq, 512, 387)
y = vector(Fq, 512)

for i, (a, b) in enumerate(outputs[:4]):
    for j in range(128):
        A[128*i+j, :] = vector(Fq, [0 for _ in range(i)] + [pk[k][0][j] for k in range(384)] + [0 for _ in range(3-i)])
        y[128*i+j]    = a[j]

x = A.solve_right(y)

state1 = sum(int(x[i+0])<<i for i in range(384))
state2 = sum(int(x[i+1])<<i for i in range(384))
state3 = sum(int(x[i+2])<<i for i in range(384))
state4 = sum(int(x[i+3])<<i for i in range(384))
assert lfsr(state1) == state2
assert lfsr(state2) == state3
assert lfsr(state3) == state4

pk_right = [pk[k][1] for k in range(384)]

state = state1
flag = 0
for (a, b) in outputs:
    flag *= 2
    if (sum(pk_right[i] * ((state>>i) & 1) for i in range(384)) - b) % q != 0:
        flag += 1
    state = lfsr(state)

    flag = int(flag)
    print(int.to_bytes(flag, len(outputs)//8, 'big'))

WhatTheHecc ($198, 45 solves)

Challenge Summary

The challenge defines a signature algorithm $\mathcal{S}$, where a key generated with elliptic curve parameter P-256 (the public and private keys are respectively $Q$ and $d$). The signing algorithm for a message $m$ is specified below ($\text{H}$ is the SHA3-256 algorithm that returns an integer given an array of bytes):

  1. Compute $r = \text{H}(m) \cdot Q$
  2. Compute $r' = r\cdot d^{-1}\ \text{mod}\ q$, where $q$ is the order of the curve
  3. Define $z = n_\text{nonce} | t$, where $n_\text{once} \in [1, q)$ and $t$ is the timestamp in seconds
  4. Compute $R = r' + \text{H}(z) \cdot G$
  5. Compute $s = [d - \text{H}(z)]\ \text{mod}\ q$
  6. Return $(R, s)$ as the signature.

Also the verifying algorithm for a message $m$ and signature $(R, s)$:

  1. If $s = 0\ \text{or}\ 1$ and $s > 0$ then the signature is considered invalid.
  2. The signature is valid only if

\[s \cdot G - Q + R = \text{H}(m) \cdot G\]

There are three functions those we can use when connected to the server:

  1. [Show] Prints the public key.
  2. [Sign] Signs one of the four commands: id, uname, ls and date with $\mathcal{S}$.
  3. [Run] Takes a signed command and executes if the signature is valid.

Solution

The verify method they implemented is really fishy:

def verify(msg, sig, pub):
    R, s = sig

    # 👇 This is sus
    if s in [0,1,''] and s > 0:
        return False

    tmp1 = s * pub._curve.G
    tmp2 = - pub.pointQ 
    tmp3 = tmp2 + R

    return tmp1 + tmp3 == hash(msg) * pub._curve.G

From the line specified, it seemed to me that $s$ should be nonzero. I tried putting $s = 0$ and found $R = Q + \text{H}(m)$. That said, we can simply send $(R, s) = (Q + \text{H}(m), 0)$ as an signature to execute arbitrary commands. With that said, we can simply craft a signature for cat flag and read the flag.

Postmortem

$\mathcal{S}$ is not secure at all. It does not help even if $s \neq 0$ is enforced. $R$ can be easily crafted given arbitrary $m$ and $s$:

\[R = [\text{H}(m) - s] \cdot G + Q\]

For instance, @RBTree_ could execute arbitrary commands with $(R, s) = (Q, \text{H}(m))$.