CIPHER7

Challenge Description

Good luck. - Unit 7

We receive a single archive. Inside:

README.txt - handling instructions, file list
key.rs - RS-encoded key material (corrupted)
curve_params.json - CIPHER7-EC256 elliptic curve parameters
archive_header.bin - Archive header (binary)
encrypted_data.bin - Encrypted intelligence briefing (AES-CBC)

The key derivation spec is not included: "Contact your division supervisor for the relevant documentation."

Stage 1: Repairing key.rs (Reed-Solomon)

key.rs is 255 bytes with no file header, no extension hint beyond .rs, and no documentation. The file size is the first clue: RS(255, 223) is a standard Reed-Solomon configuration that produces exactly 255-byte codewords from 223 data bytes, with 32 ECC bytes capable of correcting up to 16 byte errors.

Inspecting the file in a hex editor reveals no recognizable structure, it's binary data with some bytes that look corrupted (a 3-byte burst at a fixed offset, plus two scattered single-bit flips). The .rs extension and 255-byte length together point strongly toward Reed-Solomon.

Decoding:

import reedsolo

rsc = reedsolo.RSCodec(32)  # RS(255, 223) - 32 ECC bytes
raw = open('key.rs', 'rb').read()
assert len(raw) == 255

decoded, _, errata = rsc.decode(raw)
NONCE = bytes(decoded[:16])
print(f'Recovered nonce: {NONCE.hex()}')

The RS decoder corrects all 5 errors (3-byte burst + 2 scattered) and returns 223 data bytes. The first 16 bytes are the payload we need: a nonce that will be used in key derivation later.

Stage 2: ECDLP on CIPHER7-EC256 (Pohlig-Hellman)

curve_params.json presents a curve named CIPHER7-EC256 with the label AGENCY-FIPS-7-1983 and a security claim of "256-bit equivalent security."

{
  "name": "CIPHER7-EC256",
  "description": "Agency elliptic curve for CIPHER7 operations. Generated by the Cryptographic Systems Division. Parameters certified by Unit 7 (acting). Do not use for non-agency purposes.",
  "standard": "AGENCY-FIPS-7-1983",
  "field": "GF(1000003)",
  "a": 1,
  "b": 1,
  "Gx": 4,
  "Gy": 877512,
  "Px": 684708,
  "Py": 761232,
  "note": "P = k*G. Recover k. Group order not provided - compute it.",
  "security_claim": "256-bit equivalent security"
}

The note makes the goal explicit: recover scalar k such that P = k*G. This is the elliptic curve discrete logarithm problem (ECDLP).

The security claim is false. The field is GF(1000003): a seven-digit prime. Real 256-bit ECC uses primes around 2²⁵⁶. This curve has approximately 10⁶ points, not 2²⁵⁶. But the critical vulnerability isn't the small field, it's the group order.

Computing the Group Order

The group order is not provided. This is intentional, players who assume it's a standard safe curve and skip this step will fail at Pohlig-Hellman.

Computing it manually by counting points (Legendre symbol sum over all x):

def count_points(p, a, b):
    count = 1  # point at infinity
    for x in range(p):
        rhs = (pow(x, 3, p) + a*x + b) % p
        if rhs == 0:
            count += 1
        elif pow(rhs, (p-1)//2, p) == 1:
            count += 2
    return count

This takes ~10 seconds for p = 1000003. In Sage it's instant:

E = EllipticCurve(GF(1000003), [1, 1])
E.order()  # → 1000727

Factor the order:

1000727 = 7² × 13 × 1571

Every prime factor is below 2¹¹. This is an extremely smooth group order. For comparison, a secure elliptic curve has a group order that is itself a large prime (or has a large prime factor). Here the largest factor is 1571. This is the backdoor.

Pohlig-Hellman

When the group order is smooth (all prime factors small), the ECDLP can be solved by:

Solving the DLP independently in each prime-order subgroup
Combining results via the Chinese Remainder Theorem

For each prime power factor q^e of n:

# Project G and P into the subgroup of order q^e
Gq = pt_mul(n // q**e, G)   # order q^e
Pq = pt_mul(n // q**e, P)   # k mod q^e satisfies Pq = k_sub * Gq

# Brute-force DLP in the tiny subgroup (max order 1571, trivial)
curr = None
for j in range(q**e):
    if curr == Pq:
        k_sub = j
        break
    curr = pt_add(curr, Gq)

Subgroup orders: 49 (7²), 13, 1571. Brute force is instant for all three.

CRT to combine residues:

k ≡ 0 (mod 49)
k ≡ 10 (mod 13)
k ≡ 434 (mod 1571)

Note: Python's sympy.ntheory.modular.crt has a known issue with residue = 0. Implement CRT manually:

def manual_crt(residues, moduli):
    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

k = manual_crt([0, 10, 434], [49, 13, 1571])
# → 517293

Verify: k*G should equal P:

assert pt_mul(517293, G) == P  # (684708, 761232) ✓

Stage 3: Key Derivation (Hidden Nonce in Binary Header)

We have k = 517293 from Stage 2 and NONCE from Stage 1.

Inspect archive_header.bin in a hex editor:

4337455945530100 acff284bafcd36a8e30ca19158beee0f 00000000 a0c84d8911142a9a4acbe049f28c3a43 fffe

Parsing it:

Offset	Length	Value	Meaning
0x00	8	`43 37 45 59 45 53 01 00`	Magic: `C7EYES\x01\x00`
0x08	16	`acff284b...beee0f`	AES IV
0x18	4	`00000000`	Reserved (looks like padding)
0x1C	16	`a0c84d89...3a43`	NONCE, matches Stage 1 output
0x2C	2	`ff fe`	End marker

The nonce from Stage 1 (RS recovery) and the nonce embedded at 0x1C in the header are the same value. This is the connection between Stage 1 and Stage 3 and why Stage 1 matters even though the nonce appears in the header: you need to know what you're looking for, and recognizing those 16 bytes as significant requires the RS output to confirm them.

The key derivation is SHA256(k_bytes || nonce):

import hashlib

k_bytes = k.to_bytes(32, 'big')   # k as 32-byte big-endian integer
IV = header[8:24]
NONCE = header[28:44]

AES_KEY = hashlib.sha256(k_bytes + NONCE).digest()

Players who pipe the raw integer k directly into AES (without the SHA256 and nonce) get garbage plaintext with no indication of why. This is the intentional friction, the key derivation step is undocumented in the README and requires forensic analysis of the header.

Stage 4: AES-256-CBC Decryption

With AES_KEY and IV both recovered:

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

cipher = AES.new(AES_KEY, AES.MODE_CBC, iv=IV)
plaintext = unpad(cipher.decrypt(encrypted_data), 16).decode()
print(plaintext)

Full Solve Script

import tarfile, json, hashlib, re
import reedsolo
from sympy import factorint
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

# Extract archive
files = {}
with tarfile.open('EYES_ONLY_CIPHER7.tar.gz', 'r:gz') as tar:
    for m in tar.getmembers():
        if not m.isfile():
            continue
        name = m.name.split('/')[-1]
        files[name] = tar.extractfile(m).read()

# Stage 1: RS repair
rsc = reedsolo.RSCodec(32)
decoded, _, _ = rsc.decode(files['key.rs'])
NONCE = bytes(decoded[:16])

# Stage 2: ECDLP via Pohlig-Hellman
params = json.loads(files['curve_params.json'])
p = int(params['field'].split('(')[1].rstrip(')'))
a, b = params['a'], params['b']
G = (params['Gx'], params['Gy'])
P = (params['Px'], params['Py'])

def pt_add(A, B):
    if A is None: return B
    if B is None: return A
    if A[0] == B[0]:
        if A[1] != B[1]: return None
        lam = (3*A[0]**2 + a) * pow(2*A[1], -1, p) % p
    else:
        lam = (B[1]-A[1]) * pow(B[0]-A[0], -1, p) % p
    x = (lam**2 - A[0] - B[0]) % p
    return (x, (lam*(A[0]-x) - A[1]) % p)

def pt_mul(k, Q):
    R = None; T = Q
    while k:
        if k & 1: R = pt_add(R, T)
        T = pt_add(T, T); k >>= 1
    return R

# Compute group order (not provided, use Sage: E.order())
# E = EllipticCurve(GF(1000003), [1, 1]); E.order() → 1000727
n = 1000727  # = 7^2 * 13 * 1571
factors = factorint(n)

def manual_crt(residues, moduli):
    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

residues, moduli = [], []
for q, e in factors.items():
    qe = q**e
    Gq = pt_mul(n // qe, G)
    Pq = pt_mul(n // qe, P)
    curr = None
    for j in range(qe):
        if curr == Pq:
            residues.append(j % qe)
            moduli.append(qe)
            break
        curr = pt_add(curr, Gq)

k_rec = manual_crt(residues, moduli)

# Stage 3: Key derivation
header = files['archive_header.bin']
IV = header[8:24]
nonce = header[28:44]   # looks like reserved padding, it isn't
k_bytes = k_rec.to_bytes(32, 'big')
AES_KEY = hashlib.sha256(k_bytes + nonce).digest()

# Stage 4: Decrypt
cipher = AES.new(AES_KEY, AES.MODE_CBC, iv=IV)
plaintext = unpad(cipher.decrypt(files['encrypted_data.bin']), 16).decode()
print(plaintext)

flag = re.search(r'DEADROP\{[^}]+\}', plaintext)
if flag:
    print(f'\n*** FLAG: {flag.group()} ***')

Output

EYES ONLY - CIPHER7 OPERATION BRIEFING
CLASSIFICATION: BEYOND TOP SECRET
DATE: 1983-09-12

The asset known as NIGHTINGALE has provided confirmation of a second
weather modification array operating covertly in the northern latitudes.
This array is not affiliated with our own program. The Eastern bureau
is aware of our operations at the level of the directorate. Immediate
compartmentalisation of all array personnel is authorised.

Operation NIGHTJAR enters its final phase upon receipt of the extraction
authorisation code NIGHTINGALE-ALPHA-1983. All avian relay stations are
to be placed on active status. Unit 7 will coordinate directly with the
Bratislava cell. KOVACS has been briefed. Do not brief KOVACS again.

The CIPHER7 elliptic curve was generated by this office. The parameters
were chosen for operational security reasons that we will not be
documenting here. If you are reading this and you are not the intended
recipient, congratulations on your mathematical skills. The curve was
backdoored by us. Obviously.

DEADROP{the_curve_was_backdoored_by_us_obviously}

P.S. The cryptography division has formally requested we clarify the
agency position on whether birds are real. The position is: some birds
are real. The important ones - specifically the pigeons - are government
assets and are very real. The question of whether the OTHER birds are
real is classified at a level above this document. The intern is not
cleared for that information and should stop asking.

Key Takeaways

1. Smooth group order = broken ECC. The entire security of elliptic curve cryptography depends on the ECDLP being hard. Pohlig-Hellman reduces the ECDLP to a series of tiny subgroup problems when the group order is smooth. A curve with order 7² × 13 × 1571 provides essentially zero security, the largest subgroup DLP is brute-forceable in microseconds.

2. Always verify the group order of any curve you use. The CIPHER7-EC256 curve comes with a fake NIST-style name, a standards reference, and a security claim. None of it matters if the group order is smooth. When evaluating an elliptic curve, the first check is always: factor the group order. If the largest prime factor is small, the curve is backdoored or broken.

3. Reed-Solomon is everywhere. RS codes appear in QR codes, CDs, DVDs, satellite communications, and storage systems. Recognizing the RS(255, 223) parameters from a 255-byte binary file is a legitimate forensics and reverse engineering skill. The .rs extension is a hint; the file length is the confirmation.

4. Binary headers hide things in plain sight. The nonce at offset 0x1C in archive_header.bin is framed by 00000000 reserved bytes on one side and \xff\xfe on the other, it looks like padding. Forensic analysis of binary file formats requires methodical parsing, not assumptions about what "looks" important.

5. Undocumented key derivation is a deliberate obstacle. The README says the key derivation spec is not included. Players who recover k and immediately try AES(k, ...) get garbage. The SHA256 wrapping and nonce concatenation are only discoverable by correlating the RS nonce output with the header binary, the two stages are linked by design.

Flag

DEADROP{the_curve_was_backdoored_by_us_obviously}