Crypter (Russian CTF Cup 2024 Final; A/D, crypto) RU VERSION

Веселый сервис, на котором я просидел почти весь Кубок, около семи часов.

Интро

В общем, с этого сервиса я и начал, увидев намек на криптографию; не то чтобы я был особенно рад увидеть там C++, но ради крипты я на многое готов.

Надо признаться, про криптосистему Пэйе я почти ничего не знал до этого таска, хотя некоторый запоминающийся опыт с ней был, поэтому $(n + 1)^{m} (mod n^{2})$ я быстро заметил.

Сурсы сервиса я сохранил тут.

Сервис

Сервис простой по функционалу, написан на C++ с использованием gRPC, gmp и Postgres. Основные фичи:

Система юзеров. При регистрации каждый юзер получает токен для отправки сообщений, случайный $n = pq$ публичный ключ, а также приватный ключ в виде значения функции Эйлера $ϕ (n) = (p - 1) (q - 1)$ (тут была первая уязвимость попроще). Публичные ключи других юзеров сохранены в базе данных и доступны без ограничений.
Сообщения. Можно отправить сообщение, посмотреть сообщения, адресованные тебе или посмотреть сообщение по id (вне зависимости от адресата). Сообщения шифруются самодельной криптосистемой. Сервис не умеет расшифровывать (приватные ключи даже не хранятся на сервере).
Криптосистема. Реализация криптосистемы Пэйе через gmp, на первый взгляд корректная. Я не буду здесь расписывать, как она работает, почитаете сами.

Простая часть

Очевидная и скучная ошибка лежит в функции random_integer:

uint8_t seed = device();

Этот сид - единственное, на чем базируется PRNG, поэтому можно просто сгенерировать себе все возможные части ключа и перебрать по ним. После этого нужно разобраться в процессе расшифровки и готово. Почти все команды это осилили, поэтому вдаваться в подробности я не буду.

К сожалению, я был отвлечен остальными ошибками и долго не мог заметить эту, что довольно сильно утянуло команду вниз.

Сложная часть

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

mpz_class r = random_integer(32); - r не такое же по размеру, как n, а в два раза короче. К сожалению, я не придумал, как это эксплуатировать.
Ошибки утекают в ответы юзеру, могло бы быть полезным, но не здесь.
Сообщение маленькое, всего 128 бит. Очень мало в сравнении с остальными параметрами.
return res1 * res2; - Хмм, нету % n2. 6000 бит информации вместо ожидаемых 4096 🤔

За время соревнования я перепробовал кучу всего: раскрывать штуки, делить штуки, гуглить штуки, распихивать штуки в тулзы. Как оказалось, я ходил кругами, заметив большинство ключевых моментов, которые просто не складывались у меня в голове в решение.

Через пару часов я уже начал сомневаться в существании другой уязвимости, но по сути очевидные ошибки не давали мне покоя…

Шли последние полчаса эвента. Я пошел сделать перерыв, после этого сел… и просто вот понял. Не верил до самого конца, что получилось.

По итогу, вот прямой путь к решению, минуя все тупики, в которых я проторчал:

Рассмотрим зашифрованное сообщение: $mod ((1 + n)^{m}, n^{2}) \cdot mod (r^{n}, n^{2})$ .
В соотвествии с основной идеей криптосистемы, его можно записать вот так: $mod (1 + nm, n^{2}) \cdot mod (r^{n}, n^{2})$ .
Заметим, что $1 + nm < n^{2}$ , поэтому можно дальше сократить до $(1 + nm) \cdot mod (r^{n}, n^{2})$ .
Теперь заменим штуку справа на некое $R$ ; получаем $(1 + nm) \cdot R$ .
Многочлен $R + nm R - c t$ тогда имеет корень $(m_{0}, R_{0})$ с $m_{0}$ ~ 128 бит и $R_{0}$ ~ 4096 бит. Смотря в священные писания про упрощенный метод Копперсмита, можно заметить, что $W$ больше всего для свободного члена $c t$ с 6370 бит, когда $X Y$ ~ 4224 бит - намного меньше, чем $W$ . Раз наибольшая степень всего 1, метод сработает.

Этот путь я сократил уже после изучения в подробностях, почему и когда это все работает (после соревнования). Вот дополнительные шаги, которые я делал изначально

Заметим, что $mod ((1 + nm) \cdot R, n) = mod (R, n)$ , назовем это $e$ . Тогда $R = kn + e$ для некоего $k$ .
Рассмотрим полученное выражение: $(1 + nm) (kn + e) = km n^{2} + kn + e mn + e$ . У многочлена все еще первая степень и $W$ ~ 6370 bits, но границы корней упали аж до 2176 bits. Это делает солвер намного быстрее, практически моментальным.

Остальное

Эксплоит (написанный в торопях) устроен тоже довольно интересно:

Во-первых, требует сгенерированных файлов gRPC, подробнее в доках.
Во-вторых, требует сейдж, и это даже не все. Запускается он только (костыльно) из репозитория crypto-attacks т.к. я все еще понятия не имею, как именно работает метод и поэтому использую реализации других (умных) людей.
Вот так выглядит эксплоит, кое-как собранный на полной скорости:

#!/usr/bin/env python3
 
from sage.all import *
from primefac import primefac
 
path = os.path.dirname(os.path.dirname(os.path.dirname(os.path.realpath(os.path.abspath(__file__)))))
if sys.path[1] != path:
    sys.path.insert(1, path)
 
from shared.small_roots import coron
 
from crypter_pb2 import *
from crypter_pb2_grpc import *
from requests import get
from random import shuffle
import sys
 
 
sys.set_int_max_str_digits(999999)
 
ip = sys.argv[1]
 
 
data = get("https://cbsctf.live/api/client/attack_data/").json()
ids = [s.removeprefix("{\"message\": \"").removesuffix("\"}") for s  in data["crypter"][ip]]
 
with grpc.insecure_channel(f'{ip}:2112') as channel:
    stub = CrypterStub(channel)
    for msg_id in ids:
        message = stub.GetMessage(GetMessageRequest(id=str(msg_id)))
        public_key = stub.GetUserPublicKey(GetUserPublicKeyRequest(username=message.username))
        n = int(public_key.n)
        ct = int(message.encrypted)
        e = ct % n
 
        PR = PolynomialRing(ZZ, "m, k")
        m, k = PR.gens()
 
        poly = m * k * n ** 2 + m * e * n + k * n + e - ct
 
        sol = coron.integer_bivariate(poly, 1, 2 ** 128, 2 ** 2048)
 
        for sol in sol:
            m, k = sol
            print(int(m).to_bytes((int(m).bit_length() + 7) // 8, 'big'), flush=True)

Когда я его выкатил, у нас буквально за раунд прибавилось около 5000 очков, что переставило нас с десятого сразу на шестое место. Не то чтобы это повлияло на результат, но все равно приятно.

📝 Writeup dump