AffineNoiseCipher (ECHO MIRAGE)

Platform: HackTheBox | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: D3v0o0Nu11 | Date: 2026-08-23 | Status: Solved Techniques: Approximate GCD (ACD), Orthogonal Lattice (OL), LLL, Coppersmith, DGHV

Summary

Walkthrough of the HackTheBox challenge AffineNoiseCipher (ECHO MIRAGE). The service encrypts each bit as c = p*q + 2*r + b with a 1024-bit prime anchor p. With 328 samples (gamma~3072, eta=1024, rho~513) the hidden p is recovered via the Orthogonal Lattice ACD attack (LLL + kernel), then each bit is decrypted as b = (c mod p) mod 2.

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 'output.txt' 'source.py'

Files:

• source.py — encryption script (AffineNoiseCipher)
• output.txt — 328 ciphertext integers (list)

Solution Approach

Decrypt the Affine Noise Cipher by recovering the 1024-bit anchor p via lattice-based Approximate GCD attack, then extract bits.

Techniques: ACD/AGCD, orthogonal lattice, LLL, simultaneous Diophantine approximation.

Steps

Analysis

Encryption Source Code

 python read-only • copy allowed Copy
from Crypto.Util.number import getPrime as getAnchor
import random
from secrets import flag

class AffineNoiseCipher:
    """
    ┌───────────────────────────────────────────────────────────────────┐
    │     A N C   :   A F F I N E   N O I S E   C I P H E R             │
    │───────────────────────────────────────────────────────────────────│
    │ "If truth must be hidden, drown it in the thunder of primes."     │
    │  c = p*q  +  2*r  +  b                                             │
    │   p — Anchor, 1024-bit prime                                       │
    │   q — structural distortion in [p, p^2]                            │
    │   r — deep noise in [2^256, 2^512]                                 │
    │   b — message bit                                                  │
    └───────────────────────────────────────────────────────────────────┘
    """
    def __init__(self, anchor):
        self.anchor = anchor

    def inscribe_noise(self, message: str):
        bits = "".join(f"{ord(c):08b}" for c in message)
        ciphertext = []
        for bit in bits:
            b = int(bit)
            distortion = random.randint(self.anchor, self.anchor**2)
            entropy = random.randint(2**256, 2**512)
            c = self.anchor * distortion + 2 * entropy + b
            ciphertext.append(c)
        return ciphertext

anchor = getAnchor(1024)
noise = AffineNoiseCipher(anchor)
with open("output.txt", "w") as file:
    file.write(str(noise.inscribe_noise(flag)))

Vulnerability

The cipher is an instance of the Approximate Common Divisor (ACD) Problem from DGHV Fully Homomorphic Encryption over Integers:

c_i = p * q_i + r_i'   where r_i' = 2*r_i + b_i
|p| = 1024 (eta), |r_i'| < 2^513 (rho), |c_i| ~ 3072 (gamma)
t = 328 samples

• q_i = distortion is large (|q_i| ~ 2048), so gamma = eta + |q_i| ~ 3072
• r_i' is small (rho=513 << eta)
• All 328 values are approximate multiples of the same secret p with small error

Conditions for OL/SDA attack: t >= (gamma - rho)/(eta - rho) ≈ 5 — we have 328 >> 5, attack is feasible.

Decryption if p known is trivial:

r_i' = c_i mod p   (= 2*r_i + b_i < p)
b_i  = r_i' mod 2

So the problem reduces to recovering p.

Solution

Step 1: Recognize ACD parameters

 bash read-only • copy allowed Copy
sage -c "
import ast
with open('output.txt') as f: c=ast.literal_eval(f.read())
print(len(c))               # 328 -> 41 chars (328/8)
print(c[0].bit_length())    # 3070
print(min(ci.bit_length() for ci in c))  # 3063
print(max(ci.bit_length() for ci in c))  # 3072
"

328 bits = 41 bytes, gamma~3072, eta=1024, rho~513 — classic ACD.

Step 2: Orthogonal Lattice Attack

Galbraith et al. "Algorithms for the Approximate Common Divisor Problem" Section 4 (jvdsn/crypto-attacks attacks/acd/ol.py):

Given x_i = p*q_i + r_i, |r_i| < R=2^rho, build lattice:

B = [ x_0  R  0  ... 0
      x_1  0  R  ... 0
       .   .  .  .   .
      x_{t-1}0 0 ... R ]  t x (t+1)

1. LLL(B) → short vectors correspond to integer relations annihilating p
2. Take M = B[0:t-1, 1:t] (first t-1 rows, last t columns), compute K = ker(M) (right kernel)
3. K is 1-dimensional, its element q = (q_0,...,q_{t-1}) are the hidden multipliers
4. Recover p = (x_0 - symmetric_mod(x_0, q_0)) / q_0

Implementation uses t=30, rho=512 (smallest that satisfies |r_i| < R and gives good LLL reduction):

 python read-only • copy allowed Copy
from sage.all import matrix, ZZ

def symmetric_mod(a, m):
    r = a % m
    if r > m//2: r -= m
    return r

R = 2**512
B = matrix(ZZ, t, t+1)
for i, xi in enumerate(x):
    B[i,0] = xi
    B[i,i+1] = R
B = B.LLL()
K = B.submatrix(row=0,col=1,nrows=t-1,ncols=t).right_kernel()
q = K.an_element()
p = abs((x[0] - symmetric_mod(x[0], q[0])) // q[0])

With t=30 LLL finds p instantly (1024 bits):

p = 164402719672345215073829428735717557756567193421978009297551706902713108670016609570405874271706278725280615925611348168195172295728363418512008345720021892377239594133562822511728463730646210357687537560736691914954360902850522686962670978389935704755300357272786671321093585282806313799135559664510432674677
is_prime(p) = True

Step 3: Decrypt

 python read-only • copy allowed Copy
bits = [(ci % p) % 2 for ci in c]
flag = ''.join(chr(int(''.join(str(b) for b in bits[i:i+8]), 2))
               for i in range(0, len(bits), 8))

Full solve script

 python read-only • copy allowed Copy
#!/usr/bin/env sage
import ast, sys
def symmetric_mod(a,m):
    r=a%m
    if r>m//2: r-=m
    return r

def ol_attack(x, rho):
    from sage.all import matrix, ZZ
    R=2**rho
    B=matrix(ZZ, len(x), len(x)+1)
    for i,xi in enumerate(x):
        B[i,0]=xi; B[i,i+1]=R
    B=B.LLL()
    M=B.submatrix(row=0,col=1,nrows=len(x)-1,ncols=len(x))
    K=M.right_kernel()
    if K.dimension()==0: return None
    q=K.an_element()
    for idx, qi in enumerate(q):
        if qi==0: continue
        r0=symmetric_mod(x[idx], qi)
        p=abs((x[idx]-r0)//qi)
        if all(-R < symmetric_mod(xi,p) < R for xi in x):
            return int(p), [symmetric_mod(xi,p) for xi in x]
    return None

with open(sys.argv[1] if len(sys.argv)>1 else "output.txt") as f:
    c=ast.literal_eval(f.read())

for t,rho in [(30,512),(40,513)]:
    res=ol_attack(c[:t], rho)
    if res:
        p,_=res
        bits=[(ci%p)%2 for ci in c]
        flag=''.join(chr(int(''.join(map(str,bits[i:i+8])),2)) for i in range(0,len(bits),8))
        print(flag); break

Run:

 bash read-only • copy allowed Copy
sage solve.py output.txt source.py
# [*] Loaded 328 samples
# [+] Found p (1024 bits):
# [+] FLAG: HTB{LLL_r3c0V3R_7H3_tRu7H_fR0m_7H3_n0153}

Result

[*] Loaded 328 samples
[*] c[0] bits: 3070, c[-1] bits: 3063
[*] t=30 rho=512
[+] Found p (1024 bits):
164402719672345215073829428735717557756567193421978009297551706902713108670016609570405874271706278725280615925611348168195172295728363418512008345720021892377239594133562822511728463730646210357687537560736691914954360902850522686962670978389935704755300357272786671321093585282806313799135559664510432674677
[*] is_prime(p): True
[*] max |r_i| bits: 513

[+] FLAG: HTB{LLL_r3c0V3R_7H3_tRu7H_fR0m_7H3_n0153}

Verification:

 python read-only • copy allowed Copy
assert all((c_i % p) %2 == b_i for c_i,b_i in zip(c, bits))
assert max(c_i % p for c_i in c).bit_length() == 513

Flags

Key Takeaways / Lessons

• Approximate GCD (DGHV) Recognize c = p*q + r with small r → lattice attack, not GCD
• Orthogonal Lattice vs SDA vs Multivariate Polynomial — OL (LLL + kernel) is most practical when t >= (gamma - rho)/(eta - rho)
• Parameters Matter: gamma~3072, eta=1024, rho~513, t=328 → t=30 already breaks it; rho off-by-one kills attack
• Decryption Simplicity: Once p known, b = (c mod p) mod 2 because 2*r is even
• Sage LLL workflow: B.LLL() → right_kernel() → symmetric_mod → gcd verification

---