4.1 ; REMNANT

Challenge Description

A stripped ELF binary and an encrypted payload file. The binary is a C2 beacon recovered from ECHELON NODE 07. Decrypt the payload.

URL: https://echelon.two-shoes.org/topsecret

Files provided: beacon (stripped x86-64 ELF), beacon.enc

Overview

This challenge combines light reverse engineering with a discrete logarithm attack. The binary implements a Diffie-Hellman key exchange using parameters with a smooth group order, making the private key recoverable via Pohlig-Hellman. The recovered key decrypts an AES-128-CBC payload containing the flag and a handshake key needed in the next challenge.

Step 1: Reconnaissance

Load the binary into Ghidra (https://ghidra-sre.org). Since it is stripped, begin with the entry point and work forward from main.

The binary reads a file, parses a structured header, performs modular exponentiation, derives an AES key, and decrypts the result. Four 64-bit constants participate in a XOR chain to produce a private key value. Three additional constants are used directly in the exponentiation: the modulus, the base, and the client public key.

Extract the following values from the .rodata section and the constant pool:

p          = 3837683530458959173
g          = 7
client_pub = 126667451012935862

The IV is also visible in .rodata as the ASCII string ECHLON-INIT-VECT.

The beacon.enc file structure is straightforward. Parse it manually or with Python:

import struct

with open("beacon.enc", "rb") as f:
    server_pub = struct.unpack("<Q", f.read(8))[0]
    iv         = f.read(16)
    ct_len     = struct.unpack("<I", f.read(4))[0]
    ciphertext = f.read(ct_len)

Step 2: Identify the Vulnerability

Factor p - 1 to assess the group order:

from sympy.ntheory import factorint
print(factorint(p - 1))
# {2: 2, 3: 1, 47: 1, 311: 3, 523: 2, 827: 1}

Every prime factor of p - 1 is at most 827. This is a smooth group order. Standard baby-step giant-step (BSGS) runs in O(sqrt(p)) which is infeasible for a 62-bit prime. Pohlig-Hellman exploits smooth order to reduce the problem into a set of small subgroup discrete logs, each solvable in O(sqrt(q_i)) for each prime factor q_i. With a maximum factor of 827, each subgroup solve takes fewer than 30 steps.

Step 3: Pohlig-Hellman Attack

The goal is to recover client_privkey such that g^client_privkey = client_pub mod p.

Pohlig-Hellman works as follows. For each prime power q^e dividing p - 1:

1. Project into the subgroup of order q^e using gamma = g^((p-1)/q) mod p.
2. Recover x mod q^e digit by digit using BSGS on the small subgroup.
3. Combine all residues using the Chinese Remainder Theorem (CRT).

from sympy.ntheory import factorint

def bsgs(g, h, p, n):
    m = int(n**0.5) + 1
    table = {}
    gj = 1
    for j in range(m):
        table[gj] = j
        gj = (gj * g) % p
    gm_inv = pow(pow(g, m, p), p - 2, p)
    factor = h
    for i in range(m):
        if factor in table:
            return (i * m + table[factor]) % n
        factor = (factor * gm_inv) % p
    return None

def pohlig_hellman(g, h, p, factors):
    order = p - 1
    residues, moduli = [], []
    for q, e in factors.items():
        qe = q**e
        gamma = pow(g, order // q, p)
        x_k = 0
        for k in range(e):
            g_inv = pow(pow(g, x_k, p), p - 2, p)
            h_k = pow((g_inv * h) % p, order // (q**(k + 1)), p)
            d_k = bsgs(gamma, h_k, p, q) or 0
            x_k = (x_k + d_k * q**k) % qe
        residues.append(x_k)
        moduli.append(qe)
    # CRT
    M = 1
    for m in moduli:
        M *= m
    x = 0
    for r, m in zip(residues, moduli):
        Mi = M // m
        x += r * Mi * pow(Mi, -1, m)
    return x % M

p          = 3837683530458959173
g          = 7
client_pub = 126667451012935862
order      = p - 1

factors        = factorint(order)
client_privkey = pohlig_hellman(g, client_pub, p, factors)

assert pow(g, client_privkey, p) == client_pub

Alternatively, SageMath (https://www.sagemath.org) solves this in one line:

F  = GF(p)
x  = discrete_log(F(client_pub), F(g))

SageMath applies Pohlig-Hellman automatically when the group order is smooth.

Step 4: Derive the AES Key and Decrypt

With client_privkey recovered, compute the shared secret and derive the AES key:

import struct, hashlib

shared       = pow(server_pub, client_privkey, p)
shared_bytes = struct.pack("<Q", shared)
aes_key      = hashlib.sha256(shared_bytes).digest()[:16]

Decrypt using AES-128-CBC:

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

cipher    = AES.new(aes_key, AES.MODE_CBC, iv)
plaintext = unpad(cipher.decrypt(ciphertext), 16)
print(plaintext.decode())

The decrypted output is a JSON beacon configuration containing the flag and a handshake_key field. Preserve the handshake key, it is required for 4.2 ; EXFIL.

Key Takeaways

Diffie-Hellman security depends entirely on the discrete logarithm problem being intractable. When the group order p - 1 is smooth, Pohlig-Hellman reduces the problem to a series of trivially small subgroup computations. The fix is to use a safe prime: a prime p where (p - 1) / 2 is also prime, giving the group a large prime order subgroup resistant to this attack. Real-world protocols use standardized groups (RFC 3526, RFC 7919) that satisfy this property.

Sometimes the simplest approach works. If you ran ./beacon beacon.enc and got the flag without touching the DH math, fair play. The intended solve involves Pohlig-Hellman on a smooth-order group, which is documented above if you want to understand why this binary was breakable. But a field operative who finds a C2 beacon and just runs it to see what happens? That takes guts.

Flag

ECHELON{beac0ns_have_heartbeats}