CH - LWE 2 - Too Many Errors

Challenge

from Crypto.Random.random import getrandbits
import random

SEED = getrandbits(32)
FLAG = b'crypto{????????????????????}'
q = 127

class Challenge():
    def __init__(self):
        self.before_input = f"Welcome to the LWE sample generator! Retrieve a sample using the 'get_sample' option, or reset the distribution using the 'reset' option.\n"
        self.rand = random.Random(SEED)

    def challenge(self, your_input):
        if not "option" in your_input:
            return {"error": "You must send an option to this server"}

        elif your_input["option"] == "reset":
            self.rand.seed(SEED)
            
            return {"success": "The distribution has been reset"}

        elif your_input["option"] == "get_sample":
            a = []
            for i in range(len(FLAG)):
                a.append(self.rand.randint(0, q - 1))

            e = self.rand.randint(-1, 1)

            self.rand.seed(getrandbits(32))

            if self.rand.randint(0, 1):
                a[self.rand.randint(0, len(a) - 1)] = self.rand.randint(0, q - 1)

            b = 0
            for (i, j) in zip(a, FLAG):
                b += i * j
            b += e
            b %= q

            return {"a": a, "b": b}

        else:
            return {"error": "Invalid option"}

The challenge

The server has a secret vector s (the flag bytes, so n = 28) and a modulus q = 127. Each get_sample call returns a pair $(a, b)$ where

$b = a \cdot s + e \mod q$, with $e \in \{−1, 0, 1\}$

This is exactly LWE (Learning With Errors) with a very small error. The “fault” (random replacement of one coordinate of a) is applied before b is computed, so every sample is still a valid LWE sample. Faults don’t break anything.

Solution

The oracle shows us that using deterministic random seed it creates the vector a; this vector is afterwards used as coefficients for each byte of the flag. After, the total is being summed with an eror vector e, and then reduced modulo q.

There are a lot of ways to attack this cipher; the most logical way is trying to find the error vector using learnt LWE techniques.

The idea

Collect m samples (m > n) and stack them:

$b = A \cdot s + e \mod q$

If e were zero, Gaussian elimination mod q would give s immediately. Because e is tiny, we can find it with a lattice: e is a very short vector hiding inside a lattice we can build from A and b.

Once we know e, we solve $A·s = b − e \mod q$ and read off the flag.

How do we build the lattice ??

Well, remember we are looking for a short vector

corresponding to $e = b-A\cdot S \mod q$. Basically we need a Lattice where we are reducing our b vector by coeffients of a and we can reduce by p since reducing by modulus doesn’t cost anything. We build the lattice generated by the rows of the following block matrix $M$:

$$M = \begin{bmatrix} A^{T} & 0\\ -I_{m} \cdot q & 0\\ b & 1 \end{bmatrix}$$

Running LLL on this basis will expose a target row where the last element is $\pm 1$ and all other components are bounded by 1 (representing the error entries). Once we extract $e$, we resolve the exact linear system over $\mathbb{F}_q$:

$A \cdot \text{flag} = b - \text{err} \implies \text{flag} = A^{-1} \cdot (b-\text{err})$

Solve

import json
from pwn import remote

q, n, m = 127, 28, 60          # m > n: qualche campione in più per margine

io = remote("socket.cryptohack.org", 13390)
io.recvline()                   # banner

rows, bs = [], []
for _ in range(m):
    io.sendline(json.dumps({"option": "get_sample"}).encode())
    r = json.loads(io.recvline())
    rows.append(r["a"])
    bs.append(r["b"])

A = matrix(ZZ, rows)            # m x n, entrate in [0, q-1]

B = block_matrix(ZZ, [
    [A.transpose(),           zero_matrix(ZZ, n, 1)],
    [q*identity_matrix(ZZ, m), zero_matrix(ZZ, m, 1)],
    [matrix(ZZ, [bs]),        matrix(ZZ, [[1]])],
])

e = None
for row in B.LLL():
    if row[-1] in (1, -1) and all(abs(c) <= 1 for c in row):
        if row[-1] == -1:
            row = -row
        e = vector(ZZ, row[:-1])
        break


Aq  = matrix(GF(q), rows)
rhs = vector(GF(q), bs) - vector(GF(q), e)
s   = Aq.solve_right(rhs)
print(bytes(int(x) for x in s))

Flag

crypto{f4ult_4ttack5_0n_lw3}