Noise Cheap

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-23 | Status: Solved Techniques: babai_nearest_plane, lll_reduction, lwe_secret_recovery, qary_lattice_construction

Summary

Task: LWE encryption with e in {-1,0,1}, q=1048583, p=257, n=64. Server encrypts flag characters and chosen messages. Solution: encrypt m=0 to get b=AS+pe, multiply by p^{-1} mod q to get standard LWE with tiny noise; build q-ary lattice with 128 samples, LLL-reduce, Babai nearest plane recovers error vector and secret S.

Noise Cheap — CryptoHack (Post-Quantum / LWE)

Description

The Learning With Errors problem is hard because of the noise. What if we try to make the noise cheaper?

Interactive server at socket.cryptohack.org:13413. Parameters:

 python read-only • copy allowed Copy
n = 64        # dimension
p = 257       # plaintext modulus
q = 1048583   # ciphertext modulus
e ∈ {-1, 0, 1}  # tiny noise!

S = random secret vector in GF(q)^n

def encrypt(m):
    A = random vector in GF(q)^n
    e = randint(-1, 1)
    b = A * S + m + p * e   (mod q)
    return A, b

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Two options: encrypt (chosen message) or get_flag (encrypt a flag character by index).

Analysis

The noise is extremely small: e ∈ {-1, 0, 1}. The encryption formula is:

b = A · S + m + p · e   (mod q)

Step 1: Remove the message. Encrypt m = 0 to get:

b = A · S + p · e   (mod q)

Step 2: Remove the p factor. Multiply both sides by p⁻¹ mod q:

b · p⁻¹ = A · (S · p⁻¹) + e   (mod q)

This is now standard LWE with secret S' = S · p⁻¹ and noise e ∈ {-1, 0, 1}. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Step 3: Solve with lattice reduction. With such tiny noise, the Closest Vector Problem (CVP) via Babai's nearest plane algorithm on an LLL-reduced q-ary lattice works perfectly.

The q-ary lattice for m = 2n = 128 samples:

L = [ q·I_m    0  ]
    [  A^T    I_n ]

where A is the m × n matrix of sample vectors. The target vector is t = (b · p⁻¹, 0, ..., 0). Babai's nearest plane finds the closest lattice point, and the difference gives the error vector e.

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import json
from pwn import remote
from fpylll import IntegerMatrix, LLL, GSO
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

n = 64
p = 257
q = 1048583
m = 2 * n  # 128 samples

# Connect and collect samples with m=0
conn = remote('socket.cryptohack.org', 13413)
conn.recvline()

A_rows = []
b_vals = []

for _ in range(m):
    conn.sendline(json.dumps({"option": "encrypt", "message": 0}).encode())
    resp = json.loads(conn.recvline())
    A_rows.append(eval(resp["A"]))
    b_vals.append(int(resp["b"]))

# Multiply b by p^{-1} mod q
p_inv = pow(p, -1, q)
b_scaled = [(b * p_inv) % q for b in b_vals]

# Build q-ary lattice: (m+n) x (m+n)
dim = m + n
M = IntegerMatrix(dim, dim)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Top-left: q * I_m
for i in range(m):
    M[i, i] = q

# Bottom-left: A^T (n x m), placed at rows m..m+n-1, cols 0..m-1
for j in range(n):
    for i in range(m):
        M[m + j, i] = (A_rows[i][j] * p_inv) % q

# Bottom-right: I_n
for j in range(n):
    M[m + j, m + j] = 1

# LLL reduction
LLL.reduction(M)

# Babai nearest plane
def babai_cvp(B, target):
    G = GSO.Mat(B)
    G.update_gso()
    n = B.nrows
    t = list(target)
    b = [0.0] * n

    for i in range(n - 1, -1, -1):
        # t_star = <t, b*_i> / <b*_i, b*_i>
        gs = [G.get_mu(i, j) for j in range(i)] + [1.0]
        bi_star = [0.0] * len(t)
        for k in range(i + 1):
            for d in range(len(t)):
                bi_star[d] += gs[k] * B[k, d] if k < i else 0
        # Use fpylll's built-in
        pass
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

    # Simplified: use matrix operations
    from fpylll import CVP
    return CVP.closest_vector(B, target)

from fpylll import CVP
target = list(b_scaled) + [0] * n
closest = CVP.closest_vector(M, target)

# Error vector = target - closest
errors = [(b_scaled[i] - closest[i]) % q for i in range(m)]
# Normalize to {-1, 0, 1}
errors = [e if e <= 1 else e - q for e in errors]

# Recover S' = S * p^{-1} from A * S' + e = b_scaled
# S' = A^{-1} * (b_scaled - e)  -- use first n samples
from sage.all import Matrix, vector, GF
F = GF(q)
A_mat = Matrix(F, [A_rows[i] for i in range(n)])
b_vec = vector(F, [b_scaled[i] - errors[i] for i in range(n)])
S_prime = A_mat.solve_right(b_vec)
S = vector(F, [int(s) * p % q for s in S_prime])
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Now decrypt flag characters
flag_chars = []
for idx in range(31):  # flag length
    conn.sendline(json.dumps({"option": "get_flag", "index": idx}).encode())
    resp = json.loads(conn.recvline())
    a = vector(F, eval(resp["A"]))
    b = int(resp["b"])
    # b = a * S + m + p * e, so m = b - a*S - p*e
    raw = (b - int(a * S)) % q
    # m = raw mod p (since p*e is a multiple of p)
    char = raw % p
    flag_chars.append(chr(char))

print(''.join(flag_chars))
conn.close()

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍