crypto — pingCTF

Description

ECDH key exchange server on NIST P-192. The flag is encrypted with AES-CTR using a key derived from the server's private scalar. The server accepts arbitrary public points and returns a MAC of the shared secret.

Given: server.py (server implementation), ECDH.py (elliptic curve library), docker-compose.yml, DOCKERFILE.

Remote: nc 178.104.42.20 55137

Authors: mixer + Wintoch/Kubson

Analysis

Server behavior

1. Server generates a random private scalar b_priv on NIST P-192
2. Flag is encrypted with AES-CTR using sha256(str(b_priv).encode()).digest() as the key
3. Server prints nonce + ciphertext in hex
4. Server accepts arbitrary public points R_A as JSON [x, y]
5. Server computes shared_secret = ECDH.ecdh_responder(R_A, b_priv) and returns MAC = sha256(shared_secret).hexdigest()

# server.py - key derivation
aes_key = hashlib.sha256(str(b_priv).encode()).digest()
cipher = AES.new(aes_key, AES.MODE_CTR)
ciphertext = cipher.encrypt(flag)

# server.py - MAC oracle
shared_secret, R_B = ECDH.ecdh_responder(R_A, b_priv)
mac = hashlib.sha256(shared_secret).hexdigest()
print(f"MAC: {mac}")

The vulnerability

The critical flaw is in ECDH.py. The point_add and scalar_mult functions use only the curve parameters p (field prime) and a (curve coefficient), but never validate that the input point lies on the intended curve and never check subgroup membership:

# ECDH.py - point_add only uses p and a, not b!
def point_add(P: Point, Q: Point, curve: Curve = NIST_P192) -> Point:
    p = curve.p
    # ...
    if P == Q:
        m = (3 * x1 * x1 + curve.a) * pow(2 * y1, -1, p) % p  # Only uses 'a'
    else:
        m = (y2 - y1) * pow(x2 - x1, -1, p) % p
    # ...

This enables an invalid-curve attack: we can send points from curves with the same a and p but different b values. The server will happily compute b_priv * R_A on whatever curve R_A actually belongs to.

NIST P-192 parameters

p = 6277101735386680763835789423207666416083908700390324961279
a = -3
b = 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1  # Original curve
n = 6277101735386680763835789423176059013767194773182842284081  # Group order

Attack Strategy

Invalid-curve attack with smooth-order curves

The goal is to recover b_priv mod q for many small primes q, then combine using CRT.

Key insight: We can choose invalid curves where the group order has many small factors (smooth order), making Pohlig-Hellman tractable.

Invalid curve 1: Supersingular curve (b = 0)

The curve y² = x³ - 3x (same a = -3, but b = 0) is supersingular with order p + 1:

p + 1 = 2^64 × 3 × 5 × 17 × 257 × 641 × 65537 × 274177 × 6700417 × 67280421310721

The smooth part (excluding the large 67280421310721 factor) gives us:

M = (p + 1) / 2 = 3138550867693340381917894711603833208041954350195162480639

We can recover b_priv mod M using subgroups of order 2^63, 3, 5, 17, 257, 641, 65537, 274177, 6700417.

Invalid curve 2: Singular curve (b = 2)

The curve y² = x³ - 3x + 2 = (x-1)²(x+2) is singular (has a node). Its group structure is isomorphic to F_p*, with order p - 1:

p - 1 = 2 × 3 × ... × 59 × 149309 × 11393611 × ...

We can recover additional residues modulo 59, 149309, 11393611 from this curve.

Combined modulus

After combining all residues via CRT:

L = 4682091057308272901103194083609846045089279316764068413440

Since L < n < 2L, there are at most 2 candidates for b_priv after CRT, which we can test by decrypting the ciphertext.

Exploit Details

Precomputed points on invalid curves

Points of specific orders on the b = 0 curve:

# Order-M point on y² = x³ - 3x (b = 0)
G = (
    461048470750775475725516942201552941322069226183577675461,
    2187895538754867708883053334610028496092714684786383124245,
)

FACTOR_POINTS_B0 = {
    3: (1094210748148774040406682605236104878775999313120518109195,
        1906387580838892495682034466391218832589648744398662771751),
    5: (5366623076200026835529673457443383901317994259874882677620,
        1490246190388914632017454284884239304008637755043219394867),
    17: (560021892084998975194193639075260529661929995099286294628,
         4271521640559419268184203911700607200881799221631179290437),
    # ... more points for 257, 641, 65537, 274177, 6700417
}

Recovering the 2-adic component

For the 2^63 subgroup, we use a lifting approach with up to 2 candidates at each stage:

def recover_mod_2pow(io):
    odd_full = 3 * 5 * 17 * 257 * 641 * 65537 * 274177 * 6700417 * 67280421310721
    G2 = scalar_mult(odd_full, G)  # Point of order 2^63
    candidates = {0}

    for k in range(1, 64):
        mod = 1 << k
        Pk = scalar_mult(1 << (63 - k), G2)  # Point of order 2^k
        target = query(io, Pk)
        new_candidates = set()

        for s in candidates:
            for t in (s, s + (1 << (k - 1))):
                if mac_of_scalar(t, Pk) == target:
                    new_candidates.add(t % mod)

        candidates = new_candidates
    
    return candidates

Recovering odd prime residues

For each small prime factor q, we send a point of order q and brute-force the discrete log:

def recover_mod_prime(io, P, q):
    target = query(io, P)
    if target is None:
        return {0}

    cur = P
    for k in range(1, q // 2 + 1):
        if mac_of_point(cur) == target:
            return {k % q, (-k) % q}  # ±k are both valid
        cur = point_add(cur, P)

    raise RuntimeError(f"Failed to recover residue modulo {q}")

CRT combination and decryption

def combine_residue_sets(residue_sets, moduli):
    residues = {0}
    current_modulus = 1
    for options, mod in zip(residue_sets, moduli):
        new_residues = set()
        for r1, r2 in product(residues, options):
            merged, _ = crt_pair(r1, current_modulus, r2, mod)
            new_residues.add(merged)
        residues = new_residues
        current_modulus *= mod
    return residues, current_modulus

# After CRT, try both candidates
for r in residues:
    for candidate in [r, r + modulus]:
        if 1 <= candidate < n:
            key = hashlib.sha256(str(candidate).encode()).digest()
            cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
            pt = cipher.decrypt(ciphertext)
            if pt.startswith(b"ping{"):
                print(f"Found: {pt.decode()}")

Successful run

[+] recovered mod 2^63: 2 candidates
[+] residue mod 3: ±1
[+] residue mod 5: ±2
[+] residue mod 17: ±8
...
[+] total combined modulus: 4682091057308272901103194083609846045089279316764068413440
[+] total CRT residue candidates: 512
[+] scalar candidates below n: 1024
[+] candidate private key: 4454063842188739304164675812496842424376522700508205349156
ping{b_p4r4m3t3r_d03snt_m4tt3r_h3r3}