Summary
The challenge provides a Sage script and an output file containing 46 ciphertext vectors. Each character of the flag is encrypted by packing it into a 3-dimensional vector alongside two random integers, multiplying by a fixed public 3x3 integer matrix, and adding a "random" error vector. The catch: that error vector is generated once, outside the encryption loop, and reused for every single character — turning what looks like a lattice/CVP problem into a straightforward linear algebra one.
Attack chain: Read the encryption scheme -> Spot the reused error vector r -> Invert the public matrix -> Brute-force r over its tiny keyspace -> Recover the flag
Files
Two files are provided: source.sage and output.txt.
source.sage:
r = vector(ZZ, [randint(0, 10) for _ in range(3)])
FLAG = open('flag.txt').read()
pubkey = Matrix(ZZ, [
[47, -77, -85],
[-49, 78, 50],
[57, -78, 99]
])
with open('output.txt', 'w') as f:
for c in FLAG:
f.write(f'{vector([ord(c), randint(0, 100), randint(0, 100)]) * pubkey + r}\n')
output.txt (46 lines, one vector per flag character):
(171, -237, -634)
(7806, -11691, 89)
(5350, -7653, 4362)
(6225, -9858, -7129)
(7872, -12129, -4390)
(3597, -4626, 9221)
(2277, -3485, -1777)
(5120, -7602, 193)
(6043, -9414, -4797)
(1316, -1742, 2350)
(5340, -8077, -1501)
(6195, -8818, 5672)
(7777, -11758, -1389)
(5205, -7837, -1114)
(1126, -1719, -1137)
(4341, -6498, -25)
(5725, -8950, -4953)
(4012, -6519, -6987)
(3787, -5249, 5061)
(9244, -13999, -1935)
(2742, -4203, -1816)
(3674, -5274, 2113)
(4577, -6762, 628)
(3418, -4686, 4965)
(4764, -7624, -6487)
(6343, -9249, 2736)
(2305, -2756, 8256)
(4350, -7144, -8395)
(6159, -8820, 4997)
(4412, -7000, -5342)
(4506, -6673, 293)
(894, -1119, 2189)
(5405, -7543, 6421)
(-200, 597, 2991)
(6043, -8945, 981)
(3465, -5212, -853)
(-428, 1056, 4500)
(4300, -6356, 318)
(5483, -8170, 166)
(9765, -14705, -904)
(3935, -5811, 256)
(4014, -5487, 6392)
(4847, -7699, -5897)
(9675, -14553, -664)
(3081, -4314, 3461)
(4317, -6160, 3437)
(5628, -8530, -1879)
Analysis
The script builds a fixed 3x3 integer matrix M (pubkey) and, before the encryption loop, generates a single "noise" vector r = (r0, r1, r2) with each component in [0, 10]. For every character c of the flag it then:
- Builds a plaintext vector
p = (ord(c), rand1, rand2), whererand1andrand2are fresh random integers in[0, 100]— pure padding, not part of the actual message. - Computes the ciphertext row as
p * M + rand writes it tooutput.txt.
Mathematically, for each line i:
c_i = p_i · M + r
Since M is a known, fixed, invertible matrix (det(M) = 6297 ≠ 0), this would already be reversible in isolation — but p_i has two unknown padding values plus r has three unknowns, which is normally not enough to solve from a single row. The real break is that r never changes across the 46 lines. That means once the correct r is guessed, M⁻¹ can be applied to every ciphertext row independently and all of them decrypt correctly at once — there's no ambiguity left to resolve per character.
Since each component of r is bounded to [0, 10], the entire keyspace for r is only 11³ = 1331 combinations, trivial to brute-force. For each guess of r:
p_i = (c_i - r) · M⁻¹
A correct guess is one where every p_i comes out as an integer vector with p_i[0] in the printable ASCII range and p_i[1], p_i[2] ∈ [0, 100] (matching the padding bounds from the script) — checking all 46 lines simultaneously makes false positives essentially impossible.
Exploitation
The plan is simple: recover the single reused error vector r, then invert every ciphertext row independently using M⁻¹. This is implemented in solve.py:
Script
#!/usr/bin/env python3
from sympy import Matrix
M = Matrix([
[47, -77, -85],
[-49, 78, 50],
[57, -78, 99]
])
Minv = M.inv()
cts = [
(171, -237, -634), (7806, -11691, 89), (5350, -7653, 4362),
(6225, -9858, -7129), (7872, -12129, -4390), (3597, -4626, 9221),
(2277, -3485, -1777), (5120, -7602, 193), (6043, -9414, -4797),
(1316, -1742, 2350), (5340, -8077, -1501), (6195, -8818, 5672),
(7777, -11758, -1389), (5205, -7837, -1114), (1126, -1719, -1137),
(4341, -6498, -25), (5725, -8950, -4953), (4012, -6519, -6987),
(3787, -5249, 5061), (9244, -13999, -1935), (2742, -4203, -1816),
(3674, -5274, 2113), (4577, -6762, 628), (3418, -4686, 4965),
(4764, -7624, -6487), (6343, -9249, 2736), (2305, -2756, 8256),
(4350, -7144, -8395), (6159, -8820, 4997), (4412, -7000, -5342),
(4506, -6673, 293), (894, -1119, 2189), (5405, -7543, 6421),
(-200, 597, 2991), (6043, -8945, 981), (3465, -5212, -853),
(-428, 1056, 4500), (4300, -6356, 318), (5483, -8170, 166),
(9765, -14705, -904), (3935, -5811, 256), (4014, -5487, 6392),
(4847, -7699, -5897), (9675, -14553, -664), (3081, -4314, 3461),
(4317, -6160, 3437), (5628, -8530, -1879),
]
for r0 in range(11):
for r1 in range(11):
for r2 in range(11):
r = Matrix([[r0, r1, r2]])
chars, ok = [], True
for c in cts:
p = (Matrix([list(c)]) - r) * Minv
vals = list(p)
if not all(v == int(v) for v in vals):
ok = False; break
a, b, cc = (int(v) for v in vals)
if not (32 <= a <= 126 and 0 <= b <= 100 and 0 <= cc <= 100):
ok = False; break
chars.append(chr(a))
if ok:
print(f"r = ({r0}, {r1}, {r2})")
print("".join(chars))
raise SystemExit
Broken down piece by piece below.
Matrix
from sympy import Matrix
M = Matrix([
[47, -77, -85],
[-49, 78, 50],
[57, -78, 99]
])
Minv = M.inv()
sympy is used instead of sage because the attack no longer needs any lattice machinery — it's pure linear algebra, so a standard Python environment is enough. Minv is computed once, outside the brute-force loop, instead of being recomputed on every one of the 1331 guesses.
Ciphertexts
cts = [
(171, -237, -634), (7806, -11691, 89), (5350, -7653, 4362),
...
(5628, -8530, -1879),
]
Each tuple corresponds to one line of output.txt, copied as-is — Python parses Sage's vector printout as a plain tuple without any changes needed.
Brute force
for r0 in range(11):
for r1 in range(11):
for r2 in range(11):
r = Matrix([[r0, r1, r2]])
Since each component of r is bounded to [0, 10] (from randint(0, 10) in source.sage), the entire search space is only 11³ = 1331 combinations — small enough to exhaust in milliseconds without needing any lattice reduction.
Validation
chars, ok = [], True
for c in cts:
p = (Matrix([list(c)]) - r) * Minv
vals = list(p)
if not all(v == int(v) for v in vals):
ok = False; break
a, b, cc = (int(v) for v in vals)
if not (32 <= a <= 126 and 0 <= b <= 100 and 0 <= cc <= 100):
ok = False; break
chars.append(chr(a))
For each guessed r, every row is decrypted with p_i = (c_i - r) · M⁻¹. A candidate is only kept if every one of the 46 rows passes all three checks:
- The result is an exact integer vector — for a wrong
r,M⁻¹almost always produces non-integer values, sincedet(M) = 6297won't cleanly cancel out an incorrect offset. - The first component (
ord(c)) falls inside the printable ASCII range[32, 126]. - The other two components (the random padding) fall inside
[0, 100], matching exactly howsource.sagegenerates them withrandint(0, 100).
Requiring all 46 lines to pass simultaneously is what removes any risk of a false positive: it is statistically negligible for a wrong r to produce 46 valid-looking rows by chance.
Result
if ok:
print(f"r = ({r0}, {r1}, {r2})")
print("".join(chars))
raise SystemExit
As soon as the unique r satisfying every constraint is found, it gets printed alongside the reconstructed flag, and the search stops immediately via raise SystemExit.
Execution
Running the script:
python3 .\solve.py
produces the following output:
r = (7, 3, 0)
HTB{r3duc1nG_tH3_l4tTicE_l1kE_n0b0dY's_pr0bl3M}
Tools used: SageMath · SymPy · Python 3.11