IERAE CTF 2025

ierae_2025

Trunc

Challenge File

1
from sage.all import *
2
import secrets
3

4
q = 2**20
5
n = 512
6
m = 4 * n
7
c = 8
8

9
with open("flag.txt", "rb") as f:
10
    FLAG = f.read().strip()
11

12
def trunc_matrix(M, c):
13
    F = M.base_ring()
14
    modulus = 2**c
15
    return matrix(F, M.nrows(), M.ncols(), [F(Integer(x) - (Integer(x) % modulus)) for x in M.list()])
16

17
def keygen():
18
    U = random_matrix(Integers(q), m, n)
19
    A = trunc_matrix(U, c)
20
    s = vector(Zmod(q), [secrets.randbelow(q) for _ in range(n)])
21
    e = vector(Zmod(q), [ZZ(secrets.randbelow(400)) for _ in range(m)])
22
    return A, A * s + e
23

24
def encrypt_bit(x, A, b):
25
    S = [i for i in range(A.nrows()) if secrets.randbits(1)]
26
    if len(S) == 0:
27
        S = [secrets.randbelow(A.nrows())]
28
    a_sum = sum([A[i] for i in S])
29
    b_sum = sum([b[i] for i in S])
30
    encoded_bit = (x * (q // 2)) % q
31
    return (a_sum, (encoded_bit + b_sum) % q)
32

33
def encrypt_message(message, A, b):
34
    bits = []
35
    for byte in message:
36
        for i in range(8):
37
            bits.append((byte >> i) & 1)
38
    ciphertext = [encrypt_bit(bit, A, b) for bit in bits]
39
    return ciphertext
40

41
def main():
42
    A, b = keygen()
43
    flag_ciphertext = encrypt_message(FLAG, A, b)
44
    print("q =", q)
45
    print("n =", n)
46
    print("m =", m)
47
    print("c =", c)
48
    print("A =", [list(A[i]) for i in range(A.nrows())])
49
    print("b =", list(b))
50
    print("flag_ciphertext =", flag_ciphertext)
51

52
if __name__ == "__main__":
53
    main()

Summary of Challenge

The challenge outputs a standard Learning With Errors public key and an LWE‑encrypted flag:

modulus $q = 2^{20}$
secret length $n = 512$
number of equations $m = 4n = 2048$
“truncation” parameter $c = 8$ every entry of $A$ is an exact multiple of $2^c = 256$
noise vector $e \in \{0,\dots,399\}^m$

1
b = A·s + e   (mod q)                  # public part of key
2
a_sum, c2 = encrypt_bit(…)             # ciphertext pairs

Our task is to recover FLAG from the printed A, b, and flag_ciphertext.

Key observation – drop a factor 256

Because every coefficient of $A$ is divisible by 256 we can divide each public equation by that factor:

A = 256·A', \qquad b = 256·A's + e \pmod{q} \;\Longrightarrow\; A's \equiv \bigl\lfloor b/256 \bigr\rfloor \pmod{q/256}\,.

Set $q' = q/256 = 4096$ . After division we still have an LWE instance — but with dramatically smaller noise:

$e \mapsto e' := \lfloor e/256 \rfloor \in \{0,1\}$ .

If we could find rows where $e'=0$ the system would become noise‑free.

Which rows are noise‑free?

The byte $e_i \bmod 256$ is visible in $b_i$ . If that byte is $\ge 144$ then $e_i < 256$ ⇒ $e'_i=0$ . Roughly 30 % of the rows meet that test — more than enough for a full‑rank $512\times512$ sub‑matrix.

Linear algebra mod $4096$

Select the clean indices

1
clean_idx = [i for i, bi in enumerate(b) if (bi % 256) >= 144][:n]

and build the exact system

A'_{\text{clean}} · s \;\equiv\; d_{\text{clean}} \pmod{4096},

where each equation is noise‑free.

Solving over Z/2^12

Modulo a power of two the ring is not a field, but odd numbers are still units. A plain Gaussian elimination that always pivots on an odd entry gives the unique solution $s\pmod{4096}$ .

The function solver() below implements exactly that.

Decrypting the ciphertext

Every ciphertext contains a pair $(\sum a_i, \sum b_i)$ . Because each $a_i$ is again a multiple of 256, the inner product that shows up during decryption depends only on $s\pmod{4096}$ , which we now possess.

After subtracting that inner product the remaining value is either

close to $0$ or
close to $q/2 = 2^{20}/{2} = 524288$

with an error bounded by $\le |S|·399 \ll q/4$ . A single comparison therefore recovers each plaintext bit with certainty.

Solver script

1
from sage.all import *
2

3
# constants
4
q  = 2**20
5
cf = 256
6
qp = q // cf
7

8
from output import q as q_, n, m, c, A, b, flag_ciphertext
9
A = [[int(x) for x in row] for row in A]
10
b = [int(x) for x in b]
11

12

13
clean = [i for i, bi in enumerate(b) if (bi % cf) >= 144][:n]
14
A_cl = [[(A[i][j] // cf) % qp for j in range(n)] for i in clean]
15
d_cl = [((b[i] - (b[i] % cf)) // cf) % qp for i in clean]
16

17

18
def solve_mod2k(mat, vec, mod=4096):
19
    M   = [row[:] for row in mat]
20
    rhs = vec[:]
21
    r = 0
22
    rows, cols = len(M), len(M[0])
23
    for c in range(cols):
24
        pivot = next((k for k in range(r, rows) if M[k][c] & 1), None)
25
        if pivot is None:
26
            continue
27
        if pivot != r:
28
            M[r], M[pivot] = M[pivot], M[r]
29
            rhs[r], rhs[pivot] = rhs[pivot], rhs[r]
30
        inv = Integer(M[r][c]).inverse_mod(mod)
31
        M[r]  = [(x * inv) % mod for x in M[r]]
32
        rhs[r] = (rhs[r] * inv) % mod
33
        for k in range(rows):
34
            if k == r or M[k][c] == 0:
35
                continue
36
            f = M[k][c]
37
            M[k]  = [(M[k][j] - f * M[r][j]) % mod for j in range(cols)]
38
            rhs[k] = (rhs[k] - f * rhs[r]) % mod
39
        r += 1
40
        if r == cols:
41
            break
42
    sol = [0]*cols
43
    for i in range(r):
44
        lead = next(j for j, x in enumerate(M[i]) if x == 1)
45
        sol[lead] = rhs[i]
46
    return sol
47

48
s_mod = solve_mod2k(A_cl, d_cl, qp)
49

50
def bit(ct, s4096):
51
    a_sum, c2 = ct
52
    a_red = [int(x)//cf for x in a_sum]
53
    prod  = sum(ai*si for ai,si in zip(a_red, s4096)) % qp
54
    inner = (prod * cf) % q
55
    diff  = (int(c2) - inner) % q
56
    return 0 if diff < q//4 or diff > 3*q//4 else 1
57

58
bits = [bit(ct, s_mod) for ct in flag_ciphertext]
59
flag = bytes(sum(bits[i+k]<<k for k in range(8))
60
             for i in range(0, len(bits), 8)).decode(errors='ignore')
61
print(flag)

FLAG : IERAE{b4ndw1d7h_54v1ng_c1ph3r}

Take‑aways

Truncating the low bits of $A$ leaks structure that survives in the public key.
Dividing by that common factor moves us to a tiny modulus where the noise collapses to 0 or 1.
Selecting the right equations turns LWE into plain linear algebra.
Over powers of two, odd coefficients are still invertible ⇒ classic elimination works.