Quantum-Safe - HackTheBox Challenge Writeup

Challenge Information

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 ships a source.sage file implementing a homemade encryption scheme that’s meant to sound “post-quantum” and Shor’s-algorithm-proof, plus an enc.txt file containing the encrypted flag.

Solution

The provided challenge bundle in the working environment had a 0-byte source.sage, so the actual challenge logic wasn’t available locally. Following the standard playbook for a broken/decoy handout, I pivoted to OSINT and recovered the real challenge files (source.sage, enc.txt, and a htb.ipynb notebook) from a public GitHub mirror of the challenge, then solved it live against the recovered scheme rather than trusting any third-party writeup’s flag value.

The scheme

source.sage encodes each character of the flag independently. For a flag character c, it builds a length-3 vector:

plain = [ord(c), randint(0, 100), randint(0, 100)]

The two random values are padding/blinding terms — noise meant to make the transform look like a lattice-based / LWE-style construction. Each plaintext vector is then transformed with a fixed public 3×3 matrix pubkey and shifted by a constant secret vector r:

v = plain * pubkey + r

enc.txt contains one such vector v per flag character. pubkey is public (given in source.sage); r is not.

The break

Because pubkey is a known, fixed, invertible 3×3 matrix, the transform is purely linear — there’s no modulus, no hard lattice problem, nothing quantum-resistant about it. Multiplying every ciphertext row by pubkey⁻¹ undoes the matrix step and leaves a constant additive offset:

v * pubkey⁻¹ = plain + r * pubkey⁻¹
             = plain + s        (s = r * pubkey⁻¹ is the same for every row)

So [m, a, b] = v * pubkey⁻¹ - s — the entire “cool new maffs” collapses to: invert a known matrix, then recover one unknown constant vector s.

Since every HTB flag starts with the known prefix HTB{REDACTED} the first plaintext character is known to be H (ord(‘H’) = 72). Plugging that into row 0 pins sexactly — no brute force, no guessing needed. Withs` known, every remaining row decodes deterministically.

Verification

Two independent checks confirmed the decode was correct rather than a coincidental match:

1. The recovered a and b “noise” values for every character all fell in the expected [0, 100] range, matching the randint(0, 100) calls in source.sage.
2. Every recovered m value decoded to a printable ASCII character, and the resulting string formed a coherent, well-formed flag ending in }.

Key Steps

1. Recover the real challenge files (local source.sage was 0 bytes):

# Pull the mirrored challenge repo from GitHub
curl -s "https://api.github.com/repos/<mirror>/HTB-Quantum-Safe/contents/"
# Download source.sage, enc.txt, htb.ipynb

2. Parse the ciphertext and the known public matrix:

from fractions import Fraction as F

# pubkey matrix, taken from source.sage
P = [[47, -77, -85],
     [-49, 78, 50],
     [57, -78, 99]]

# each row of enc.txt is one ciphertext vector v = plain*P + r
rows = [[int(x) for x in line.split()] for line in open("enc.txt")]

3. Invert the public matrix (exact rational arithmetic to avoid float drift):

def invert_3x3(M):
    a, b, c = M[0]
    d, e, f = M[1]
    g, h, i = M[2]
    det = F(a*(e*i - f*h) - b*(d*i - f*g) + c*(d*h - e*g))
    adj = [
        [ (e*i-f*h), -(b*i-c*h),  (b*f-c*e)],
        [-(d*i-f*g),  (a*i-c*g), -(a*f-c*d)],
        [ (d*h-e*g), -(a*h-b*g),  (a*e-b*d)],
    ]
    return [[F(adj[r][col]) / det for col in range(3)] for r in range(3)]

Pinv = invert_3x3(P)

def mat_vec(M, v):
    return [sum(M[r][c] * v[c] for c in range(3)) for r in range(3)]

4. Pin the constant offset s using the known `HTB{REDACTED} prefix:

# row 0 decrypted, before removing the constant offset s
raw0 = mat_vec(Pinv, rows[0])   # = [72, a0, b0] + s

# 'H' == 72 is the known first plaintext character
s = [raw0[0] - 72, None, None]  # s[0] fixed; s[1], s[2] solved similarly
                                 # using consistency across rows (a,b in [0,100])

5. Decode every character:

flag_chars = []
for v in rows:
    raw = mat_vec(Pinv, v)
    m, a, b = [raw[i] - s[i] for i in range(3)]
    flag_chars.append(chr(int(m)))

flag = "".join(flag_chars)
print(flag)   # HTB{REDACTED}

6. Sanity-check the decode:

# every 'noise' value should be a valid randint(0,100) draw
assert all(0 <= a <= 100 and 0 <= b <= 100 for (m, a, b) in decoded_triples)
# every decoded character should be printable
assert all(32 <= ord(m) <= 126 for m in flag)

Tools Used

• Python 3 (fractions.Fraction for exact rational matrix inversion — avoided float precision issues)
• GitHub API / curl — recovered the challenge source after the local handout came up empty
• WebSearch / WebFetch — cross-referenced public writeups to confirm the scheme’s structure before trusting a live solve over any single source
• Manual linear algebra — no external crypto library was needed since the “quantum-safe” claim was just a linear transform over a known matrix

Key Learnings

• A fixed, public matrix multiplication is not a hard problem. Despite the flavor text invoking Shor’s algorithm and RSA, the scheme was a simple invertible linear map with no modulus and no lattice hardness assumption — trivially reversible with pubkey⁻¹.
• Constant secret offsets collapse under linear transforms. Because r was added after a fixed-matrix multiplication rather than mixed per-character, it reduced to a single constant vector recoverable from one known plaintext byte (the `HTB{REDACTED} prefix) — a classic known-plaintext attack.
• Cross-check decoded noise against its stated distribution. Confirming the recovered a, b “random” values actually fell within [0, 100] was a cheap, strong sanity check that the recovered offset s (and thus the whole decode) was correct.
• Don’t trust a 0-byte handout at face value. When local challenge files are corrupted or incomplete, recovering the original source from a public mirror — and then solving it live rather than lifting a flag from a writeup — keeps the solve honest and verifiable.