← All writeups

GPN24

GPN24 — fortune2 (crypto)

Flag: GPNCTF{sOMTImES_a11_YOU_neED_I5_lUck}

Connection: ncat --ssl <instance>.gpn24.ctf.kitctf.de 443 Files: fortune2.py, fortuneUtils2.py

TL;DR

The challenge looks like NTRU over the dihedral group ring Z[D_100] and dares you to break a lattice. It's a red herring. The encryption multiplies the noise term by p = 3 without reducing modulo q, and only then adds the ternary message. So every ciphertext coefficient satisfies

c_k = 3·t_k + m_k      with m_k ∈ {-1, 0, 1}
  ⇒  c_k ≡ m_k  (mod 3)

The message is recovered directly as c mod 3. No key, no lattice.

The challenge

On connect, the server prints public parameters, a public key h, and a ciphertext c, then gives you 60 seconds to send back the encoded message:

got params N=100 p=3 d=33 q=512
h= [...]            # 200 integers in [0, 512)
c= [...]            # 200 integers in [-1, 1534]
Give me the message:

If your guess equals msg_to_guess(msg), you get the flag.

The cryptosystem

fortuneUtils2.py implements a group ring. A FortuneWheel is an element of the dihedral group D_100 (rotations r^k and reflections s·r^k), and a FortuneForest is a formal integer combination of them — i.e. an element of the group ring Z[D_100]. The to_vector() encoding is a length-2N = 200 coefficient vector: the first 100 entries are the rotation coefficients, the last 100 are the reflection coefficients.

fortune2.py then builds a textbook NTRU instance over this ring:

def generatePattern(n, p, d, q):
    while True:
        f  = P(d+1, d, n)          # ternary, d+1 ones and d minus-ones
        fq = f.inv(mod=q)
        fp = f.inv(mod=p)
        if fp is None or fq is None: continue
        g  = P(d, d, n)            # ternary
        h  = (fq * g) % q          # public key  h = g / f  (mod q)
        return f, fq, fp, g, h, p, q

with N = 100, p = 3, d = 33, q = 2**floor(log2((6d+1)·p)) = 2**floor(log2(597)) = 512.

Encryption (hideInPattern) is standard NTRU c = p·r·h + m:

def hideInPattern(pattern, message, d):
    h, p, q = pattern
    doubt = P(d, d, h.segments)     # ternary blinding r
    t = (h * doubt) % q             # coeffs in [0, q)
    return (t).rescale(p) + message # << the bug lives here

The decrypt routine is provided but disabled, with the hint:

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

That is the whole challenge talking to you: you are not supposed to recover the private key. There is a pattern in c itself.

The vulnerability

Look closely at rescale and __mod__ in fortuneUtils2.py:

def rescale(self, modifier):        # multiplies every coefficient by `modifier`
    ...
    w_copy.modifier = w.modifier * modifier   # NO modular reduction
    ...

def __mod__(self, other):           # this one DOES reduce
    w_copy.modifier = w.modifier % other      # coeffs land in [0, other)

So in hideInPattern:

Therefore, over the integers:

c_k = 3·t_k + m_k

Reducing modulo 3 kills the noise entirely (3·t_k ≡ 0):

c_k ≡ m_k  (mod 3)

Because the message alphabet is exactly {-1, 0, 1}, this congruence uniquely determines each m_k. The dihedral group ring, the NTRU key, g, fq, fp — all irrelevant.

This is consistent with the observed ciphertext range [-1, 3·511+1] = [-1, 1534] (the live data even contained a -1, which maps cleanly via -1 ≡ 2 (mod 3) ⇒ m = -1).

Decoding table

msg_to_guess uses MAPPING = {-1: "A", 0: "C", 1: "B"}. Combining with c_k mod 3:

c_k % 3 m_k letter
0 0 C
1 1 B
2 -1 A

The answer is simply:

guess = "".join({0: "C", 1: "B", 2: "A"}[c_k % 3] for c_k in c)

(Python's % already maps -1 → 2, so negative coefficients are handled for free.)

Solver

Pure socket + ssl, no dependencies. The whole solve is microseconds; the 60-second timer is a non-issue.

import socket, ssl, re

HOST = "<instance>.gpn24.ctf.kitctf.de"
PORT = 443
LETTER = {0: "C", 1: "B", 2: "A"}   # c_k % 3 -> letter

ctx = ssl.create_default_context()
ctx.check_hostname = False
ctx.verify_mode = ssl.CERT_NONE      # ncat --ssl presents a self-signed cert

s  = socket.create_connection((HOST, PORT), timeout=30)
ss = ctx.wrap_socket(s, server_hostname=HOST)
ss.settimeout(90)

data = b""
while b"message:" not in data:
    chunk = ss.recv(8192)
    if not chunk:
        break
    data += chunk

c = [int(x) for x in re.search(r"c=\s*\[([^\]]*)\]", data.decode()).group(1).split(",")]
guess = "".join(LETTER[ci % 3] for ci in c)

ss.sendall(guess.encode() + b"\n")
print(ss.recv(8192).decode())

Output:

You are lucky!
here is your flag GPNCTF{sOMTImES_a11_YOU_neED_I5_lUck}

The rabbit hole (what NOT to do)

Before spotting the mod 3 leak I tried to actually break the NTRU instance — recovering the private key / message by lattice reduction. It's a trap, and a costly one:

None of it was necessary. The intended path is the one-liner c mod 3. The flag — "sometimes all you need is luck" — is a wink at exactly this: stop trying to be clever and read the ciphertext.

Key takeaways

  1. rescale(p) does not reduce mod q. Multiplying the masking term by p and then adding a message whose alphabet is {-1,0,1} ⊂ (-p/2, p/2] leaks the entire message mod p. In real NTRU the message is added before the public-key product is reduced, and the "small" message lives inside the lattice noise — never as an exact c ≡ m (mod p) channel.
  2. When a challenge ships a decryption routine but disables it with a nudge to "see the pattern", look for an algebraic shortcut before reaching for BKZ.
  3. The impressive-looking crypto (non-abelian group ring, NTRU) was pure misdirection.