Fortune — GPNCTF 2024 (KitCTF)

Description

You can't eat the entire time, so why not gamble a bit?

A remote SSL service (ncat --ssl <host> 443) implements a custom NTRU-like cryptosystem and challenges you to recover a hidden ternary "fortune wheel" message within a 60-second SIGALRM window. The server prints the public key h and a ciphertext c, then asks for the message encoded as a string over {A, C, B}. Get it right → flag.

Provided files: fortune2.py (service) and fortuneUtils2.py (crypto classes).

Analysis

The cryptosystem

The scheme is a faithful NTRU port, but instead of the usual cyclic polynomial ring Z[x]/(x^N - 1) it operates over the group ring (group algebra) of the dihedral group, Z[D_N].

• FortuneWheel — an element of D_N. The base elements are N rotations r^0 … r^{N-1} (labels are cyclic shifts of [0..N-1]) and N reflections s·r^k (mirrored labels). __mul__ composes the underlying permutations, i.e. it is group multiplication in D_N.
• FortuneForest — an element of Z[D_N]. to_vector() returns a length 2N coefficient vector: the first N entries are coefficients on the rotation wheels, the next N are coefficients on the reflection wheels. It supports +, * (group-algebra convolution), % q (coefficient reduction), rescale(s) (scalar multiply of all coefficients), and inv(mod) — a group-ring inverse computed via the regular representation: it builds the 2N × 2N block matrix [[M1, M0], [M0, M1]] and inverts it modulo the given modulus.

Parameters: N=100, p=3, d=floor(N/3)=33, q=2^floor(log2((6d+1)*p))=2^9=512.

The NTRU flow

P(t1,t2)        random ternary forest: t1 coeffs = +1, t2 = -1 on distinct wheels
keygen:         f = P(d+1,d); fq = f.inv(q); fp = f.inv(p); g = P(d,d)
                h = (fq * g) % q                       # public key
message:        msg = P(d,d)                           # ternary, 33×(+1), 33×(-1) of 200
encrypt:        doubt = P(d,d)
                t = (h * doubt) % q
                c = t.rescale(p) + msg                 # c[i] = p*t[i] + msg[i] = 3*t[i] + msg[i]

The server prints h= and c= (both as raw Python lists from .to_vector()), asks for msg mapped through MAPPING = {-1:"A", 0:"C", 1:"B"}.

A decrypt() function exists in the source but is commented out with the hint:

The fortunate don't need such functions to see the pattern

That is a direct tell: you are not supposed to use the private key f.

The vulnerability — the unreduced ciphertext

Encryption computes c = t.rescale(p) + msg, i.e. coefficient-wise

c[i] = p * t[i] + msg[i] = 3 * t[i] + msg[i]

In a correct NTRU implementation the ciphertext would be reduced mod q before transmission. Here it is printed raw, straight from to_vector(), with no % q. Because t[i] ∈ [0, q) and msg[i] ∈ {-1, 0, 1}, the message is simply the residue of each coefficient mod 3:

msg[i] ≡ c[i]  (mod 3)        # since 3*t[i] ≡ 0 (mod 3)

Mapping residues back to the ternary alphabet:

c[i] mod 3 == 0  →  msg[i] =  0
c[i] mod 3 == 1  →  msg[i] = +1
c[i] mod 3 == 2  →  msg[i] = -1   (because -1 ≡ 2 mod 3)

The entire dihedral-group-ring machinery — h, fq, fp, the regular representation inverse, the lattice structure — is a red herring. The whole break is a single mod 3. This is the "luck/gamble" theme: you "guess" the fortune-wheel message, but in fact compute it deterministically.

Critical reproducibility detail: if you reduce c mod q (512) before applying the trick, the 3*t[i] term wraps and the leak is destroyed. You must use the RAW printed c values.

Solution

1. Connect over SSL to port 443.
2. Read the banner up to Give me the message:.
3. Extract the c= Python list (it appears after the h= vector — take the part after the last c=) and parse it with ast.literal_eval.
4. Compute msg[i] = {0:0, 1:1, 2:-1}[c[i] % 3] for every coefficient.
5. Encode with MAPPING = {-1:"A", 0:"C", 1:"B"} and send within 60 s.
6. Server replies You are lucky! and prints the flag.

#!/usr/bin/env python3
import sys, re, ast
from pwn import remote, context

context.log_level = "info"

MAP = {-1: "A", 0: "C", 1: "B"}

def cmap(x):
    # residue of (3*t + msg) mod 3 -> ternary message symbol
    return {0: 0, 1: 1, 2: -1}[x % 3]

def parse_vec(line):
    m = re.search(r"\[.*\]", line, re.S)
    return ast.literal_eval(m.group(0))

def main():
    host, port = sys.argv[1], int(sys.argv[2])
    ssl = (len(sys.argv) > 3 and sys.argv[3] == "ssl") or port == 443
    io = remote(host, port, ssl=ssl)
    buf = io.recvuntil(b"Give me the message:", timeout=30).decode(errors="replace")
    idx = buf.rindex("c=")                 # the c vector comes after the h vector
    c = parse_vec(buf[idx:])
    guess = "".join(MAP[cmap(x)] for x in c)   # use RAW c, never reduce mod q
    io.sendline(guess.encode())
    print(io.recvall(timeout=10).decode(errors="replace"))

main()

Run:

python3 solve.py <host> 443 ssl

Verification

The trick was validated offline by reimplementing the dihedral group-ring multiplication in pure Python, generating a sample (h, c, msg) instance, and confirming msg[i] == cmap(c[i]) for all 200/200 coefficients. It then worked first try against the live SSL instance.

Lessons Learned / Key Indicators

Use this technique when:

• An NTRU-style ciphertext has the form c = p·t + msg (here 3·t + msg) with a small ternary message and is transmitted/printed without reduction mod q.
• The output is a raw Python list (or raw integers) rather than values bounded in [0, q) — a sign the implementation skipped the final % q.
• A decrypt/private-key path is present but explicitly commented out or hinted as unnecessary ("the fortunate don't need such functions").
• The challenge wraps the real arithmetic in an exotic, intimidating algebra (here Z[D_N], dihedral group ring, regular-representation inverse) that has nothing to do with the actual leak — a classic "scary math is a red herring" pattern.

Core insight: when plaintext is added to a multiple of p, plaintext = c mod p recovers it directly, regardless of all the surrounding lattice/group-ring structure. The only trap is reducing mod q first, which destroys the leak.