Noise Codex - HackTheBox Challenge Writeup

Challenge Information

Description

This code once circulated through the cyber-underground circles of the crew known only as ECHO MIRAGE. Their doctrine was simple: “Let corporations hoard data, we’ll bury truth beneath untrackable noise”. Don’t trust it. Don’t worship it. Just run it.

The challenge ships a source file and an output file, ostensibly billed under a forensics-flavored theme. In reality it’s a lattice-based cryptography challenge built around an approximate-GCD style scheme.

Solution

The provided archive extracted cleanly with the standard HTB zip password. Once unpacked, source.py revealed the encryption scheme: the flag is encrypted bit by bit, where each ciphertext is:

c = p * distortion + 2*r + b

• p — a secret 1024-bit prime (the “key”)
• distortion — a random value in [p, p^2]
• r — random noise in [2^256, 2^512]
• b — the plaintext bit being encrypted

This is textbook DGHV (van Dijk-Gentry-Halevi-Vaikuntanathan) / Approximate-GCD, where a large prime is deliberately obscured by multiplicative and additive noise, and the security reduces to recovering p from many noisy multiples of it. The output file contained 328 such ciphertexts (each ~3072 bits), encoding a 41-character flag one bit at a time.

Before committing to a full attack, a feasibility check confirmed the approach was sound: since 2r + b < 2^513, which is far smaller than p ≈ 2^1024, it follows that:

c mod p = 2r + b

So recovering b reduces entirely to recovering p. The classic technique for this is the Simultaneous Diophantine Approximation (SDA) attack via lattice reduction (LLL), which requires the noise/prime-size gap to satisfy η − ρ > γ/t. Plugging in the challenge’s parameters (511 > 3072/t) showed any t > 6 ciphertexts would suffice — t = 20 was used for a comfortable margin.

Key Steps

1. Recover the hidden files from the zip

The staged artifact appeared to be a 0-byte decoy; the real archive needed the standard password.

# Original zip listed real file sizes (source.py, output.txt)
unzip -o -P hackthebox a289e12a-1cb9-46f5-8a65-d9375c754aff.zip

2. Parse the ciphertext list

import ast

# output.txt contains a Python-literal list of 328 ciphertexts
d = ast.literal_eval(open('ext/output.txt').read())

3. Build the SDA lattice and run LLL

# Basis construction for Simultaneous Diophantine Approximation:
#   row_0    = [2^(rho+1), c_1, c_2, ..., c_t]
#   row_i[i] = -c_0   (for i = 1..t)
#
# LLL finds a short vector v where v_0 / 2^(rho+1) approximates
# the hidden multiplier q_0 = distortion_0 (the "denominator" tying
# c_0 to the secret prime p).
from sympy.polys.matrices import DomainMatrix
from sympy import ZZ

t = 20
rho = 512  # noise bit-length bound

# ... construct (t+1) x (t+1) integer matrix from ciphertexts c[0..t] ...
# ... reduce with LLL ...

q0 = v0 // (2 ** (rho + 1))
p  = d[0] // q0   # recovered secret prime, exact integer division

4. Validate the recovered prime

# Sanity check before trusting p: every ciphertext's residue mod p
# must fall within the expected noise range (2r + b < 2^514)
assert all((c % p) < 2**514 for c in d)

5. Decode the flag bit by bit

bits = []
for c in d:
    b = (c % p) % 2       # b = (2r + b) mod 2 == b, since 2r is even
    bits.append(b)

# Pack bits back into bytes to recover the flag string
flag = bytes(
    int(''.join(map(str, bits[i:i+8])), 2)
    for i in range(0, len(bits), 8)
)
print(flag)  # HTB{REDACTED}

Tools Used

• unzip (with the standard HTB archive password) to recover the source and output files
• Python 3 (ast) for parsing the ciphertext list
• sympy for LLL-based lattice reduction (DomainMatrix / ZZ)
• fpylll (attempted, required cysignals as a dependency) as an alternative lattice library
• Standard integer/bitwise operations for decoding the recovered bits into the flag

Key Learnings

• Category labels can mislead. A challenge tagged “forensics” turned out to be a pure lattice-cryptography problem once the encryption formula was examined — always read the source before trusting the stated category.
• Approximate-GCD / DGHV recognition. The pattern c = p * distortion + 2*r + b is a strong fingerprint for approximate-GCD schemes; recognizing it immediately points toward Simultaneous Diophantine Approximation (SDA) or orthogonal-lattice attacks via LLL.
• Check feasibility before building the attack. Confirming 2r + b ≪ p up front proved that recovering p alone was sufficient to decrypt every bit — this simplified the entire attack down to a single lattice reduction rather than per-ciphertext factoring.
• Parameter sizing matters. The SDA success condition η − ρ > γ/t directly determines the minimum number of ciphertexts (t) needed; computing this before running a slow lattice reduction avoids wasted attempts with too few samples.
• Environment gotcha: installing fpylll via pip can fail with a missing cysignals dependency — installing cysignals first resolves it, or sympy’s built-in LLL support can be used as a fallback without extra dependencies.
• Archive staging quirks: a 0-byte staged file doesn’t necessarily mean a broken download — check the original zip listing for real file sizes and retry extraction with the known challenge password.