Quantum Safe — HackTheBox

Description

"I heard Shor's algorithm can do all sorts of nasty things to RSA, so I've decided to be super modern and protect my flag with cool new maffs!"

The challenge provides two files:

1. source.sage — SageMath encryption script
2. output.txt — 47 lines of encrypted vectors

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 (47 lines)

(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

Encryption Scheme

Each flag character c is encrypted as:

ct = [ord(c), rand1, rand2] × pubkey + r

Where:

• pubkey — known 3×3 integer matrix
• r — fixed random vector, each component ∈ [0, 10] (same for all characters)
• rand1, rand2 — random integers ∈ [0, 100] (different for each character)

The Irony of the Name

The name "Quantum Safe" is ironic. The author "switched" from RSA to a lattice-like scheme to protect against Shor's algorithm, but implemented it so poorly that no lattice reduction is needed.

Vulnerabilities

1. Matrix is invertible over Q: det(pubkey) ≠ 0, so pubkey⁻¹ exists in rational numbers
2. Noise r is fixed and small: each component ∈ [0, 10], only 11³ = 1331 variants
3. Strict plaintext constraints: ord(c) ∈ [32, 126], rand1, rand2 ∈ [0, 100]

Key Observation

If we know r, we can exactly recover the plaintext:

[ord(c), rand1, rand2] = (ct - r) × pubkey⁻¹

Since r has only 1331 possible values, we can brute force all variants and check which one gives valid values for all 47 ciphertext lines.

Solution

Algorithm

1. Compute pubkey⁻¹ in rational numbers (using Fraction for precision)
2. Iterate through all 11³ = 1331 candidates for r = (r0, r1, r2)
3. For each candidate, check all 47 ciphertexts:
   • (ct - r) × pubkey⁻¹ must yield integers
   • First component ∈ [32, 126] (printable ASCII)
   • Second and third components ∈ [0, 100]
4. The only r passing all checks: r = (7, 3, 0)

Solve script

#!/usr/bin/env python3
"""
Quantum Safe — HackTheBox Crypto
Brute force fixed noise vector r, invert pubkey matrix to recover flag.
"""
from fractions import Fraction

pubkey = [
    [47, -77, -85],
    [-49, 78, 50],
    [57, -78, 99]
]

def mat_inv_3x3(m):
    """Compute exact 3x3 matrix inverse using Fraction arithmetic."""
    m = [[Fraction(x) for x in row] for row in m]
    det = (m[0][0]*(m[1][1]*m[2][2] - m[1][2]*m[2][1])
          -m[0][1]*(m[1][0]*m[2][2] - m[1][2]*m[2][0])
          +m[0][2]*(m[1][0]*m[2][1] - m[1][1]*m[2][0]))
    cofactors = [
        [ m[1][1]*m[2][2]-m[1][2]*m[2][1], -(m[1][0]*m[2][2]-m[1][2]*m[2][0]),  m[1][0]*m[2][1]-m[1][1]*m[2][0]],
        [-(m[0][1]*m[2][2]-m[0][2]*m[2][1]),  m[0][0]*m[2][2]-m[0][2]*m[2][0], -(m[0][0]*m[2][1]-m[0][1]*m[2][0])],
        [ m[0][1]*m[1][2]-m[0][2]*m[1][1], -(m[0][0]*m[1][2]-m[0][2]*m[1][0]),  m[0][0]*m[1][1]-m[0][1]*m[1][0]]
    ]
    return [[cofactors[i][j] / det for j in range(3)] for i in range(3)]

inv = mat_inv_3x3(pubkey)

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):
            flag = ""
            ok = True
            for ct in cts:
                v = [Fraction(ct[j] - [r0, r1, r2][j]) for j in range(3)]
                plain = [sum(v[k] * inv[k][j] for k in range(3)) for j in range(3)]
                if any(p.denominator != 1 for p in plain):
                    ok = False
                    break
                p = [int(p) for p in plain]
                if not (32 <= p[0] <= 126 and 0 <= p[1] <= 100 and 0 <= p[2] <= 100):
                    ok = False
                    break
                flag += chr(p[0])
            if ok:
                print(f"r = ({r0}, {r1}, {r2})")
                print(f"Flag: {flag}")

Result

r = (7, 3, 0)
Flag: HTB{r3duc1nG_tH3_l4tTicE_l1kE_n0b0dY's_pr0bl3M}

Notes

• The flag text r3duc1nG_tH3_l4tTicE ("reducing the lattice") hints that authors expected a solution via lattice reduction (LLL/BKZ), but the challenge is solved more easily through noise brute force
• In real lattice-based cryptosystems (Kyber, NTRU), noise is added modulo a large number, and the matrix is not directly invertible — this is what makes the problem hard
• The key mistake of the scheme author: r is fixed for all characters and too small (11³ = 1331 variants)