Сплетники - WriteUp

Задача находится в категории Blackbox (реверс без бинарника) и предполагает наблюдение за работой неизвестного протокола. Уже из вывода эндпоинтов feed, status и settings можно получить базовую картину:

Есть одна сущность, которая задаёт вопросы, и две сущности, которые отвечают.
Вопросы имеют жёсткую форму: вопросительное слово, существительное, прилагательное и обстоятельство (ровно 4 слова + ?).
Ответы всегда длиной 12 "слов" (фрагментов между пробелами) и выглядят как непрерывная последовательность из "Трёх мушкетёров".
Сообщения валидируются системным участником SYSTEM.
Общение идёт в рамках "эпох".
Перед концом эпохи запускается выбор нового лидера: все участники задают вопросы и отвечают, а победитель выбирается по числу правильных ответов и средней задержке.

По обращению в эндпоинт `status` можно понять следующее:

{
  "epoch": 12841, - номер эпохи
  "mode": "CHAT/ELECTION/PAUSE", - режим фида
  "leader_kid": "d997ba98d4de71fb", - id задающего в эпохе
  "election_duration_sec": 7.0, - длительность элекции
  "post_election_pause_sec": 2.0, - длительность паузы
  "pause_remaining_sec": 0.0,
  "answer_algo": "rsa_vdf_v1", - понимаем, что ответ детерминирован по RSA VDF
  "question_algo": "xs64_v1", - понимаем, что вопросы генерируются xorshift64
  "vdf_N_hex": "a0ede10c4195e4334e0622f66d94977f3d95ed014847af5c908adfd0d016eac45f8feca1edacd09393e8182039ec9fc0a1521a2d29cc7822084cb8bbe1e2e319e8db7243984c632cf87832d0147291f825a0be20c969bbcbfc0dd8c34a2230382584ffcb066aafa48c98ed5596b6f663dcd29a4fd39a5f7ce31177077e19112093595a68af689da8db66dcc68ff85e1b686621a1777ff2d964a6500550ebdf5de1526ec6135e7147f2afae2ddb975899c891e63cd7a534e461b7b7499a62bd55014d6212584a6feac79b51d438165f4ca890982975e7cc4325932a44fed1d0a305c19a80889be8f9e22cfa074dd325e2eda8bd344a280c36c75f3594c41b498f", - параметр N функции получения ответа
  "vdf_T": 10000000, - параметр T функции получения ответа
}

А если зайдём в `settings`, то увидим:

{
  "vdf_keygen": "det_rsa_xs64_v1", - понимаем, что модуль RSA детерминированно генерируется из xorshift64
  "vdf_prime_bits": 1024,
  "miller_rabin_rounds": 32,
  "kid_algo": "sha256:8bytes:hex_lower",
  "answer_space": 131072, - пространство возможных ответов (dict_size для hint.py)
  "question_vocab": "16x16x16x16", - размерность словаря вопросов
  "book_encoding": "koi8_r",
  "book_sha256_src": "1babc9e9994556119ea941d0de6d867ce15640d55a2ee3801f577cf86633ea00", - помощь для нахождения книги
  "question_xs64_v1": {
    "u64_per_question": 4, - 4 генерации на построение вопроса
    "index_mask_bits": 4 - утекают 4 бита
  },
  "master_seed64_sha256_le64_prefix": "...", - жирный намёк, что есть общая часть сида (64-бит)
  "epoch_seed64_sha256_le64_prefix": "...", - и тут понимаем, что сид зависит от эпохи
}

На этом этапе делаем выводы

Книгу можно найти из открытых источников по хешу или по характерным фрагментам ответов.
Ответ детерминирован и зависит от вопроса, эпохи и конкретного отвечающего.
Для расчёта ответа используется RSA VDF.
Свои сообщения можно отправлять в фид, если соблюдён формат и подпись.
Вопросы в CHAT генерируются от epoch_seed64.
Генерация RSA-ключа сидится от master_seed64 (иначе N менялся бы по эпохам).

Эксперименты с сообщениями

Подбор канона подписи показывает, что sig считается по всем полям, кроме самого sig. Попытка отправить QUESTION в обычной фазе не даёт результата, если мы не лидер, а попытка отправить ELECTION_QUESTION в CHAT сразу возвращает 400.

При ответах на вопросы получаем либо "самозванец" (неверный ответ), либо просто не успеваем в тайм-окно. Отсюда основной вывод: алгоритм вычисления ответа нужно радикально ускорять.

Тут и начинается ключевая сложность задачи.

Путь решения (обязательный)

Нужен бот для работы в реальном времени. Он должен уметь генерировать kid (как в hint.py), корректно подписывать сообщения и отслеживать смену эпох и режимов.

Минимальный функционал бота:

опрашивать /status и понимать текущие mode (CHAT/ELECTION/PAUSE), epoch, leader_kid, vdf_N_hex, vdf_T;
читать /feed, парсить события и хранить локальный лог по эпохам;
отправлять POST /feed только в допустимом режиме (в PAUSE будет 409);
корректно выставлять epoch и подбирать qid, чтобы не конфликтовать с уже существующими сообщениями.

После этого восстанавливаем словарь вопросов, а затем epoch_seed64 по вопросам лидера. В CHAT используется xorshift64, на вопрос тратится 4 значения u64, а в текст попадают только младшие 4 бита каждого значения. Это сводится к линейной системе GF(2), которая решается обычным гауссом.

Зная epoch_seed64, получаем master_seed64 = epoch_seed64 ^ epoch и проверяем себя по master_seed64_sha256_le64_prefix из settings. Далее берём master_seed32 = master_seed64 & 0xFFFFFFFF.

Дальнейший путь

Есть два рабочих направления.

1) "В лоб"

Можно писать максимально быструю реализацию VDF (параллель, низкоуровневый язык) и делать предвычисления для заранее выбранной эпохи.

Ключевой шаг - реверс формулы election-сида (из наблюдений видно, что election-вопросы зависят от epoch и kid):

seed = master_seed32 ^ epoch ^ kid16

Этот сид прогоняется через xorshift32 (не xorshift64) для генерации election-вопросов. После предсказания трёх ELECTION_QUESTION на нужную эпоху можно выигрывать выборы и получать флаг как лидер.

2) "Каноническое"

Из settings видно vdf_keygen: det_rsa_xs64_v1, то есть модуль N детерминированно генерируется из xorshift64 на master_seed64. Поскольку vdf_N_hex стабилен между эпохами, это и есть нужный корневой сид.

Далее воспроизводим генерацию RSA-ключей, получаем p и q, проверяем p*q == vdf_N_hex, а затем считаем VDF-ответы на ELECTION_QUESTION через CRT и сокращение итераций до одной модэкспоненты. Это позволяет обогнать боссов, выиграть выборы и получить флаг.

Хвосты

Эти факты неочевидны, но сильно упрощают решение:

Ответ с высокой вероятностью можно однозначно преобразовать в вопрос (последовательности из 12 слов в книге почти всегда уникальны).
Полезно логировать и feed, и status: между перезапусками задания RSA-ключи не меняются, так что накопленный датасет пригодится позже.
В фазе элекции игрок даёт не 2 ответа, а 3, поэтому даже относительно медленная реализация может победить в рамках окна.

9.6 KiB Raw Permalink Blame History Unescape Escape