Daily Alpacahack 2026 #27 - ToyPQC

Executive Summary

Challenge: ToyPQC CTF: Daily Alpacahack 2026 #27 Category: Cryptography Difficulty: Hard Flag: Alpaca{sa6em4th_i5_u5efu1^_^}

ToyPQC is a cryptography challenge based on the Learning With Errors (LWE) problem. We are given an overdetermined system of linear equations over a finite field, perturbed by a “noise” vector. The critical vulnerability lies in the small size of the error vector (binary elements, length 10), which allows for a brute-force attack to recover the correct error, solve the linear system, and decrypt the flag.

1. Challenge Analysis

The provided SageMath script implements an LWE-based system:

Setup: Defines a finite field $F_p$ with $p = 8380417$ .
Secret ( $s$ ): The flag is split into 7 chunks, forming the secret vector $s \in F_p^7$ .
Matrix ( $A$ ): A random $10 \times 7$ matrix $A$ is generated.
Error ( $e$ ): A random error vector $e \in \{0, 1\}^{10}$ is generated.
Encryption: The public vector $b$ is computed as $b = A \cdot s + e$ .

We are provided with $A$ and $b$ .

2. Vulnerability Assessment

The equation $b = A \cdot s + e$ represents a noisy system of linear equations. while LWE is typically hard, the specific parameters here make it vulnerable.

The error vector $e$ has length $m=10$ , and each element is chosen from $\{0, 1\}$ . Total search space: $2^{10} = 1024$ .

This extremely small search space allows us to brute-force the error vector $e$ .

3. Solution Strategy

Iterate: Generate all $2^{10}$ possible binary vectors for $e$ .
Clean: Compute candidate target $b' = b - e_{guess}$ .
Solve: Attempt to solve $A \cdot s = b'$ $A \cdot s = b^{'}$ .
- If $e_{guess}$ is incorrect, the system is inconsistent (no solution).
- If $e_{guess}$ is correct, we find the unique $s$ .
Decode: Convert the resulting secret vector $s$ back to bytes.

4. Solve Script (SageMath)

1
import itertools
2
from Crypto.Util.number import long_to_bytes
3

4
# Challenge Parameters
5
p = 8380417
6
n = 7
7
m = 10
8
F = GF(p)
9

10
# Assume A (matrix) and b (vector) are loaded from challenge output
11
# A = matrix(F, ...)
12
# b = vector(F, ...)
13

14
print("[-] Starting Brute-Force on Error Vector...")
15

16
possible_errors = itertools.product([0, 1], repeat=m)
17

18
for err_tuple in possible_errors:
19
    e_guess = vector(F, err_tuple)
20
    target = b - e_guess
21

22
    try:
23
        # Attempt to solve A * s = target
24
        s_candidate = A.solve_right(target)
25

26
        flag_content = b""
27
        for val in s_candidate:
28
            flag_content += int(val).to_bytes(3, "big")
29

30
        full_flag = f"Alpaca{{{flag_content.decode()}}}"
31
        print(f"[+] Success! Error vector: {err_tuple}")
32
        print(f"[+] FLAG: {full_flag}")
33
        break
34

35
    except ValueError:
36
        continue
37
    except UnicodeDecodeError:
38
        continue

5. Conclusion

By exploiting the low entropy of the error vector, we reduced the problem to a trivial brute-force check. Validating each of the 1024 possibilities against the linear system allowed us to isolate the correct error and recover the plaintext.