Six-Seven — alfactf

Description

Сикс-севен

Сервис: sixseven

English summary: the challenge provided a live coffee shop service at https://sixseven-i15fbvlm.alfactf.ru/ and a source archive at https://alfactf.ru/files/sixseven_git_4547ca8.tar.gz. The goal was to recover the coupon for a special drink and then extract the real flag from the returned QR code.

Analysis

Recon

The source archive was unusually useful because it contained a bundled .git directory. That immediately made git history part of the attack surface.

The first promising artifact was commit a28c686 with message Fix: blur flag. Older revisions of app/app.py contained a hardcoded string:

alfa{i_love_coffee_so_much!!!}

That looked like a flag at first, but it was only an outdated placeholder from history. Submitting it failed, so it was a false lead, not the solution.

The real breakthrough came from reconstructing the application layout:

• the current Python Flask app handled registration, login, dashboard pages, espresso purchases, and the final QR rendering,
• nginx/default.conf showed that /api/ was proxied to a separate backend service,
• the first commit still contained the old Rust backend source in api/src/main.rs.

That Rust file documented the real backend endpoints:

• POST /api/create_profile
• POST /api/check_coupon
• GET /api/get_module
• POST /api/set_module
• GET /api/calc_shares
• POST /api/combine_shares

Even though the Rust source was no longer present in the latest tree, probing the live target confirmed those routes still existed.

Session format

After registering normally through the Flask app, the sixseven_session cookie could be base64-decoded into JSON like:

{"user_id":2051}

This did not give an auth bypass by itself, but it revealed the authenticated user_id required by the hidden /api/* routes.

Intended logic vs. actual bug

The frontend implements a Shamir-style loyalty card:

• each user starts with 40 coins,
• one espresso costs 10,
• therefore a user can buy only 4 espressos,
• but the coupon reconstruction requires 6 shares because the polynomial degree is 5.

So the intended route is impossible for a normal player. The secret had to be recovered another way.

The root cause was in the hidden Rust API. POST /api/set_module?user_id=<id> allowed an authenticated user to replace the stored modulus q with any attacker-chosen prime that passed only Fermat-based primality checks. Crucially, the endpoint updated only module_q and did not regenerate:

• the stored polynomial coefficients,
• the existing coupon secret,
• or the already issued espresso order IDs.

Then GET /api/calc_shares?user_id=<id> recomputed the shares for the existing espresso orders using:

• the same hidden polynomial coefficients,
• the same order UUID-derived x values,
• but the new attacker-controlled modulus.

This turns the backend into an oracle for values of the same integer polynomial under many different moduli:

F(x_i) mod q_j

for known x_i and attacker-chosen primes q_j.

Why this is exploitable

Each order ID is a UUID, and the challenge used its integer form as the x-coordinate:

int(uuid_str.replace('-', ''), 16)

Those x_i values are huge, roughly 128-bit integers. The polynomial coefficients, including the constant term we want, are bounded by < 2^256.

That size mismatch matters. If we query calc_shares under several pairwise-coprime large primes q_1, q_2, q_3, q_4, then for each fixed order ID we learn multiple residues of the same exact integer F(x_i). Once the product Q = q_1 q_2 q_3 q_4 exceeds the maximum possible size of F(x_i), Chinese Remainder Theorem reconstructs the unique integer value F(x_i), not just a modular residue.

With four espresso purchases we only know four exact points of a degree-5 polynomial, so that still looks underdetermined. But the coefficient bounds save the day.

Let g(x) be the cubic interpolant through the four recovered points, and let:

R(x) = (x - x1)(x - x2)(x - x3)(x - x4)

Then every degree-5 polynomial matching those four points has the form:

F(x) = g(x) + (u x + v) R(x)

for two unknown integers u and v.

Because the x_i are very large while every true coefficient of F(x) must remain below 2^256, the coefficients of g(x) + (u x + v)R(x) can only fall into the allowed range for one pair (u, v). Once u and v are fixed, the constant coefficient a0 = F(0) is determined, and that constant term is exactly the coupon secret.

In one successful solve session, the recovered coupon was:

0d90726346d1f00c11da96417ca8f68a58494e9d948b0891864b46388e17f73e

That value is per-user, so it is just an example from the solve session, not a universal coupon.

Solution

Step 1: register and log in

Create a fresh account through the normal Flask interface, then log in and extract your user_id from the sixseven_session cookie payload.

Step 2: buy four espressos

Spend the initial 40 coins on four espresso orders. This produces four order UUIDs, which become the known x-coordinates.

Step 3: query the share oracle under multiple moduli

Choose four large pairwise-coprime primes around 290-293 bits. For each prime:

1. call POST /api/set_module?user_id=<id> with the chosen prime,
2. call GET /api/calc_shares?user_id=<id>,
3. record each returned (order_id, share) pair.

Now each known order ID has four residues of the same hidden polynomial evaluation.

Step 4: reconstruct exact evaluations with CRT

For every order ID, combine the four residues with Chinese Remainder Theorem to obtain the exact integer F(x_i).

Step 5: recover the constant term

Interpolate the cubic g(x) through the four exact points. Then write the true degree-5 polynomial as:

F(x) = g(x) + (u x + v) R(x)

Search for the unique integers u and v whose resulting coefficients satisfy the challenge bound < 2^256. The constant coefficient is the coupon secret.

Step 6: unlock the exclusive order and decode the QR

Submit the recovered coupon to /buy-exclusive. After that:

1. extract the exclusive order ID from the dashboard HTML,
2. fetch /orders/<order_id>/qr.svg,
3. render the SVG QR into a normal raster image,
4. decode the QR contents.

The QR payload is the real flag.

#!/usr/bin/env python3
import base64
import json
import math
import re
import uuid
from fractions import Fraction

import requests


BASE = "https://sixseven-i15fbvlm.alfactf.ru"
USERNAME = "solver_user"
PASSWORD = "strongpass123"
PRIMES = [
    2**293 - 29,
    2**292 - 93,
    2**291 - 189,
    2**290 - 27,
]
BOUND = 1 << 256


def decode_user_id(session_cookie: str) -> int:
    payload = session_cookie.split(".", 1)[0]
    payload += "=" * (-len(payload) % 4)
    return json.loads(base64.urlsafe_b64decode(payload))["user_id"]


def uuid_to_int(value: str) -> int:
    return int(value.replace("-", ""), 16)


def crt(residues, moduli):
    x = 0
    m = 1
    for r, n in zip(residues, moduli):
        t = ((r - x) * pow(m, -1, n)) % n
        x += m * t
        m *= n
    return x


def poly_add(a, b):
    out = [Fraction(0)] * max(len(a), len(b))
    for i, v in enumerate(a):
        out[i] += v
    for i, v in enumerate(b):
        out[i] += v
    return out


def poly_mul(a, b):
    out = [Fraction(0)] * (len(a) + len(b) - 1)
    for i, av in enumerate(a):
        for j, bv in enumerate(b):
            out[i + j] += av * bv
    return out


def interpolate(points):
    result = [Fraction(0)]
    for i, (xi, yi) in enumerate(points):
        basis = [Fraction(1)]
        denom = Fraction(1)
        for j, (xj, _yj) in enumerate(points):
            if i == j:
                continue
            basis = poly_mul(basis, [Fraction(-xj), Fraction(1)])
            denom *= Fraction(xi - xj)
        result = poly_add(result, [c * Fraction(yi, 1) / denom for c in basis])
    return result


def recover_coupon(xs, ys):
    g = interpolate(list(zip(xs, ys)))
    R = [Fraction(1)]
    for x in xs:
        R = poly_mul(R, [Fraction(-x), Fraction(1)])

    xR = [Fraction(0)] + R
    candidates = []

    # Use the x^5 and x^4 coefficients to solve for u and v.
    r4 = R[4]
    r3 = R[3]
    u = -g[5]
    v = -g[4] - u * r4

    F = poly_add(g, [u * c for c in xR])
    F = poly_add(F, [v * c for c in R])

    coeffs = []
    for c in F:
        if c.denominator != 1:
            raise ValueError("non-integral coefficient")
        coeffs.append(int(c))

    if not all(0 <= c < BOUND for c in coeffs[:6]):
        raise ValueError("coefficient bounds failed")

    return coeffs[0]


def main():
    s = requests.Session()

    s.post(BASE + "/register", data={"username": USERNAME, "password": PASSWORD})
    s.post(BASE + "/login", data={"username": USERNAME, "password": PASSWORD})

    user_id = decode_user_id(s.cookies.get("sixseven_session"))

    for _ in range(4):
        s.post(BASE + "/buy-espresso")

    order_rows = []
    all_data = {}

    for prime in PRIMES:
        s.post(BASE + f"/api/set_module?user_id={user_id}", json={"q": str(prime)})
        data = s.get(BASE + f"/api/calc_shares?user_id={user_id}").json()
        for row in data["shares"]:
            all_data.setdefault(row["id"], []).append((int(row["share"]), prime))

    ids = sorted(all_data)[:4]
    xs = [uuid_to_int(i) for i in ids]
    ys = [crt([r for r, _ in all_data[i]], [m for _, m in all_data[i]]) for i in ids]
    coupon = f"{recover_coupon(xs, ys):064x}"
    print("coupon:", coupon)

    s.post(BASE + "/buy-exclusive", data={"coupon": coupon})
    html = s.get(BASE + "/dashboard").text
    order_id = re.findall(r"/orders/([0-9a-f-]+)/qr\.svg", html)[0]
    svg = s.get(BASE + f"/orders/{order_id}/qr.svg").text
    print(svg)


if __name__ == "__main__":
    main()

The live solve used exactly this flow: register a fresh user, buy four espressos, rotate the modulus several times, collect share recomputations, apply CRT, recover the coupon secret, unlock the exclusive drink, and decode the returned QR after rendering the SVG properly.

Lessons / Remediation

• Never expose administrative or debug API endpoints that mutate cryptographic parameters independently from the protected state.
• If a modulus changes, all dependent secrets, coefficients, and shares must be regenerated atomically.
• Fermat-only primality checks are too weak for validation of attacker-controlled cryptographic parameters.
• Do not rely on frontend workflow limits such as “users can only buy four items” when a backend side channel can recompute the same secret under attacker-chosen conditions.
• Old git history in distributed source archives should be treated as public disclosure.